Greed Works-Online Algorithms for Unrelated Machine Stochastic Scheduling (vol 46, pg 835, 2021)

• 成果类型: Correction
• 署名作者: Gupta, Varun; Moseley, Benjamin; Uetz, Marc; Xie, Qiaomin
• 署名单位: University of Chicago; Carnegie Mellon University; University of Twente; Cornell University
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2021.1149
• 发表日期: 2021
• 页码: 1230-1234

摘要

This corrigendum fixes an incorrect claim in the paper Gupta et al. [Gupta V, Moseley B, Uetz M, Xie Q (2020) Greed works-online algorithms for unrelated machine stochastic scheduling. Math. Oper. Res. 45(2):497-516.], which led us to claim a performance guarantee of 6 for a greedy algorithm for deterministic online scheduling with release times on unrelated machines. The result is based on an upper bound on the increase of the objective function value when adding an additional job j to a machine i (Gupta et al., lemma 6). It was pointed out by Sven Jager from Technische Universit at Berlin that this upper bound may fail to hold. We here present a modified greedy algorithm and analysis, which leads to a performance guarantee of 7.216 instead. Correspondingly, also the claimed performance guarantee of (6 + 3 Delta)h(Delta) in theorem 4 of Gupta et al. for the stochastic online problem has to be corrected. We obtain a performance bound (7:216 + 3:608.)h(Delta).