Stochastic online scheduling on unrelated machines

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

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

13 Citations (Scopus)


We derive the first performance guarantees for a combinatorial online algorithm that schedules stochastic, nonpreemptive jobs on unrelated machines to minimize the expectation of the total weighted completion time. Prior work on unrelated machine scheduling with stochastic jobs was restricted to the offline case, and required sophisticated linear or convex programming relaxations for the assignment of jobs to machines. Our algorithm is purely combinatorial, and therefore it also works for the online setting. As to the techniques applied, this paper shows how the dual fitting technique can be put to work for stochastic and nonpreemptive scheduling problems.

Original languageEnglish
Title of host publicationInteger Programming and Combinatorial Optimization
Subtitle of host publication19th International Conference, IPCO 2017, Waterloo, ON, Canada, June 26-28, 2017, Proceedings
EditorsFriedrich Eisenbrand, Jochen Koenemann
Number of pages13
ISBN (Electronic)978-3-319-59250-3
ISBN (Print)978-3-319-59249-7
Publication statusPublished - Jun 2017
Event19th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2017 - Waterloo, Canada
Duration: 26 Jun 201728 Jun 2017
Conference number: 19

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference19th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2017
Abbreviated titleIPCO


Dive into the research topics of 'Stochastic online scheduling on unrelated machines'. Together they form a unique fingerprint.

Cite this