TY - JOUR
T1 - Minimizing the expected maximum lateness for a job shop subject to stochastic machine breakdowns
AU - Zambrano-Rey, Gabriel Mauricio
AU - González-Neira, Eliana María
AU - Forero-Ortiz, Gabriel Fernando
AU - Ocampo-Monsalve, María José
AU - Rivera-Torres, Andrea
N1 - Publisher Copyright:
© 2023, The Author(s).
PY - 2023
Y1 - 2023
N2 - This paper addresses a stochastic job shop scheduling problem with sequence-dependent setup times, aiming to minimize the expected maximum lateness. The stochastic nature is modeled by considering uncertain times between failures (TBF) and uncertain times to repair (TTR). To tackle this problem, a simheuristic approach is proposed, which combines a tabu search (TS) algorithm with Monte Carlo simulation. A total of 320 instances were used to conduct multiple experiments. Instances were generated with two distributions to study the behavior of stochastic TTR and TBF under log-normal and exponential distributions. Firstly, the performance of the simheuristic was evaluated for small instances by comparing it with the simulation of optimal solutions obtained with a mixed-integer linear programming (MILP) model. The simheuristic approach demonstrated an average improvement of around 7% compared to the simulation of MILP model solutions. Secondly, the simheuristic performance was evaluated for medium and large-size instances by comparing it with the simulation of the solutions obtained by the earliest due date (EDD) and process time plus work in the next queue plus negative slack (PT + WINQ + SL) dispatching rules. The results showed an average improvement of around 11% compared to EDD and 14% compared to PT + WINQ + SL. Furthermore, the results highlight that even when the two distributions have the same expected value and coefficient of variation, they can yield different expected maximum lateness values. This emphasizes the importance of precise distribution fitting when solving real cases to achieve effective scheduling performance.
AB - This paper addresses a stochastic job shop scheduling problem with sequence-dependent setup times, aiming to minimize the expected maximum lateness. The stochastic nature is modeled by considering uncertain times between failures (TBF) and uncertain times to repair (TTR). To tackle this problem, a simheuristic approach is proposed, which combines a tabu search (TS) algorithm with Monte Carlo simulation. A total of 320 instances were used to conduct multiple experiments. Instances were generated with two distributions to study the behavior of stochastic TTR and TBF under log-normal and exponential distributions. Firstly, the performance of the simheuristic was evaluated for small instances by comparing it with the simulation of optimal solutions obtained with a mixed-integer linear programming (MILP) model. The simheuristic approach demonstrated an average improvement of around 7% compared to the simulation of MILP model solutions. Secondly, the simheuristic performance was evaluated for medium and large-size instances by comparing it with the simulation of the solutions obtained by the earliest due date (EDD) and process time plus work in the next queue plus negative slack (PT + WINQ + SL) dispatching rules. The results showed an average improvement of around 11% compared to EDD and 14% compared to PT + WINQ + SL. Furthermore, the results highlight that even when the two distributions have the same expected value and coefficient of variation, they can yield different expected maximum lateness values. This emphasizes the importance of precise distribution fitting when solving real cases to achieve effective scheduling performance.
KW - Machine breakdowns
KW - Maximum lateness
KW - Simheuristics
KW - Stochastic job shop scheduling
KW - Tabu search
UR - http://www.scopus.com/inward/record.url?scp=85173098863&partnerID=8YFLogxK
U2 - 10.1007/s10479-023-05592-z
DO - 10.1007/s10479-023-05592-z
M3 - Article
AN - SCOPUS:85173098863
SN - 0254-5330
JO - Annals of Operations Research
JF - Annals of Operations Research
ER -