Made available in DSpace on 2014-06-12T18:29:06Z (GMT). No. of bitstreams: 2
arquivo4270_1.pdf: 3240198 bytes, checksum: 40ce23c71a96036f67deaa9c0522df1a (MD5)
license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5)
Previous issue date: 2008 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / 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
| Identifer | oai:union.ndltd.org:IBICT/oai:repositorio.ufpe.br:123456789/7116 |
| Date | 31 January 2008 |
| Creators | Rios dos Santos, Jalila |
| Contributors | Luiz Soares Lins, Sóstenes |
| Publisher | Universidade Federal de Pernambuco |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/doctoralThesis |
| Source | reponame:Repositório Institucional da UFPE, instname:Universidade Federal de Pernambuco, instacron:UFPE |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0022 seconds