Please use this identifier to cite or link to this item:
For citation please use:
Main Title: Scheduling-LPs Bear Probabilities: Randomized Approximations for Min-Sum Criteria
Author(s): Schulz, Andreas S.
Skutella, Martin
Type: Research Paper
Abstract: In this paper, we provide a new class of randomized approximation algorithms for scheduling problems by directly interpreting solutions to so-called time-indexed 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/3-approximation algorithm for preemptive single machine scheduling to minimize the average weighted completion time subject to release dates. This improves upon a 1.466-approximation algorithm due to Goemans, Wein, and Williamson. Finally, the results for identical parallel machine as well as single machine scheduling apply to both the off-line and the on-line settings with no difference in performance guarantees. In the on-line 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.
Subject(s): approximation algorithm
parallel machine
Min-Sum Criteria
Bear Probabilities
Issue Date: 1996
Date Available: 17-Dec-2021
Language Code: en
DDC Class: 510 Mathematik
Series: Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin
Series Number: 1996, 533
ISSN: 2197-8085
TU Affiliation(s): Fak. 2 Mathematik und Naturwissenschaften » Inst. Mathematik
Appears in Collections:Technische Universität Berlin » Publications

Files in This Item:
Format: Adobe PDF | Size: 213.92 kB
DownloadShow Preview
Format: Unknown | Size: 75.23 kB

Item Export Bar

Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.