Schedule in round robin fashion,
for P|pmtn|Cmax

We are given n jobs. Each job j has a processing time pj. We wish to find a feasible preemptive schedule for m parallel machines, which minimizes the maximal completion time.

Algorithm by Mc Naughton: The maximal completion time is easy to compute, it is Cmax = max{(p1+..+pn)/m, max p_j}. Then we processes jobs in arbitrary order and schedule them earliest possible on the first available machine, possibly preempting the job and continuing on the next machine.


number of machines
processing times
zoom x2