Skip navigation
Please use this identifier to cite or link to this item: https://repositorio.ufpe.br/handle/123456789/7116
Title: AST Um modelo para automação de horários escolares
Authors: Rios dos Santos, Jalila
Keywords: Automação de horários escolares;Fator para complexidade;Programação inteira;Grafo Híbrido e Busca Tabu.
Issue Date: 31-Jan-2008
Publisher: Universidade Federal de Pernambuco
Citation: 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.
Abstract: 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
Appears in Collections:Teses de Doutorado - Matemática Computacional

Files in This Item:
File Description SizeFormat 
arquivo4270_1.pdf3.16 MBAdobe PDFView/Open


This item is protected by original copyright



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.