Conceitos
Como a geração automática realmente funciona
Sem marketing. O que o motor está a fazer, por que razão o problema é difícil e por que razão a qualidade das suas restrições importa mais do que a sofisticação do algoritmo.
O problema, enunciado de forma simples
Tem um conjunto de sessões de lecionação. Cada uma precisa de um horário, uma sala e um docente. Alguns recursos são partilhados, certas sessões não podem sobrepor-se, e uma longa lista de regras restringe as combinações admissíveis. Encontre uma atribuição que não viole nenhuma regra rígida e viole o menor número possível de preferências.
Trata-se de um problema de satisfação de restrições, e a elaboração de horários universitários é um caso difícil dele, amplamente estudado. O número de atribuições possíveis cresce de forma explosiva com o número de sessões: a pesquisa exaustiva não é apenas lenta, é astronomicamente inviável mesmo para uma faculdade de dimensão modesta.
Por isso, nenhum sistema prático pesquisa de forma exaustiva. Usam heurísticas — estratégias informadas para decidir o que colocar a seguir e o que fazer quando se fica bloqueado — para encontrar rapidamente uma boa solução, em vez de, eventualmente, uma solução comprovadamente ótima.
O que o motor faz efetivamente
- Ordenação. Decidir que sessões colocar primeiro. As sessões muito condicionadas — uma grande coorte que precisa de um laboratório específico com um único técnico qualificado — costumam ser colocadas cedo, porque colocá-las em último lugar implica desfazer tudo o resto.
- Colocação. Atribuir uma sessão a uma combinação admissível de horário, sala e docente que não viole nenhuma restrição rígida.
- Retrocesso. Desfazer decisões anteriores quando uma sessão fica sem qualquer colocação admissível. É aqui que se gasta a maior parte do tempo de execução.
- Pontuação. Avaliar em que medida a solução parcial atual satisfaz as preferências flexíveis, para que a pesquisa possa privilegiar as regiões melhores do espaço de soluções.
- Melhoria. Depois de existir uma solução admissível completa, efetuar alterações locais que melhoram a pontuação sem violar nada.
Por que razão as suas restrições importam mais do que o algoritmo
Esta é a parte que os fornecedores menos gostam de dizer. Perante um conjunto de restrições bem especificado, a maioria dos motores competentes produz resultados comparáveis. Perante um mal especificado, nenhum motor produz algo útil.
A falha mais comum não é algorítmica. É um conjunto de restrições em que as preferências foram declaradas invioláveis, pelo que não existe solução admissível e o motor indica, corretamente, um grande número de sessões impossíveis de colocar. A segunda mais comum são dados de entrada desatualizados ou errados — capacidades de salas que ninguém verifica desde uma remodelação, disponibilidades recolhidas há seis semanas.
Por isso, a pergunta útil a fazer a um fornecedor não é "que algoritmo utilizam", mas "como me ajudam a acertar nas restrições e na disponibilidade".
Como é o bom funcionamento na prática
Um sistema utilizável gera com rapidez suficiente para que a regeneração seja rotina e não uma tarefa noturna — o Wise Timetable regenera mesmo horários de grande dimensão em menos de um minuto, o que permite experimentar em vez de se comprometer com uma única execução.
Indica o que não conseguiu colocar, e porquê, em vez de violar silenciosamente uma regra para produzir algo com aspeto de acabado. Respeita as sessões que bloqueou, de modo que o trabalho automático e o manual possam ser combinados. E produz várias variantes para que possa compará-las em vez de aceitar a primeira.
Quer ver isto a funcionar?
Marque uma apresentação online de 45 minutos e percorreremos a solução com base no problema de planeamento de horários da sua própria instituição.