TY - GEN
T1 - Online Makespan Minimization with Budgeted Uncertainty
AU - Albers, Susanne
AU - Janke, Maximilian
N1 - Publisher Copyright:
© 2021, Springer Nature Switzerland AG.
PY - 2021
Y1 - 2021
N2 - We study Online Makespan Minimization with uncertain job processing times. Jobs are assigned to m parallel and identical machines. Preemption is not allowed. Each job has a regular processing time while up to Γ jobs fail and require additional processing time. The goal is to minimize the makespan, the time it takes to process all jobs if these Γ failing jobs are chosen worst possible. This models real-world applications where acts of nature beyond control have to be accounted for. So far Makespan Minimization With Budgeted Uncertainty has only been studied as an offline problem. We are first to provide a comprehensive analysis of the corresponding online problem. We provide a lower bound of 2 for general deterministic algorithms showing that the problem is more difficult than its special case, classical Online Makespan Minimization. We further analyze Graham’s Greedy strategy and show that it is precisely (3-2m) -competitive. This bound is tight. We finally provide a more sophisticated deterministic algorithm whose competitive ratio approaches 2.9052.
AB - We study Online Makespan Minimization with uncertain job processing times. Jobs are assigned to m parallel and identical machines. Preemption is not allowed. Each job has a regular processing time while up to Γ jobs fail and require additional processing time. The goal is to minimize the makespan, the time it takes to process all jobs if these Γ failing jobs are chosen worst possible. This models real-world applications where acts of nature beyond control have to be accounted for. So far Makespan Minimization With Budgeted Uncertainty has only been studied as an offline problem. We are first to provide a comprehensive analysis of the corresponding online problem. We provide a lower bound of 2 for general deterministic algorithms showing that the problem is more difficult than its special case, classical Online Makespan Minimization. We further analyze Graham’s Greedy strategy and show that it is precisely (3-2m) -competitive. This bound is tight. We finally provide a more sophisticated deterministic algorithm whose competitive ratio approaches 2.9052.
KW - Budgeted Uncertainty
KW - Competitive analysis
KW - Lower bound
KW - Makespan Minimization
KW - Online algorithm
KW - Scheduling
KW - Uncertainty
UR - http://www.scopus.com/inward/record.url?scp=85113476851&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-83508-8_4
DO - 10.1007/978-3-030-83508-8_4
M3 - Conference contribution
AN - SCOPUS:85113476851
SN - 9783030835071
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 43
EP - 56
BT - Algorithms and Data Structures - 17th International Symposium, WADS 2021, Proceedings
A2 - Lubiw, Anna
A2 - Salavatipour, Mohammad
PB - Springer Science and Business Media Deutschland GmbH
T2 - 17th International Symposium on Algorithms and Data Structures, WADS 2021
Y2 - 9 August 2021 through 11 August 2021
ER -