Cost-based workflow scheduling using algebraic structures

Workflow is a common model for describing a wide range of applications in distributed systems. Due to the computing power of cloud computing, it has been widely applied to solve large workflows. Cloud workflow scheduling aims to find the most suitable resources for each task of a workflow to meet certain performance metrics, such as execution time and cost. Since scheduling is a well-known NP-complete problem, many heuristic approaches have been proposed for homogeneous and heterogeneous distributed systems. The longest path of a workflow is called the critical path that the entire workflowchr('39')s completion time depends on this path. In fact, delays in the execution of critical path tasks can delay the workflowchr('39')s completion time and violate the deadline of it. Hence, in this paper, we present a parallel heuristic algorithm for workflow scheduling to satisfy the quality of service parameters, called Critical Paths-based scheduling using Lattice algebra (CPL). The proposed approachchr('39')s objective is to create a schedule that minimizes the cost of a workflow while it satisfies the workflow deadline. By assigning a semi-lattice to each sub-workflow, the start and end time of its tasks and the appropriate resources for them are determined. The simulation results on the Montage and LIGO workflows show that the proposed approach reduces the cost by 5.5% compared to IC-PCP and by 11% compared to IC-PCPD2.