Multi-car paint shop optimization with quantum annealing
Multi-car paint shop optimization with quantum annealing
复制标题
通过量子退火优化多车涂装车间
DOI：
--
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Thomas Bäck
中科院分区：
文献类型：
--
作者：
S. Yarkoni;A. Alekseyenko;Michael Streif;David Von Dollen;F. Neukart;Thomas Bäck
我们提出了一个一般化的二元涂装车间问题（BPSP）来解决汽车工业中的一个应用问题，即多车涂装车间问题（MCPS）。优化的目标是在制造过程中最小化油漆车间队列中汽车之间的颜色切换次数，这是一个已知的np困难问题。我们区分了喷漆车间问题的不同子类，并展示了如何将基本的MCPS问题表述为一个Ising模型。本研究中使用的问题实例是使用来自德国沃尔夫斯堡一家工厂的真实数据生成的。我们将D-Wave 2000Q和Advantage量子处理器的性能与D-Wave Systems提供的其他经典求解器和混合量子经典算法进行了比较。我们观察到量子处理器非常适合较小的问题，而混合算法适用于中等规模的问题。然而，我们发现这些算法在大尺寸限制下的性能很快接近简单贪婪算法的性能。
We present a generalization of the binary paint shop problem (BPSP) to tackle an automotive industry application, the multi-car paint shop (MCPS) problem. The objective of the optimization is to minimize the number of color switches between cars in a paint shop queue during manufacturing, a known NP-hard problem. We distinguish between different sub-classes of paint shop problems, and show how to formulate the basic MCPS problem as an Ising model. The problem instances used in this study are generated using real-world data from a factory in Wolfsburg, Germany. We compare the performance of the D-Wave 2000Q and Advantage quantum processors to other classical solvers and a hybrid quantum-classical algorithm offered by D-Wave Systems. We observe that the quantum processors are well-suited for smaller problems, and the hybrid algorithm for intermediate sizes. However, we find that the performance of these algorithms quickly approaches that of a simple greedy algorithm in the large size limit.
影响因子：
6.4
作者：
Preskill, John
通讯作者：
Preskill, John