On an on-line scheduling problem for parallel jobs
This paper addresses the non-preemptive on-line scheduling of parallel jobs. In particular we assume that the release dates and the processing times of the jobs are unknown. It is already known that for this problem Garey and Graham's list scheduling algorithm achieves the competitive factor 2 - 1/m for the makespan if m identical machines are available and if each job requires only a single machine for processing. Here, we show that the same factor also holds in the case of parallel jobs. (C) 2002 Elsevier Science B.V. All rights reserved.
scheduling on-line algorithms analysis of algorithms