Top

Published in:

2020 | OriginalPaper | Chapter

Approximation Results for Makespan Minimization with Budgeted Uncertainty

Authors : Marin Bougeret, Klaus Jansen, Michael Poss, Lars Rohwedder

Published in: Approximation and Online Algorithms

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

We study approximation algorithms for the problem of minimizing the makespan on a set of machines with uncertainty on the processing times of jobs. In the model we consider, which goes back to [3], once the schedule is defined an adversary can pick a scenario where deviation is added to some of the jobs’ processing times. Given only the maximal cardinality of these jobs, and the magnitude of potential deviation for each job, the goal is to optimize the worst-case scenario. We consider both the cases of identical and unrelated machines. Our main result is an EPTAS for the case of identical machines. We also provide a 3-approximation algorithm and an inapproximability ratio of \(2-\epsilon \) for the case of unrelated machines.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Robust Online Algorithms for Certain Dynamic Packing Problems

next chapter Streaming Algorithms for Bin Packing and Vector Scheduling

Aloulou, M.A., Croce, F.D.: Complexity of single machine scheduling problems under scenario-based uncertainty. Oper. Res. Lett. 36(3), 338–342 (2008)MathSciNetCrossRef

Basu Roy, A., Bougeret, M., Goldberg, N., Poss, M.: Approximating robust bin packing with budgeted uncertainty. In: Friggstad, Z., Sack, J.-R., Salavatipour, M.R. (eds.) WADS 2019. LNCS, vol. 11646, pp. 71–84. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-24766-9_6CrossRef

Bertsimas, D., Sim, M.: Robust discrete optimization and network flows. Math. Program. 98(1–3), 49–71 (2003)MathSciNetCrossRef

Bertsimas, D., Sim, M.: The price of robustness. Oper. Res. 52(1), 35–53 (2004)MathSciNetCrossRef

Bougeret, M., Pessoa, A.A., Poss, M.: Robust scheduling with budgeted uncertainty. Discrete Appl. Math. 261, 93–107 (2019)MathSciNetCrossRef

Daniels, R.L., Kouvelis, P.: Robust scheduling to hedge against processing time uncertainty in single-stage production. Manag. Sci. 41(2), 363–376 (1995)CrossRef

Jansen, K., Klein, K., Verschae, J.: Closing the gap for makespan scheduling via sparsification techniques. In: 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, 11–15 July 2016, Rome, Italy, pp. 72:1–72:13 (2016)

Jansen, K., Maack, M.: An EPTAS for scheduling on unrelated machines of few different types. Algorithms and Data Structures. LNCS, vol. 10389, pp. 497–508. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-62127-2_42CrossRef

Kasperski, A., Kurpisz, A., Zielinski, P.: Approximating a two-machine flow shop scheduling under discrete scenario uncertainty. Eur. J. Oper. Res. 217(1), 36–43 (2012)MathSciNetCrossRef

10.

Kasperski, A., Kurpisz, A., Zieliński, P.: Parallel machine scheduling under uncertainty. In: Greco, S., Bouchon-Meunier, B., Coletti, G., Fedrizzi, M., Matarazzo, B., Yager, R.R. (eds.) IPMU 2012. CCIS, vol. 300, pp. 74–83. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-31724-8_9CrossRef

11.

Lenstra, J.K., Shmoys, D.B., Tardos, E.: Approximation algorithms for scheduling unrelated parallel machines. Math. Program. 46(1–3), 259–271 (1990)MathSciNetCrossRef

12.

Mastrolilli, M., Mutsanas, N., Svensson, O.: Approximating single machine scheduling with scenarios. In: Goel, A., Jansen, K., Rolim, J.D.P., Rubinfeld, R. (eds.) APPROX/RANDOM -2008. LNCS, vol. 5171, pp. 153–164. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-85363-3_13CrossRef

13.

Tadayon, B., Smith, J.C.: Algorithms and complexity analysis for robust single-machine scheduling problems. J. Scheduling 18(6), 575–592 (2015)MathSciNetCrossRef

Title: Approximation Results for Makespan Minimization with Budgeted Uncertainty
Authors: Marin Bougeret
Klaus Jansen
Michael Poss
Lars Rohwedder
Publisher: Springer International Publishing
Book: Approximation and Online Algorithms
Print ISBN: 978-3-030-39478-3

Electronic ISBN: 978-3-030-39479-0

Copyright Year: 2020
DOI: https://doi.org/10.1007/978-3-030-39479-0_5

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner