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

What is it about?

Understanding how metaheuristics explore the enormous combinatorial spaces of parallel batch scheduling problems is essential for designing robust solvers. This study focuses on the Oven Scheduling Problem (OSP), a key bottleneck in semiconductor fabrication, and evaluates two state-of-the-art heuristics—Simulated Annealing (SA) and Large Neighborhood Search (LNS)—through the lens of Search Trajectory Networks (STNs). STNs map every accepted solution encountered during a run to a node and connect successive solutions with directed edges, creating a data-driven representation of the search path that can be analysed with network science tools. The reconstructed trajectories reveal three principal insights. First, hierarchical agglomerative clustering applied to the networks shows that SA and LNS initially traverse almost identical regions of the search space, suggesting a shared basin of attraction shaped by the common construction heuristic used for seeding. Second, most benchmark instances exhibit a markedly multimodal fitness landscape: instead of a single dominant basin, multiple pockets of high-quality schedules are dispersed throughout the space. This explains why both algorithms occasionally escape local optima yet still terminate with different elite solutions. Third, although SA generates considerably longer trajectories—because its temperature schedule continues to accept worse moves deep into the run—the absolute number of distinct solution locations explored by SA and LNS remains comparable; SA simply revisits promising zones more often. These observations highlight the complementary strengths of the two heuristics and demonstrate the explanatory power of STNs for comparative algorithm analysis, paving the way for hybrid or adaptive strategies tailored to specific landscape features in real-world settings.

Featured Image

Why is it important?

It is important because it helps in understanding not just whether an algorithm performs well, but how and why it behaves in certain ways when solving complex optimization problems like the Oven Scheduling Problem (OSP).