Robust job-shop scheduling under deterministic and stochastic unavailability constraints due to preventive and corrective maintenance

This paper presents a modeling and solution approach for a robust job-shop scheduling problem (JSP) under deterministic and stochastic machine unavailability caused, respectively, by planned preventive maintenance (PM) and unplanned corrective maintenance (CM) following random breakdowns. The goal is to optimize the sequence of jobs and run-based planned preventive maintenance tasks in a robust manner while considering the degradation of machines over time. The time to failure for each machine is assumed to follow a Weibull distribution. The robust objective function to be minimized is a weighted sum of the expected values of the makespan and the gross positive deviation between the actual and planned start times of the jobs, as proxies for quality robustness and solution robustness, respectively. Two metaheuristic algorithms that aim at providing a good balance between performance quality and solution robustness are developed. In both algorithms, the true makespan objective function (with both PM and CM) is approximated using three surrogate measures. Genetic algorithm (GA) is first used to optimize the surrogate functions, then the fittest solutions from the three oracles are simulated with random breakdown scenarios and the best among them is introduced as an elite member in the next GA iteration. The first algorithm terminates as soon as the solution obtained is worse than the best know solution or when the maximum number of iterations is reached, whereas the second algorithm applies a rule inspired by Simulated Annealing for termination. Numerical experimentation on benchmark instances from the literature showed excellent performance of the proposed algorithms in terms of average marginal improvement and runtime. These results show that the proposed framework can generate high-quality robust job shop schedules under deterministic and stochastic machine unavailability constraints. Moreover, the sensitivity analysis results recommended some key insights and directions for future research.

Automated summary

This paper presents a modeling and solution approach for a robust job-shop scheduling problem, considering machine availability and degradation over time, and develops two metaheuristic algorithms to optimize job sequences and preventive maintenance tasks. Experimental results show excellent performance of the proposed algorithms in terms of both quality and runtime.