Desarrollo de la estructura de datos
En este programa, dadas ciertas combinaciones de profesores, asignaturas, aulas y grupos, y cuántas veces deben aparecer en el horario, el objetivo es ordenar dichas combinaciones y asignarlas en un horario dados los días y el número de horas por día que éste tendrá. Por ello el programa en el software R parte de un dataframe en el que aparecen estos datos (que como explicamos en el manual de la aplicación los podemos escribir en un archivo Excel.
El siguiente paso consiste buscar qué profesores se repiten en los datos y qué aulas pues esto definirá las restricciones. Las variables serán xijk donde la i representa las combinaciones que queremos que aparezcan en el horario (es decir, i es el número de la fila del archivo Excel), j es el día y k la hora. Los valores que pueden tomar las variables son 0 si no se da la combinación i, el día j a la hora k y 1 si sí se da.
A continuación, se forma una matriz que tendrá los coeficientes de las restricciones para luego pasar esta matriz al software LP solve ID. Las restricciones serán:
- Que las combinaciones se realicen el número de horas que se muestra en la tabla. En este caso para cada fila de la tabla Excel tendremos un sumatorio en los días y en las horas y debe cumplirse la igualdad con el número de horas que aparezca en la tabla. $$\displaystyle\sum_{j=1}^{\text{nº días}}\sum_{k=1}^{\text{nº horas}} x_{ijk} = \text{nº horas combinación } i, \qquad \text{ para todo } i=1,\dots, n,$$ siendo n el número de filas de la tabla.
Así tendremos que añadir a la matriz que se va a pasar a LP Solve una fila por cada una de las restricciones y fijada una i tendrá 1 en todas las variables que tengan el mismo subíndice i y 0 en el resto.
- Que los profesores no puedan dar dos clases a la vez. Para ello los profesores que aparezcan repetidos, esto es, las filas del archivo Excel que tengan los mismos profesores fijados un día j y una hora k, no pueden sumar más de 1. Por lo tanto añadiremos una fila a la matriz con 1 si la variable es de la fila en que el profesor que se repite aparece y un 0 si no, y esto se hace para cada día y cada hora y también para cada profesor que se repite.
- Que no se den a la misma hora dos clases en un mismo aula. Razonando de la misma manera, vemos las aulas que hay diferentes y para cada aula añadimos una restricción para cada día y hora, añadiendo 1 en las variables correspondientes.
Así ya tendríamos la matriz de coeficientes que se pasa a LP solve ID. El vector de recursos es un vector con el número de horas que se lleva a cabo cada combinación y el resto son 1.
Nuestro programa no tiene una solución óptima pues no tenemos costos que maximizar o minimizar. Por lo tanto sólo queremos que el programa nos devuelva un posible horario a realizar. Para ello definimos la función objetivo z que símplemente será 0 si la solución es factible. El problema tendrá soluciones múltiples, así que el programa nos devolverá una de las posibles.
Una vez pasadas la matriz de coeficientes y el vector de recursos a LP solve ID la solución que nos devuelve es un vector de 0 y 1. El vector tiene el siguiente significado: si hay h horas en el horario, cada h elementos del vector será una de las filas del archivo Excel, es decir que si hay f filas podríamos dividir nuestra solución en f vectores de h componentes; si hay hd horas cada día, cada vector que hemos definido antes se podría dividir en d vectores (siendo d el número de días) con hd componentes; así de esta nueva división de vectores se tiene un 1 si se verifica que la fila i el día j y la hora k se da en el horario, 0 si no se da.
Teniendo en cuenta esta estructura, se forma una matriz y se va a transformar de manera que en vez de 1 aparezca el número de la fila en el archivo Excel, para poder saber qué combinación tiene lugar qué día y a qué hora.
A continuación, se concatenan las filas de esta matriz pues podría ocurrir que dos profesores den clase a la misma hora si no comparten aula por ejemplo, y se reordena de manera que obtenemos la matriz final del horario.
Finalmente, se usa una función que hace que en el horario aparezca como texto la asignatura que da un profesor en un aula y a un grupo por día y hora.