Abstract
In this paper, we address the Unrelated Parallel Machine Scheduling Problem (UPMSP) with sequence- and machine-dependent setup times and job due-date constraints. Different uncertainties are typically involved in real-world production planning and scheduling problems. If ignored, they can lead to suboptimal or even infeasible schedules. To avoid this, we present two new robust optimization models for this UPMSP variant, considering stochastic job processing and machine setup times. To the best of our knowledge, this is the first time that a robust optimization approach is used to address uncertain processing and setup times in the UPMSP with sequence- and machine-dependent setup times and job due-date constraints. We carried out computational experiments to compare the performance of the robust models and verify the impact of uncertainties to the problem solutions when minimizing the production makespan. The results of computational experiments indicate that the robust models incorporate uncertainties appropriately into the problem and produce effective and robust schedules. Furthermore, the results show that the models are useful for analyzing the impact of uncertainties in the cost and risk of the scheduling solutions.
Access this article
We’re sorry, something doesn't seem to be working properly.
Please try refreshing the page. If that doesn't work, please contact support so we can address the problem.
Similar content being viewed by others
References
Afzalirad M, Rezaeian J (2016) Resource-constrained unrelated parallel machine scheduling problem with sequence dependent setup times, precedence constraints and machine eligibility restrictions. Comput Ind Eng 98:40–52
Alem D, Morabito R (2012) Production planning in furniture settings via robust optimization. Comput Oper Res 39(2):139–150
Arnaout J-P, Rabadi G, Musa R (2010) A two-stage ant colony optimization algorithm to minimize the makespan on unrelated parallel machines with sequence-dependent setup times. J Intell Manuf 21(6):693–701
Arnaout J-PP, Musa R, Rabadi G, Rami J-PA, Ghaith M (2014) A two-stage ant colony optimization algorithm to minimize the makespan on unrelated parallel machines—part II: enhancements and experimentations. J Intell Manuf 25(1):43–53
Avalos-Rosales O, Angel-Bello F, Alvarez A (2015) Efficient metaheuristic algorithm and re-formulations for the unrelated parallel machine scheduling problem with sequence and machine-dependent setup times. Int J Adv Manuf Technol 76(9):1705–1718
Ben-Tal A, Nemirovski A (2000) Robust solutions of linear programming problems contaminated with uncertain data. Math Program Ser B 88:411–424
Ben-Tal A, El Ghaoui L, Nemirovski A (2009) Robust optimization. Princeton Series in Applied Mathematics. Princeton University Press, Princeton
Bertsimas D, Ng Y (2019) Robust and stochastic formulations for ambulance deployment and dispatch. Eur J Oper Res 279(2):557–571
Bertsimas D, Sim M (2003) Robust discrete optimization and network flows. Math Program 98(1–3):49–71
Bertsimas D, Sim M (2004) The price of robustness. Oper Res 52(1):35–53
Bertsimas D, Thiele A (2006) A robust optimization approach to inventory theory. Oper Res 54(1):150–168
Bertsimas D, Brown DB, Caramanis C (2011) Theory and applications of robust optimization. SIAM Rev 53(3):464–501
Bertsimas D, Goyal V, Lu B (2015) A tight characterization of the performance of static solutions in two-stage adjustable robust linear optimization. Math Program 150(2):281–319
Bertsimas D, Gupta V, Kallus N (2018) Data-driven robust optimization. Math Program 167(2):235–292
Bougeret M, Pessoa AA, Poss M (2019) Robust scheduling with budgeted uncertainty. Discrete Appl Math 261:93–107
Chen J-F (2009) Scheduling on unrelated parallel machines with sequence- and machine-dependent setup times and due-date constraints. Int J Adv Manuf Technol 44(11–12):1204–1212
Chen J-F (2015) Unrelated parallel-machine scheduling to minimize total weighted completion time. J Intell Manuf 26(6):1099–1112
Cheng T, Sin C (1990) A state-of-the-art review of parallel-machine scheduling research. Eur J Oper Res 47(3):271–292
Chyu C-C, Chang W-S (2011) Optimizing fuzzy makespan and tardiness for unrelated parallel machine scheduling with archived metaheuristics. Int J Adv Manuf Technol 57(5–8):763–776
De La Vega J, Munari P, Morabito R (2019) Robust optimization for the vehicle routing problem with multiple deliverymen. Cent Eur J Oper Res 27(4):905–936
De La Vega J, Munari P, Morabito R (2020) Exact approaches to the robust vehicle routing problem with time windows and multiple deliverymen. Comput Oper Res 124:105062
De Ruiter FJCT, Ben-Tal A, Brekelmans RCM, den Hertog D (2017) Robust optimization of uncertain multistage inventory systems with inexact data in decision rules. Comput Manag Sci 14(1):45–66
Dolan ED, Moré JJ (2002) Benchmarking optimization software with performance profiles. Math Program 91(2):201–213
Feng X, Zheng F, Xu Y (2016) Robust scheduling of a two-stage hybrid flow shop with uncertain interval processing times. Int J Prod Res 54(12):3706–3717
Gharehgozli A, Tavakkoli-Moghaddam R, Zaerpour N (2009) A fuzzy-mixed-integer goal programming model for a parallel-machine scheduling problem with sequence-dependent setup times and release dates. Robot Comput Integr Manuf 25(4–5):853–859
Gomes FRA, Mateus GR (2017) Improved combinatorial benders decomposition for a scheduling problem with unrelated parallel machines. J Appl Math 2017:1–10
González-Neira EM, Montoya-Torres JR, Barrera D (2017) Flow-shop scheduling problem under uncertainties: review and trends. Int J Ind Eng Comput 8(4):399–426
Gorissen BL, Yamkoǧlu I, den Hertog D (2015) A practical guide to robust optimization. Omega 53:124–137
Hu H, Ng K KH, Qin Y (2016) Robust parallel machine scheduling problem with uncertainties and sequence-dependent setup time. Sci Program, 13
Liao TW, Su P (2017) Parallel machine scheduling in fuzzy environment with hybrid ant colony optimization including a comparison of fuzzy number ranking methods in consideration of spread of fuzziness. Appl Soft Comput 56:65–81
Lin S-W, Lu C-C, Ying K-C (2011) Minimization of total tardiness on unrelated parallel machines with sequence- and machine-dependent setup times under due date constraints. Int J Adv Manuf Technol 53(1–4):353–361
Macedo PB, Alem D, Santos M, Junior ML, Moreno A (2016) Hybrid manufacturing and remanufacturing lot-sizing problem with stochastic demand, return, and setup costs. Int J Adv Manuf Technol 82(5):1241–1257
Munari P, Moreno A, De La Vega J, Alem D, Gondzio J, Morabito R (2019) The robust vehicle routing problem with time windows: compact formulation and branch-price-and-cut method. Transp Sci 53(4):1043–1066
Ng K, Lee C, Chan FT, Qin Y (2017) Robust aircraft sequencing and scheduling problem with arrival/departure delay using the min–max regret approach. Transp Res Part E Logist Transp Rev 106:115–136
Ng K, Lee C, Chan FT, Chen C-H, Qin Y (2020) A two-stage robust optimisation for terminal traffic flow problem. Appl Soft Comput 89:106048
Nogueira JP, Arroyo JEC, Villadiego HMM, Gonçalves LB (2014) Hybrid GRASP heuristics to solve an unrelated parallel machine scheduling problem with earliness and tardiness penalties. Electron Notes Theor Comput Sci 302:53–72
Ravetti MG, Mateus GR, Rocha PL, Pardalos PM (2007) A scheduling problem with unrelated parallel machines and sequence dependent setups. Int J Oper Res 2(4):380
Rodríguez SV, Albornoz VM, Plá LM (2009) A two-stage stochastic programming model for scheduling replacements in sow farms. Top 17(1):171–189
Sadati A, Tavakkoli-moghaddam R, Naderi B, Mohammadi M (2017) Solving a new multi-objective unrelated parallel machines scheduling problem by hybrid teaching-learning based optimization. Int J Eng 30(2):224–233
Salehi Mir MS, Rezaeian J (2016) A robust hybrid approach based on particle swarm optimization and genetic algorithm to minimize the total machine load on unrelated parallel machines. Appl Soft Comput 41:488–504
Salmasnia A, Khatami M, Kazemzadeh RB, Zegordi SH (2015) Bi-objective single machine scheduling problem with stochastic processing times. Top 23(1):275–297
Seo K-K, Chung BD (2014) Robust optimization for identical parallel machine scheduling with uncertain processing time. J Adv Mech Design Syst Manuf 8(2):1–11
Soyster AL (1973) Convex programming with set-inclusive constraints and applications to inexact linear programming. Oper Res 21(5):1154–1157
Sungur I, Ordonez F, Dessouky M (2008) A robust optimization approach for the capacitated vehicle routing problem with demand uncertainty. IIE Trans (Inst Ind Eng) 40(5):509–523
Tadayon B, Smith JC (2015) Algorithms and complexity analysis for robust single-machine scheduling problems. J Sched 18(6):575–592
Torabi S, Sahebjamnia N, Mansouri S, Bajestani MA (2013) A particle swarm optimization for a fuzzy multi-objective unrelated parallel machines scheduling problem. Appl Soft Comput 13(12):4750–4762
Xu X, Cui W, Lin J, Qian Y (2013) Robust makespan minimisation in identical parallel machine scheduling problem with interval data. Int J Prod Res 51(12):3532–3548
Ying K-C, Lee Z-J, Lin S-W (2012) Makespan minimization for scheduling unrelated parallel machines with setup times. J Intell Manuf 23(5):1795–1803
Zeidi JR, MohammadHosseini S (2015) Scheduling unrelated parallel machines with sequence-dependent setup times. Int J Adv Manuf Technol 81(9–12):1487–1496
Acknowledgements
The authors thank the anonymous reviewers for their valuable comments.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
This work was supported by the Sao Paulo Research Foundation (FAPESP) [grant numbers 15/14582-7, 16/15966-6, 19/23596-2 and 16/01860-1], the National Council for Scientific and Technological Development (CNPq) [grant number 313220/2020-4]; and Coordenação de Aperfeiçoamento de Pessoal de Nível Superior—Brasil (CAPES) [Finance code 001].
Rights and permissions
About this article
Cite this article
De La Vega, J., Moreno, A., Morabito, R. et al. A robust optimization approach for the unrelated parallel machine scheduling problem. TOP 31, 31–66 (2023). https://doi.org/10.1007/s11750-021-00621-1
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11750-021-00621-1
Keywords
- Production scheduling
- Unrelated parallel machines
- Sequence-dependent setups
- Due-date constraints
- Uncertain processing and setup times
- Robust optimization