arXiv:2511.16045cs.AI2025-11

提出新约束模型,高效解决有最小批量要求的串行批次调度问题。

An Aligned Constraint Programming Model For Serial Batch Scheduling With Minimum Batch Size

  • 基于关键对齐参数直接建模作业序列,避免虚拟批次集带来的维度灾难。
  • 在100个以内作业的小中型实例上求解更快,500个作业的大规模实例上优化结果提升25%。
  • 适合半导体制造等需最小批量的工业场景,也适用于批量调度研究者。

在串行批次调度中,相同家族的作业被分组处理以避免不同家族连续作业时重复设置。尽管该问题在调度领域广泛应用,但考虑最小批量限制的约束编程(CP)模型仅有三个,且依赖预设的虚拟批次集合,易引发维度爆炸并增加复杂性。本文提出一种新型CP模型,无需虚拟批次集,而是通过关键对齐参数直接对同一家族作业在机器上的序列进行推理,实现更紧凑的公式化表达。进一步通过定制搜索策略和强化约束传播器推断水平来挖掘问题结构。在近五千个实例上的大量计算实验表明,所提模型在最多含100个作业的小中型实例上表现优越,并在含500个作业、10个家族、10台机器的大规模实例上,相比现有方法(包括混合整数规划、禁忌搜索元启发式及CP方法)能获得最高达25%的改进。

原文摘要 · Abstract (English)

In serial batch (s-batch) scheduling, jobs from similar families are grouped into batches and processed sequentially to avoid repetitive setups that are required when processing consecutive jobs of different families. Despite its large success in scheduling, only three Constraint Programming (CP) models have been proposed for this problem considering minimum batch sizes, which is a common requirement in many practical settings, including the ion implantation area in semiconductor manufacturing. These existing CP models rely on a predefined virtual set of possible batches that suffers from the curse of dimensionality and adds complexity to the problem. This paper proposes a novel CP model that does not rely on this virtual set. Instead, it uses key alignment parameters that allow it to reason directly on the sequences of same-family jobs scheduled on the machines, resulting in a more compact formulation. This new model is further improved by exploiting the problem's structure with tailored search phases and strengthened inference levels of the constraint propagators. The extensive computational experiments on nearly five thousand instances compare the proposed models against existing methods in the literature, including mixed-integer programming formulations, tabu search meta-heuristics, and CP approaches. The results demonstrate the superiority of the proposed models on small-to-medium instances with up to 100 jobs, and their ability to find solutions up to 25\% better than the ones produces by existing methods on large-scale instances with up to 500 jobs, 10 families, and 10 machines.

批量调度约束编程半导体制造优化算法

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。