A NSGA-II Algorithm Hybridizing Local Simulated-Annealing Operators for a Bi-Criteria Robust Job-Shop Scheduling Problem Under Scenarios

This paper discusses a bi-criteria robust job-shop scheduling problem. Uncertain processing times are described by discrete scenario set. Two objectives are to minimize the mean makespan and to minimize the worst-case makespan among all scenarios, which reflect solution optimality and solution robustness, respectively. The NSGA-II algorithm framework is incorporated with local simulated annealing (SA) operators to solve the proposed problem. The Metropolis criterion is defined by considering two objectives in order to evaluate bi-criteria individuals. United-scenario neighborhood structure is used in local SA operators to adapt to the uncertainty described by scenarios. The developed hybrid algorithm was compared with four alternative algorithms to obtain Pareto solution sets for the proposed bi-criteria problem in an extensive experiment. The computational results show that the developed algorithm obviously outperformed other algorithms in all test instances.