A Comparison of List Schedules for Parallel Processing Systems

The problem of scheduling two or more processors
to minimize the execution time of a program 
which consists of a set of partially ordered tasks
is studied.  Cases where task execution times are 
deterministic and others in which execution times are
random variables are analyzed.  It is shown that 
different algorithms suggested in the literature vary significantly
in execution time and that the B-schedule 
of Coffman and Graham is near-optimal.  A dynamic programming
solution for the case in which execution 
times are random variables is presented.

CACM December, 1974

Adam, T. L.
Chandy, K. M.
Dickson, J. R.

parallel processing, precedence graphs, scheduling,
list scheduling, optimization, dynamic programming

4.3 4.32 4.34 4.35 5.3 5.32 5.4 5.42 8.1

CA741204 JB January 16, 1978  9:42 AM

2570	5	2570
2570	5	2570
2570	5	2570