Solving Distributed Flexible Job Shop Scheduling Problems in the Wool Textile Industry with Quantum Annealing

技术摘要：利用量子退火解决羊毛纺织业中的分布式柔性车间调度问题

问题定义
本文研究了羊毛纺织业背景下的分布式柔性车间调度问题（DFJSP）。与传统的车间调度问题（JSSP）甚至标准的柔性车间调度问题（FJSP）不同，DFJSP 涉及地理位置分散的生产站点，其中单个生产订单（工件）可能需要在不同的工厂进行操作。这一特定用例源自一家真实的羊毛纺织制造商，引入了一种独特的复杂性：不仅生产订单是分布式的，单个生产步骤（操作）也可以是分布式的。因此，模型必须在考虑标准加工时间和机器约束的同时，还要考虑不同工厂之间机器间的运输时间。其目标是在满足优先顺序约束、确保操作仅开始一次以及防止机器重叠的前提下，最小化完工时间（makespan）。该问题被确定为 NP-hard 问题，且跨工厂运输时间的加入显著增加了组合复杂性。

方法论
作者将扩展后的 DFJSP 建模为一个二次无约束二值优化（QUBO）问题，并使用 D-Wave Advantage System 4.1 量子退火机（QPU）进行求解。

1. QUBO 建模： 该问题被映射到二值变量 $x_{i,o,m,t}$，代表工件 $i$ 的操作 $o$ 是否在机器 $m$ 上的时间 $t$ 开始。代价函数 $H(x)$ 被构建为针对约束条件（优先顺序、操作仅执行一次、无重叠）的惩罚函数与最小化完工时间目标函数的加权和。
2. 变量剪枝： 为了在 QPU 的物理限制内管理问题规模，作者采用了变量剪枝技术。这包括根据最小前序时间计算下界，以及根据最大完工时间限制计算上界，从而剔除对应于无效调度的二值变量。
3. 参数确定： 一个关键的方法论步骤是系统地计算用于惩罚项的拉格朗日参数（$\alpha, \beta, \gamma$）。作者并非依赖试错法，而是根据特定问题实例的最大可能完工时间（$t_{max}$）通过数学方式推导这些权重。这确保了任何有效解的能量都低于任何无效解的能量。
4. 嵌入与配置： 逻辑 QUBO 变量通过量子比特链（chains of qubits）嵌入到物理 QPU 拓扑结构中。作者研究了“链强度”（链中量子比特之间的耦合强度）对解质量的影响，通过分析系统能量与断链率之间的权衡来确定最优值。
5. 对比： 量子退火（QA）的结果与使用 D-Wave Ocean SDK 的模拟退火（SA）进行了基准测试。两种方法都在 50 到 250 个变量（测试的 QPU 可嵌入的最大规模）的问题实例上进行了测试，同时 SA 也测试了更大的实例（高达 400 个变量），以建立计算缩放的基准。

主要贡献
本文概述了三个主要贡献：

1. 结合量子退火的扩展 DFJSP 模型： 作者提出了首个将量子退火应用于扩展 DFJSP 的应用案例，在该模型中，生产订单及单个生产步骤均分布在不同工厂，并明确模拟了厂际运输时间。
2. 系统化的参数计算： 本文详细介绍了一种基于问题数学公式确定拉格朗日参数和 QPU 配置设置（特别是链强度）的方法，摆脱了启发式的试错法。
3. 经济与性能评估： 研究评估了使用 QA 处理特定行业分布式调度的潜在速度优势，并将解质量和计算时间与经典的 SA 进行了对比。

结果

• 解质量： 对于最多 150 个变量的问题实例，QA 产生了一致且有效的解（无约束违反），尽管模拟退火（SA）通常返回能量略低（更优）的解。随着问题规模增加到 200 和 250 个变量，QA 解开始出现约束违反（分别为 1 个和 2 个违反），导致能量值升高。这种退化归因于将较大的逻辑问题嵌入到物理 QPU 图形中的难度增加，导致了更长的链和更高的断链率。
• 完工时间： 对于大多数问题规模，QA 的解处于可能完工时间范围的下半部分，表明其调度方案是可行的。然而，对于 250 个变量的实例，完工时间处于范围的上半部分。
• 计算时间： SA 在处理小规模问题实例时表现出更快的计算速度。然而，SA 的 CPU 时间随问题规模呈指数级增长。相比之下，QA 的 QPU 访问时间以递减（对数级）的速度增长。虽然目前的硬件限制了 QA 只能嵌入最多 250 个变量的问题，但趋势表明，对于更大的实例（外推至 300 个变量以上），QA 可能会提供显著的计算速度优势。

意义与主张
本文声称，虽然目前的量子退火硬件在处理大规模问题嵌入以及在小规模实例中达到全局最优方面面临挑战，但它对于羊毛纺织业特定的 DFJSP 挑战具有巨大的潜力。作者认为，由于 QA 在计算时间相对于问题规模具有良好的缩放特性，它为大规模分布式调度提供了一个极具前景的替代方案。他们总结道，随着未来硬件的改进（更多的量子比特、更好的连通性和稳定性），QA 对于超过约 300 个变量的问题实例可能提供决定性的加速优势，使其成为复杂、真实世界多工厂生产规划的可行工具。该研究强调，成功应用 QA 很大程度上取决于精细的问题建模，特别是惩罚权重的数学推导以及嵌入参数的优化。