Cost-Driven Scheduling of Grid Workflows Using Partial Critical Paths
Top Cited Papers
- 13 December 2011
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Parallel and Distributed Systems
- Vol. 23 (8) , 1400-1414
Abstract
Recently, utility Grids have emerged as a new model of service provisioning in heterogeneous distributed systems. In this model, users negotiate with service providers on their required Quality of Service and on the corresponding price to reach a Service Level Agreement. One of the most challenging problems in utility Grids is workflow scheduling, i.e., the problem of satisfying the QoS of the users as well as minimizing the cost of workflow execution. In this paper, we propose a new QoS-based workflow scheduling algorithm based on a novel concept called Partial Critical Paths (PCP), that tries to minimize the cost of workflow execution while meeting a user-defined deadline. The PCP algorithm has two phases: in the deadline distribution phase it recursively assigns subdeadlines to the tasks on the partial critical paths ending at previously assigned tasks, and in the planning phase it assigns the cheapest service to each task while meeting its subdeadline. The simulation results show that the performance of the PCP algorithm is very promising.Keywords
This publication has 30 references indexed in Scilit:
- Deadline division-based heuristic for cost optimization in workflow schedulingInformation Sciences, 2009
- Runtime Prediction Based Grid Scheduling of Parameter Sweep Jobs2008
- Characterization of scientific workflows2008
- An Ant Colony Optimization Approach to a Grid Workflow Scheduling Problem With Various QoS RequirementsIEEE Transactions on Systems, Man and Cybernetics, Part C (Applications and Reviews), 2008
- Performance and cost optimization for multiple large-scale grid workflow applications2007
- European Strategies Towards Next Generation Grids2006
- A taxonomy of market‐based resource management systems for utility‐driven cluster computingSoftware: Practice and Experience, 2006
- A Market-Oriented Grid Directory Service for Publication and Discovery of Grid Service Providers and their ServicesThe Journal of Supercomputing, 2006
- A Low‐Cost Rescheduling Policy for Efficient Mapping of Workflows on Grid SystemsScientific Programming, 2004
- GridSim: a toolkit for the modeling and simulation of distributed resource management and scheduling for Grid computingConcurrency and Computation: Practice and Experience, 2002