Los que nos hemos enfrentado a planificar horarios universitarios, ya sean personales o para otros, conocemos lo engorroso que puede ser organizar los eventos para llegar a horarios cómodos y que no dejen nada fuera. Típicas situaciones que querríamos evitar: choques de horario, días con una sola clase o muchas clases seguidas, largas ventanas entre horas de clases, días con horarios muy diferentes entre sí, clases demasiado tarde.

La situación se complica cuando hay varias opciones de horarios disponibles para cada curso, multiplicando el número de combinaciones. Entonces empezamos con el horario versión uno, versión dos…

Como en Foris creemos que para este tipo de tareas deberían existir procesos automáticos, en esta publicación vamos a explorar cómo se podría automatizar la elección de horarios (aplausos). Para un primer análisis, nos centraremos en el caso simplificado en que las clases son parte de un solo horario.

Sabemos que el primer paso para poder generar un proceso automático que mejore cualquier aspecto de algo es tener una buena función objetivo. En otras palabras, que lo podamos medir.

El primer paso para poder generar un proceso automático que mejore cualquier aspecto de algo es tener una buena función objetivo.

[…] una buena función objetivo debería ser capaz de indicar a un agente inteligente si sus posibles elecciones de horario estarían mejorando o empeorando su calidad.

Funciones Objetivo

Hay un típico juego de niños en que una persona esconde algo y después le repite a otra caliente o frío dependiendo de qué tan cerca está de encontrarlo. Ese es un excelente ejemplo de una función objetivo. En nuestro caso, una buena función objetivo debería ser capaz de indicar a un agente inteligente si sus posibles elecciones de horario estarían mejorando o empeorando su calidad. Por ejemplo, si muevo la sección 3 de IH0213 Antropología Americana desde el martes a las 8 a.m. hasta el jueves a las 10 p.m., ¿eso mejora o empeora el horario?

Para responder estas preguntas de manera automática, presentamos la función evaluadora de calidad horaria, que abreviaremos por \(f\). La idea es que esta función asigne a cada horario una puntuación o penalización dependiendo de qué tan lejos esté de un horario ideal según varios criterios. Así, si el agente inteligente quiere saber cuál es mejor entre un horario \(S\) y una versión modificada \(S’\), sólo tendría comparar los números \(f(S)\) y \(f(S’)\).

¿Cómo se comienza a construir algo así? Matemáticamente, podemos representar esta función como una suma de funciones más sencillas $$f = f_1+\cdots+f_n,$$ donde cada término \(f_k\) asigna una puntuación del horario analizado en un criterio particular. Ahora podemos usar el ingenio para definir funciones de penalización que midan los criterios de calidad que nos gustaría cumplir. Exploremos un par de posibilidades.

Penalización de ventanas

Uno de los motivos de queja más frecuentes después del período de toma de ramos en las universidades. Una ventana horaria es un intervalo de tiempo de espera indeseado entre dos sesiones de clases.

Para precisar a qué nos referimos sería bueno definir cuánto tiempo de espera es aceptable. Esto podría variar según la distribución del horario. Por ejemplo, un estudiante que lleva cuatro horas sentado en una sala probablemente estaría mucho más feliz de tener un bloque libre antes de su siguiente clase que uno que solo ha tenido una clase corta.

Tomando esto en cuenta, definimos que una porción libre de un horario es una ventana si está entre dos sesiones de clase de un mismo día y si su duración es mayor a un máximo tolerable, representado por la letra \(r\). Esta tolerancia puede variar según las circunstancias para acomodarse a los casos anteriores (ver figura).

Figura: El horario de la izquierda tiene 1 bloque de ventana, según una espera tolerable de 1 bloque. El de la derecha suma 3, según una espera tolerable de 0.

 

En símbolos: para cada ventana \(v\) con duración \(T(v)\) de un horario \(S\), podemos penalizar una cantidad proporcional a la espera excesiva de esa ventana. Siguiendo el espíritu de los ejemplos, la tolerancia \(r(v)\) depende de cada ventana, así que penalizamos la diferencia \(T(v)-r(v)\) (cuando es positiva).
Podemos definir la puntuación \(f_1\) sumando todas estas penalizaciones: $$f_1(S) = \sum_{v\in S}\max(T(v)-r(v), 0).$$

Penalización de sobre carga

Pero ¿por qué tendríamos que tener cuatro horas seguidas de clases en primer lugar? Otro buen criterio de penalización es el de sobre cargas.
Para calcular la penalización, primero fijamos una cantidad máxima de horas de clase consecutivas \(m\) que estimamos razonable. La idea es penalizar cada hora adicional a \(m\) de clases consecutivas (sin bloques de descanso).

Podemos definir \(f_2\) encontrando primero todas las cadenas de sesiones seguidas de clases en nuestro horario, que conforman un conjunto \(B\). Para cada cadena \(b\) de este conjunto, llamamos \(T(b)\) a su duración total. Con esta notación, \(f_2\) se escribe $$f_2(S) = \sum_{b\in B}\max(T(b)-m, 0).$$

Más penalizaciones, ecualización e independencia

Podemos seguir añadiendo penalizaciones para tantos criterios como queramos considerar en los horarios: sub cargas, alineamiento de horarios, similaridad entre días, días de descanso, simetría, inicio temprano, eventos en días sábado, etc. Una vez que terminemos, ya tendremos una función evaluadora de calidad operativa.

Ahora, es muy posible que sencillamente no exista la combinación de horarios que cumpla al 100% con todos nuestros criterios. En caso de que haya que sacrificar alguno de ellos, ¿cuál descartamos primero? Y si dos de nuestros criterios penalizaran indirectamente un mismo aspecto en común, ¿no sería injusto sumar dos veces penalizaciones para él?.

Estos detalles afectan el comportamiento que esperamos de la función evaluadora y los podremos ajustar después de discutir sobre la ecualización y la independencia de los criterios que la componen. En el siguiente post discutiremos estos conceptos e investigaremos cómo generalizar las métricas al caso de varios horarios a la vez.

David Cozmar desarrolla algoritmos de optimización y proyección para DarwinEd en Foris

Agregar un comentario

Su dirección de correo no se hará público. Los campos requeridos están marcados *