SA-Based QoS Aware Workflow Scheduling of Collaborative Tasks in Grid Computing

Abstract

Scheduling workflow tasks in grid computing is a complex process, especially if it is associated with satisfying the user's requirements to complete tasks within a specified time, with lowest possible cost. This paper presents a proposed Simulated Annealing (SA) based Grid Workflow Tasks Scheduling Approach (SA-GWTSA) that takes into account users’ QoS (quality of service) constraints in terms of cost and time. For a given set of inter-dependent workflow tasks, it generates an optimal schedule, which minimizes the execution time and cost, such that the optimized time is within the time constraints (deadline) imposed by the user. In SA-GWTSA, the workflow tasks, which are modeled as a DAG, are divided into task divisions, each of which consists of a set of sequential tasks. Then, the optimal sub-schedules of all task divisions are computed applying SA algorithm, and used to obtain the execution schedule of the entire workflow. In the proposed algorithm, the sub-schedule of each branch division is represented by a vector, in which each element holds the ID of the service provider chosen from a list of service providers capable of executing the corresponding task in the branch. The algorithm uses a fitness function that is formulated as a multi-objective function of time and cost, which gives users the ability to determine their requirements of time against cost, by changing the weighting coefficients in the objective function. The paper also exhibits the experimental results of assessing the performance of SA-GWTSA with workflows samples of different sizes, compared to different scheduling algorithms: Greedy-Time, Greedy-Cost, and Modified Greedy-Cost.