Cost Optimization For Deadline-constrained Grid Workflows

Workflow scheduling is one of the key issues in the workflow management. It allocates suitable resources to execute workflow tasks so that the execution can be completed to meet the requirements of the users or the system. Many grid applications must be modeled as complex workflows. Thus, the scheduling of workflow applications becomes a significant and essential problem in Grids.Over the last few years, the increasing demand for grid computing resources calls for an incentive-compatible pricing mechanism for differentiated services. In such"pay-per-use"Grids, each service provider charges users a differentiated price according to the requests. Cost and time become two primary factors that users are concerned about. So the time–cost optimization problem for scheduling workflow applications which described by Directed Acyclic Graph (DAG) becomes an essential and complex problem. In general, it is NP-hard.Firstly, this thesis introduces the related concepts of grid and grid workflow. Secondly, this paper summarizes the correlative scheduling algorithms for Grid workflow. And then, we proposed three new algorithms GSA-GW (Greedy Scheduling Algorithm for Grid Workflow), IGSA-GW(Improved GSA-GW) and BLGA-GW(Bottom Level and Greedy Algorithm for Grid Workflow) to optimize the cost of workflow while meeting the deadline delivered by users. According to the Deadline submitted by users, this paper establishes a mathematical model, and then use the algorithms proposed in this paper to tackle it. Simulation results reveal that the algorithms can satisfy the user's Deadline and optimize the costs well.