Speed-robust scheduling: sand, bricks, and rocks

• 成果类型: Article
• 署名作者: Eberle, Franziska; Hoeksma, Ruben; Megow, Nicole; Noelke, Lukas; Schewior, Kevin; Simon, Bertrand
• 署名单位: University of London; London School Economics & Political Science; University of Twente; University of Bremen; University of Southern Denmark; Centre National de la Recherche Scientifique (CNRS); CNRS - National Institute of Nuclear and Particle Physics (IN2P3)
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-022-01829-0
• 发表日期: 2023
• 页码: 1009-1048
• 关键词: approximation algorithms

摘要

The speed-robust scheduling problem is a two-stage problem where, given m machines, jobs must be grouped into at most m bags while the processing speeds of the machines are unknown. After the speeds are revealed, the grouped jobs must be assigned to the machines without being separated. To evaluate the performance of algorithms, we determine upper bounds on the worst-case ratio of the algorithm's makespan and the optimal makespan given full information. We refer to this ratio as the robustness factor. We give an algorithm with a robustness factor 2 - 1/m for the most general setting and improve this to 1.8 for equal-size jobs. For the special case of infinitesimal jobs, we give an algorithm with an optimal robustness factor equal to e/e - 1 approximate to 1.58. The particular machine environment in which all machines have either speed 0 or 1 was studied before by Stein and Zhong (ACM Trans Algorithms 16(1):1-20, 2020. https://doi.org/10.114/3340320) . For this setting, we provide an algorithm for scheduling infinitesimal jobs with an optimal robustness factor of 1+root 2/2 approximate to 1.207. It lays the foundation for an algorithm matching the lower bound of 4/3 for equal-size jobs.