🤖 AI

Quantum Annealing for Staff Scheduling in Educational Environments

This paper presents a quantum annealing-based optimization model that effectively solves complex staff scheduling challenges across multiple educational levels in a real-world Italian school system, demonstrating the practical viability of quantum computing for resource allocation.

Original authors: Alessia Ciacco, Francesca Guerriero, Eneko Osaba

Published 2026-05-20

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Alessia Ciacco, Francesca Guerriero, Eneko Osaba

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are the head of a massive, multi-building school district. You have a team of 20 support staff members (think of them as the "glue" that keeps the school running—cleaning, supervising, helping students). Your job is to figure out who goes where, and when, for the entire week.

This isn't just a simple puzzle. It's a giant, multi-layered jigsaw with some very strict rules:

The Rules: Some staff can only work at specific buildings. Some need to be there in the morning, others in the afternoon. If someone works too long without a break, they must get a 30-minute rest.
The Fairness: You can't send one person to three different schools in one week if they'd rather stay put. You also have to make sure every kindergarten has at least one female staff member.
The Goal: You want to minimize the chaos. You want everyone happy, every building covered, and no one working too many or too few hours.

Doing this by hand is a nightmare. Doing it with a standard computer is like trying to solve a Rubik's cube while blindfolded; it takes a long time, and for big schools, the computer might just give up.

The Quantum Solution: A "Magic Compass"

The authors of this paper tried a new tool: Quantum Annealing.

Think of a standard computer as a hiker trying to find the lowest point in a foggy mountain valley. The hiker has to walk step-by-step, checking every single path. If the valley is huge and full of hills, the hiker might get stuck in a small dip and think, "This is the bottom!" even though there's a deeper valley nearby.

Quantum Annealing is like giving that hiker a magic compass that can sense the shape of the entire mountain at once. Instead of walking step-by-step, it can "tunnel" through the hills to find the absolute lowest point (the perfect schedule) much faster. It uses the strange laws of quantum physics (like superposition and tunneling) to explore millions of possible schedules simultaneously.

What They Actually Did

The researchers took a real school in Italy (the Istituto Comprensivo di Cerisano) with 20 staff members and 9 different school sites (kindergartens, primary, and secondary schools).

They built a digital model: They wrote down all the rules (who can work where, how many hours, gender requirements) into a math equation.
They ran the test: They used a special quantum computer (from a company called D-Wave) to solve the puzzle.
The Result: The quantum computer found the perfect schedule in about 15 seconds. It matched the best possible solution a standard super-computer could find, but it did it incredibly fast.

Testing the Limits

To see if this magic compass works for bigger problems, they created "fake" but realistic scenarios with more staff (up to 40 people).

Small groups (25–30 staff): The quantum computer was a champion, finding the perfect schedule every time.
Medium groups (35 staff): It still found great schedules, but it didn't always find the absolute perfect one (it found a "very good" one 80% of the time).
Large groups (40 staff): The puzzle got too big and too complex. The computer hit a wall and couldn't find a valid schedule within the time limit.

The Bottom Line

This paper shows that quantum computing is ready to help solve real-world scheduling headaches for schools, at least for medium-sized teams. It proves that this high-tech "magic compass" can quickly organize people and places in a way that is fair, efficient, and follows all the strict rules.

However, the authors are careful to say: This works for the school context they tested. They don't claim it can solve every scheduling problem in the world yet. For very large, complex systems, the technology still needs to grow stronger. But for the specific problem of organizing school staff, it's a promising new tool.

Technical Summary: Quantum Annealing for Staff Scheduling in Educational Environments

Problem Definition
This study addresses a complex staff allocation problem specific to the Italian public school system, focusing on the scheduling of non-teaching school collaborators. The problem involves assigning a heterogeneous workforce (full-time and part-time staff, male and female) across multiple educational sites (kindergartens, primary, and secondary schools) distributed across three municipalities. The planning horizon covers a standard five-day workweek with morning and afternoon shifts.

The problem is characterized by a dense set of operational and regulatory constraints:

Coverage: Every active shift at every site must be staffed by at least one collaborator.
Workload Limits: Full-time staff are capped at 36 hours/week, and part-time staff at 18 hours/week.
Break Rules: A mandatory 30-minute break is required if daily working hours exceed 7.2 hours.
Gender Constraints: At least one female collaborator must be assigned to every kindergarten site.
Continuity and Preferences: Staff may have binding constraints (mandatory assignment to specific sites) or soft preferences (encouraged but not required site assignments).
Objective: The goal is to minimize conflicts by balancing three criteria: reducing multi-site assignments (to limit commuting and ensure continuity), minimizing deviations from contractual weekly workloads, and respecting staff site preferences.

Methodology
The authors formulate the problem as a combinatorial optimization model, specifically a Constrained Quadratic Model (CQM). The mathematical formulation includes:

Decision Variables: Binary variables for daily shift assignments ( $x_{c,s,d,j}$ ), weekly site indicators ( $y_{c,s}$ ), and break indicators ( $b_{c,d}$ ).
Objective Function: A weighted sum of three normalized components:
1. Penalty for working across multiple sites.
2. Penalty for deviation from standard weekly workloads.
3. Penalty for assignments to non-preferred sites.
Constraints: Linear constraints enforce coverage, single-shift-per-day limits, workload caps, gender requirements, and logical consistency between daily and weekly variables.

To solve this NP-hard problem, the authors employ Quantum Annealing (QA) using D-Wave's LeapCQMHybrid solver. This hybrid approach combines classical heuristic techniques with quantum-guided exploration (utilizing superposition and tunneling) to navigate the solution space. The experiments were conducted on a D-Wave Advantage2 system (4596 qubits) and compared against the exact Gurobi Optimizer.

Key Contributions

Novel Application: This is the first study to propose a specific optimization model for school collaborators in Italy, addressing the unique organizational, spatial, and regulatory peculiarities of this context (e.g., gender requirements for kindergartens and multi-campus management).
Real-World Case Study: The model was tested on real data from the Istituto Comprensivo di Cerisano, involving 20 collaborators across 9 sites.
Scalability Analysis: The authors generated larger synthetic instances (scaling up to 40 collaborators) to evaluate the robustness and scalability of the quantum-inspired approach beyond the specific case study.
CQM Formulation: The work demonstrates the practical application of D-Wave's CQM framework for mixed-integer problems with linear constraints in a non-industrial, public sector setting.

Results

Real-World Instance (20 collaborators): The LeapCQMHybrid solver consistently reached the optimal solution (verified by Gurobi) across five independent runs. The objective function value was 0.070602, with average execution times of approximately 15.16 seconds. The results confirmed the model's ability to produce balanced, feasible schedules that respect all constraints.
Large-Scale Instances:
- For 25 and 30 collaborators, the solver consistently found the optimal solution (100% success rate).
- For 35 collaborators, the solver found high-quality solutions but reached the true optimal solution in only 20% of runs, indicating increased difficulty.
- For 40 collaborators, the solver failed to produce a feasible solution within the 10-second time limit, highlighting current scalability limits for very large instances.

Significance and Claims
The paper claims that quantum annealing-based hybrid optimization methods are practically applicable for complex combinatorial problems in educational scheduling. The results provide evidence that these methods can produce balanced assignments in short runtimes for moderate-sized real-world instances.

The authors position this work as a step toward bridging the gap between theoretical quantum optimization research and real-world organizational planning. They emphasize that while significant challenges remain for large-scale instances, the proposed approach demonstrates the versatility of quantum computing techniques beyond traditional industrial domains. The study concludes that hybrid quantum-inspired solvers offer a competitive alternative for resource allocation tasks where exact methods become impractical, though it modestly acknowledges that current hardware limitations restrict the solution of very large-scale instances without further algorithmic or architectural advancements.

The Quantum Solution: A "Magic Compass"

What They Actually Did

Testing the Limits

The Bottom Line

Technical Summary: Quantum Annealing for Staff Scheduling in Educational Environments

More like this