Title
Approximation in stochastic scheduling: The power of
LP-based priority policies
Authors
-
Publication
Extended abstract in: Randomization, Approximation, and
Combinatorial Optimization, Dorit Hochbaum, Klaus Jansen, Jose
D. P. Rolim, Alistair Sinclair (eds.), Lecture Notes in Computer
Science 1671, Springer, Berlin, 1999, pages 144-155, Journal
version: Journal of the ACM 46(6), 1999, pages 924-942.
Source
-
Classification
-
not available
Keywords
-
Stochastic scheduling, Approximation, Worst-case
performance, Priority policy, LP-relaxation, WSEPT rule, Asymptotic
optimality
-
-
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. Job processing
times are not known in advance, they are realized on-line according
to given probability distributions. The aim is to find a scheduling
policy that minimizes the objective in expectation. Motivated by
the success of LP-based approaches to deterministic scheduling, we
present a polyhedral relaxation of the performance space of
stochastic parallel machine scheduling. This relaxation extends
earlier relaxations that have been used, among others, by Hall,
Schulz, Shmoys, and Wein (1997) in the deterministic setting. We
then derive constant performance guarantees for priority policies
which are guided by optimum LP solutions, and thereby generalize
previous results from deterministic scheduling. In the absence of
release dates, the 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, thus complementing previous work by Weiss (1990). The
corresponding LP lower bound generalizes a previous lower bound from
deterministic scheduling due to Eastman, Even, and Isaacs (1964),
and exhibits a relation between parallel machine problems and
corresponding problems with only one fast single machine. Finally,
we show that all employed LPs can be solved in polynomial time by
purely combinatorial algorithms.
