PaperlayerView exact revision on arXiv

Source-linked AI summary

Application of Quantum Annealing to Nurse Scheduling Problem

Kazuki Ikeda, Yuma Nakamura, Travis S. Humble

arXiv:1904.12139v2quant-ph

TL;DR

The paper examines whether quantum annealing can find nurse schedules satisfying hard constraints, a problem involving constrained assignments of nurses to shifts. It encodes NSP as an Ising-type Hamiltonian and evaluates the D-Wave 2000Q; success probability declines as schedule and roster size increase, while reverse annealing improves success nonuniformly.

  • Problem

    The paper evaluates quantum annealing for NSP, a nurse-roster problem requiring assignments that satisfy scheduling constraints.

    Source: §I · p. 2, §II · p. 3

  • Method

    The authors formulate NSP as an Ising spin Hamiltonian and solve it using the D-Wave 2000Q quantum annealer.

    Source: §V · p. 15

  • Results

    With fixed sample size and annealing duration, constraint-matching success probability declines as schedule size D and roster size N increase; reverse annealing improves success, but not uniformly.

    Source: §V · p. 15

  • Takeaways & Limitations

    The results demonstrate that the D-Wave 2000Q can be used to seek schedules satisfying NSP constraints, with reverse annealing improving success in some cases.

    Source: §V · p. 15

    The study is limited to the schedule shown in Fig. 5, and different schedule parameters may influence results.

    Source: §V · p. 16

Abstract

from arXiv · show

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 sufficient 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 a returned results by using the annealing process a second time. We compare the performance NSP using both forward and reverse annealing methods and describe how these approach might be used in practice.

I. INTRODUCTION

The paper empirically evaluates quantum annealing for nurse scheduling, a constrained rostering problem, using the D-Wave 2000Q. It frames the study as a test of the method’s performance, not proof of quantum advantage.

I. INTRODUCTION

  • NSP schedules nurses to shifts while respecting availability and personnel constraints, such as days off, minimum availability, and minimum shift assignments.Source: §I · p. 2
  • Quantum annealing is treated as a heuristic because practical runs may not recover the true minimum, leaving computational advantage an open question.Source: §I · p. 2
  • The study evaluates quantum annealing on the nurse scheduling problem (NSP), which requires assignments that satisfy multiple hard constraints.The authors assess solution efficiency and accuracy empirically.Source: §I · pp. 2–3
  • The authors reduce NSP to QUBO and embed it on the D-Wave 2000Q to obtain candidate schedules, while leaving quantum advantage unassessed.The introduction also notes limits in existing hardware capacity and control.Source: §I · pp. 2–3

II. NURSE SCHEDULING PROBLEM

The nurse scheduling problem is to create a rotating hospital roster while respecting constraints on nurse availability and effort. This section describes shift coverage and nurse working conditions as key constraints.

II. NURSE SCHEDULING PROBLEM

  • NSP creates a rotating hospital roster subject to constraints on nurses’ availability and level of effort.Source: §II · p. 3
  • Shift constraints specify how many nurses must cover each shift, while nurse constraints address working conditions such as rest between shifts and days off.Source: §II · pp. 3–4
  • Roster goals may also include allocating the minimum workforce needed for jobs and distributing work evenly among nurses.Source: §II · p. 4
  • The example formulation also considers limits on breaks, staffing per shift slot, and intervals between duty days.Source: §II · p. 4

A. Quantum Annealing with the D-Wave 2000Q

The D-Wave 2000Q anneals a time-dependent Hamiltonian whose final state encodes an optimization solution. The section describes forward and reverse annealing as approaches for generating and refining NSP solutions.

A. Quantum Annealing with the D-Wave 2000Q

B. Ising Model Formulation of NSP

The formulation converts nurse and shift assignments into a QUBO objective and then an equivalent Ising model. Penalty terms encode hard constraints and nurse preferences.

B. Ising Model Formulation of NSP

  • The formulation represents each nurse’s assignment to each working day with a binary variable and combines shift and nurse constraints into a QUBO objective.Source: B. Ising Model Formulation of NSP · p. 6
  • The hard shift penalty discourages a nurse from working two consecutive days, while the hard nurse penalty penalizes staffing above or below required workforce.Source: B. Ising Model Formulation of NSP · pp. 6–7
  • A soft nurse penalty accounts for each nurse’s desired workdays and day preferences, with the preference function decomposed into nurse- and day-specific factors.Source: B. Ising Model Formulation of NSP · p. 7
  • The combined objective reaches its minimum when all constraints are satisfied; the QUBO expression is transformed into an equivalent Ising spin model by changing binary variables qi to bipolar spins si = 2qi − 1.Source: B. Ising Model Formulation of NSP · pp. 7–8

IV. RESULTS

The D-Wave 2000Q results illustrate that the Ising model distinguishes satisfying schedules from schedules that violate constraints. The study evaluates forward and reverse annealing across nurse-scheduling instances.

IV. RESULTS

  • The authors used randomized embedding to run the NSP Ising model on the D-Wave 2000Q, first with forward and then reverse annealing.The embedding algorithm was based on work by Cai, Macready and Roy [24].Source: §IV · p. 8
  • The experiments used 200 µs per sample and 1000 samples per instance, testing N = 3 and 4 nurses and D = 5–14 days.The study fixed γ = 0.3, λ = 1.3, and penalty a = 7/2 for its soft nurse constraints.Source: §IV · p. 8
  • For N = 3, D = 4, forward annealing produced a satisfying ground-state schedule and a higher-energy schedule violating the nurse-assignment constraint.The ground state can be degenerate, allowing multiple satisfying schedules.Source: §IV · p. 8

A. Forward Annealing

Forward annealing sometimes found schedules satisfying all constraints, but the observed frequency declined on larger instances. Its solutions remained a nonzero Hamming distance from the ground state on average.

A. Forward Annealing

  • The authors report the frequency of solutions satisfying all constraints for N = 3 and 4 across schedule days, and plot mean Hamming distance from all computed solutions against schedule length.Source: A. Forward Annealing · pp. 9–10
  • The mean Hamming distance of forward-annealing solutions was below ND but remained greater than zero across the tested schedules.A distance of zero indicates exact agreement with the observed ground-state solution.Source: A. Forward Annealing · pp. 9–10
  • Satisfying-schedule frequency fell below the sampling level for larger instances; none were observed for N = 3, D = 13 or N = 4, D = 10–14.Some ground states were obtained for N = 3, D = 11, 12, and 14, and N = 4, D = 9.Source: A. Forward Annealing · p. 9, Figure 2 · p. 10

B. Reverse Annealing

The study applies reverse annealing to forward-annealing schedules and to low-energy states. Reverse annealing reduced Hamming-distance statistics overall, but its effect on finding satisfying schedules depended on the initial-state distribution.

B. Reverse Annealing

  • The reverse-annealing schedule used a 10 µs hold after reversing to s = 0.6 at 2 µs, then annealed forward to 14 µs.The authors report the heuristic worked for s ∈ [0.6, 0.8] and hold times of 10, 50, or 100 µs.Source: B. Reverse Annealing · p. 11
  • With randomly selected forward solutions as inputs, reverse annealing did not always improve satisfying-solution accuracy; some instances improved while others worsened.For N = 4, D = 11–14, the reported probabilities were exactly zero; N = 3, D = 13 and N = 4, D = 10 were successfully improved.Source: B. Reverse Annealing · p. 12
  • Accuracy gains depended on the forward-solution distribution because reverse annealing selected its initial inputs randomly.The authors relate improvement to having many forward solutions close to ground states available for selection.Source: B. Reverse Annealing · p. 12
  • Reverse annealing reduced the mean and standard deviation of Hamming distance overall, with the standard deviation approaching zero.The authors interpret this as refinement and grouping of the returned solutions.Source: B. Reverse Annealing · p. 12, Figure 7 · p. 13, Figure 8 · p. 13
  • Using each forward distribution’s lowest-energy solution as input, reverse annealing had zero average accuracy at N = 3, D = 13 and nearly 100% at N = 3, D = 14.At N = 4, D = 10, it found some ground states even though the initial input was not a ground state.Source: B. Reverse Annealing · p. 14
  • Even a satisfying initial state was not guaranteed to be returned unchanged, as reverse annealing could become trapped in local minima depending on schedule parameters.The study tested a particular schedule; different schedule parameters may influence results.Source: B. Reverse Annealing · p. 14

V. DISCUSSION AND CONCLUSION

The paper formulates the Nurse Scheduling Problem as an Ising model for quantum annealing and finds that constraint-satisfaction probability declines as roster and schedule sizes increase. Reverse annealing improves success in some cases, but the study leaves practical scope and parameter limits unresolved.

V. DISCUSSION AND CONCLUSION

  • The NSP constraint-satisfaction problem is cast into QUBO, translated directly to an Ising model, and tested with multiple annealing techniques on the D-Wave 2000Q.The authors describe the formulation as an Ising spin Hamiltonian solvable by commercially available quantum annealing hardware.Source: §V · p. 15
  • With fixed sample size and annealing duration T, constraint-satisfaction probability decays as schedule size D and roster size N increase; reverse-annealing gains are nonuniform.The authors report this as the overall pattern across the tested instances and methods.Source: §V · p. 15
  • The results are an encouraging sign that quantum annealing can solve a complementary set of practical problems.The paper does not assess performance relative to conventional solver methods.Source: §V · p. 16
  • Current quantum annealers lack capacity to explore realistic N and D; decomposition into smaller optimization problems is proposed as a possible route.The authors note that qbsolv, a tabu-search package, found satisfying NSP solutions at (N, D) = (4, 160) with the same parameters.Source: §V · p. 16
  • Reverse annealing can help obtain ground-state solutions, but the necessary improvement parameters remain unclear and only the Fig. 5 schedule was studied.The authors call for further empirical investigation of parameter dependence.Source: §V · p. 16
  • The authors present this work as a first step toward extending the NSP method to different scheduling problems.They describe broader scheduling applications as a possible extension.Source: §V · p. 16

APPENDIX: THREE-SHIFT SYSTEM AND ADDITIONAL CONSTRAINTS

The appendix extends the scheduling Hamiltonian to three shifts and adds prioritized day-off requests as soft constraints. In a three-shift example, one priority setting satisfies all listed requests, while another prioritizes higher-priority constraints over some requests.

Loading 1904.12139v2…