Gestão & Produção
https://www.gestaoeproducao.com/article/doi/10.1590/0104-530x3241-19
Gestão & Produção
Original Article

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

Otimização na geração de grade horária escolar através de um modelo matemático e dos procedimentos busca local e Iterated Local Search

Pedro Rochavetz de Lara Andrade; Maria Teresinha Arns Steiner; Anderson Roges Teixeira Góes

http://dx.doi.org/10.1590/0104-530x3241-19 Gest. Prod., vol.26, n4, p.0, 2019
Downloads: 0
Views: 1263

Abstract

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.

Keywords

Timetabling, Iterated Local Search, Local search, Non-Linear Binary Integer Programming

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.

Palavras-chave

Grade horária, Iterated Local Search, Busca local, Programação Não Linear Inteira Binária

References

Andrade P. R. L. 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. 2014.

Andrade P. R. L., Scarpin C. T., Steiner M. T. A. Geração da grade horária do curso de engenharia de produção da UFPR através de programação linear binária. 2012.

Babaei H., Karimpour J., Hadidi A. A survey of approaches for university course timetabling problem. Computers & Industrial Engineering. 2015;86:43-59.

Bucco G. B., Bornia Poulsen C. J., Bandeira D. L. Desenvolvimento de um modelo de programação linear para o problema da construção de grades horárias em universidades. Gestão & Produção. 2017;24(1):40-9.

Cooper T. B., Kingston J. H. The complexity of timetabling construction problems. 1995.

Fonseca G. H. G., Santos H. G., Carrano E. G., Stidsen T. J. Integer programming techniques for educational timetabling. European Journal of Operational Research. 2017;262(1):28-39.

Ghiani G., Manni E., Romano A. Training offer selection and course timetabling for remedial education. Computers & Industrial Engineering. 2017;111:282-8.

Góes A. R. T., Costa D. M. B., Steiner M. T. A. Otimização na programação de horários de professores/turmas: modelo matemático, abordagem heurística e método misto. Revista Eletrônica Sistemas & Gestão. 2010;5(1):50-66.

Gotlieb C.C. The construction of class-teacher time-tables. 1963:73-7.

Guersola M. S. Otimização na distribuição física de produtos a granel: uma aplicação à distribuição de gás. 2013.

Jardim A. M., Semaan G. S., Penna P. H. V. Uma heurística para o problema de programação de horários: um estudo de caso. 2016.

Lewis R., Thompson J. Analyzing the effects of solution space connectivity with an effective metaheuristic for the course timetabling problem. European Journal of Operational Research. 2015;240(3):637-48.

Lindahl M., Mason A. J., Stidsen T., Sørensen M. A strategic view of University timetabling. European Journal of Operational Research. 2018;266(1):35-45.

Liu L., Dessouky M. Stochastic passenger train timetabling using a branch and bound approach. Computers & Industrial Engineering. 2019;127:1223-40.

Lourenço H., Martin O., Stützle T. Iterated Local Search. Handbook of metaheuristics. 2002:321-53.

Penna P., Subramanian A., Ochi L. An iterated local search heuristic for the heterogeneous Fleet vehicle routing problem. Journal of Heuristics. 2013;19(2):201-32.

Resende M. G. C., Silva R. M. A. GRASP: procedimentos de busca gulosos, aleatórios e adaptativos. Meta-heurísticas em pesquisa operacional. 2013.

Ribeiro C., Aloise D., Noronha T., Rocha C., Urrutia S. An eficient implementation of a VNS/ILS heuristic for a real-life car sequencing problem. European Journal of Operational Research. 2008;191(3):596-611.

Saviniec L., Santos M. O., Costa A. M. Parallel local search algorithms for high school timetabling problems. European Journal of Operational Research. 2018;265(1):81-98.

Silva T. C. L., Steiner M. T. A., Carnieri C., Silva A. C. L. Determinação de escalas de plantão para militares considerando preferências e hierarquia. Pesquisa Operacional. 2004;24(3):373-91.

Soria-Alcaraz J. A., Ochoa G., Swan J., Carpio M., Puga H., Burke E. K. Effective learning hyper-heuristics for the course timetabling problem. European Journal of Operational Research. 2014;238(1):77-86.

Sousa V. N., Moretti A. C., Podestá V. A. Programação da grade de horário em escolas de ensino fundamental e médio. Pesquisa Operacional. 2008;28(3):399-421.

Souza M. J. F., Maculan N., Ochi L. S. Uma heurística para o problema de programação de horários em escolas. Tendências em Matemática Aplicada e Computacional. 2001;2(1):213-22.

Veenstra M., Vis I. F. A. School timetabling problem under disturbances. Computers & Industrial Engineering. 2016;95:175-86.

5dde7fd30e8825e7767b23c6 gp Articles
Links & Downloads
1806-9649 (Electronic) 0104-530X (Printed)
Gest. Prod. ©2025 All rights reserved.

Gest. Prod.

Share this page
Page Sections