BNMG: A Novel Deterministic Hybrid Algorithm with Global Makespan-Based Swap Mechanism for the Permutation Flow Shop Scheduling Problem

Abstract

The Permutation Flow Shop Planning Problem (PFSSP) is fundamental and frequently encountered in manufacturing systems and service operations. This problem is known to be NP-hard for three or more machines. Therefore, various heuristic and metaheuristic algorithms exist to approximate solutions to the problem. The solutions produced by deterministic heuristic algorithms are frequently used as initial solutions for population-based metaheuristic algorithms because they provide feasible schedules of relatively high quality within a short computational time. Heuristic algorithms are also divided into two groups: deterministic and random. In this study, we aim to develop a new deterministic method that improves both solution quality and computational efficiency. Rather than replacing existing deterministic heuristics, we propose a method that aims to enrich the design space of deterministic PFSSP heuristics by introducing two new problem-specific sequence improvement operators inspired by classical sorting principles. The proposed method is based on the integrated use of three complementary components: (i) a Bubble-Swap-based neighborhood structure that increases local search power, (ii) an NEH-style insertion mechanism that uses the strong insertion logic of the classical NEH algorithm, and (iii) a Merge-Global-Swap strategy that provides global optimization based on the completion time value of the entire sequence at each merge step. By integrating these three components, we develop a new deterministic hybrid algorithm called BNMG (Bubble–NEH–Merge–Global). We also call the locally search-enhanced version of our algorithm BNMG-II. Furthermore, we propose a new metric that accounts for computation time to evaluate the performance of the algorithms. When we comprehensively compare the BNMG and BNMG-II algorithms with the classical NEH, the recently developed vN-NEH and NEH-II, vN-NEH+ algorithms in Taillard test problems, we report that they exhibit superior performance according to the mean relative deviation metric (M1/ARPD) and the proposed new metric.