¿Sabías que calcular los horarios de las universidades o colegios pertenece a la clase de problemas más complicados de resolver? En este post presentamos los aspectos fundamentales de este problema y explicamos cómo podemos mejorar las planificaciones de las instituciones docentes.
El problema de la planificación docente o School Timetabling Problem (STP) consiste en determinar la programación de las “actividades académicas” de un conjunto de titulaciones correspondientes a un periodo de tiempo. La programación de las actividades debe satisfacer las restricciones establecidas tanto de los alumnos como de los profesores y de las aulas.
Bill Gates explica cómo se puede poner el ingenio al servicio de diferentes criterios y requisitos. Con dieciséis años desarrolló un programa para componer los horarios de las clases de su instituto:
“Of course, a whole new dimension of relevance came when I was asked to do a computerized class schedule for the high school.
It was complex, but ultimately very rewarding. By the time I was done, I found that I had no classes at all on Fridays. And even better, there was a disproportionate number of interesting girls in all my classes.”
Este tipo de problemas abarcan desde la planificación de las clases convencionales de colegios y universidades hasta la elaboración de calendarios de exámenes.
Los problemas de STP son problemas NP-Completos, lo que implica que a medida que crece el tamaño del problema, su complejidad y tiempo de resolución aumentan a un ritmo mucho mayor. Esto hace que calcular los horarios de forma automática se convierta en todo un reto.
En muchos colegios y universidades tanto la planificación del horario de las clases como de los exámenes se realiza de forma manual, lo cual requiere de mucho esfuerzo y tiempo. Además, al realizarse de forma manual, suelen producirse errores o no siempre se consiguen satisfacer todas las restricciones del problema.
La programación generalmente se realiza de forma iterativa, empezando con un calendario en blanco en la que se van cuadrando las clases de los diferentes grupos. Esto provoca que la calidad de los calendarios de alumnos de distintos grupos sea heterogénea (es más sencillo atender bien a los primeros y cada vez es más complicado a medida que se van añadiendo más grupos). Lo mismo ocurre con los profesores.
En general, la planificación docente realizada manualmente:
- Es un proceso largo y que requiere de mucho tiempo y esfuerzo por parte del equipo de planificación.
- Debido al largo tiempo de creación del calendario, no es posible probar distintas configuraciones o mejoras, lo cual hace que la planificación no sea flexible.
- Como resultado, la calidad de los horarios de los alumnos puede verse afectada, incluso impidiendo al alumno asistir a alguna clase por la existencia de solapamientos.
- La poca flexibilidad de los horarios puede hacer que sean incompatibles con la disponibilidad de profesores, lo que dificulta los procesos de contratación y las condiciones de los profesores.
Hasta ahora solo hemos hablado de la complejidad de encontrar una planificación que cumpla con las restricciones del problema, ya que únicamente resolver el problema ya consume el tiempo de los planificadores. Sin embargo, si dos personas distintas generaran la programación de una misma universidad el resultado no sería el mismo. Entonces, ¿qué hace que una planificación sea mejor que otra? O, dicho de otra manera, ¿cuáles son los términos de la función objetivo de este problema?
Si preguntáramos a Bill Gates, él lo tenía claro. Pero no es aconsejable que los alumnos sean los que decidan cómo quieren su calendario. En efecto, la función objetivo de un modelo que resuelva un STP debe ser multiobjetivo, para encontrar un equilibrio entre las preferencias de alumnos y profesores sin desatender la forma en la que se hace uso de la infraestructura del colegio o universidad. Algunos ejemplos de los términos de la función objetivo podrían ser:
- El número de horas en blanco entre clases de un alumno.
- El número de horas en blanco entre clases de un profesor.
- El número de días que el alumno o profesor tiene que acudir al aula.
- La homogeneidad de la carga de las asignaturas.
- La homogeneidad de la ocupación de las aulas a lo largo del día.
Pero si hemos explicado que estos problemas no se pueden resolver en un tiempo razonable a media que el problema aumenta, ¿qué pueden hacer las grandes instituciones académicas? En lugar de obtener la solución óptima del problema, lo que se busca es encontrar la mejor solución posible en el tiempo que disponemos para resolver el problema. Es ahí donde entra la investigación operativa para resolver la planificación docente, mediante técnicas matemáticas como heurísticos, descomposiciones, modelos exactos o modelos híbridos de tal manera que las instituciones permitan obtener planificaciones que mejoren la calidad de horario tanto de los alumnos como de los profesores o que satisfagan las preferencias de unos y otros de forma equilibrada.
Algunos estudios han intentado definir una estructura común que caracterice los problemas de planificación, pero no existe un problema general que se ajuste a todos los casos. Precisamente, dado que cada institución tiene sus particularidades, el problema varía y hay que adaptar la técnica de resolución para conseguir mejores soluciones y cumplir los requisitos específicos. Entre otras, cabe destacar distintas técnicas que podemos encontrar en la literatura como la heurística de coloreado de grafos (Yanez y Ramirez, 1999), la búsqueda tabú (Azimi, 2005), los algoritmos genéticos (Burke y Petrovic, 2002) y la programación matemática (Aizam y Liong, 2013) y (Daskalaki y Housos, 2004).
El uso de estas técnicas combinado con la experiencia de los planificadores de las instituciones académicas permite la obtención de mejores planes docentes con menor esfuerzo y sin errores. En baobab soluciones ponemos a disposición de las instituciones académicas los servicios de optimización diseñados a medida de su operativa de tal forma que permitan a los planificadores:
- Evaluar más alternativas en menos tiempo.
- Dedicar menos esfuerzo a “cuadrar” la planificación y más a explorar planificaciones alternativas.
- Analizar cambios sobre ciertas políticas y su impacto sobre el resultado de la planificación.
- Evaluar el impacto de la incorporación de más alumnos.
- Evaluar el impacto de la implantación de nuevos cursos.
- Identificar futuras necesidades de recursos.
Hay tareas que, en cambio, sólo puede hacer una persona: negociar cambios con un profesor, conseguir presupuesto para una ampliación de infraestructura, diseñar nuevos planes de estudios, etc.
Por eso, es conveniente disponer de una buena herramienta de planificación para liberar a los gestores de la tarea tediosa que puede hacer una máquina y permitirle dedicar sus esfuerzos a todos los aspectos que debe hacer una persona.