List scheduling of parallel tasks (Q758191)

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\).