TU Berlin

Combinatorial Optimization & Graph Algorithms group (COGA)2001

COGA 5-Wheel

Page Content

to Navigation

Preprints 2001

Scheduling Parallel Jobs to Minimize Makespan
Citation key Report-723-2001
Author Berit Johannes
Year 2001
Number 723
Institution Technische Universität Berlin, Institut für Mathematik
Abstract 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.
Bibtex Type of Publication Preprint
Link to publication Download Bibtex entry

Navigation

Quick Access

Schnellnavigation zur Seite über Nummerneingabe