A Variable Iterated Local Search Algorithm for Energy-Efficient No-idle Flowshop Scheduling Problem

Abstract

No-idle permutation flowshop scheduling problem (NIPFSP) is a well-known NP-hard problem in which each machine must perform the jobs consecutively without any idle time. Even though various algorithms have been proposed for this problem energy efficiency has not been considered in these studies. In this paper we consider a bi-objective energy-efficient NIPFSP (EE-NIPFSP) with the objectives of makespan and total energy consumption. In the studied EE-NIPFSP we employ a speed scaling approach in which there are various speed levels for the jobs. We propose a novel mixed-integer linear programming model for the problem and we obtain Pareto-optimal solution sets for small instances using the augmented ε-constraint method. As the studied problem is NP-hard three metaheuristic algorithms are also proposed namely a multi-objective variable iterated local search (MOVILS) algorithm a multi-objective genetic algorithm (MOGA) and a MOGA with local search (MOGA-LS) for the problem. Then the performance of the proposed algorithms is assessed on both small and large instances in terms of various quality measures. The results show that the proposed algorithms are very effective for the EE-NIPFSP in terms of solution quality. Especially MOVILS and MOGA-LS algorithms are more efficient to solve large instances when compared to the MOGA. © 2020 Elsevier B.V. All rights reserved.