Scholarlink

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.

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

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

  • 会议论文

  • 发表日期：

    2025年

查看全文
  • Francesca Da Ros,
  • Luca Di Gaspero,
  • Marie-Louise Lackner,
  • Nysret Musliu,
  • Michael Soprano

摘要

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.