Atenção: Todas as denúncias são sigilosas e sua identidade será preservada.
Os campos nome e e-mail são de preenchimento opcional
Metadados | Descrição | Idioma |
---|---|---|
Autor(es): dc.contributor | Ochi, Luiz Satoru | - |
Autor(es): dc.contributor | CPF:31609080822 | - |
Autor(es): dc.contributor | http://lattes.cnpq.br/9171815778534257 | - |
Autor(es): dc.contributor | Lucena Filho, Abilio Pereira de | - |
Autor(es): dc.contributor | CPF:75123400922 | - |
Autor(es): dc.contributor | http://lattes.cnpq.br/0907883161698484 | - |
Autor(es): dc.contributor | Ribeiro, Celso da Cruz Carneiro | - |
Autor(es): dc.contributor | CPF:34620081022 | - |
Autor(es): dc.contributor | http://lattes.cnpq.br/3614186131432854 | - |
Autor(es): dc.contributor | Barboza, Eduardo Uchoa | - |
Autor(es): dc.contributor | CPF:85462487922 | - |
Autor(es): dc.contributor | http://buscatextual.cnpq.br/buscatextual/visualizacv.do?id=K4721785E2 | - |
Autor(es): dc.contributor | Souza, Marcone Jamilson Freitas | - |
Autor(es): dc.contributor | CPF:32723547604 | - |
Autor(es): dc.contributor | http://buscatextual.cnpq.br/buscatextual/visualizacv.do?id=K4793954E6 | - |
Autor(es): dc.contributor | Maculan Filho, Nelson | - |
Autor(es): dc.contributor | CPF:74008070522 | - |
Autor(es): dc.contributor | http://lattes.cnpq.br/4436183480921146 | - |
Autor(es): dc.creator | Santos, Haroldo Gambini | - |
Data de aceite: dc.date.accessioned | 2024-07-11T18:04:14Z | - |
Data de disponibilização: dc.date.available | 2024-07-11T18:04:14Z | - |
Data de envio: dc.date.issued | 2021-03-10 | - |
Data de envio: dc.date.issued | 2010-04-22 | - |
Data de envio: dc.date.issued | 2021-03-10 | - |
Data de envio: dc.date.issued | 2007-03-30 | - |
Fonte completa do material: dc.identifier | https://app.uff.br/riuff/handle/1/18770 | - |
Fonte: dc.identifier.uri | http://educapes.capes.gov.br/handle/capes/762923 | - |
Descrição: dc.description | This 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.description | Esta 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.format | application/pdf | - |
Idioma: dc.language | pt_BR | - |
Publicador: dc.publisher | Programa de Pós-Graduação em Computação | - |
Publicador: dc.publisher | Computação | - |
Direitos: dc.rights | Acesso Aberto | - |
Direitos: dc.rights | CC-BY-SA | - |
Palavras-chave: dc.subject | Programação de horários em escolas | - |
Palavras-chave: dc.subject | Programação linear inteira | - |
Palavras-chave: dc.subject | Metaheurística | - |
Palavras-chave: dc.subject | Algoritmo | - |
Palavras-chave: dc.subject | Otimização combinatória | - |
Palavras-chave: dc.subject | School Timetabling | - |
Palavras-chave: dc.subject | Mixed Integer Programming | - |
Palavras-chave: dc.subject | Metaheuristic | - |
Palavras-chave: dc.subject | Algorithm | - |
Palavras-chave: dc.subject | Combinatorial optimization | - |
Palavras-chave: dc.subject | CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO | - |
Título: dc.title | Formulações e algoritmos para o problema de programação de horários em escolas | - |
Tipo de arquivo: dc.type | Tese | - |
Aparece nas coleções: | Repositório Institucional da Universidade Federal Fluminense - RiUFF |
O Portal eduCAPES é oferecido ao usuário, condicionado à aceitação dos termos, condições e avisos contidos aqui e sem modificações. A CAPES poderá modificar o conteúdo ou formato deste site ou acabar com a sua operação ou suas ferramentas a seu critério único e sem aviso prévio. Ao acessar este portal, você, usuário pessoa física ou jurídica, se declara compreender e aceitar as condições aqui estabelecidas, da seguinte forma: