Otimização na construção da grade horária escolar : uma aplicação

Abstract

Resumo: O problema da construção de horário escolar das turmas se repete a cada início de ano letivo nas escolas de ensino fundamental e médio, quer por mudança de turmas e professores, ou por aposentadorias e licenças. Por ser um problema complexo, envolvendo inúmeras variáveis, trata-se de uma tarefa difícil para o responsável pelo pequeno prazo que dispõe e também por, na maioria das vezes, não atender as preferências e necessidades individuais de cada professor, pois atualmente tal tarefa é feita manual e empiricamente. Este trabalho objetiva utilizar técnicas da Pesquisa Operacional para a otimização de horários dos professores, de uma forma rápida e eficaz, respeitando as preferências e limitações de professores que trabalham em duas ou mais escolas, fazendo uso de um modelo de Programação Linear Inteira. O modelo gerado contempla restrições para número de aulas por turma, para máximo de duas aulas por dia em uma mesma turma, para assegurar uma aula por turma em um mesmo horário e uma aula por professor em um mesmo horário, levando em consideração dados coletados em uma escola pública de Prudentópolis-Pr. Além disso, para atender as exigências de aulas vagas no início e/ou final do tumo, foram estabelecidos pesos adequados para interferência nas regras lexicográficas do simplex, forçando definições de horários que melhoram o valor da função objetivo. A definição das variáveis de decisão (binárias) foi realizada a partir de conjuntos de turmas e dias da semana de cada professor, proporcionando uma redução no problema abordado de 6300 variáveis de decisão possíveis para 2510 utilizadas, devido à estrutura de esparsidade, pois nem todos os professores têm aulas em todas as turmas. O problema foi implementado no softwam LINGO 6.0, cuja solução do modelo conta com 300 variáveis não nulas (horários designados)

Abstract: The scholar schedule problem repeats every beginning of year in state schools and, either because of change of groups and teachers, or because of retirements and leaves. For being a complex problem, with a countless number of variables, it Is a difficult task for the person in charge and forthe small period that he/she disposes and also for, most of the time, not to assist the preferences and individual needs of each the teacher, because such task is now made by hand and empirically. This work aims to ase Operational Research techniques to optimize the teachers schedules, in a fast and effective way, considering the teachers preferences and their availabieness for working in two or more schools, making use of a Linear Integer Programming model. The generated model take in account restrictions for number of classes per group, for maximum of two classes a day in a same group, to assure a class for group in a same schedule and a class per teacher in a same schedule, based on data collected in a Brazilian public school in Prudentópolis. Moreover, to assist the demands of vague classes in the beginning and/or end of terms, adapted weights were established for interference in the lexicographical rules of the simplex method, to force schedules that improve the objective function value. The (binary) decision variables definition were accomplished starting from sets of groups and sets of working days for each teacher, providing a reduction from 6300 possible decision variables to 2510 used, due to the sparse structure, as not ali the teachers have classes in ali groups. The problem was implemented in the software LINGO version 6.0, whose model solution counts with 300 non-null variables (assigned schedules)