Search Trajectory Networks Applied to a Real-World Parallel Batch Scheduling Problem

Abstract

We investigate solution methods for the Oven Scheduling Problem (OSP), a parallel batch scheduling optimization problem in semiconductor manufacturing, using Search Trajectory Networks (STNs). STNs are a recently introduced tool to analyze and compare the behavior of metaheuristic algorithms concerning their exploration ability w.r.t. single problem instances. We consider two state-of-the-art algorithms for the OSP, a Simulated Annealing (SA) and a Large Neighborhood Search (LNS), and instances from the literature. The STNs enable us to draw the following conclusions: (i) The two algorithms’ trajectories overlap especially at the beginning of the trajectories, as revealed by a search space partitioning based on Hierarchical Agglomerative Clustering; (ii) The fitness landscape of many instances is multi-modal, with several high-quality solutions scattered in the search space; (iii) SA trajectories are longer, but the number of locations visited by SA and LNS is similar.