Otimização na geração de grade horária escolar através de um modelo matemático e das meta-heurísticas busca local e iterated local search
Abstract
Resumo: Com a atual tendência de crescimento das instituições de ensino, aumenta-se também a necessidade de melhoria na utilização dos recursos desses estabelecimentos. Entre os recursos que podem ser otimizados está a definição de uma grade horária escolar, envolvendo professores, alunos, disciplinas, horários e salas de aula. Mais especificamente, o tema deste trabalho é a geração da grade horária escolar, com a definição de dias e horários para encontros entre alunos e professores com o objetivo de tratar sobre disciplinas específicas. Para a resolução do problema foi desenvolvida uma ferramenta chamada "Classe Mestre" capaz de gerar a grade horária de instituições de Ensino Fundamental, baseada em técnicas meta-heurísticas que levem em consideração, também, as preferências dos professores. No presente trabalho são aplicados o modelo matemático de Programação Linear Inteira Binária (PLIB) e as meta-heurísticas Busca Local (BL) e Iterated Local Search (ILS) a alguns problemas. Tendo em vista que o ILS contém a BL no seu procedimento, analisam-se os ganhos que a aplicação do ILS fornece em relação à aplicação isolada da BL, bem como a dispersão de ambas as técnicas em relação à solução ótima do problema. Todos os resultados apresentados são gerados a partir da aplicação da ferramenta em estudos de caso de escolas da rede pública do Município de Araucária-PR. Abstract: The current growth trend of educational institutions increases the need for improvement in the use of establishments' resources. Among the resources that can be optimized is the ones used for the definition of a school timetable involving teachers, students, courses, schedules, and classrooms. The theme of this dissertation is, more specifically, the generation of this school timetable, that establishes dates and times for meetings between students and teachers that lecture specific disciplines. To solve this problem, a tool called "Classe Mestre" has been developed, capable of generating the timetable for institutions of primary education, considering teachers' preferences and based on meta-heuristic techniques. In this paper, the mathematical model of Binary Integer Linear Programming (BILP), the meta-heuristics Local Search (LS) and Iterated Local Search (ILS) are applied to selected problems. Since ILS contains the LS in its procedure, the gains that the application of ILS provides for the application of isolated LS are analyzed, as well as the dispersion of both techniques regarding the optimal solution. All results are generated from the application of the tool in case studies of public schools in the city of Araucária-PR.
Collections
- Teses & Dissertações [9996]