We consider the NP-hard problem of
scheduling parallel jobs with release dates on identical parallel
machines to minimize the makespan. A parallel job requires
simultaneously a pre-specified, job-dependent number of machines when
being processed. Our main result is the following. The makespan of a
(non-preemptive) schedule constructed by any listscheduling
algorithm is within a factor of 2 of the optimal preemptive
makespan. This gives the best known approximation algorithms for both
the preemptive and the non-preemptive variant of the problem,
improving upon previously known performance guarantees of 3. We
also show that no listscheduling algorithm can achieve a better
performance guarantee than 2 for the non-preemptive problem, no
matter which priority list is chosen.
Since listscheduling also works in the online setting in which jobs
arrive over time and the length of a job becomes only known when it
completes, the main result yields a deterministic online algorithm
with competitive ratio 2 as well. In addition, we consider a different
online model in which jobs arrive one by one and need to be scheduled
before the next job becomes known. In this context, no listscheduling
algorithm has a constant competitive ratio. We present the first
online algorithm for scheduling parallel jobs with a constant
competitive ratio. We also prove a new information-theoretic lower
bound of 2.25 for the competitive ratio of any deterministic online
algorithm for this model.
