为芯片制造中的烤箱调度问题设计快速计算的理论下界，提升求解效率与质量评估能力。
Theoretical Lower Bounds for the Oven Scheduling Problem
- 针对烤箱调度问题构建专用理论下界，计算高效且贴合实际约束。
- 在大规模实例上验证下界有效性，支撑精确算法与模拟退火等启发式方法性能评估。
- 适用于半导体生产调度优化场景，尤其适合需快速评估解质量的研究者与工程师。
烤箱调度问题（Oven Scheduling Problem, OSP）是半导体行业中一种典型的NP-hard并行批处理调度问题。其目标是在满足烤箱可用性、作业释放时间、批次间准备时间及容量限制等约束条件下，最小化总烤箱运行时间、作业延迟和设置成本。高效调度的关键在于将兼容作业合并成批次同时处理。本文提出可快速计算的问题特异性理论下界，全面评估其质量，并研究其在现有求解方法中的集成效果。具体而言，考察了这些下界在精确算法与基于模拟退火的元启发式局部搜索中的贡献。此外，这些下界使得对大规模实例的解质量评估成为可能，而传统精确方法常难以提供紧致下界。
原文摘要 · Abstract (English)
The Oven Scheduling Problem (OSP) is an NP-hard real-world parallel batch scheduling problem arising in the semiconductor industry. The objective of the problem is to schedule a set of jobs on ovens while minimizing several factors, namely total oven runtime, job tardiness, and setup costs. At the same time, it must adhere to various constraints such as oven eligibility and availability, job release dates, setup times between batches, and oven capacity limitations. The key to obtaining efficient schedules is to process compatible jobs simultaneously in batches. In this paper, we develop theoretical, problem-specific lower bounds for the OSP that can be computed very quickly. We thoroughly examine these lower bounds, evaluating their quality and exploring their integration into existing solution methods. Specifically, we investigate their contribution to exact methods and a metaheuristic local search approach using simulated annealing. Moreover, these problem-specific lower bounds enable us to assess the solution quality for large instances for which exact methods often fail to provide tight lower bounds.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。