量子计算论文精讲《混合量子退火启发式方法解决任务调度问题》
欢迎大家扫码关注MindSpore Quantum Gitee社区
内容简介
任务调度问题（JSSP）一直引起研究者和业界的广泛关注。近年来，量子退火算法在许多NP-hard问题上展现出了优势与潜力。本文以一个经典的任务调度问题为例，探究量子退火算法是否能够、以及如何被用于解决JSSP问题，并在D-Wave 2000Q量子退火机上进行了实验。作者提出了一种方案，将调度问题分解成一系列小规模的子问题进行优化，以便能更好地与量子硬件相适应。
相关论文1
标题：Hybrid quantum annealing heuristic method for solving Job shop scheduling problem
作者：Krzysztof Kurowski, Jan Wȩglarz, Marek Subocz, Rafał Różycki & Grzegorz Waligóra
期刊：Computational Science--ICCS 2020: 20th International Conference
相关论文2
标题：Evaluating the job shop scheduling problem on a D-wave quantum annealer
作者：Costantino Carugno, Maurizio Ferrari Dacrema & Paolo Cremonesi
期刊: Scientific Reports 12, 6539 (2022)
01
问题建模
1.1 JSSP问题
考虑N个任务，每个任务包含Ln个操作，每个操作必须在某一特定机器上执行，共有R台机器。
图示如下
图1（来源：Computational Science--ICCS 2020，pp 502–515）
1.2 构建QUBO模型
将调度策略映射为一个01向量，
引入惩罚函数来施加约束：
1. 在每一个任务中，操作必须按照顺序进行。
2. 在任意时刻，一台机器上只能有一个任务在进行。
3. 每个任务必须开始一次，且仅能开始一次。
调度目标是使完成所有任务的时间周期尽量短，假设所有任务都在0时刻同时开始，结束时刻分别为t1,t2,...tN,则目标函数可表示为：
容易看出，任意非最优解（即使紧密排布），其对应的Ho也一定会大于任意非紧密排布的最优解。
最后，此JSSP对应的哈密顿量可表示为：
其中p1,p2,p3为待定参数，依据实验而确定。
1.3 变量剪枝
对时间进行粗粒化处理，如将[0,5)记为0，[5,9)记为1，以此类推。
去除过早或过晚的开始时间，即令x(i,t)=0，如果t小于i的所有前置操作的时间之和，或t大于时间上限T减去i及其所有后续操作的时间之和。
02
混合启发式方法
引入时间窗口（processing window），从而将JSSP分解成多个子问题。
图2（来源：Computational Science--ICCS 2020，pp 502–515）
在每一轮中，以随机顺序截取时间窗口（尽量覆盖整个时间周期），通过QUBO优化其中的任务排布；进行多轮迭代。
对于从左或右方伸出窗口的任务，为它在相应的机器上预留时间（通过变量剪枝完成）。
03
实验结果
3.1 经典任务调度问题ft06
优化过程的图示如下
图3（来源：GitHub - mareksubocz/QuantumJSP）
以下三张图，从上到下，分别展现了（1）经典算法（贪心搜索）求解JSSP问题的结果；（2）时间粗粒化后的初始解；以及（3）进行QUBO优化，再将每个工作的时间展开为原始长度后的最终结果。
图4（来源：Computational Science--ICCS 2020，pp 502–515）
在这个问题中，即使是简单的经典算法也可以达到和量子退火类似的效果。扩大时间窗口的宽度有望提升算法性能，解决更大规模的问题。
3.2 构造的Cyclic square problem
此问题的最优解如图5所示。在这篇文章中，不再采用时间窗口，而是直接对整个时间跨度进行求解。
图5、图6（来源：Scientific Reports 12, 6539 (2022)）
图6显示了将不同算法（经典、量子）用于Cyclic square problem时，取得的最优解所对应能量随问题规模的增长趋势。其中，经典的贪心和Tabu搜索因为能量过高而没有绘入。值得注意的是，在SA，QA和RA中都需要将一个CSP问题映射到QUBO问题，这一步骤非常耗时，对上述规模为26的例子，耗时约为8h。
04
总结
本文提出了一种混合启发式算法，作为用量子退火求解任务调度问题的概念验证，并在D-Wave 2000Q量子退火机上进行了实验，发现可以找到接近最优的解。但此方法需多轮迭代，效率偏低，且从约束满足问题到QUBO的映射可能耗时较长，对于实时的调度任务不太适合。
欢迎专家学者在公众号投稿分享优秀论文和创新成果，投稿录取者可获得精美礼品一份，投稿联系HiQ量子计算小助手：LLT66TT（备注“量子计算专题投稿”）
欢迎大家订阅“量子计算HiQ”，查看更多论文分享和学术活动信息
END
期待您成为新时代的开源贡献者，
加入MindSpore Quantum的开发者行列，共同携手推进量子计算新发展！
长按下方二维码加入MindSpore Quantum项目↓
MindSpore官网：https://www.mindspore.cn/mindquantum/docs/zh-CN/r0.9/index.html
欢迎关注MindSpore Quantum!