Quantum Annealing for Staff Scheduling in Educational Environments

Resumen Técnico: Recocido Cuántico para la Programación de Personal en Entornos Educativos

Definición del Problema
Este estudio aborda un complejo problema de asignación de personal específico del sistema de escuelas públicas italianas, centrado en la programación de colaboradores escolares no docentes. El problema implica asignar una fuerza laboral heterogénea (personal a tiempo completo y a tiempo parcial, hombres y mujeres) en múltiples sitios educativos (guarderías, escuelas primarias y secundarias) distribuidos en tres municipios. El horizonte de planificación cubre una semana laboral estándar de cinco días con turnos de mañana y tarde.

El problema se caracteriza por un denso conjunto de restricciones operativas y regulatorias:

• Cobertura: Cada turno activo en cada sitio debe estar cubierto por al menos un colaborador.
• Límites de Carga de Trabajo: El personal a tiempo completo está limitado a 36 horas/semana, y el personal a tiempo parcial a 18 horas/semana.
• Reglas de Descanso: Se requiere un descanso obligatorio de 30 minutos si las horas de trabajo diarias superan las 7,2 horas.
• Restricciones de Género: Al menos una colaboradora debe ser asignada a cada sitio de guardería.
• Continuidad y Preferencias: El personal puede tener restricciones vinculantes (asignación obligatoria a sitios específicos) o preferencias suaves (asignaciones a sitios fomentadas pero no requeridas).
• Objetivo: El objetivo es minimizar conflictos equilibrando tres criterios: reducir las asignaciones a múltiples sitios (para limitar los desplazamientos y garantizar la continuidad), minimizar las desviaciones de las cargas de trabajo semanales contractuales y respetar las preferencias de ubicación del personal.

Metodología
Los autores formulan el problema como un modelo de optimización combinatoria, específicamente un Modelo Cuadrático Restringido (CQM). La formulación matemática incluye:

• Variables de Decisión: Variables binarias para asignaciones de turnos diarios ($x_{c,s,d,j}$), indicadores semanales de sitio ($y_{c,s}$) e indicadores de descanso ($b_{c,d}$).
• Función Objetivo: Una suma ponderada de tres componentes normalizados:
  1. Penalización por trabajar en múltiples sitios.
  2. Penalización por desviación de las cargas de trabajo semanales estándar.
  3. Penalización por asignaciones a sitios no preferidos.
• Restricciones: Las restricciones lineales hacen cumplir la cobertura, los límites de un solo turno por día, los topes de carga de trabajo, los requisitos de género y la consistencia lógica entre las variables diarias y semanales.

Para resolver este problema NP-duro, los autores emplean Recocido Cuántico (QA) utilizando el solver LeapCQMHybrid de D-Wave. Este enfoque híbrido combina técnicas heurísticas clásicas con exploración guiada por cuántica (utilizando superposición y efecto túnel) para navegar el espacio de soluciones. Los experimentos se realizaron en un sistema D-Wave Advantage2 (4596 qubits) y se compararon con el Optimizador exacto Gurobi.

Contribuciones Clave

1. Aplicación Novel: Este es el primer estudio que propone un modelo de optimización específico para colaboradores escolares en Italia, abordando las peculiaridades organizativas, espaciales y regulatorias únicas de este contexto (por ejemplo, requisitos de género para guarderías y gestión de múltiples campus).
2. Estudio de Caso Real: El modelo fue probado con datos reales del Istituto Comprensivo di Cerisano, involucrando a 20 colaboradores en 9 sitios.
3. Análisis de Escalabilidad: Los autores generaron instancias sintéticas más grandes (escalando hasta 40 colaboradores) para evaluar la robustez y escalabilidad del enfoque inspirado en la cuántica más allá del estudio de caso específico.
4. Formulación CQM: El trabajo demuestra la aplicación práctica del marco CQM de D-Wave para problemas de enteros mixtos con restricciones lineales en un entorno del sector público no industrial.

Resultados

• Instancia Real (20 colaboradores): El solver LeapCQMHybrid alcanzó consistentemente la solución óptima (verificada por Gurobi) en cinco ejecuciones independientes. El valor de la función objetivo fue 0,070602, con tiempos de ejecución promedio de aproximadamente 15,16 segundos. Los resultados confirmaron la capacidad del modelo para producir horarios equilibrados y factibles que respetan todas las restricciones.
• Instancias a Gran Escala:
  • Para 25 y 30 colaboradores, el solver encontró consistentemente la solución óptima (tasa de éxito del 100%).
  • Para 35 colaboradores, el solver encontró soluciones de alta calidad pero alcanzó la solución óptima real solo en el 20% de las ejecuciones, lo que indica una mayor dificultad.
  • Para 40 colaboradores, el solver no logró producir una solución factible dentro del límite de tiempo de 10 segundos, destacando los límites actuales de escalabilidad para instancias muy grandes.

Significado y Afirmaciones
El artículo afirma que los métodos de optimización híbrida basados en recocido cuántico son prácticamente aplicables a problemas combinatorios complejos en la programación educativa. Los resultados proporcionan evidencia de que estos métodos pueden producir asignaciones equilibradas en tiempos de ejecución cortos para instancias reales de tamaño moderado.

Los autores posicionan este trabajo como un paso hacia la reducción de la brecha entre la investigación teórica de optimización cuántica y la planificación organizativa real. Subrayan que, aunque persisten desafíos significativos para instancias a gran escala, el enfoque propuesto demuestra la versatilidad de las técnicas de computación cuántica más allá de los dominios industriales tradicionales. El estudio concluye que los solvers híbridos inspirados en la cuántica ofrecen una alternativa competitiva para tareas de asignación de recursos donde los métodos exactos se vuelven poco prácticos, aunque reconocen modestamente que las limitaciones actuales del hardware restringen la resolución de instancias de muy gran escala sin avances algorítmicos o arquitectónicos adicionales.