Arc-Based Formulation and Grasp-Enhanced Iterated Greedy Algorithm for Identical Parallel Machine Scheduling with a Common Server

Abstract

The identical parallel machine scheduling problem with a single server and sequence-dependent setup times is a challenging optimization problem with important applications in manufacturing and service industries. In such environments, several machines depend on a common server to perform setup operations before production can begin, which creates strong interdependencies and demands more effective scheduling strategies. This characteristic highlights the practical relevance of the problem. The interaction between machine availability and server operations often becomes a critical bottleneck. This study introduces two complementary approaches. The first is an exact method based on a novel arc-based mixed-integer linear programming (ABF) model, which extends the modeling capability of existing formulations by capturing server-related constraints more effectively. The second is an approximation method built on an Iterated Greedy (IG) algorithm. The IG procedure is improved by two evaluation mechanisms: one model-based evaluation derived from the proposed ABF model, and another employing a greedy randomized adaptive search procedure (GRASP)-based strategy that integrates greedy selection, randomization, and reconstruction to enhance solution quality. Computational experiments are conducted on existing benchmark instances. The results show that the proposed ABF model performs well on small and medium-sized instances compared to existing exact methods, while the IG variants, particularly the proposed GRASP-based version, deliver strong performance against state-of-the-art metaheuristics developed for this problem. In addition, 21 new best-known solutions are reported, further demonstrating the effectiveness of the proposed approaches.