TY - JOUR

T1 - Speed-robust scheduling

T2 - sand, bricks, and rocks

AU - Eberle, Franziska

AU - Hoeksma, Ruben

AU - Megow, Nicole

AU - Nölke, Lukas

AU - Schewior, Kevin

AU - Simon, Bertrand

N1 - Funding Information:
A preliminary version was published in the Proceedings of the Conference on Integer Programming and Combinatorial Optimization (IPCO) 2021. Research was partially supported by Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) under Project 146371743 within TRR 89 Invasive Computing and under Contract ME 3825/1.
Publisher Copyright:
© 2022, Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society.

PY - 2022/7/2

Y1 - 2022/7/2

N2 - 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)≈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.1145/3340320). For this setting, we provide an algorithm for scheduling infinitesimal jobs with an optimal robustness factor of (1+√2)/2≈1.207. It lays the foundation for an algorithm matching the lower bound of 4/3 for equal-size jobs.

AB - 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)≈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.1145/3340320). For this setting, we provide an algorithm for scheduling infinitesimal jobs with an optimal robustness factor of (1+√2)/2≈1.207. It lays the foundation for an algorithm matching the lower bound of 4/3 for equal-size jobs.

KW - Makespan

KW - Resource allocation

KW - Robust

KW - Scheduling

KW - Unknown processing speed

KW - 22/3 OA procedure

UR - http://www.scopus.com/inward/record.url?scp=85133217591&partnerID=8YFLogxK

U2 - 10.1007/s10107-022-01829-0

DO - 10.1007/s10107-022-01829-0

M3 - Article

AN - SCOPUS:85133217591

JO - Mathematical programming

JF - Mathematical programming

SN - 0025-5610

ER -