Hybrid evolutionary algorithm for the permutation flow shop scheduling problem with shifts constraints

Abstract

A Flow Shop is a production system in which a series of jobs must follow a one-directional flow to be processed in several workstations. This article introduces the Permutation Flow Shop Scheduling Problem with Shifts Constraints (PFSSPSC), a variant of the Permutation Flow Shop Scheduling Problem (PFSSP) where the objective is to minimize the completion time of all jobs, while imposing shift constraints. The paper proposes a hybrid algorithm, composed of a Genetic Algorithm and a Variable Neighborhood Search (VNS), to solve the PFSSPSC. Results show that this algorithm provides better solutions in terms of quality and execution time compared to three other heuristic algorithms.