Risk measure of job shop scheduling with random machine breakdowns

Job shop scheduling problem (JSP) with random machine breakdowns (RMBs) is studied in this paper for the purpose of finding an efficient measure for assessing and minimizing the schedule risk to optimize the stability of the schedule makespan. A novel and comprehensive measure for schedule risk evaluation is proposed based on the internal relation among the total slack time, the probability and downtime of RMBs, and the makespan delay. Since it does not come with an exact solution, an analytical approximation method is developed for practical calculation. Based on this method, the genetic algorithm is used to minimize the schedule risk. Experiments of twenty-one benchmark JSPs with RMBs are provided. Results show that while both the analytical approximation method and the Monte Carlo simulation perform similarly in the optimization of the schedule risk, the former computes much faster than the latter. Thorough comparison is also made with the state-of-the-art surrogate robustness measures, which confirms the superiority of the proposed measure for schedule risk evaluation.