Metaheuristics for Energy-Efficient No-Wait Flowshops: A Trade-off Between Makespan and Total Energy Consumption

Abstract

No-wait flowshop scheduling problem (NWFSP) is a well-known strongly NP-hard problem where in-process waiting is not allowed between any two consecutive machines in such a way that once a job is started subsequent processing must be carried out on all machines until completion. In this paper we propose an energy-efficient NWFSP in order to investigate the trade-off between makespan and total energy consumption. The energy-efficient NWFSP aims to seek to obtain Pareto solution sets to minimize the makespan and the total energy consumption conflicting with each other. Unlike the classical NWFSP there are different speed levels for each job on machines and the processing times of jobs can differ according to the assigned speed levels. Therefore we modify the formulation of NWFSP by introducing a speed scaling strategy in order to approximate Pareto solution sets i.e. non-dominated solution sets. In this paper we propose a mixed-integer linear programming model (MILP) an energy-efficient variable block insertion heuristic (EE-VBIH) an energy-efficient iterated greedy algorithm (IG) and an energy-efficient & IG-ALL) to solve the energy-efficient NWFSP. Extensive computational analyses on Taillard's benchmark suite show that the proposed algorithms are very effective for approximating Pareto solution sets.