Robust task scheduling in non-deterministic heterogeneous computing systems
Authors:
- 1 September 2006
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 15525244,p. 1-10
Abstract
The paper addresses the problem of matching and scheduling of DAG-structured application to both minimize the makespan and maximize the robustness in a heterogeneous computing system. Due to the conflict of the two objectives, it is usually impossible to achieve both goals at the same time. We give two definitions of robustness of a schedule based on tardiness and miss rate. Slack is proved to be an effective metric to be used to adjust the robustness. We employ epsiv-constraint method to solve the bi-objective optimization problem where minimizing the makespan and maximizing the slack are the two objectives. Overall performance of a schedule considering both makespan and robustness is defined such that user have the flexibility to put emphasis on either objective. Experiment results are presented to validate the performance of the proposed algorithmKeywords
This publication has 22 references indexed in Scilit:
- A new metric for robustness with application to job scheduling2005
- Scheduling Precedence Task Graphs with DisturbancesRAIRO - Operations Research, 2003
- Task execution time modeling for heterogeneous computing systems2002
- Static scheduling algorithms for allocating directed task graphs to multiprocessorsACM Computing Surveys, 1999
- ROBUSTNESS MEASURES AND ROBUST SCHEDULING FOR JOB SHOPSIIE Transactions, 1994
- A genetic algorithm for multiprocessor schedulingIEEE Transactions on Parallel and Distributed Systems, 1994
- DSC: scheduling parallel tasks on an unbounded number of processorsIEEE Transactions on Parallel and Distributed Systems, 1994
- A Comparative Analysis of Selection Schemes Used in Genetic Algorithms1991
- Scheduling parallel program tasks onto arbitrary target machinesJournal of Parallel and Distributed Computing, 1990
- Grain size determination for parallel processingIEEE Software, 1988