Programación entera para el cálculoautomatizado de horarios de clase
Daniel Ayala María Belén Heredia Luis Miguel Torres
Centro de Modelización MatemáticaEscuela Politécnica Nacional
Segundo Congreso Internacional de Matemática AplicadaSan Salvador, 5 – 7 de septiembre de 2016
1 / 32
Contenido
El problema
El modelo y el algoritmo
El sistema informático
Los resultados
2 / 32
Antecedentes
I El cálculo de horarios en la EPN se realiza manualmente anivel de cada unidad académica
I Es una tarea difícil que requiere de días (o semanas)
I Es propensa a erroresI conflictos en el uso de aulasI excesivos crucesI horarios incómodos para profesores y alumnos (p.ej.
almuerzo)
3 / 32
Antecedentes
I Proyecto semilla Octubre 2012 – Diciembre 2013I modelo de optimización basado en la programación enteraI algoritmo de solución a nivel de prototipoI pruebas de uso en la Facultad de CienciasI proyecto de titulación María Belén Heredia
I Proyecto investigación Rectorado-ModeMat-DGIPEnero 2014- Marzo 2015
I implementación del sistema a nivel de la EPNI desarrollo de bases de datosI desarrollo de interfaces de usuarioI integración a los servicios informáticos de la EPN
4 / 32
Objetivo
I Desarrollar un modelo de optimización y un sistemainformático de ayuda a la decisión para
I asignación de horarios de claseI asignación de aulas
respetando los requerimientos de la EPN.
I Estos requerimientos se expresan mediante restriccionesfuertes y débiles.
I El horario calculado satisface TODAS las restriccionesfuertes y tantas restricciones débiles como sea posible.
5 / 32
Restricciones fuertes
I cruces entre materias asignadas al mismo profesor
I disponibilidad de tiempo de los profesores
I cruces entre materias de un mismo nivel
I cantidad de aulas disponibles
I capacidad y tipo de aulas
I configuración de las materias
I cruces definidos por el usuario
6 / 32
Restricciones débiles
I cruces entre materias de distintos niveles(excepto en presencia de prerrequisitos)
I preferencia de horario de los profesores
I compacidad del horario por nivel
I número máximo de horas de clase diarias por nivel
7 / 32
Contenido
El problema
El modelo y el algoritmo
El sistema informático
Los resultados
8 / 32
Algunas definiciones básicas...
I materia: unidad (semestral) para agrupar contenidos quese imparten en una carrera; se organiza en pénsums
I curso: grupo de estudiantes y profesor reunidos para laimpartición de una materia
I un curso puede reunir a estudiantes que toman distintasmaterias
I una materia puede impartirse por medio de varios decursos
I período: unidad temporal para organizar la impartición declases (=una hora en la EPN)
I sesión: cada una de las reuniones semanales de un curso;cada sesión tiene una duración específica
9 / 32
Ejemplo: Carrera Ing. Matemática
10 / 32
Problema de asignación de horarios
Dados:I cursos planificados
I disponibilidad horaria de los profesores
I disponibilidad de aulas
asignar cada sesión de clase a un período y a un aula demanera que se respeten todas las restricciones fuertes ytantas restricciones débiles como sea posible.
11 / 32
Distancias entre cursos y sesiones
La distancia entre dos cursos es:
d(c1, c2) = min |niv(c1, p)− niv(c2, p)| : p ∈ Pc1 ∩ Pc2
donde Pc es el conjunto de pénsums asociados al curso c y niv(c, p)es el nivel de la materia asociada a c en el pénsum p ∈ Pc.La distancia di` entre dos sesiones i, ` ∈ S es la distancia entre suscursos respectivos.
12 / 32
Otros parámetros
I matriz de conflictos entre sesiones
ai` =
1, si di` = 0 o i y ` están a cargo del mismo profesor,0, caso contrario.
I Lik es el conjunto de períodos en los que la sesión i puedeiniciar en el día k
I Nrkj es la cantidad de aulas de tipo r disponibles el períodoj del día k
I ωijk es la penalización por preferencias de horario deprofesor si la sesión i inicia en el período j del día k
13 / 32
Otros parámetros
I matriz de conflictos entre sesiones
ai` =
1, si di` = 0 o i y ` están a cargo del mismo profesor,0, caso contrario.
I Lik es el conjunto de períodos en los que la sesión i puedeiniciar en el día k
I Nrkj es la cantidad de aulas de tipo r disponibles el períodoj del día k
I ωijk es la penalización por preferencias de horario deprofesor si la sesión i inicia en el período j del día k
13 / 32
Otros parámetros
I matriz de conflictos entre sesiones
ai` =
1, si di` = 0 o i y ` están a cargo del mismo profesor,0, caso contrario.
I Lik es el conjunto de períodos en los que la sesión i puedeiniciar en el día k
I Nrkj es la cantidad de aulas de tipo r disponibles el períodoj del día k
I ωijk es la penalización por preferencias de horario deprofesor si la sesión i inicia en el período j del día k
13 / 32
Otros parámetros
I matriz de conflictos entre sesiones
ai` =
1, si di` = 0 o i y ` están a cargo del mismo profesor,0, caso contrario.
I Lik es el conjunto de períodos en los que la sesión i puedeiniciar en el día k
I Nrkj es la cantidad de aulas de tipo r disponibles el períodoj del día k
I ωijk es la penalización por preferencias de horario deprofesor si la sesión i inicia en el período j del día k
13 / 32
Variables de decisión
xirkj =
1, si la sesión i ∈ S es programada
en un aula de tipo r ∈ Ri,para empezar en el período j ∈ Hen el día k ∈ D,
0, caso contrario.
yi` =
1, si existe un cruce entre las sesiones i y `,0, caso contrario.
14 / 32
Variables de decisión
xirkj =
1, si la sesión i ∈ S es programada
en un aula de tipo r ∈ Ri,para empezar en el período j ∈ Hen el día k ∈ D,
0, caso contrario.
yi` =
1, si existe un cruce entre las sesiones i y `,0, caso contrario.
14 / 32
Modelo de PE (1)
min∑i∈S
∑`∈S`>i
γ(di`)yi` +∑i∈S
∑r∈Ri
∑k∈D
∑j∈Lik
ωijkxirkj
s.t.∑r∈Ri
∑k∈D
∑j∈Lik
xirkj = 1, ∀i ∈ S, (1)
∑i∈S
∑`∈S` 6=i
ai`yi` = 0, (2)
∑i∈Sc
∑r∈Ri
∑j∈Lik
xirkj ≤ 1, ∀c ∈ C,∀k ∈ D, (3)
∑i:r∈Ri
∑j:j∈Γij
xirkj ≤ Nrkj, ∀r ∈ R,∀k ∈ D,∀j ∈ H, (4)
15 / 32
Modelo de PE (2)
∑r∈R
xirkj +∑r∈R
∑j∈Ωi`j
x`rkj − 1 ≤ yi` (5)
∀i, ` ∈ S, ` > i,∀k ∈ D,∀j ∈ Lik,
xirkj ∈ 0, 1, ∀i ∈ S, ∀r ∈ R, (6)∀k ∈ D, ∀j ∈ H,
yi` ∈ 0, 1, ∀i, ` ∈ S, ` > i. (7)
16 / 32
Heurística constructiva
La heurística constructiva está basada en un método deinserción secuencial.En cada iteración principal:
I Ordenar aleatoriamente las sesionesI Para cada sesión i ∈ S
I asignar i al mejor período (y aula) posiblesI si i no puede ser asignada a ningún período,
remover sesiones conflictivas jhasta que i pueda ser asignada
17 / 32
Heurística de mejora
Mejorar localmente la solución encontrada por la heurísticaconstructiva
I Para cada par de sesiones i, ` ∈ S× S, si yi` = 1:I remover i y `I reprogramar i y ` al mejor par posible de períodos
18 / 32
Contenido
El problema
El modelo y el algoritmo
El sistema informático
Los resultados
19 / 32
Esquema de funcionamiento
Envío dedatos
Lab. Nacional deCálculo Científico
Reportes deresultados
20 / 32
Datos requeridos
I estructura curricular
I características de aulas y laboratorios
I disponibilidad de aulas
I disponibilidad de horario de los profesores
I configuración de cursos
21 / 32
Estructura curricular
I carrerasI materiasI mallasI prerrequisitos
22 / 32
Aulas
I tipoI capacidadI disponibilidad
23 / 32
Horario de profesores
I disponibilidadI preferencia
24 / 32
Configuración de cursos
I cursosvs. materias
I sesionesI cupoI profesorI cruces
específicos
25 / 32
Reportes
El modelo reporta el horario calculado
I por profesor
I por nivel
I por aula
I condensado (estilo SAEw)
26 / 32
Detalles técnicos
I Modelo de programación lineal entera con variablesbinarias para las asignación de sesiones de clase aperíodos y aulas
I Solución por heurísticas primales (inserción secuencial yde mejoramiento), y por medio del solver SCIP
I Módulo de cálculo implementado en C++
I Base de datos implementada en MySQL
I Interfaces de usuario basadas en PHP
27 / 32
Contenido
El problema
El modelo y el algoritmo
El sistema informático
Los resultados
28 / 32
Test Set
Table : Test Set
Ins. |C| |P| #Pre. #Lect. |S| Var. Cons.
1 26 3 14 30 66 778 182,619
2 45 1 40 58 108 1,827 233,089
3 45 2 36 58 108 1,827 233,089
4 43 4 28 58 113 2,193 371,197
5 32 1 13 58 87 18,152 225,134
6 37 2 26 58 98 21,447 334,512
7 40 4 48 58 104 21,945 300,679
8 37 1 27 58 98 26,774 334,932
9 61 6 65 58 156 39,789 747,881
10 98 8 153 58 241 92,449 1,501,199
11 98 8 81 58 241 92,449 1,501,199
12 98 4 105 58 241 92,449 1,501,199
13 107 8 135 64 260 101,981 1,746,631
14 104 11 110 69 253 126,921 2,325,177
29 / 32
Table : Computational Results: Heuristics
Ins.Constructive Heuristic Improvement Heuristic
Initial Sol. Time Final Sol. Time # iter. Impr. (%) Sol. Time Impr. (%)
1 110.00 0.02 88.33 19.93 963 20% 87.17 4.47 21%
2 353.26 0.44 288.02 259.69 920 18% 278.43 6.46 21%
3 230.83 0.00 183.00 155.92 523 21% 180.33 5.8 22%
4 429.50 0.10 313.17 141.85 629 27% 277.83 4.03 35%
5 321.29 0.00 234.64 87.00 888 27% 219.27 7.42 32%
6 323.00 0.10 172.33 167.14 967 47% 154.17 4.05 52%
7 253.00 0.03 156.00 164.83 672 38% 101.00 5.33 60%
8 363.88 0.29 245.36 133.53 712 33% 216.87 6.72 40%
9 555.50 1.15 463.67 1,637.18 648 17% 450.33 7.41 19%
10 1,259.38 18.77 1,060.33 3,609.40 288 16% 998.26 59.45 21%
11 680.83 13.80 488.67 3,605.94 370 28% 446.17 59.75 34%
12 1,125.07 10.50 1,040.50 3,604.10 256 8% 964.12 59.03 14%
13 1,031.00 31.96 977.67 3,624.29 18 5% 859.50 159.27 17%
14 1,037.05 4.74 844.79 3,601.82 544 19% 744.51 74.98 28%
30 / 32
Table : Computational Results: Gurobi, Scip and Heuristics
Ins.Gurobi SCIP Heuristics
Best sol. LB Gap Best sol. LB Gap Sol. Time
1 81.17 2.20 3,589% 110.33 1.00 10,933% 87.17 24.40
2 256.69 150.60 70% 293.26 127.83 129% 278.43 266.15
3 143.00 109.67 30% 190.50 103.67 84% 180.33 161.72
4 221.50 22.00 907% 340.33 6.00 5,572% 277.83 145.88
5 239.98 28.67 737% 252.81 19.33 1,208% 219.27 94.42
6 48.50 14.00 246% 202.83 11.00 1,744% 154.17 171.19
7 48.00 31.00 55% 133.00 34.00 291% 101.00 170.16
8 150.60 15.11 897% 300.14 11.00 2,629% 216.87 140.25
9 332.67 26.00 1,179% 627.17 11.00 5,602% 450.33 1,644.59
10 1,309.69 167.53 682% - 89.37 - 998.26 3,668.85
11 217.00 135.33 60% - 91.17 - 446.17 3,665.69
12 1,194.10 170.21 602% - 98.43 - 964.12 3,663.13
13 919.67 72.21 1,174% - 70.36 - 859.50 3,783.56
14 1,930.57 10.00 19,206% 2,269.85 2.00 113,392% 744.51 3,676.80
31 / 32
Referencias I
E. Burke, J. Marecek, A. J. Parkers, and H. Rudová.A Branch-and-Cut Procedure for the Udine Course Timetabling Problem.Annals of Operations Research, 194:71–87, 2012.
E. Burke and S. Petrovic.Recent Search Directions in Automated Timetabling.European Journal of Operational Research, 140(2):266–280, 2002.
A. Dorneles, O. C. de Araújo, and L. S. Buriol.A fix-and-optimize heuristic for the high school timetabling problem.Computers and Operation Research, 52:29–38, 2014.
G. Lach and M. Lübbecke.Curriculum Based Course Timetabling: New Solutions to Udine Benchmark Instances.Annals of Operations Research, 194:399–412, 2010.
R. Qu, E. Burke, B. McCollum, L. Merlot, and S. Lee.A Survey of Search Methodologies and Automated System Development for Examination Timetabling.Journal of Scheduling, 12(1):55–89, 2009.
K. Schimmelpfeng and S. Helber.Application of a real-world university-course timetabling model solved by integer programming.OR Spectrum, 29:783–803, 2006.
A. Shaerf.A Survey of Automated Timetabling.Artificial Intelligence Review, 13(2):87–127, 1999.
Gracias por su atención!
32 / 32
