@inproceedings{f882413547854dd3b0ee24ad4a251fe3,
title = "Stochastic machine scheduling: Performance guarantees for LP-based priority policies: (Extended abstract)",
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.",
author = "M{\"o}hring, {Rolf H.} and Schulz, {Andreas S.} and Marc Uetz",
note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1999.; 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 ; Conference date: 08-08-1999 Through 11-08-1999",
year = "1999",
doi = "10.1007/978-3-540-48413-4_16",
language = "English",
isbn = "3540663290",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "144--155",
editor = "Rolim, {Jose D. P.} and Alistair Sinclair and Dorit Hochbaum and Klaus Jansen",
booktitle = "Randomization, Approximation, and Combinatorial Optimization",
}