Abstract

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.

Details

Title
Application of Quantum Annealing to Nurse Scheduling Problem
Author
Ikeda, Kazuki 1 ; Nakamura, Yuma 2 ; Humble, Travis S 3 

 Department of Physics, Osaka University, Toyonaka, Osaka, Japan 
 Department of Physics and Astronomy, University of Tennessee, Knoxville, TN, USA 
 Quantum Computing Institute, Oak Ridge National Laboratory, Oak Ridge, Tennessee, USA 
Pages
1-10
Publication year
2019
Publication date
Sep 2019
Publisher
Nature Publishing Group
e-ISSN
20452322
Source type
Scholarly Journal
Language of publication
English
ProQuest document ID
2285700552
Copyright
© 2019. This work is published under http://creativecommons.org/licenses/by/4.0/ (the “License”). Notwithstanding the ProQuest Terms and Conditions, you may use this content in accordance with the terms of the License.