Unrelated Machine Scheduling with Stochastic Processing Times

Martin Skutella, Maxim Sviridenko, Marc Jochen Uetz

Research output: Contribution to journalArticleAcademicpeer-review

15 Citations (Scopus)

Abstract

Two important characteristics encountered in many real-world scheduling problems are heterogeneous processors and a certain degree of uncertainty about the processing times of jobs. In this paper we address both, and study for the first time a scheduling problem that combines the classical unrelated machine scheduling model with stochastic processing times of jobs. By means of a novel time-indexed linear programming relaxation, we show how to compute in polynomial time a scheduling policy with provable performance guarantee for the stochastic version of the unrelated parallel machine scheduling problem with the weighted sum of completion times objective. Our performance guarantee depends on the squared coefficient of variation of the processing times and we show that this dependence is tight. Currently best-known bounds for deterministic scheduling problems are contained as special cases.
Original languageUndefined
Pages (from-to)851-864
Number of pages14
JournalMathematics of operations research
Volume41
Issue number3
DOIs
Publication statusPublished - Aug 2016

Keywords

  • METIS-317229
  • Stochastic Scheduling
  • Approximation Algorithm
  • IR-100710
  • unrelated machines
  • 90B36, 68M20, 90C27, 90C59, 68W25, 68W40, 68Q25
  • minsum objective
  • EWI-27086

Cite this

Skutella, Martin ; Sviridenko, Maxim ; Uetz, Marc Jochen. / Unrelated Machine Scheduling with Stochastic Processing Times. In: Mathematics of operations research. 2016 ; Vol. 41, No. 3. pp. 851-864.
@article{9def878e3992447cb8aac94c7d62fc9d,
title = "Unrelated Machine Scheduling with Stochastic Processing Times",
abstract = "Two important characteristics encountered in many real-world scheduling problems are heterogeneous processors and a certain degree of uncertainty about the processing times of jobs. In this paper we address both, and study for the first time a scheduling problem that combines the classical unrelated machine scheduling model with stochastic processing times of jobs. By means of a novel time-indexed linear programming relaxation, we show how to compute in polynomial time a scheduling policy with provable performance guarantee for the stochastic version of the unrelated parallel machine scheduling problem with the weighted sum of completion times objective. Our performance guarantee depends on the squared coefficient of variation of the processing times and we show that this dependence is tight. Currently best-known bounds for deterministic scheduling problems are contained as special cases.",
keywords = "METIS-317229, Stochastic Scheduling, Approximation Algorithm, IR-100710, unrelated machines, 90B36, 68M20, 90C27, 90C59, 68W25, 68W40, 68Q25, minsum objective, EWI-27086",
author = "Martin Skutella and Maxim Sviridenko and Uetz, {Marc Jochen}",
note = "eemcs-eprint-27086",
year = "2016",
month = "8",
doi = "10.1287/moor.2015.0757",
language = "Undefined",
volume = "41",
pages = "851--864",
journal = "Mathematics of operations research",
issn = "0364-765X",
publisher = "INFORMS Institute for Operations Research and the Management Sciences",
number = "3",

}

Unrelated Machine Scheduling with Stochastic Processing Times. / Skutella, Martin; Sviridenko, Maxim; Uetz, Marc Jochen.

In: Mathematics of operations research, Vol. 41, No. 3, 08.2016, p. 851-864.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - Unrelated Machine Scheduling with Stochastic Processing Times

AU - Skutella, Martin

AU - Sviridenko, Maxim

AU - Uetz, Marc Jochen

N1 - eemcs-eprint-27086

PY - 2016/8

Y1 - 2016/8

N2 - Two important characteristics encountered in many real-world scheduling problems are heterogeneous processors and a certain degree of uncertainty about the processing times of jobs. In this paper we address both, and study for the first time a scheduling problem that combines the classical unrelated machine scheduling model with stochastic processing times of jobs. By means of a novel time-indexed linear programming relaxation, we show how to compute in polynomial time a scheduling policy with provable performance guarantee for the stochastic version of the unrelated parallel machine scheduling problem with the weighted sum of completion times objective. Our performance guarantee depends on the squared coefficient of variation of the processing times and we show that this dependence is tight. Currently best-known bounds for deterministic scheduling problems are contained as special cases.

AB - Two important characteristics encountered in many real-world scheduling problems are heterogeneous processors and a certain degree of uncertainty about the processing times of jobs. In this paper we address both, and study for the first time a scheduling problem that combines the classical unrelated machine scheduling model with stochastic processing times of jobs. By means of a novel time-indexed linear programming relaxation, we show how to compute in polynomial time a scheduling policy with provable performance guarantee for the stochastic version of the unrelated parallel machine scheduling problem with the weighted sum of completion times objective. Our performance guarantee depends on the squared coefficient of variation of the processing times and we show that this dependence is tight. Currently best-known bounds for deterministic scheduling problems are contained as special cases.

KW - METIS-317229

KW - Stochastic Scheduling

KW - Approximation Algorithm

KW - IR-100710

KW - unrelated machines

KW - 90B36, 68M20, 90C27, 90C59, 68W25, 68W40, 68Q25

KW - minsum objective

KW - EWI-27086

U2 - 10.1287/moor.2015.0757

DO - 10.1287/moor.2015.0757

M3 - Article

VL - 41

SP - 851

EP - 864

JO - Mathematics of operations research

JF - Mathematics of operations research

SN - 0364-765X

IS - 3

ER -