Greed works-online algorithms for unrelated machine stochastic scheduling

Varun Gupta, Benjamin Moseley, Marc Uetz*, Qiaomin Xie

*Corresponding author for this work

Research output: Contribution to journalArticleAcademicpeer-review

2 Citations (Scopus)
10 Downloads (Pure)

Abstract

This paper establishes performance guarantees for online algorithms that schedule stochastic, nonpreemptive jobs on unrelated machines to minimize the expected total weighted completion time. Prior work on unrelated machine scheduling with stochastic jobs was restricted to the offline case and required linear or convex programming relaxations for the assignment of jobs to machines. The algorithms introduced in this paper are purely combinatorial. The performance bounds are of the same order of magnitude as those of earlier work and depend linearly on an upper bound on the squared coefficient of variation of the jobs' processing times. Specifically for deterministic processing times, without and with release times, the competitive ratios are 4 and 6, respectively. As to the technical contribution, this paper shows how dual fitting techniques can be used for stochastic and nonpreemptive scheduling problems.

Original languageEnglish
Pages (from-to)497-516
Number of pages20
JournalMathematics of operations research
Volume45
Issue number2
Early online date29 Jan 2020
DOIs
Publication statusPublished - May 2020

Keywords

  • Online scheduling
  • Stochastic scheduling
  • Unrelated machine scheduling

Fingerprint Dive into the research topics of 'Greed works-online algorithms for unrelated machine stochastic scheduling'. Together they form a unique fingerprint.

Cite this