Métodos de busca heurística para problemas de programação de horários modelados em XHSTT.

Simple item page
dc.contributor.advisorSantos, Haroldo Gambinipt_BR
dc.contributor.authorFonseca, George Henrique Godim da
dc.date.accessioned2013-07-05T16:16:18Z
dc.date.available2013-07-05T16:16:18Z
dc.date.issued2013
dc.description.abstractO Problema da Programação de Horários Escolares é alvo de diversas pesquisas em Pesquisa Operacional e Inteligência Artificial devido a sua dificuldade de resolução e import^ancia prática. Uma solução para esse problema consiste basicamente na alocação de aulas a horários e na alocação dos recursos para essas aulas. Essa alocação deve atender a várias restrições especificadas a priori. O presente trabalho considera a solução do problema proposto pela Third Interntional Timetabling Competition (ITC2011), a qual inclui um amplo conjunto de inst^ancias originadas de diversas instituições educacionais ao redor do mundo. O presente trabalho prop~oe diversas técnicas de busca local para solucionar o problema. O formato de especificação de inst^ancias considerado foi o XHSTT, permitindo que qualquer inst^ancia especificada no referido formato possa ser manipulada pelos algoritmos propostos. Uma característica estrutural importante da nossa abordagem é o uso da plataforma KHE para gerar soluções iniciais, combinada com uma abordagem de busca multi-vizinhança. Os resultados obtidos incluem o desenvolvimento do algoritmo vencedor da competição. Fomos ainda capazes de encontrar soluções factíveis para treze de dezoito inst^ancias e melhorar quinze de dezesseis melhores soluções conhecidaspt_BR
dc.description.abstractenThe High School Timetabling Problem remains subject of many research in Operational Research and Arti cial Intelligence elds because of its hardness to solve and practical importance. A solution for this problem basically consists in the schedule of lessons to timeslots and the assignment of resources for these lessons. This allocation should satisfy many a priori speci ed constraints. This work considers the solution of the problem of the Third International Timetabling Competition (ITC2011), which includes a diverse set of instances from many educational institutions around the world. This work presents many local search methods to solve the problem. The format for specifying instances considered was XHSTT, allowing any instance speci ed in that format to be manipulated by the proposed algorithms. One important structural feature of our approach is the use of the KHE engine to generate initial solutions combined with a multi-neighborhood search approach. The achieved results include the development of the algorithm winner of competition. Moreover, we found feasible solutions to thirteen out of eighteen instances and we improved the best known solution to fteen out of sixteen instances.
dc.identifier.citationFONSECA, G.H. G. da. Métodos de busca heurística para problemas de programação de horários modelados em XHSTT. 2013. 69 f. Dissertação (Mestrado em Ciência da Computação) - Universidade Federal de Ouro Preto, Ouro Preto, 2012.pt_BR
dc.identifier.urihttp://www.repositorio.ufop.br/handle/123456789/3056
dc.language.isopt_BRpt_BR
dc.publisherPrograma de Pós-Graduação em Ciência da Computação. Departamento de Ciência da Computação, Instituto de Ciências Exatas e Biológicas, Universidade Federal de Ouro Preto.pt_BR
dc.subjectProgramação heurísticapt_BR
dc.subjectOtimização combinatóriapt_BR
dc.subjectHorários escolarespt_BR
dc.titleMétodos de busca heurística para problemas de programação de horários modelados em XHSTT.pt_BR
dc.typeDissertacaopt_BR
Files
Original bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
DISSERTAÇÃO_MétodoBuscaHeurística.PDF
Size:
1.26 MB
Format:
Adobe Portable Document Format
Download
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
2.62 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
PPGCC - Mestrado (Dissertações)