Application of Quantum Annealing to Nurse Scheduling Problem

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 s...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Kazuki Ikeda, Yuma Nakamura, Travis S. Humble
Formato:	article
Lenguaje:	EN
Publicado:	Nature Portfolio 2019
Materias:	Medicine R Science Q
Acceso en línea:	https://doaj.org/article/cdcb2da3e09143ebb027db669d67d597
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:cdcb2da3e09143ebb027db669d67d597
record_format	dspace
spelling	oai:doaj.org-article:cdcb2da3e09143ebb027db669d67d5972021-12-02T15:08:31ZApplication of Quantum Annealing to Nurse Scheduling Problem10.1038/s41598-019-49172-32045-2322https://doaj.org/article/cdcb2da3e09143ebb027db669d67d5972019-09-01T00:00:00Zhttps://doi.org/10.1038/s41598-019-49172-3https://doaj.org/toc/2045-2322Abstract 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.Kazuki IkedaYuma NakamuraTravis S. HumbleNature PortfolioarticleMedicineRScienceQENScientific Reports, Vol 9, Iss 1, Pp 1-10 (2019)
institution	DOAJ
collection	DOAJ
language	EN
topic	Medicine R Science Q
spellingShingle	Medicine R Science Q Kazuki Ikeda Yuma Nakamura Travis S. Humble Application of Quantum Annealing to Nurse Scheduling Problem
description	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.
format	article
author	Kazuki Ikeda Yuma Nakamura Travis S. Humble
author_facet	Kazuki Ikeda Yuma Nakamura Travis S. Humble
author_sort	Kazuki Ikeda
title	Application of Quantum Annealing to Nurse Scheduling Problem
title_short	Application of Quantum Annealing to Nurse Scheduling Problem
title_full	Application of Quantum Annealing to Nurse Scheduling Problem
title_fullStr	Application of Quantum Annealing to Nurse Scheduling Problem
title_full_unstemmed	Application of Quantum Annealing to Nurse Scheduling Problem
title_sort	application of quantum annealing to nurse scheduling problem
publisher	Nature Portfolio
publishDate	2019
url	https://doaj.org/article/cdcb2da3e09143ebb027db669d67d597
work_keys_str_mv	AT kazukiikeda applicationofquantumannealingtonurseschedulingproblem AT yumanakamura applicationofquantumannealingtonurseschedulingproblem AT travisshumble applicationofquantumannealingtonurseschedulingproblem
_version_	1718388088738152448

Application of Quantum Annealing to Nurse Scheduling Problem

Ejemplares similares