An NSGA-II-Based Memetic Algorithm for an Energy-Efficient Unrelated Parallel Machine Scheduling Problem with Machine-Sequence Dependent Setup Times and Learning Effect

Abstract

In this study, an energy-efficient unrelated parallel machine scheduling problem is discussed. The speed scaling mechanism has been taken into account as an energy-efficient strategy. Unrelated parallel machine scheduling with speed scaling is generalized by considering machine-sequence dependent setup times and learning effect features. A multiobjective mixed-integer linear programming (MILP) model has been proposed for the problem. Due to the NP-hard nature of the problem, a multiobjective evolutionary algorithm, the NSGA-II-based memetic algorithm, is proposed. An encoding scheme, decoding algorithm, and local search algorithms are proposed for the problem. Speed tuning heuristic and job-machine switch heuristic algorithms are proposed as local search algorithms. A restarting strategy has been applied to ensure the diversification of the algorithm. The classical NSGA-II algorithm and the proposed memetic algorithm were compared over the generated test problems. As a result, the proposed memetic algorithm is more successful according to performance metrics.