Quantum Annealing for Solving a Nurse-physician Scheduling Problem in Covid-19 Clinics
Kunal K. Das, Sahil Zaman, Arindam Sadhu, Asmita Banerjee, Faisal Shah Khan · viXra · 2020
Quantum annealing (QA) is a metaheuristic methodologythat has recently been used to analyze the performance of first generation adiabatic quantum processors, like the oneavailable from D-wave Systems, in solving combinatorial optimization problems. In this paper, we formulate QA representation of problems essential to mitigating the effects of the COVID-19 pandemic, namely, the Nurse Scheduling Problem (NSP), the Physician Scheduling Problem (PSP), and the Nurse-Physician Scheduling Problem (NPSP). The proposed objective functions for each problem are scripted to the Ising model and then transformed into thequadratic unconstrained binary optimization (QUBO)format. An optimal solutionis soughtfor a set of constraints, including thenumber ofnurses or physicians per shift andthe maximum number of shifts for each nurse or physician.After reducingtheproposed NSP, PSP, and NPSP QUBOs to a novel Ising type Hamiltonian, we obtain solutions from a classical (simulated) annealer,and then from the D-wave 2000Q forward and reverse annealer. Results from the reverse quantum annealer show a dramatic improvement in solution quality as compared to those from the classical annealer. We observe that the reverse annealing method gives us the most satisfactory output from among three heuristic processes used, for each scheduling problem.