Optimization in timetabling in schools using a mathematical model, local search and Iterated Local Search procedures

AUTOR(ES)
FONTE

Gest. Prod.

DATA DE PUBLICAÇÃO

07/10/2019

RESUMO

Resumo Este artigo aborda o problema de otimização na geração da grade horária escolar. Tal problema consiste em definir os dias e horários das disciplinas a serem ministradas por cada um dos professores de instituições de ensino. Para isto foi desenvolvida uma ferramenta que faz uso de técnicas de Pesquisa Operacional (PO), com foco na geração e otimização de grade horária de instituições de Ensino Fundamental, considerando as preferências dos professores, tais como, preferências por dias de aula e por aulas em sequência (geminadas). Para a resolução do problema foi utilizado um modelo matemático de Programação Não Linear Inteira Binária (PNLIB) e os procedimentos Busca Local (BL) e Iterated Local Search (ILS), comparativamente. Foi aqui analisado um problema real com 14 grades horárias de escolas públicas da cidade de Araucária, PR. Os resultados indicam que o tempo computacional demandado pelo modelo matemático é viável para os problemas analisados. A técnica ILS possui potencial para testes em problemas de maior porte, já que apresenta uma dispersão de 3,5% a 7,7% em relação à solução ótima (obtida pelo PNLIB), com tempo computacional de 15 a 338 vezes mais rápido. Abstract This paper addresses the school timetabling problem, which consists of defining the date and time in which classes will be given by teachers in educational institutions. For this purpose, a tool that uses Operational Research (OR) techniques was developed, focused on generating and optimizing Elementary and High School timetables, taking into account teachers’ preferences for certain days or for sequenced (twinned) classes. Conductive to solving the problem, a Non Linear Binary Integer Programming mathematical model (NLBIP) and Local Search (LS) and Iterated Local Search (ILS) procedures were comparatively applied. A real problem with 14 timetables of public schools in the city of Araucária (in Paraná State, Brazil) was analyzed. The results indicate that the computational time required by the mathematical model is feasible for the problems in question. The ILS technique has the potential for testing larger scale problems, as it presents a dispersion of 3.5% to 7.7% relative to the optimal solution (obtained by the NLBIP) and a computational time that is 15 to 338 times faster.

Documentos Relacionados