Multi-neighborhood simulated annealing for the oven scheduling problem
针对半导体制造中的NP难烤箱调度问题，提出一种结合四个邻域和构造启发式的模拟退火算法，在更短时间内找到更优或相当的解，并验证了其在不同批调度问题上的有效性。
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.