Heuristic Algorithms for Scheduling Independent Tasks on Nonidentical Processors
- 1 April 1977
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 24 (2), 280-289
- https://doi.org/10.1145/322003.322011
Abstract
The finishing time properties of several heuristic algorithms for scheduling n independent tasks on m nonidentical processors are studied. In particular, for m = 2 an n log n time-bounded algorithm is given which generates a schedule having a finishing time of at most (√5 + 1)/2 of the optimal finishing time. A simplified scheduling problem involving identical processors and restricted task sets is shown to be P-complete. However, the LPT algorithm applied to this problem yields schedules which are near optimal for large n .Keywords
This publication has 4 references indexed in Scilit:
- Exact and Approximate Algorithms for Scheduling Nonidentical ProcessorsJournal of the ACM, 1976
- A generalized bound on LPT sequencingPublished by Association for Computing Machinery (ACM) ,1976
- Scheduling independent tasks to reduce mean finishing timeCommunications of the ACM, 1974
- Reducibility among Combinatorial ProblemsPublished by Springer Science and Business Media LLC ,1972