List scheduling of parallel tasks (Q758191)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: List scheduling of parallel tasks |
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | List scheduling of parallel tasks |
scientific article |
Statements
List scheduling of parallel tasks (English)
0 references
1991
0 references
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\).
0 references
scheduling
0 references
parallel tasks
0 references
combinatorial problems
0 references
task precedence graph
0 references
