Inhalt des Dokuments
Preprint 5331996
Combinatorial Optimization & Graph Algorithms group (COGAPreprints) Title
 SchedulingLPs Bear Probabilities: Randomized Approximations for MinSum Criteria
 Authors
 Publication
 In Rainer Burkard and Gerhard Woeginger (eds.): Algorithms  ESA '97, Lecture Notes in Computer Science 1284, Springer: Berlin, 1997, pp. 416429, Proceedings of the 5th Annual European Symposium on Algorithms (ESA'97).
 Classification

not available
 Keywords

not available
 Abstract

In this paper, we provide a new class of randomized approximation algorithms for scheduling problems by directly interpreting solutions to socalled timeindexed LPs as probabilities. The most general model we consider is scheduling unrelated parallel machines with release dates (or even network scheduling) so as to minimize the average weighted completion time. The crucial idea for these multiple machine problems is not to use standard list scheduling but rather to assign jobs randomly to machines (with probabilities taken from an optimal LP solution) and to perform list scheduling on each of them.For the general model, we give a (2 + ε)approximation algorithm. The best previously known approximation algorithm has a performance guarantee of 16/3. Moreover, our algorithm also improves upon the best previously known approximation algorithms for the special case of identical parallel machine scheduling (performance guarantee `(2.89 + ε) in general and 2.85` for the average completion time, respectively). 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.For minimizing the average weighted completion time on a single machine under release dates, a refined version of our algorithm produces in O}(n log n) time a schedule that is expected to be within a factor of 1.6853 of the optimum. An appropriately adapted version is a 4/3approximation algorithm for preemptive single machine scheduling to minimize the average weighted completion time subject to release dates. This improves upon a 1.466approximation algorithm due to Goemans, Wein, and Williamson.Finally, the results for identical parallel machine as well as single machine scheduling apply to both the offline and the online settings with no difference in performance guarantees. In the online setting, we are scheduling jobs that continually arrive to be processed and, for each time t, we must construct the schedule until time t without any knowledge of the jobs that will arrive afterwards.
 Source
Zusatzinformationen / Extras
Direktzugang
Schnellnavigation zur Seite über Nummerneingabe