通过约束编程实现不兼容作业族的并行批量调度

《IEEE Transactions on Semiconductor Manufacturing》：Parallel Batch Scheduling With Incompatible Job Families via Constraint Programming

并行批次调度中存在不同家族任务无法同批处理的不兼容问题，传统约束规划模型依赖商业求解器的特定函数。本文提出四类新型CP模型：基于自动机约束的通用模型，以及三种融合分配与调度决策的不同策略模型，均可在商业和开源求解器运行。实验表明新模型在多目标优化下展现出灵活性和竞争力。

　　

摘要：

本文研究了并行批量调度中的不兼容问题，即兼容的作业属于同一类，而来自不同类的作业不能在同一批次中一起处理。目前针对这一问题的最先进的约束编程（CP）模型依赖于特定的函数和全局约束，而这些仅在成熟的商业CP求解器中可用。本文通过提出四种新的CP模型扩展了相关研究，这些模型可以在商业和开源求解器中实现：一种基于自动机约束的新模型，以及三种结合了分配和调度决策的不同策略及全局约束的替代模型。在多种目标和多种求解器下的标准测试案例上进行的大量计算实验证明了所提模型的实现灵活性和竞争性能。

引言

在当前竞争激烈的制造业环境中，企业面临着降低生产成本和缩短周期时间的压力。实现这些目标的一个关键方法是采用批量生产方式[1]、[2]。在并行批量处理（p-batch）中，同一批次内的作业可以同时并行处理，从而缩短其周期时间[2]、[3]、[4]。