Métodos de busca heurística para problemas de programação de horários modelados em XHSTT
| Autor: | Fonseca, George Henrique Godim da |
|---|---|
| Přispěvatelé: | Santos, Haroldo Gambini |
| Jazyk: | portugalština |
| Rok vydání: | 2013 |
| Předmět: | |
| Zdroj: | Repositório Institucional da UFOP Universidade Federal de Ouro Preto (UFOP) instacron:UFOP |
| Popis: | O 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 conhecidas The 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|