Greedy Randomized Adaptive Search and Benders Decomposition Algorithms To Solve the Distributed No-Idle Permutation Flowshop Scheduling Problem

Abstract

In today's competitive manufacturing landscape, large enterprises manage multiple production sites, leading to complex scheduling challenges. This study investigates the Distributed No-Idle Permutation Flowshop Scheduling Problem (DNIPFSP), where the objective is to minimize makespan across multiple identical factories while ensuring continuous machine utilization without idle time. To address this problem, we propose both approximation and exact methods. For the approximation method, we introduce a novel Greedy Randomized Adaptive Search Procedure (GRASP). On the exact optimization side, we develop three mathematical formulations: a sequence-based model, an improved position-based model, and a restricted version of the improved position-based model, where the upper bounds of decision variables are determined through a two-stage process. First, an initial GRASP solution is obtained, and based on this solution, an additional model is solved to compute the upper bounds of decision variables. The Benders decomposition algorithm is then applied to efficiently solve problem instances. To further improve computational efficiency, we introduce a hybrid Benders decomposition algorithm, incorporating heuristic-derived cuts alongside standard Benders cuts. Additionally, symmetry-breaking constraints are integrated to strengthen the formulations. Extensive benchmark experiments demonstrate the superiority of the proposed methods over existing approaches. The hybrid Benders decomposition algorithm with symmetry-breaking constraints significantly outperforms the best-known models in the literature, optimally solving 419 out of 420 small-sized instances with an average optimality gap of 0.011%. Additionally, the GRASP achieves the lowest average relative percentage deviation (RPD) for large-sized instances, demonstrating its effectiveness in large-scale scheduling optimization.