O Problema de Agendamento

      A maneira como gerenciamos o tempo é um aspecto muito importante de nossa sociedade. Transporte público, escolas, universidades, aeroportos, portos, empresas de logística, entre outras instituições, precisam regularmente de uma forma de organizar o seu tempo.  O Problema de Agendamento de horários, chamado de timetabling problem em inglês, define formalmente esse aspecto de organização. É comum que o Problema de Agendamento seja descrito no contexto de uma escola ou uma universidade, onde é então chamado school timetabling problem, em que se procura uma distribuição de aulas em uma grade de horários de forma que nenhum professor ou aluno tenha que participar de duas aulas ao mesmo tempo. Soluções apresentadas para o Problema de Agendamento de horários em uma escola podem ser facilmente adaptadas para serem usadas em outros contextos.

Ilustração de uma tabela com os horários aqui

 

      O Problema de Agendamento é um problema de otimização combinatória. Nesse tipo de problema procura-se achar uma atribuição de valores a um conjunto de variáveis que segue alguns critérios, chamados de restrições fortes e restrições fracas. As restrições fortes definem a viabilidade da solução encontrada e as restrições fracas definem a qualidade. Restrições fracas podem ser quebradas, porém, para que uma resposta seja viável todas as restrições fortes devem ser cumpridas.


Exemplos de Restrições para o School Timetabling Problem

Fortes

Fracas

Duas aulas simultâneas não podem ser ocorrer na mesma sala.

Os alunos não deveriam ter aula durante o último período do dia.

Um professor não pode ser alocado para duas aulas simultâneas.

Os alunos não deveriam ter apenas uma aula durante o dia.

Um aluno não pode participar de duas aulas simultâneas.

Os alunos não deveriam ter mais do que duas aulas consecutivas durante o dia.

 

      O Problema de Agendamento pertence à classe dos problemas NP-Completos (EVEN; ITAI; SHAMIR, 1976), ou seja, não se conhece nenhum método eficiente para se encontrar uma solução ótima gastando uma quantidade de tempo razoável à medida que o número de variáveis do problema aumenta.

Ilustração de uma árvore com as ramificações de todas as possíveis soluções. Considerar todos os ordenamentos da tabela anterior

      Quando se considera apenas as restrições fortes, o Problema de Agendamento pode ser representado pelo Problema da Coloração de Vértices de um grafo (BUDIONO; WONG, 2012). A coloração de um grafo é obtida selecionando uma cor para cada nodo de um grafo de forma que nenhum de seus vizinhos compartilhe essa cor. A coloração de grafos serve como um modelo geral para resolução de conflitos.

Ilustração de um grafo aqui com os nodos coloridos.

 Computadores NISQ

      Os computadores quânticos atuais são descritos como computadores NISQ (noise intermediate-scale quantum) (PRESKILL, 2018), que em tradução livre significa computadores de escala intermediária com ruído. Eles possuem de dezenas a centenas de qubits (bits quânticos) imperfeitos e com conectividade de circuito limitada. Essas limitações impedem a implementação de alguns algoritmos quânticos notáveis, como o algoritmo de fatoração de Shor. Entretanto espera-se que o regime atual ainda seja suficiente para rodar algumas classes de algoritmos e obter vantagem quântica.
     A classe dos Algoritmos Quânticos Variacionais (VQA - Variational Quantum Algorithms) (CEREZO et al., 2020) vem chamando muita atenção da comunidade científica pela sua capacidade de ser implementada nos computadores quânticos atuais e pelo seu potencial de resolver problemas reais. Os VQAs são algoritmos híbridos quântico-clássicos que usam métodos clássicos de otimização para limitar a profundidade dos seus circuitos quânticos e assim reduzir o seu custo.
      Dois exemplos de VQAs são o Quantum Approximate Optimization Algorithm (QAOA)  (FARHI; GOLDSTONE; GUTMANN, 2014) e o Variational Quantum Eigensolver (VQE)  (PERUZZO et al., 2014).

Solução Quântica para o Problema de Agendamento

      Pelo problema do Agendamento ser reconhecidamente difícil para a computação clássica, existe muito a se ganhar explorando soluções quânticas. Um método proposto (PIRES, 2021) usa o QAOA em uma Otimização em Dois Estágios para resolver o Problema de Agendamento. A Otimização em Dois Estágios tenta minimizar as restrições fracas apenas após uma solução viável, i.e. uma solução que cumpre todas as restrições fortes, ser encontrada. Em seu primeiro estágio, o método reduz o Problema do Agendamento para o Problema da Coloração Mínima de um Grafo e usa o circuito quântico do QAOA para solucionar as restrições fortes e depois usa o próprio processo de otimização clássico do algoritmo para as restrições fracas.

      A vantagem esperada da solução quântica vem da complexidade do algoritmo. A quantidade de recursos necessária pelo QAOA nesse contexto cresce em uma velocidade menor do que a dos algoritmos clássicos conhecidos, tornando possível dessa forma solucionar instâncias consideradas muito grandes para os computadores clássicos.


REFERÊNCIAS

EVEN, S.; ITAI, A.; SHAMIR, A. On the Complexity of Timetable and Multicommodity Flow Problems. SIAM Journal on Computing, v. 5, n. 4, p. 691-703, 1976. ISSN 0097-5397. DOI: 10.1137/0205048.

BUDIONO, Tri A.; WONG, Kok Wai. A pure graph coloring constructive heuristic in timetabling. In: 2012 International Conference on Computer Information Science (ICCIS). [S.l.: s.n.], 2012. P. 307-312. DOI: 10.1109/ICCISci.2012.6297259.

PRESKILL, John. Quantum Computing in the NISQ era and beyond. Quantum, Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften, v. 2, p. 79, Aug. 2018. ISSN 2521-327X. DOI: 10.22331/q-2018-08-06-79. Available from: https://doi.org/10.22331/q-2018-08-06-79.

CEREZO, M. et al. Variational Quantum Algorithms. [S.l.: s.n.], 2020. arXiv: 2012.09265 [quant-ph].

FARHI, Edward; GOLDSTONE, Jeffrey; GUTMANN, Sam. A Quantum Approximate Optimization Algorithm. [S.l.: s.n.], 2014. arXiv: 1411.4028 [quant-ph].

PERUZZO, Alberto et al. A variational eigenvalue solver on a photonic quantum processor. Nature Communications, Springer Science and Business Media LLC, v. 5, n. 1, July 2014. ISSN 2041-1723. DOI: 10.1038/ncomms5213. Available from: http://dx.doi.org/10.1038/ncomms5213.

O. M. Pires, R. de Santiago and J. Marchi, "Two Stage Quantum Optimization for the School Timetabling Problem," 2021 IEEE Congress on Evolutionary Computation (CEC), 2021, pp. 2347-2353, doi: 10.1109/CEC45853.2021.9504701.