Robustness measures and robust scheduling for multi-objective stochastic flexible job shop scheduling problems

摘要

Flexible job shop scheduling in uncertain environments plays an important part in real-world manufacturing systems. With the aim of capturing the uncertain and multi-objective nature of flexible job shop scheduling, a mathematical model for the multi-objective stochastic flexible job shop scheduling problem (MOSFJSSP) is constructed, where three objectives of make-span, maximal machine workload, and robustness to uncertainties are considered simultaneously under a variety of practical constraints. Two new scenario-based robustness measures are defined based on statistical tools. To solve MOSFJSSP appropriately, a modified multi-objective evolutionary algorithm based on decomposition (m-MOEA/D) is developed for robust scheduling. The novelty of our approach is that it adopts a new subproblem update method which exploits the global information, allows the elitists kept in an archive to participate in the child generation, employs a subproblem selection and suspension strategy to focus more computational efforts on promising subproblems, and incorporates problem-specific genetic operators for variation. Extensive experimental results on 18 problem instances, including 8 total flexible and 10 partial flexible instances, show that the two new robustness measures are more effective than the existing scenario-based measures, in improving the schedule robustness to uncertainties and maintaining a small variance of disrupted objective values. Compared to the state-of-the-art multi-objective optimization evolutionary algorithms (MOEAs), our proposed m-MOEA/D-based robust scheduling approach achieves a much better convergence performance. Different trade-offs among the three objectives are also analyzed.