Greed Works—Online Algorithms for Unrelated Machine Stochastic Scheduling

Varun Gupta (), Benjamin Moseley (), Marc Uetz () and Qiaomin Xie ()
Additional contact information
Varun Gupta: Booth School of Business, University of Chicago, Chicago, Illinois 60637
Benjamin Moseley: Tepper School of Business, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213
Marc Uetz: Department of Applied Mathematics, University of Twente, 7522 NB Enschede, Netherlands
Qiaomin Xie: Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139

Mathematics of Operations Research, 2020, vol. 45, issue 2, 497-516

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.

Keywords: unrelated machine scheduling; stochastic scheduling; online scheduling (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://doi.org/10.1287/moor.2019.0999 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:45:y:2020:i:2:p:497-516

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().