Multi-neighborhood simulated annealing for the oven scheduling problem

Abstract

The Oven Scheduling Problem (OSP) is an NP-hard real-world parallel batch scheduling problem that arises in the semiconductor manufacturing sector. It aims to group compatible jobs in batches and to find an optimal schedule in order to reduce oven runtime, setup costs, and job tardiness. This work proposes a Simulated Annealing (SA) algorithm for the OSP, encompassing a unique combination of four neighborhoods and a construction heuristic as initial solution. An extensive experimental evaluation is performed, benchmarking the proposed SA algorithm against state-of-the-art methods. The results show that this approach consistently finds new upper bounds for large instances, while for smaller instances, it achieves solutions of comparable quality to state-of-the-art methods. These results are delivered in significantly less time than the literature approaches require. Additionally, the SA is extended to tackle a related batch scheduling problem from the literature. Even in this case, the algorithm confirms its effectiveness and robustness across different problem formulations by improving results for many instances.