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.
This work was partially supported by DFG Project, “Robuste Online-Algorithmen für Scheduling-und Packungsprobleme”, JA 612/19-1, and ANR project ROBUST (ANR-16-CE40-0018).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Aloulou, M.A., Croce, F.D.: Complexity of single machine scheduling problems under scenario-based uncertainty. Oper. Res. Lett. 36(3), 338–342 (2008)
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_6
Bertsimas, D., Sim, M.: Robust discrete optimization and network flows. Math. Program. 98(1–3), 49–71 (2003)
Bertsimas, D., Sim, M.: The price of robustness. Oper. Res. 52(1), 35–53 (2004)
Bougeret, M., Pessoa, A.A., Poss, M.: Robust scheduling with budgeted uncertainty. Discrete Appl. Math. 261, 93–107 (2019)
Daniels, R.L., Kouvelis, P.: Robust scheduling to hedge against processing time uncertainty in single-stage production. Manag. Sci. 41(2), 363–376 (1995)
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_42
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)
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_9
Lenstra, J.K., Shmoys, D.B., Tardos, E.: Approximation algorithms for scheduling unrelated parallel machines. Math. Program. 46(1–3), 259–271 (1990)
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_13
Tadayon, B., Smith, J.C.: Algorithms and complexity analysis for robust single-machine scheduling problems. J. Scheduling 18(6), 575–592 (2015)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Bougeret, M., Jansen, K., Poss, M., Rohwedder, L. (2020). Approximation Results for Makespan Minimization with Budgeted Uncertainty. In: Bampis, E., Megow, N. (eds) Approximation and Online Algorithms. WAOA 2019. Lecture Notes in Computer Science(), vol 11926. Springer, Cham. https://doi.org/10.1007/978-3-030-39479-0_5
Download citation
DOI: https://doi.org/10.1007/978-3-030-39479-0_5
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-39478-3
Online ISBN: 978-3-030-39479-0
eBook Packages: Mathematics and StatisticsMathematics and Statistics (R0)