Random-Key Optimizer for Scheduling Problem with Sequence-Dependent Changeover Costs

The production scheduling problem with sequence-dependent setup costs on heterogeneous machines (MM-SDCO) is a challenging NP-hard problem requiring simultaneous task allocation and sequencing. This work investigates the Random-Key Optimizer (RKO) to solve the MM-SDCO, analyzing the evolution of decoding strategies. Initial evaluations of traditional metaheuristic decoders indicated that greedy insertion logics consistently provided the most effective mapping for cost minimization. Building upon this premise, we introduce a pure Global Cheapest Insertion (GCI) heuristic. While computationally efficient and highly effective, this strictly greedy approach occasionally yields infeasible schedules. To address this, the heuristic is integrated into the RKO framework as a novel Windowed GCI Decoder. This strategy uses random keys to dynamically filter the search space during the insertion phase, enabling a stochastic semi-greedy search. Experiments demonstrate that this integrated approach overcomes the limitations of purely constructive methods, outperforming GCI and literature benchmarks, achieving a 52% mean cost reduction.