1 May 2020 in Mathematics of Operations Research
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.
1 January 2022 in Operations Research Letters
28 September 2023 in Foundations and Trends® in Optimization
The algorithms community has been modeling the underlying key features and constraints of massively parallel frameworks and using these models to discover new algorithmic techniques tailored to them. This monograph focuses on the Massively Parallel Model of Computation (MPC) framework, also known as the MapReduce model in the literature. It describes algorithmic tools that have been developed to leverage the unique features of the MPC framework. These tools were chosen for their broad applicability, as they can serve as building blocks to design new algorithms. The monograph is not exhaustive and includes topics such as partitioning and coresets, sample and prune, dynamic programming, round compression, and lower bounds.
1 August 2021 in Mathematics of Operations Research
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 [ ] to a machine [ ] (Gupta et al., lemma 6). It was pointed out by Sven Jäger from Technische Universität 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 [ ] in theorem 4 of Gupta et al. for the stochastic online problem has to be corrected. We obtain a performance bound [ ].