Practical Effectiveness of Quantum Annealing for Shift Scheduling Problem
Natsuki Hamada, Kazuhiro Saito, Hideyuki Kawashima · 2022 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW) · 2022
Quantum annealing (QA) is a novel computing approach for solving computationally demanding problems more rapidly than approaches using classical computers by exploiting parallelism in the variable state updates (spin updates). A number of previous studies have shown that QA performs well in benchmarking combinatorial optimization problems, but no works have evaluated QA in the shift scheduling problem. This paper formulates it for QA and evaluates the effectiveness of QA in comparison with other methods on a classical computer. We confirmed that QA is up to about 14 times faster than classical methods in obtaining high-quality solutions for several instances.