Speed-robust scheduling: sand, bricks, and rocks

Franziska Eberle, Ruben Hoeksma, Nicole Megow, Lukas Nölke, Kevin Schewior*, Bertrand Simon

*Corresponding author for this work

Research output: Contribution to journalArticleAcademicpeer-review

68 Downloads (Pure)

Abstract

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.

Original languageEnglish
Pages (from-to)1009–1048
Number of pages40
JournalMathematical programming
Volume197
Issue number2
Early online date2 Jul 2022
DOIs
Publication statusPublished - Feb 2023

Keywords

  • Makespan
  • Resource allocation
  • Robust
  • Scheduling
  • Unknown processing speed
  • 22/3 OA procedure

Fingerprint

Dive into the research topics of 'Speed-robust scheduling: sand, bricks, and rocks'. Together they form a unique fingerprint.
  • Speed-Robust Scheduling: Sand, Bricks, and Rocks

    Eberle, F., Hoeksma, R., Megow, N., Nölke, L., Schewior, K. & Simon, B., 5 May 2021, Integer Programming and Combinatorial Optimization - 22nd International Conference, IPCO 2021, Proceedings. Singh, M. & Williamson, D. P. (eds.). Springer, p. 283-296 14 p. (Lecture Notes in Computer Science; vol. 12707).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    Open Access
    File
    2 Citations (Scopus)
    58 Downloads (Pure)

Cite this