Please use this identifier to cite or link to this item:
For citation please use:
Main Title: Scheduling unrelated machines by randomized rounding
Author(s): Schulz, Andreas S.
Skutella, Martin
Type: Research Paper
Abstract: 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.
Subject(s): approximation algorithm
randomized rounding
LP relaxation
online algorithm
Issue Date: 1999
Date Available: 17-Dec-2021
Language Code: en
DDC Class: 510 Mathematik
MSC 2000: 90C27 Combinatorial optimization
68Q25 Analysis of algorithms and problem complexity
90B35 Scheduling theory, deterministic
68M20 Performance evaluation; queueing; scheduling
90C59 Approximation methods and heuristics
Series: Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin
Series Number: 1999, 653
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: 297.21 kB
DownloadShow Preview
Format: Unknown | Size: 108.63 kB

Item Export Bar

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