Speed-Robust Scheduling: Sand, Bricks, and Rocks

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

doi:10.1007/978-3-030-73879-2_20

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

Mathematics of Operations Research

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

2 Citations (Scopus)

80 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-1m 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 ee-1≈1.58. The particular machine environment in which all machines have either speed 0 or 1 was studied before by Stein and Zhong (SODA 2019). For this setting, we provide an algorithm for scheduling infinitesimal jobs with an optimal robustness factor of 1+22≈1.207. It lays the foundation for an algorithm matching the lower bound of 43 for equal-size jobs.

Original language	English
Title of host publication	Integer Programming and Combinatorial Optimization - 22nd International Conference, IPCO 2021, Proceedings
Editors	Mohit Singh, David P. Williamson
Publisher	Springer
Pages	283-296
Number of pages	14
ISBN (Electronic)	978-3-030-73879-2
ISBN (Print)	978-3-030-73878-5
DOIs	https://doi.org/10.1007/978-3-030-73879-2_20
Publication status	Published - 5 May 2021
Event	22nd International Conference on Integer Programming and Combinatorial Optimization, IPCO 2021 - Virtual, Online Duration: 19 May 2021 → 21 May 2021 Conference number: 22

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	12707
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	22nd International Conference on Integer Programming and Combinatorial Optimization, IPCO 2021
Abbreviated title	IPCO 2021
City	Virtual, Online
Period	19/05/21 → 21/05/21

Access to Document

10.1007/978-3-030-73879-2_20

Eberle-2021-Speed-robustFinal published version, 318 KBLicence: Taverne

Cite this

Eberle, F., Hoeksma, R., Megow, N., Nölke, L., Schewior, K., & Simon, B. (2021). Speed-Robust Scheduling: Sand, Bricks, and Rocks. In M. Singh, & D. P. Williamson (Eds.), Integer Programming and Combinatorial Optimization - 22nd International Conference, IPCO 2021, Proceedings (pp. 283-296). (Lecture Notes in Computer Science; Vol. 12707). Springer. https://doi.org/10.1007/978-3-030-73879-2_20

@inproceedings{201a33a625c94ae2979dbefd19aeb753,

title = "Speed-Robust Scheduling: Sand, Bricks, and Rocks",

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{\textquoteright}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-1m 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 ee-1≈1.58. The particular machine environment in which all machines have either speed 0 or 1 was studied before by Stein and Zhong (SODA 2019). For this setting, we provide an algorithm for scheduling infinitesimal jobs with an optimal robustness factor of 1+22≈1.207. It lays the foundation for an algorithm matching the lower bound of 43 for equal-size jobs.",

author = "Franziska Eberle and Ruben Hoeksma and Nicole Megow and Lukas N{\"o}lke and Kevin Schewior and Bertrand Simon",

note = "Funding Information: by the German Science Foundation (DFG) under contract ME Publisher Copyright: {\textcopyright} 2021, Springer Nature Switzerland AG.; 22nd International Conference on Integer Programming and Combinatorial Optimization, IPCO 2021, IPCO 2021 ; Conference date: 19-05-2021 Through 21-05-2021",

year = "2021",

month = may,

day = "5",

doi = "10.1007/978-3-030-73879-2_20",

language = "English",

isbn = "978-3-030-73878-5",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "283--296",

editor = "Mohit Singh and Williamson, {David P.}",

booktitle = "Integer Programming and Combinatorial Optimization - 22nd International Conference, IPCO 2021, Proceedings",

address = "Germany",

}

Eberle, F, Hoeksma, R, Megow, N, Nölke, L, Schewior, K & Simon, B 2021, Speed-Robust Scheduling: Sand, Bricks, and Rocks. in M Singh & DP Williamson (eds), Integer Programming and Combinatorial Optimization - 22nd International Conference, IPCO 2021, Proceedings. Lecture Notes in Computer Science, vol. 12707, Springer, pp. 283-296, 22nd International Conference on Integer Programming and Combinatorial Optimization, IPCO 2021, Virtual, Online, 19/05/21. https://doi.org/10.1007/978-3-030-73879-2_20

Speed-Robust Scheduling: Sand, Bricks, and Rocks. / Eberle, Franziska; Hoeksma, Ruben; Megow, Nicole et al.
Integer Programming and Combinatorial Optimization - 22nd International Conference, IPCO 2021, Proceedings. ed. / Mohit Singh; David P. Williamson. Springer, 2021. p. 283-296 (Lecture Notes in Computer Science; Vol. 12707).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Speed-Robust Scheduling

T2 - 22nd International Conference on Integer Programming and Combinatorial Optimization, IPCO 2021

AU - Eberle, Franziska

AU - Hoeksma, Ruben

AU - Megow, Nicole

AU - Nölke, Lukas

AU - Schewior, Kevin

AU - Simon, Bertrand

N1 - Conference code: 22

PY - 2021/5/5

Y1 - 2021/5/5

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-1m 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 ee-1≈1.58. The particular machine environment in which all machines have either speed 0 or 1 was studied before by Stein and Zhong (SODA 2019). For this setting, we provide an algorithm for scheduling infinitesimal jobs with an optimal robustness factor of 1+22≈1.207. It lays the foundation for an algorithm matching the lower bound of 43 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-1m 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 ee-1≈1.58. The particular machine environment in which all machines have either speed 0 or 1 was studied before by Stein and Zhong (SODA 2019). For this setting, we provide an algorithm for scheduling infinitesimal jobs with an optimal robustness factor of 1+22≈1.207. It lays the foundation for an algorithm matching the lower bound of 43 for equal-size jobs.

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

U2 - 10.1007/978-3-030-73879-2_20

DO - 10.1007/978-3-030-73879-2_20

M3 - Conference contribution

AN - SCOPUS:85106199993

SN - 978-3-030-73878-5

T3 - Lecture Notes in Computer Science

SP - 283

EP - 296

BT - Integer Programming and Combinatorial Optimization - 22nd International Conference, IPCO 2021, Proceedings

A2 - Singh, Mohit

A2 - Williamson, David P.

PB - Springer

Y2 - 19 May 2021 through 21 May 2021

ER -

Speed-Robust Scheduling: Sand, Bricks, and Rocks

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Speed-robust scheduling: sand, bricks, and rocks

Speed-Robust Scheduling: Sand, Bricks, and Rocks

Cite this