Application of Quantum Annealing to Nurse Scheduling Problem
Application of Quantum Annealing to Nurse Scheduling Problem
复制标题
DOI：
10.1038/s41598-019-49172-3
复制
发表时间：
2019-09-06
影响因子：
4.6
通讯作者：
Humble, Travis S.
中科院分区：
文献类型：
--
作者：
Ikeda, Kazuki;Nakamura, Yuma;Humble, Travis S.
量子退火是解决组合优化问题的一种很有前途的启发式方法，并且量化现实问题的性能的努力为如何在实践中最好地使用这种方法提供了见解。我们研究了量子退火的经验性能，以解决护士调度问题（NSP）与硬约束使用D-Wave 2000 Q量子退火设备。NSP寻求一组护士的最佳分配下的时间表和人员的约束下的一套陪同轮班。在将NSP减少到一个新的伊辛型哈密顿量之后，我们评估了从D-Wave 2000 Q获得的解的质量，以满足约束要求以及解的多样性。对于这里探索的测试问题，我们的结果表明，量子退火恢复满意的解决方案NSP，并建议启发式方法是潜在的实际应用中实现。此外，我们观察到，解决方案的质量可以大大提高，通过使用反向退火，其中有可能通过使用退火过程的第二次细化返回的结果。我们比较了使用正向和反向退火方法的NSP的性能，并描述了这种方法如何在实践中使用。
Quantum annealing is a promising heuristic method to solve combinatorial optimization problems, and efforts to quantify performance on real-world problems provide insights into how this approach may be best used in practice. We investigate the empirical performance of quantum annealing to solve the Nurse Scheduling Problem (NSP) with hard constraints using the D-Wave 2000Q quantum annealing device. NSP seeks the optimal assignment for a set of nurses to shifts under an accompanying set of constraints on schedule and personnel. After reducing NSP to a novel Ising-type Hamiltonian, we evaluate the solution quality obtained from the D-Wave 2000Q against the constraint requirements as well as the diversity of solutions. For the test problems explored here, our results indicate that quantum annealing recovers satisfying solutions for NSP and suggests the heuristic method is potentially achievable for practical use. Moreover, we observe that solution quality can be greatly improved through the use of reverse annealing, in which it is possible to refine returned results by using the annealing process a second time. We compare the performance of NSP using both forward and reverse annealing methods and describe how this approach might be used in practice.