direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Logo der TU Berlin

Inhalt des Dokuments

Preprint 653-1999

Combinatorial Optimization & Graph Algorithms group (COGA-Preprints)

Scheduling unrelated machines by randomized rounding
SIAM Journal on Discrete Mathematics, to appear. This article combines the results from our ESA'97 paper (see Technical Report 533-1996) and from Section 4 of our Random'97 paper (see Technical Report 549-1997).
primary: 90C27 Combinatorial optimization
secondary: 68Q25 Analysis of algorithms and problem complexity
90B35 Scheduling theory, deterministic
68M20 Performance evaluation; queueing; scheduling
90C59 Approximation methods and heuristics
approximation algorithm, randomized rounding, LP relaxation, scheduling, online algorithm
In this paper, we provide a new class of randomized approximation algorithms for parallel machine scheduling problems. The most general model we consider is scheduling unrelated machines with release dates (or even network scheduling) so as to minimize the average weighted completion time. We introduce an LP relaxation in time-indexed variables for this problem. The crucial idea to derive approximation results is not to use standard list scheduling, but rather to assign jobs randomly to machines (by interpreting LP solutions as probabilities), and to perform list scheduling on each of them. Our main result is a (2+varepsilon)-approximation algorithm for this general model which improves upon performance guarantee 16/3 due to Hall, Shmoys, and Wein. In the absence of nontrivial release dates, we get a (3/2+varepsilon)-approximation. At the same time we prove corresponding bounds on the quality of the LP relaxation.
A perhaps surprising implication for identical parallel machines is that jobs are randomly assigned to machines, in which each machine is equally likely. In addition, in this case the algorithm has running time O(n log n) and performance guarantee 2. Moreover, the value of the nonpreemptive schedule computed by the algorithm is also within a bound of 2 of the value of an optimal preemptive schedule, which implies a bound on the power of preemption. Finally, the approximation results for identical parallel machine scheduling apply to both the offline and the online settings with no difference in performance guarantee.
Download as [PDF] [ps.gz]
Title: Source

Zusatzinformationen / Extras


Schnellnavigation zur Seite über Nummerneingabe