Heuristic Algorithms for Scheduling Independent Tasks on Nonidentical Processors
Journal of the ACM1977Vol. 24(2), pp. 280–289
Citations Over TimeTop 1% of 1977 papers
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 .
Related Papers
- → A Decomposition Method for Makespan Minimization in Job-Shop Scheduling Problem Using Ising Machine(2021)8 cited
- → Minimizing the Makespan in Permutation Flow Shop Scheduling Problems using Simulation(2015)3 cited
- → Future Makespan Heuristic for job shop scheculing problem(2010)2 cited
- → Network-aware task selection to reduce multi-application makespan in cloud(2020)2 cited
- → Universality of Makespan in Flowshop Scheduling Problem(2016)