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

Optimización de los horarios escolares mediante un modelo matemático, búsqueda local y procedimientos de búsqueda local iterada

En este trabajo se aborda el problema del horario escolar, que consiste en definir la fecha y hora en la que se impartirán las clases por parte de los profesores en los centros educativos. Para ello, se desarrolló una herramienta que utiliza técnicas de Investigación Operativa (IO), enfocada a generar y optimizar horarios de Primaria y Secundaria, tomando en cuenta las preferencias de los profesores por determinados días o por clases secuenciadas (hermanadas). Para resolver el problema, se aplicó comparativamente un modelo matemático de Programación Entera Binaria No Lineal (NLBIP) y procedimientos de Búsqueda Local (LS) y Búsqueda Local Iterada (ILS). Se analizó un problema real con 14 horarios de escuelas públicas de la ciudad de Araucária (en el Estado de Paraná, Brasil). Los resultados indican que el tiempo computacional requerido por el modelo matemático es factible para los problemas en cuestión. La técnica ILS tiene potencial para probar problemas de mayor escala, pues presenta una dispersión de 3,5% a 7,7% en relación a la solución óptima (obtenida por el NLBIP) y un tiempo computacional de 15 a 338 veces más rápido.

1. INTRODUCCIÓN

La necesidad de optimizar el uso de todo tipo de recursos es una exigencia tanto en los centros de enseñanza como en cualquier otro tipo de institución. Entre los recursos de los centros que pueden optimizarse se encuentran las aulas y el tiempo de que disponen los profesores para definir los tiempos de sus compromisos, es decir, su horario.

El timetabling involucra una serie de variables, entre ellas las preferencias de horarios, los días de enseñanza (o no enseñanza), las clases hermanadas (o no), la carga diaria de trabajo de las asignaturas y, por último, la minimización de los días lectivos. Por lo tanto, la programación manual de horarios suele ser muy compleja, y limitarse a lograr una solución factible se considera satisfactorio, como ocurre en muchos centros escolares hoy en día. Por lo tanto, la creación de un sistema capaz de automatizar los horarios permite a las escuelas preparar sus horarios más rápidamente y con mejor calidad.

Se pueden citar varios trabajos sobre este tema, algunos de los cuales se analizarán con más detalle más adelante, como Saviniec et al. (2018), Fonseca et al. (2017), Soria-Alcaraz et al. (2014), Andrade et al. (2012), Góes et al. (2010), Sousa et al. (2008), Cooper & Kingston (1995), Souza et al. (2001) y Gotlieb (1963).

En este trabajo se presenta el desarrollo de un programa informático que hace uso de técnicas de Investigación Operativa (IO), creado para producir horarios con la máxima optimización para escuelas primarias.