Approximation in stochastic scheduling: the power of LP-based priority policies

R.H. Möhring, A.S. Schulz, Marc Jochen Uetz

  • 91 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. 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 et al. [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 et al. [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.
Original languageUndefined
Article number10.1145/331524.331530
Pages (from-to)924-942
Number of pages19
JournalJournal of the Association for Computing Machinery
Volume46
Issue number6
DOIs
StatePublished - Nov 1999

Fingerprint

Scheduling
Probability distributions
Polynomials

Keywords

  • IR-62400
  • EWI-13115

Cite this

Möhring, R. H., Schulz, A. S., & Uetz, M. J. (1999). Approximation in stochastic scheduling: the power of LP-based priority policies. 46(6), 924-942. [10.1145/331524.331530]. DOI: 10.1145/331524.331530

Möhring, R.H.; Schulz, A.S.; Uetz, Marc Jochen / Approximation in stochastic scheduling: the power of LP-based priority policies.

Vol. 46, No. 6, 10.1145/331524.331530, 11.1999, p. 924-942.

Research output: Scientific - peer-reviewArticle

@article{c67f77a5a0784449a76ee0a379f3825e,
title = "Approximation in stochastic scheduling: the power of LP-based priority policies",
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. 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 et al. [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 et al. [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.",
keywords = "IR-62400, EWI-13115",
author = "R.H. Möhring and A.S. Schulz and Uetz, {Marc Jochen}",
year = "1999",
month = "11",
doi = "10.1145/331524.331530",
volume = "46",
pages = "924--942",
number = "6",

}

Möhring, RH, Schulz, AS & Uetz, MJ 1999, 'Approximation in stochastic scheduling: the power of LP-based priority policies' vol 46, no. 6, 10.1145/331524.331530, pp. 924-942. DOI: 10.1145/331524.331530

Approximation in stochastic scheduling: the power of LP-based priority policies. / Möhring, R.H.; Schulz, A.S.; Uetz, Marc Jochen.

Vol. 46, No. 6, 10.1145/331524.331530, 11.1999, p. 924-942.

Research output: Scientific - peer-reviewArticle

TY - JOUR

T1 - Approximation in stochastic scheduling: the power of LP-based priority policies

AU - Möhring,R.H.

AU - Schulz,A.S.

AU - Uetz,Marc Jochen

PY - 1999/11

Y1 - 1999/11

N2 - 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 et al. [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 et al. [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.

AB - 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 et al. [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 et al. [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.

KW - IR-62400

KW - EWI-13115

U2 - 10.1145/331524.331530

DO - 10.1145/331524.331530

M3 - Article

VL - 46

SP - 924

EP - 942

IS - 6

M1 - 10.1145/331524.331530

ER -

Möhring RH, Schulz AS, Uetz MJ. Approximation in stochastic scheduling: the power of LP-based priority policies. 1999 Nov;46(6):924-942. 10.1145/331524.331530. Available from, DOI: 10.1145/331524.331530