Maximizing the service level on the makespan in the stochastic flexible job-shop scheduling problem
研究了随机加工时间下柔性作业车间调度问题，通过最大化完工时间在给定截止日期前的概率（服务水平）来找到对扰动不敏感的调度方案，并提出了基于禁忌搜索和蒙特卡洛采样的求解方法。
This paper considers the flexible job-shop scheduling problem with stochastic processing times. To find a sequence insensitive to shop floor disturbances, the available probabilistic information related to the variability of processing times is taken into account by maximizing the makespan service level for a given deadline. This corresponds to the probability of the makespan to be smaller than a given threshold. After showing why this criterion makes sense compared to minimizing the average makespan, a solution approach relying on a tabu search and a Monte Carlo sampling-based approximation is presented. Then, new instances are generated by extending the deterministic benchmark instances. Extensive computational experiments are conducted to evaluate the relevance of the makespan service level and the performance of the proposed solution method. The drawbacks of a number of reference scenarios, including worst-case and best-case scenarios, in addressing effectively the problem under study are presented. A numerical analysis is also performed to compare the scope of the proposed criterion against the minimization of the expected makespan. The accuracy of the proposed solutions induced by the hyper-parameters of the Monte Carlo approximation is explicitly analyzed.