Formulações e algoritmos para o problema de programação de horários em escolas

Registro completo de metadados
MetadadosDescriçãoIdioma
Autor(es): dc.contributorOchi, Luiz Satoru-
Autor(es): dc.contributorCPF:31609080822-
Autor(es): dc.contributorhttp://lattes.cnpq.br/9171815778534257-
Autor(es): dc.contributorLucena Filho, Abilio Pereira de-
Autor(es): dc.contributorCPF:75123400922-
Autor(es): dc.contributorhttp://lattes.cnpq.br/0907883161698484-
Autor(es): dc.contributorRibeiro, Celso da Cruz Carneiro-
Autor(es): dc.contributorCPF:34620081022-
Autor(es): dc.contributorhttp://lattes.cnpq.br/3614186131432854-
Autor(es): dc.contributorBarboza, Eduardo Uchoa-
Autor(es): dc.contributorCPF:85462487922-
Autor(es): dc.contributorhttp://buscatextual.cnpq.br/buscatextual/visualizacv.do?id=K4721785E2-
Autor(es): dc.contributorSouza, Marcone Jamilson Freitas-
Autor(es): dc.contributorCPF:32723547604-
Autor(es): dc.contributorhttp://buscatextual.cnpq.br/buscatextual/visualizacv.do?id=K4793954E6-
Autor(es): dc.contributorMaculan Filho, Nelson-
Autor(es): dc.contributorCPF:74008070522-
Autor(es): dc.contributorhttp://lattes.cnpq.br/4436183480921146-
Autor(es): dc.creatorSantos, Haroldo Gambini-
Data de aceite: dc.date.accessioned2024-07-11T18:04:14Z-
Data de disponibilização: dc.date.available2024-07-11T18:04:14Z-
Data de envio: dc.date.issued2021-03-10-
Data de envio: dc.date.issued2010-04-22-
Data de envio: dc.date.issued2021-03-10-
Data de envio: dc.date.issued2007-03-30-
Fonte completa do material: dc.identifierhttps://app.uff.br/riuff/handle/1/18770-
Fonte: dc.identifier.urihttp://educapes.capes.gov.br/handle/capes/762923-
Descrição: dc.descriptionThis thesis considers an variation of a classical combinatorial NP-Complete problem: The Class-Teacher Timetabling Problem. In this variant, important practical considerations are incorporated, specifically, teachers preferences and distribution of lessons. The proposals of this work are divided in three parts. In the first part a new hybrid heuristic is presented, based on Tabu Search. Computational experiments demonstrated that the proposed heuristic improves upon existing methods presenting a consistently better performance in all test problems. In the second part, proposals for producing optimal timetables are presented, considering Mixed Integer Linear Programming Techniques. In this sense, a formulation with an exponential number of rows and columns is developed, as well an algorithm to manage this formulation by cut and column generation. Computational experiments demonstrated that the proposed formulation provides stronger bounds, which allowed the proof of optimality for 3 open instances from literature. Finally, in the third part, the synergy of heuristics and exact methods is explored, by the optimal resolution of sub-problems from timetables heuristically generated. These hybrid algorithms offered the best upper bounds available.-
Descrição: dc.descriptionEsta tese trata de uma variante de um clássico problema combinatório NP-Completo : o Problema de Programação de Horários professor-Turma. Nessa variante, importantes considerações práticas são incorporadas, especificamente tratando de preferências de professores e distribuição das aulas. As propostas apresentadas nesta tese dividem-se em 3 partes. Na primeira parte é apresentada uma nova heurística híbrida, baseada em Busca Tabu. Experimentos computacionais demonstraram que a heurística proposta melhora os resultados da literatura, apresentando um desempenho consistentemente superior em todos os problemas teste. Na segunda parte propostas foram apresentadas para a obtenção de quadros de horários provadamente ótimos, considerando técnicas de Programação Linear Inteira Mista. Nesse sentido é desenvolvida uma formulação com um número exponencial de linhas e colunas, bem como um algoritmo que utiliza as técnicas de geração de colunas e cortes para o tratamento dessa formulação. Experimentos computacionais demonstraram que a formulação apresentada permite a obtenção de limites inferiores bastante fortes, os quais permitiram a prova da otimalidade para 3 instâncias em aberto da literatura. Finalmente, na terceira parte, é explorada a sinergia entre heurísticas e métodos exatos, através da resolução ótima de sub-problemas em quadros de horários construídos heurísticamente, esses algoritmos híbridos ofereceram os melhores limites superiores disponíveis.-
Formato: dc.formatapplication/pdf-
Idioma: dc.languagept_BR-
Publicador: dc.publisherPrograma de Pós-Graduação em Computação-
Publicador: dc.publisherComputação-
Direitos: dc.rightsAcesso Aberto-
Direitos: dc.rightsCC-BY-SA-
Palavras-chave: dc.subjectProgramação de horários em escolas-
Palavras-chave: dc.subjectProgramação linear inteira-
Palavras-chave: dc.subjectMetaheurística-
Palavras-chave: dc.subjectAlgoritmo-
Palavras-chave: dc.subjectOtimização combinatória-
Palavras-chave: dc.subjectSchool Timetabling-
Palavras-chave: dc.subjectMixed Integer Programming-
Palavras-chave: dc.subjectMetaheuristic-
Palavras-chave: dc.subjectAlgorithm-
Palavras-chave: dc.subjectCombinatorial optimization-
Palavras-chave: dc.subjectCNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO-
Título: dc.titleFormulações e algoritmos para o problema de programação de horários em escolas-
Tipo de arquivo: dc.typeTese-
Aparece nas coleções:Repositório Institucional da Universidade Federal Fluminense - RiUFF

Não existem arquivos associados a este item.