Minimizing the makespan for the two-machine flow shop scheduling problem with random breakdown
研究了第一台机器随机故障下的双机流水车间调度问题，提出混合整数线性模型和启发式算法，在满足服务水平约束下最小化完工时间。
Abstract This paper studies a two-machine flow shop scheduling problem with availability constraints due to a breakdown on the first machine. The starting time of the breakdown is considered stochastic and follows a known probability distribution. A service-level constraint is introduced to model the guarantee with which the obtained schedule takes into account the stochastic nature of the breakdown’s starting time. The objective is to find a solution that minimizes the makespan while satisfying the desired service level. The studied problem is strongly NP-hard. We develop two mixed integer linear models that linearize the non-linear model. Using interval modeling of the breakdown, we propose lower bounds and a valid inequality that are used to strengthen both models. When the lower bounds and the valid inequality are applied, the performance of both models is greatly improved by reducing the gap and reaching optimality for more instances. We also introduced two heuristics that exploit the proposed interval modeling. The computational results indicate that both models are able to reach optimality for the 10-job instances. Moreover, the comparisons results between both models with the two heuristics showed their effectiveness.