Minimizing the expected maximum lateness for a job shop subject to stochastic machine breakdowns
研究随机机器故障下带顺序相关准备时间的作业车间调度问题，提出结合禁忌搜索和蒙特卡洛模拟的模拟启发式方法，通过320个实例验证，相比最优解和调度规则平均改进7%-14%。
Abstract 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.