Maximizing the service level on the makespan in the stochastic flexible job-shop scheduling problem

Abstract

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.