Scheduling Workflows with Budget Constraints
Published 29 April 2007
Rizos Sakellariou, Henan Zhao, E Tsiakkouri, Marios D. Dikaiakos
Citations248
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This paper considers a basic model for workflow applications modelled as Directed Acyclic Graphs (DAGs) and investigates heuristics that allow to schedule the nodes of the DAG (or tasks of a workflow) onto resources in a way that satisfies a budget constraint and is still optimized for overall time.
Abstract
Grids are emerging as a promising solution for resource and computation demanding applications. However, the heterogeneity of resources in Grid computing, complicates resource management and scheduling of applications. In addition, the commercialization of the Grid requires policies that can take into account user requirements, and budget considerations in particular. This paper considers a basic model for workflow applications modelled as Directed Acyclic Graphs (DAGs) and investigates heuristics that allow to schedule the nodes of the DAG (or tasks of a workflow) onto resources in a way that satisfies a budget constraint and is still optimized for overall time. Two different approaches are implemented, evaluated and presented using four different types of basic DAGs. © 2007 Springer Science+Business Media, LLC.
Keywords
Computer ScienceDecision Sciences
IEEE Transactions on Parallel and Distributed SystemsPerformance-effective and low-complexity task scheduling for heterogeneous computing
3,308 Citations2002Haluk Rahmi Topcuoglu, Salim Hariri +1 more
Two novel scheduling algorithms for a bounded number of heterogeneous processors with an objective to simultaneously meet high performance and fast scheduling time are presented, called the Heterogeneous Earliest-Finish-Time (HEFT) algorithm and the Critical-Path-on-a-Processor (CPOP) algorithm.
OPAL (Open@LaTrobe) (La Trobe University)Economic-based distributed resource management and scheduling for grid computing
493 Citations2017Rajkumar Buyya
This thesis proposes a distributed computational economy as an effective metaphor for the management of resources and application scheduling and proposes an architectural framework that supports resource trading and quality of services based scheduling that enables the regulation of supply and demand for resources.
Proceedings of the IEEEThe Grid Economy
459 Citations2005Rajkumar Buyya, David Abramson +1 more
An extensive, service-oriented Grid architecture driven by Grid economy and an approach for its realization by leveraging various existing Grid technologies are presented and commodity and auction models for resource allocation are presented.
Journal of Parallel and Distributed ComputingTask Matching and Scheduling in Heterogeneous Computing Environments Using a Genetic-Algorithm-Based Approach
405 Citations1997Lee Wang, Howard Jay Siegel +2 more
Simulation results for larger-sized problems showed that this genetic-algorithm-based approach outperformed two nonevolutionary heuristics and a random search.
Task scheduling strategies for workflow-based applications in grids
365 Citations2005James M. Blythe, Shweta Jain +5 more
This work identifies two families of resource allocation algorithms: task-based algorithms, that greedily allocate tasks to resources, and workflow-based algorithms, that search for an efficient allocation for the entire workflow.
ACM SIGMOD RecordScheduling of scientific workflows in the ASKALON grid environment
323 Citations2005Marek Wieczorek, Radu Prodan +1 more
This paper evaluates three algorithms namely genetic, HEFT, and simple "myopic" and compares incremental workflow partitioning against the full-graph scheduling strategy and demonstrates that full- graph scheduling with the HEFT algorithm performs best.
A case for economy grid architecture for service oriented grid computing
316 Citations2005Rajkumar Buyya, David Abramson +1 more
This work argues that a computational economy is required in order to create a real world scalableGrid because it provides a mechanism for regulating the Grid resources demand and supply and offers incentive for resourceowners to be part of the Grid and encourages consumers to optimally utilize resources and balance timeframe and accesscosts.
A hybrid heuristic for DAG scheduling on heterogeneous systems
296 Citations2004Rizos Sakellariou, Henan Zhao
A novel heuristic for DAG scheduling is presented, which is based upon solving a series of independent task scheduling problems and compares favourably with other related heuristics.
arXiv (Cornell University)Economic-based Distributed Resource Management and Scheduling for Grid Computing
195 Citations2002Rajkumar Buyya
Scheduling strategies for mapping application workflows onto the grid
184 Citations2005Anirban Mandal, Ken Kennedy +5 more
The results of the experiments show that the strategy of performance model based, in-advance heuristic workflow scheduling results in 1.5 to 2.2 times better makespan than other existing scheduling strategies.
Lecture notes in computer scienceEconomic Scheduling in Grid Computing
176 Citations2002Carsten Ernemann, Volker Hamscher +1 more
The evaluations show that the presented economic scheduling algorithm provides similar or even better average weighted response-times as common algorithms like backfilling as well as support for different price models, optimization objectives, access policies or quality of service demands.
Lecture notes in computer scienceAn Experimental Investigation into the Rank Function of the Heterogeneous Earliest Finish Time Scheduling Algorithm
130 Citations2003Henan Zhao, Rizos Sakellariou
The findings indicate that the length of the schedule produced may be affected significantly by the scheme used, and suggest that the mean value based approach used by HEFT may not be a particularly good choice.
Scientific ProgrammingA Low‐Cost Rescheduling Policy for Efficient Mapping of Workflows on Grid Systems
123 Citations2004Rizos Sakellariou, Henan Zhao
This paper presents a low-cost rescheduling policy, which considers rescheduled at a few, carefully selected points during the execution, which achieves performance results comparable with those achieved by a policy that dynamically attempts to reschedule before the execution of every task.
A realistic model and an efficient heuristic for scheduling with heterogeneous processors
53 Citations2002Olivier Beaumont, Vincent Boudet +1 more
A more realistic model for heterogeneous networks of workstations, where each processor can send and/or receive at most one message at any given time-step is dealt with.