List scheduling of parallel tasks

DOI10.1016/0020-0190(91)90222-4MaRDI QIDQ758191zbMATH OpenOpenAlexFDO

Authors Qingzhou Wang, Kam Hoi Cheng

Publication date 1991

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(91)90222-4

zbMATH Keywords

combinatorial problemsparallel tasksschedulingtask precedence graph

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Combinatorics in computer science (68R05)

Review text

The original list scheduling algorithm \textit{R. L. Graham} [Bounds an multprocessing timing anomalies, SIAM J. Appl. Math. 17, 416-429 (1969)] is presented and its performance ratio is shown to be \(\Delta +(m- \Delta)/m\) when parallel tasks are involved. We present a modified list scheduling algorithm which uses the earliest completion time heuristic to schedule tasks. Its performance ratio is shown to be bounded by ln \(\Delta\) \(+2\).

Recommendations

• Analysis of the list scheduling algorithm for precedence constrained parallel tasks
• A Heuristic of Scheduling Parallel Tasks and Its Analysis
• scientific article; zbMATH DE number 2162223
• An On-Line Scheduling Heuristic with Better Worst-Case Ratio Than Graham’s List Scheduling
• List scheduling revisited

Cites work

• Bounds on Multiprocessing Timing Anomalies
• Complexity of Scheduling Parallel Task Systems
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Scheduling Multiprocessor Tasks to Minimize Schedule Length

Cited in

(11)

• List scheduling in the presence of branches. A theoretical evaluation
• Scheduling multiprocessor tasks -- An overview
• Analysis of the list scheduling algorithm for precedence constrained parallel tasks
• List scheduling with and without communication delays
• List scheduling of general task graphs under LogP
• Optimal workforce assignment to operations of a paced assembly line
• List scheduling revisited
• scientific article; zbMATH DE number 3978800 (Why is no real title available?)
• An effective approximation algorithm for the malleable parallel task scheduling problem
• List Heuristic Scheduling Algorithms for Distributed Memory Systems with Improved Time Complexity
• An improved approximation algorithm for scheduling monotonic moldable tasks

This page was built for publication: List scheduling of parallel tasks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q758191)