Research output per year
Research output per year
Franziska Eberle^{*}, Ruben Hoeksma, Nicole Megow, Lukas Nölke, Kevin Schewior, Bertrand Simon
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review
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 | |
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 |
Name | Lecture Notes in Computer Science |
---|---|
Publisher | Springer |
Volume | 12707 |
ISSN (Print) | 0302-9743 |
ISSN (Electronic) | 1611-3349 |
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 |
Research output: Contribution to journal › Article › Academic › peer-review