Instance Space Analysis and Algorithm Selection for a Parallel Batch Scheduling Problem

Abstract

This paper addresses the Oven Scheduling Problem (OSP), a parallel batch scheduling problem in semiconductor manufacturing, and identifies strengths and weaknesses of solution methods using the Instance Space Analysis (ISA) methodology. We propose a comprehensive feature set to effectively characterize OSP instances and generate more diverse instances compared to the literature. The performance of two state-of-the-art algorithms for the OSP – Simulated Annealing and Large Neighborhood Search – is analyzed using ISA, revealing distinct regions of superior or inferior performance for each, as well as areas of equal performance. Finally, we propose an automated algorithm selection approach that outperforms any single algorithm.