Online Makespan Minimization with Budgeted Uncertainty

Susanne Albers, Maximilian Janke

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

3 Scopus citations

Abstract

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.

Original languageEnglish
Title of host publicationAlgorithms and Data Structures - 17th International Symposium, WADS 2021, Proceedings
EditorsAnna Lubiw, Mohammad Salavatipour
PublisherSpringer Science and Business Media Deutschland GmbH
Pages43-56
Number of pages14
ISBN (Print)9783030835071
DOIs
StatePublished - 2021
Event17th International Symposium on Algorithms and Data Structures, WADS 2021 - Virtual, Online
Duration: 9 Aug 202111 Aug 2021

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12808 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference17th International Symposium on Algorithms and Data Structures, WADS 2021
CityVirtual, Online
Period9/08/2111/08/21

Keywords

  • Budgeted Uncertainty
  • Competitive analysis
  • Lower bound
  • Makespan Minimization
  • Online algorithm
  • Scheduling
  • Uncertainty

Fingerprint

Dive into the research topics of 'Online Makespan Minimization with Budgeted Uncertainty'. Together they form a unique fingerprint.

Cite this