HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

Worst-Case Analysis of Scheduling Heuristics of Parallel Systems

Abstract : It is well-known that most scheduling problems arising from parallel systems are NP-hard, even under very special assumptions. Thus various suboptimal algorithms, in particular heuristics, were proposed in the literature. Worst-case error bounds are established in this note for heuristics of makespan minimization of parallel computations. Different parallel computation models are investigated, including interprocessor communication, task duplication, multiprocessor tasks and parallel tasks. Due to the heterogeneity of these systems, scheduling heuristics can be far away from the optimal solutions. The bounds presented here provide insights to the design of scheduling heuristics in order to obtain good performance guarantee.
Document type :
Complete list of metadata

Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Wednesday, May 24, 2006 - 2:13:52 PM
Last modification on : Friday, February 4, 2022 - 3:18:47 AM
Long-term archiving on: : Thursday, March 24, 2011 - 1:36:52 PM


  • HAL Id : inria-00073981, version 1



Zhen Liu. Worst-Case Analysis of Scheduling Heuristics of Parallel Systems. RR-2710, INRIA. 1995. ⟨inria-00073981⟩



Record views


Files downloads