ASIGNACIÓN DE SALONES EN UNA UNIVERSIDAD

En una universidad comúnmente, los alumnos tienen la posibilidad de elegir las materias que desean llevar en cada ciclo escolar, por ello, es común que sucedan traslapes, por ejemplo, que un alumno tome dos materias y éstas sean impartidas el mismo día y a la misma hora pero en diferentes salones. Otro problema que existe es que a salones muy pequeños se les asignen materias con grupos numerosos y que el aforo del salón sea rebasado por estos grupos. 

El problema de asignación de salones esta clasificado como un problema NP-completo por su complejidad en el  área de optimización discreta [1, 2].

En el Figura 1 se muestra de forma gráfica como se encuentran las principales variables que se deben de tomar en cuenta, (Periodo, Día, Salón) en un problema de asignación de salones.

Cada color a lo ancho del cubo representa un salón (ejemplo, verde es salón 1: s1) y cada casilla (en 3D) es un lugar para almacenar un evento (una casilla es la relación que dan las coordenadas periodo-día-salón). Una materia que va a tomar el alumno está compuesta de uno o varios eventos (EV1, EV2, EV3,...., etc. ver Fig. 2). Por lo que es necesario revisar que ninguna materia se traslape en ningún salón y que ningún alumno tenga más de una materia a la misma hora en diferentes salones.

Lo que consume más tiempo para encontrar una buena solución en el algoritmo de asignación es revisar que en la materia no exista un alumno que traslape con otros eventos en distintos salones. Por ejemplo un alumno elige las materia de Computación y Matemáticas, pero cuando se asignan los horarios a las materias, resulta que Computación será impartida en el Periodo 1, día Lunes en el salón 3 y Matemáticas en el mismo periodo y día  en el Salón 1, como se puede notar, ha ocurrido un traslape, así que es necesario, cambiar de horario la materia y realizar de nuevo todo el proceso de comparación hasta que no exista ningún traslape. Esto es una de las restricciones lo que se trata de cumplir  en la implementación de un algoritmo que de una solución factible, por ello es necesario realizar gran cantidad de iteraciones, esto con el fin de que se compare en todos los salones cada alumno en cada una de las materias concernientes al mismo periodo-día en el que será impartida la materia elegida.

1.- M.R. Garey, and D.S. Johnson, Computers and intractability, A Guide to the theory of NP-Completeness, W.H. Freeman and Company, New York, USA, 2003

2.- S. Even, A. Itai, and A. Shamir, On the complexity of timetable and multicommodity flow problems, SIAM Journal on Computing Vol 5, No 4, 691-703, 1976.

Regresar a inicio