A task duplication based scheduling algorithm with optimality condition in heterogeneous systems
- 25 June 2003
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 15302016,p. 531-536
Abstract
The task scheduling problem is NP-hard in heterogeneous systems. We propose a task scheduling algorithm based on task duplication with an optimality condition to determine whether or not the resulting schedule has the shortest schedule length. The optimality condition is that, given any join task, the completion time of a parent task is longer than the maximum message arrival times from the other parent tasks. An illustrative example is given to show how our algorithm differs from existing algorithms.Keywords
This publication has 11 references indexed in Scilit:
- Triplet: A clustering scheduling algorithm for heterogeneous systems2002
- Fast and effective task scheduling in heterogeneous systems2002
- A task duplication based scheduling algorithm for heterogeneous systems2002
- An optimal scheduling algorithm based on task duplicationIEEE Transactions on Computers, 2002
- An Introduction to PC Clusters for High Performance ComputingThe International Journal of High Performance Computing Applications, 2001
- Parallel program execution on a heterogeneous PC cluster using task duplication2000
- Optimal scheduling algorithm for distributed-memory machinesIEEE Transactions on Parallel and Distributed Systems, 1998
- Scheduling from the perspective of the application1996
- C.P.M. Scheduling with Small Communication Delays and Task DuplicationOperations Research, 1991
- Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey1979