Skip navigation
Use este identificador para citar ou linkar para este item: https://repositorio.ufpe.br/handle/123456789/7116
Título: AST Um modelo para automação de horários escolares
Autor(es): Rios dos Santos, Jalila
Palavras-chave: Automação de horários escolares; Fator para complexidade; Programação inteira; Grafo Híbrido e Busca Tabu.
Data do documento: 31-Jan-2008
Editor: Universidade Federal de Pernambuco
Citação: 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.
Resumo: 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
URI: https://repositorio.ufpe.br/handle/123456789/7116
Aparece na(s) coleção(ções):Teses de Doutorado - Matemática Computacional

Arquivos deste item:
Arquivo Descrição TamanhoFormato 
arquivo4270_1.pdf3,16 MBAdobe PDFVer/Abrir


Este arquivo é protegido por direitos autorais



Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.