An Exact Solution Algorithm to Solve the No-Wait Flow Shop Scheduling Problem with Earliness and Tardiness Objectives

The no-wait flow shop scheduling problem (NWFSP) is an extension of the traditional flow shop configuration, where jobs follow a fixed sequence of machines. The NWFSP extends the flow shop problem by incorporating a constraint that does not allow jobs to wait between subsequent machines. Recent studies on the NWFSP have primarily focused on traditional objectives, such as makespan, total flow time, and total completion time. However, there are limited studies addressing the simultaneous use of earliness and tardiness objectives. Classified as NP-hard, the NWFSP poses significant computational challenges when seeking optimal solutions for large problem instances. To overcome this, heuristic and metaheuristic algorithms, including simulated annealing, tabu search, and particle swarm algorithm, are commonly used to find near-optimal solutions. Nevertheless, exact solution methods for this problem remain scarce in existing literature. To fill this gap, this paper introduces a novel mixed-integer programming (MIP) model for the NWFSP and presents a branch-and-cut (BC) algorithm built upon this new model, with the objective of minimizing earliness and tardiness. The BC algorithm is combined with a heuristic approach to provide strong upper bounds. It systematically explores the problem space and improves mathematical formulations using cutting plane techniques. The algorithm’s performance is tested using a comprehensive set of benchmark problem instances, with results compared to a MIP model from the literature. Computational experiments demonstrate that the proposed BC algorithm is effective both in terms of solution quality and computational efficiency.