Carugno Costantino, Ferrari Dacrema Maurizio, Cremonesi Paolo
Politecnico di Milano, Piazza Leonardo da Vinci, 32, Milan, Italy.
ContentWise, Via Schiaffino, 11, Milan, Italy.
Sci Rep. 2022 Apr 21;12(1):6539. doi: 10.1038/s41598-022-10169-0.
Job Shop Scheduling is a combinatorial optimization problem of particular importance for production environments where the goal is to complete a production task in the shortest possible time given limitations in the resources available. Due to its computational complexity it quickly becomes intractable for problems of interesting size. The emerging technology of Quantum Annealing provides an alternative computational architecture that promises improved scalability and solution quality. However, several limitations as well as open research questions exist in this relatively new and rapidly developing technology. This paper studies the application of quantum annealing to solve the job shop scheduling problem, describing each step required from the problem formulation to the fine-tuning of the quantum annealer and compares the solution quality with various classical solvers. Particular attention is devoted to aspects that are often overlooked, such as the computational cost of representing the problem in the formulation required by the quantum annealer, the relative qubits requirements and how to mitigate chain breaks. Furthermore, the impact of advanced tools such as reverse annealing is presented and its effectiveness discussed. The results indicate several challenges emerging at various stages of the experimental pipeline which bring forward important research questions and directions of improvement.
作业车间调度是一个组合优化问题，对于生产环境尤为重要，其目标是在可用资源有限的情况下，尽可能短的时间内完成生产任务。由于其计算复杂性，对于规模稍大的问题很快就变得难以处理。新兴的量子退火技术提供了一种替代计算架构，有望提高可扩展性和解决方案质量。然而，在这个相对较新且快速发展的技术中存在一些限制以及尚未解决的研究问题。本文研究了量子退火在解决作业车间调度问题中的应用，描述了从问题表述到量子退火器微调所需的每个步骤，并将解决方案质量与各种经典求解器进行了比较。特别关注那些经常被忽视的方面，例如在量子退火器所需的表述中表示问题的计算成本、相对量子比特需求以及如何减轻链中断。此外，还介绍了反向退火等先进工具的影响并讨论了其有效性。结果表明，在实验流程的各个阶段出现了几个挑战，这些挑战提出了重要的研究问题和改进方向。
