Stochastic machine scheduling: Performance guarantees for LP-based priority policies: (Extended abstract)

Rolf H. Möhring, Andreas S. Schulz, Marc Uetz

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

2 Scopus citations

Abstract

We consider the problem to minimize the total weighted completion time of a set of jobs with individual release dates which have to be scheduled on identical parallel machines. The durations of jobs are realized on-line according to given probability distributions, and the aim is to find a scheduling policy that minimizes the objective in expectation. We present a polyhedral relaxation of the corresponding performance space, and then derive the first constant-factor performance guarantees for priority policies which are guided by optimum LP solutions, thus generalizing previous results from deterministic scheduling. In the absence of release dates, our LP-based analysis also yields an additive performance guarantee for the WSEPT rule which implies both a worst-case performance ratio and a result on its asymptotic optimality.

Original languageEnglish
Title of host publicationRandomization, Approximation, and Combinatorial Optimization
Subtitle of host publicationAlgorithms and Techniques - 3rd International Workshop on Randomization and Approximation Techniques in Computer Science and 2nd International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, RANDOM-APPROX 1999, Proceedings
EditorsJose D. P. Rolim, Alistair Sinclair, Dorit Hochbaum, Klaus Jansen
PublisherSpringer Verlag
Pages144-155
Number of pages12
ISBN (Print)3540663290, 9783540663294
DOIs
StatePublished - 1999
Externally publishedYes
Event3rd International Workshop on Randomization and Approximation Techniques in Computer Science and 2nd International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, RANDOM-APPROX 1999 - Berkeley, United States
Duration: 8 Aug 199911 Aug 1999

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume1671
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference3rd International Workshop on Randomization and Approximation Techniques in Computer Science and 2nd International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, RANDOM-APPROX 1999
Country/TerritoryUnited States
CityBerkeley
Period8/08/9911/08/99

Fingerprint

Dive into the research topics of 'Stochastic machine scheduling: Performance guarantees for LP-based priority policies: (Extended abstract)'. Together they form a unique fingerprint.

Cite this