It appears you don't have support to open PDFs in this web browser. To view this file, Open with your PDF reader
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.
You have requested "on-the-fly" machine translation of selected content from our databases. This functionality is provided solely for your convenience and is in no way intended to replace human translation. Show full disclaimer
Neither ProQuest nor its licensors make any representations or warranties with respect to the translations. The translations are automatically generated "AS IS" and "AS AVAILABLE" and are not retained in our systems. PROQUEST AND ITS LICENSORS SPECIFICALLY DISCLAIM ANY AND ALL EXPRESS OR IMPLIED WARRANTIES, INCLUDING WITHOUT LIMITATION, ANY WARRANTIES FOR AVAILABILITY, ACCURACY, TIMELINESS, COMPLETENESS, NON-INFRINGMENT, MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. Your use of the translations is subject to all use restrictions contained in your Electronic Products License Agreement and by using the translation functionality you agree to forgo any and all claims against ProQuest or its licensors for your use of the translation functionality and any output derived there from. Hide full disclaimer
Details
1 Department of Physics, Osaka University, Toyonaka, Osaka, Japan
2 Department of Physics and Astronomy, University of Tennessee, Knoxville, TN, USA
3 Quantum Computing Institute, Oak Ridge National Laboratory, Oak Ridge, Tennessee, USA