A critical-path based iterated local search for the green permutation flowshop problem. (July 2022) - Fernandez-Viagas, Victor; Prata, Bruno de Athayde; Framinan, Jose M.
Highlights: We address the flow shop scheduling problem to minimize makespan and total cost. We present several theorems for the problem. We develop several critical-path based local search methods. We propose Critical-Path based Iterated Local Search. We compare the proposal with the most promising metaheuristics in the literature. Abstract: The permutation flowshop scheduling problem is a widely studied combinatorial optimization problem with several real-world applications. In this paper we address a green variant of the problem with controllable processing times and two objective functions: one related to the service level of the factory (makespan) and another one related to the total cost or the total energy/carbon consumption. For this problem we propose a novel Critical-Path based Iterated Local Search. This metaheuristic incorporates several theoretical results to accelerate the search of solutions in the intensification phase. The proposed algorithm has been compared on an extensive benchmark with the most promising algorithms in the literature. The computational results show the excellent performance of the proposal.