An Enhanced Adaptive Large Neighborhood Search for Unrelated Parallel Machine Scheduling With Sequence Dependent Setup Times

Abstract

The unrelated parallel machine scheduling problem with sequence dependent setup times (UPMSP-SDST) addressed in this study refers to allocating jobs among a given number of machines and determining their processing sequence on each machine, to minimize the makespan (i.e., the maximum completion time). To deal with large-scale UPMSP-SDST with higher efficiency, this study presents an enhanced adaptive large neighborhood search (EALNS) algorithm with various destroy and repair operators and an efficiency-enhancement mechanism. The efficiency-enhancement mechanism is mainly composed of a simplified calculation method and a hierarchical comparison mechanism, which are applied to improve the implementation process of the greedy-based operators. The simplified calculation method obtains a new makespan by an incremental or decremental transformation, to avoid reluctant calculations. The hierarchical mechanism refines the comparison of different removal or insertion strategies of the operators, thereby arresting high-quality solutions with more metrics. The proposed algorithm is tested on 1640 instances, and numerical results demonstrate the superior performance of the EALNS over the existing methods, especially for large-scale problems. Notably, 834 instances’ best-known solutions are updated from this study. In addition, deep analysis of the impact of the distribution of setup time on the performance of the algorithm is provided, which further verifies the potential wide applicability of the proposed EALNS.

Keywords

• Adaptive large neighborhood search
• combinatorial optimization problems
• sequence-dependent setup time
• unrelated parallel machine scheduling