Path bridging: A novel local search methodology for optimizing scheduling in highly constrained continuous galvanizing line operations

This study addresses the scheduling optimization of a Continuous Galvanizing Line (CGL) within a steel factory. By conceptualizing coil sequences as paths through nodes in a directed weighted graph , our objective is to identify a minimum-cost Hamiltonian path . The problem is characterized by its asymmetry and constraints, and we analyze it using highly constrained benchmark instances where the current algorithms in use struggle to provide feasible solutions . This research explores the applicability of Local Search (LS) methods to the CGL scheduling problem. We introduce a novel and efficient LS algorithm , termed Path Bridging (PB), specifically designed to address constraints and asymmetry. It uniquely separates the overall optimization into two distinct phases: feasibility optimization and cost optimization. In a Lin-Kernighan heuristic fashion, the PB algorithm employs a series of 3-opt moves strategically designed to avoid infeasibilities. Key features of the PB algorithm include the deliberate design of base 3-opt moves, tabu-list backtracking , and comprehensive checks for chain consolidation. These enhancements render the PB algorithm highly effective in constrained environments. The additional computational effort required by the PB proves to be advantageous: empirical evaluations on challenging benchmark instances demonstrate that the PB outperforms the algorithms in use. We report new best costs in 75% of the tested instances and an average 88% reduction in computation time in comparable scenarios. As part of a rigorous stress test , we reduced the benchmark computation time from 120 s to 1 s, confirming that the PB algorithm consistently identifies feasible solutions across all the test instances.