AST Um modelo para automaÃÃo de horÃrios escolares

AUTOR(ES)

Jalila Rios dos Santos

DATA DE PUBLICAÇÃO

2008

RESUMO

The work here presented is about a model for automation of school timetable. It is tailored to deal with most of the restrictions found in the Brazilian schools. It also studies the relation between the constraints of the problem and its theoretical complexity. The school timetable problem is NP-complete even in the simplest cases, where the constraints are kept to a minimum absolutely necessary. Here are constructed and presented proofs of the above relation between the restrictions and the theoretical problem. The model uses integer programming to find a feasible initial solution. Once this is found, some heuristics to improve it are applied. Theses heuristics perform local interchanges on a graph called hybrid graph. The initial feasible solution also can be found by heuristics based on the hybrid graph. These heuristics are essentially tabu search meta-heuristics. The hybrid graph which is easily constructed from the input of the problem, permits the definition of moves (changes) which when applied to a viable solution maintains a lot of the required constraints. The discovery of the hybrid graph made a big difference in our work: no other data structure in the literature (as far as we know) has its flexibility to carry out a simple interchange of the times assigned to a pair of meetings to its ultimate consequences. The changes are quick and thousands of viable solutions are easily generated and compared. The idea of the hybrid graph has applications to a great variety of problems that involve timetable and conflict constraints

ASSUNTO(S)

automaÃÃo de horÃrios escolares grafo hÃbrido e busca tabu integer programming factor for the complexity matematica da computacao hybrid graph and tabu search programaÃÃo inteira fator para complexidade automated school timetabling

Documentos Relacionados

• Um mÃtodo para seleÃÃo de testes de regressÃo para automaÃÃo
• A automaÃÃo da educaÃÃo: o telensino e a precarizaÃÃo do trabalho docente.
• Automação de horários escolares utilizando algoritmo genético
• Desenvolvimento de um modelo de dado conceitual para um sistema de gerÃncia de pavimentos aeroportuÃrios.
• Proposta de um conjunto de critÃrios para avaliaÃÃo da maturidade em gestÃo da inovaÃÃo