Brasil
| doctoralThesis
AST Um modelo para automação de horários escolares
| dc.contributor | Luiz Soares Lins, Sóstenes | |
| dc.creator | Rios dos Santos, Jalila | |
| dc.date | 2014-06-12T18:29:06Z | |
| dc.date | 2014-06-12T18:29:06Z | |
| dc.date | 2008-01-31 | |
| dc.identifier | Rios dos Santos, Jalila; Luiz Soares Lins, Sóstenes. AST Um modelo para automação de horários escolares. 2008. Tese (Doutorado). Programa de Pós-Graduação em Matemática Computacional, Universidade Federal de Pernambuco, Recife, 2008. | |
| dc.identifier | https://repositorio.ufpe.br/handle/123456789/7116 | |
| dc.description | O trabalho aqui apresentado consiste de um modelo para automação de horários escolares, cujo problema está baseado no estudo de casos brasileiros, e também consiste de uma análise da relação entre as restrições do problema e sua complexidade. O problema automação de horários escolares é um problema NP-completo, mesmo nos casos mais simples, onde as restrições mantidas são o mínimo absolutamente necessário. Aqui são construídas ou apresentadas provas desta relação entre as restrições e o problema. O modelo usa programação inteira para encontrar uma solução viável inicial. Uma vez encontrada, é aplicada uma heurística desenvolvida para trabalhar com trocas locais via um grafo chamado grafo híbrido. A solução viável inicial também pode ser encontrada por uma heurística que usa trocas via o grafo híbrido. Estas heurísticas são essencialmente meta-heurísticas busca tabu. O grafo híbrido, que é facilmente construído dos dados do problema, permitiu a definição de movimentos (mudanças) que aplicados a uma solução preservam o atendimento a um grande número de restrições. A descoberta do grafo híbrido fez uma grande diferença em nosso trabalho: nenhuma outra estrutura de dados na literatura (tanto quanto sabemos) tem a flexibilidade de acompanhar uma troca de horários atribuídos a um par de encontros às suas últimas conseqüências. As trocas são rápidas e milhares de soluções viáveis podem ser facilmente geradas e comparadas. A idéia do grafo híbrido tem aplicações a uma grande variedade de problemas de horários e de restrições de conflitos | |
| dc.description | Coordenação de Aperfeiçoamento de Pessoal de Nível Superior | |
| dc.format | application/pdf | |
| dc.language | por | |
| dc.publisher | Universidade Federal de Pernambuco | |
| dc.subject | Automação de horários escolares | |
| dc.subject | Fator para complexidade | |
| dc.subject | Programação inteira | |
| dc.subject | Grafo Híbrido e Busca Tabu. | |
| dc.title | AST Um modelo para automação de horários escolares | |
| dc.type | doctoralThesis |