Quantum Annealing for Staff Scheduling in Educational Environments

Resumo Técnico: Recozimento Quântico para Escalonamento de Pessoal em Ambientes Educacionais

Definição do Problema
Este estudo aborda um complexo problema de alocação de pessoal específico ao sistema público de escolas italianas, focando no escalonamento de colaboradores não docentes. O problema envolve a atribuição de uma força de trabalho heterogênea (funcionários em tempo integral e parcial, homens e mulheres) em múltiplos locais educacionais (creches, escolas primárias e secundárias) distribuídos por três municípios. O horizonte de planejamento cobre uma semana de trabalho padrão de cinco dias, com turnos de manhã e tarde.

O problema caracteriza-se por um conjunto denso de restrições operacionais e regulatórias:

• Cobertura: Cada turno ativo em cada local deve ser atendido por pelo menos um colaborador.
• Limites de Carga de Trabalho: Funcionários em tempo integral são limitados a 36 horas/semana, e funcionários em tempo parcial a 18 horas/semana.
• Regras de Pausa: Um intervalo obrigatório de 30 minutos é necessário se as horas diárias de trabalho excederem 7,2 horas.
• Restrições de Gênero: Pelo menos uma colaboradora deve ser atribuída a cada local de creche.
• Continuidade e Preferências: O pessoal pode ter restrições vinculativas (atribuição obrigatória a locais específicos) ou preferências suaves (atribuições de locais incentivadas, mas não obrigatórias).
• Objetivo: O objetivo é minimizar conflitos equilibrando três critérios: reduzir atribuições em múltiplos locais (para limitar deslocamentos e garantir continuidade), minimizar desvios das cargas de trabalho semanais contratuais e respeitar as preferências de locais do pessoal.

Metodologia
Os autores formulam o problema como um modelo de otimização combinatória, especificamente um Modelo Quadrático Constrained (CQM). A formulação matemática inclui:

• Variáveis de Decisão: Variáveis binárias para atribuições de turno diário ($x_{c,s,d,j}$), indicadores semanais de local ($y_{c,s}$) e indicadores de pausa ($b_{c,d}$).
• Função Objetivo: Uma soma ponderada de três componentes normalizados:
  1. Penalidade por trabalhar em múltiplos locais.
  2. Penalidade por desvio das cargas de trabalho semanais padrão.
  3. Penalidade por atribuições a locais não preferidos.
• Restrições: Restrições lineares impõem cobertura, limites de um único turno por dia, tetos de carga de trabalho, requisitos de gênero e consistência lógica entre variáveis diárias e semanais.

Para resolver este problema NP-difícil, os autores empregam Recozimento Quântico (QA) utilizando o solucionador LeapCQMHybrid da D-Wave. Esta abordagem híbrida combina técnicas heurísticas clássicas com exploração guiada por quântica (utilizando superposição e tunelamento) para navegar no espaço de soluções. Os experimentos foram conduzidos em um sistema D-Wave Advantage2 (4596 qubits) e comparados com o Otimizador exato Gurobi.

Principais Contribuições

1. Aplicação Inovadora: Este é o primeiro estudo a propor um modelo de otimização específico para colaboradores escolares na Itália, abordando as peculiaridades organizacionais, espaciais e regulatórias únicas deste contexto (por exemplo, requisitos de gênero para creches e gestão de múltiplos campi).
2. Estudo de Caso do Mundo Real: O modelo foi testado com dados reais do Istituto Comprensivo di Cerisano, envolvendo 20 colaboradores em 9 locais.
3. Análise de Escalabilidade: Os autores geraram instâncias sintéticas maiores (escalando até 40 colaboradores) para avaliar a robustez e a escalabilidade da abordagem inspirada em quântica além do estudo de caso específico.
4. Formulação CQM: O trabalho demonstra a aplicação prática da estrutura CQM da D-Wave para problemas de inteiro misto com restrições lineares em um ambiente não industrial, do setor público.

Resultados

• Instância do Mundo Real (20 colaboradores): O solucionador LeapCQMHybrid atingiu consistentemente a solução ótima (verificada pelo Gurobi) em cinco execuções independentes. O valor da função objetivo foi 0,070602, com tempos de execução médios de aproximadamente 15,16 segundos. Os resultados confirmaram a capacidade do modelo de produzir escalas equilibradas e viáveis que respeitam todas as restrições.
• Instâncias de Grande Escala:
  • Para 25 e 30 colaboradores, o solucionador encontrou consistentemente a solução ótima (taxa de sucesso de 100%).
  • Para 35 colaboradores, o solucionador encontrou soluções de alta qualidade, mas atingiu a solução ótima verdadeira em apenas 20% das execuções, indicando maior dificuldade.
  • Para 40 colaboradores, o solucionador falhou em produzir uma solução viável dentro do limite de tempo de 10 segundos, destacando os limites atuais de escalabilidade para instâncias muito grandes.

Significado e Alegações
O artigo afirma que métodos de otimização híbrida baseados em recozimento quântico são praticamente aplicáveis a problemas combinatórios complexos no escalonamento educacional. Os resultados fornecem evidências de que esses métodos podem produzir atribuições equilibradas em tempos de execução curtos para instâncias reais de tamanho moderado.

Os autores posicionam este trabalho como um passo para preencher a lacuna entre a pesquisa teórica de otimização quântica e o planejamento organizacional do mundo real. Eles enfatizam que, embora desafios significativos permaneçam para instâncias de grande escala, a abordagem proposta demonstra a versatilidade das técnicas de computação quântica além dos domínios industriais tradicionais. O estudo conclui que solucionadores híbridos inspirados em quântica oferecem uma alternativa competitiva para tarefas de alocação de recursos onde métodos exatos se tornam impraticáveis, embora reconheça modestamente que as limitações atuais de hardware restringem a solução de instâncias de escala muito grande sem avanços algorítmicos ou arquitetônicos adicionais.