1. Introducción

Entre los mayores problemas de índole operativo que enfrentan día a día las organizaciones, ya sean estas de manufactura o de servicios, está el de calendarización (Pinedo,2016). Los problemas de calendarización se pueden definir como el proceso de toma de decisiones que se ejecuta regularmente para determinar la distribución de los recursos de la compañía a determinadas tareas dentro de un intervalo de tiempo de tal forma que uno o más indicadores de desempeño sean optimizados (Pinedo,2016). La distribución eficiente de estos recursos juega un rol fundamental en la productividad de las organizaciones debido a que, usualmente, los costos de operación suelen ser aproximadamente el 60%del precio de venta de un producto o servicio. Por lo anterior, la reducción de estos costos impacta sustancialmente la competitividad de una organización y su permanencia en el mercado (Hillier & Lieberman, 2010).

Los problemas de calendarización suelen ser muy diversos según el modelo de negocio de las organizaciones, por lo cual, los recursos y tareas pueden adoptar distintas formas. Por ejemplo, los recursos pueden ser maquinarias, personal, materias primas, entre otros, mientras que las tareas pueden ser la carga o descarga de un camión, la limpieza de una bodega, la preparación de un pedido, étc. Si bien es relativamente sencillo describir de manera genérica los problemas de calendarización en empresas de manufactura, no ocurre lo mismo en organizaciones de servicios, debido a la gran heterogeneidad que existe tanto en los tipos de servicios como en los recursos necesarios para producirlos (Blazewicz y col.,2019; Pinedo,2016). Sin embargo, si se acota el tipo de organización sobre la cual se aborda el problema de calendarización, es posible identificar claramente los recursos y tareas que participan del problema. Este trabajo se enfoca particularmente en instituciones de educación superior, más conocidas como universidades.

En la actualidad, las instituciones de educación superior a nivel mundial enfrentan grandes desafíos debido a la crisis económica, la pandemia del SARS-COV-2 y la reducción del presupuesto del Estado destinado a la educación. Este último impactó recientemente a las universidades del Ecuador (El Comercio,2020). Por esta razón se hace necesario que las universidades utilicen de manera eficiente todos los recursos que tienen disponibles, de tal forma que no se afecte negativamente la calidad de la educación brindada a los estudiantes. Si bien existen una gran variedad de problemas que de- ben resolverse en la operación diaria de una universidad, uno particularmente relevante y que suele consumir una cantidad considerable de tiempo es la elaboración de la planificación del periodo académico próximo a iniciar. Los periodos académicos son conocidos en la literatura como semestres (Mühlenthaler,2015).

En Ecuador, la regulación establece que cada institución de educación superior debe ofrecer dos periodos académicos ordinarios al año con una duración máxima de 16 semanas incluyendo las evaluaciones, y hasta dos periodos académicos extraordinarios con una duración máxima de 14 semanas. Para cada uno de los periodos académicos a ofertar, las universidades deben elaborar previamente la planificación académica respectiva junto con los distributivos de la carga de trabajo semanal asignado a cada docente de la institución. Normalmente, la planificación académica requiere el cumplimiento de varias tareas, las que se suelen ejecutar en el siguiente orden:

1. 1. El coordinador, director o gestor académico de la escuela, facultad o carrera, debe pronosticarla demanda que cada materia de la malla curricular tendrá durante el próximo semestre. Esto suele hacerse considerando el número de estudiantes que aprueban las materias que son prerrequisitos así como el número de estudiantes que reprueban la misma materia en el semestre en curso. Normalmente, dependiendo de la calidad del sistema informático de la institución, esta tarea suele ser relativamente sencilla.
2. 2. Una vez que se ha estimado la demanda de cada materia, se determina cuáles materias aperturar (aquellas que cumplen con la demanda mínima para ejecutarse) y cuántos paralelos (secciones)de esta ofertar. Por ejemplo, si una materia tiene una demanda estimada de 60 estudiantes, entonces esta se ofertará con dos secciones/paralelos, debido a que normalmente las aulas no tienen capacidad para albergar más de 30 o 40 alumnos al mismo tiempo. Esto puede variar de una institución a otra.
3. 3. Dadas las materias a ofertar junto con la cantidad de paralelos que se aperturarán para cada una de ellas, el siguiente paso consiste en elaborar los horarios de clases que se publicarán a los estudiantes. Este paso es el más crítico debido a la cantidad de decisiones que deben tomarse así como a la cantidad de restricciones, limitaciones o condiciones que deben respetarse para que sea aprobado. Según la experiencia profesional de los autores, esta tarea es realizada manualmente por una o máximo dos personas en la mayoría de las instituciones nacionales siendo, por esta razón, una de las que más tiempo consume. Dependiendo del tamaño de la unidad académica involucrada y el nivel de integración de esta planificación con la de las otras unidades académicas de la institución, el tiempo promedio de procesamiento de esta tarea oscila entre las2 semanas y los 2 meses, sin considerar los errores que puedan presentarse.
4. 4. Una vez construidos los horarios de clases, estos son entregados a la secretaría de la unidad académica para que se asignen las aulas y se carguen en el sistema informático de la institución. En esta etapa, la asignación de aulas es otro problema operativo que debe resolverse. Tradicionalmente se lo aborda por prueba y error. A medida que se ingresa la información en el sistema, si este reporta que un aula ya está asignada, entonces se escoge otra y se espera que se permita la asignación. Naturalmente esto ocasiona una pérdida de tiempo por el número de intentos que deben realizarse hasta asignar un aula.
5. 5. Tras el ingreso de la planificación académica al sistema, este se encuentra públicamente disponible para que los estudiantes puedan escoger en qué materias inscribirse según su malla curricular.

Conforme al proceso anterior, la elaboración de la planificación académica no es una tarea fácil y requiere lidiar con dos problemas críticos: la elaboración de los horarios de clases y la asignación de las aulas según el horario construido. El último problema, el de asignación, fue recientemente abordado por los autores en Saltos y Benavides (2019). En él, asumiendo que los horarios de clases ya se encuentran disponibles, proponen un modelo de programación lineal entera para asignar las aulas de clases a las distintas materias considerando restricciones tales como el cruce de horarios y la capacidad de las aulas. La métrica de desempeño que se optimiza consiste en que la asignación de las aulas considere el tipo de contenido que se imparte en la materia de tal manera que la infraestructura favorezca su ejecución. Por ejemplo, las aulas que tienen escritorios con toma corrientes brindan facilidades en materias tales como estadística y programación, debido a que los estudiantes suelen llevar sus computadores personales a estas cátedras.

Con base en lo descrito anteriormente, la creación de los horarios de clases y la asignación de aulas son tareas complicadas que pueden consumir una cantidad sustancial de tiempo en su ejecución, en especial, si se realizan manualmente. En el presente trabajo de investigación, se propone un nuevo modelo de programación lineal entera que permita, de manera simultánea, construir los horarios de clases junto con la asignación de las aulas, de tal forma que se automaticen estos dos pasos del proceso. Los principales beneficios de esta automatización son: (1) se eliminan los errores de calendarización, (2) se reduce el tiempo para completar el proceso de planificación, (3) se obtienen horarios de clases de mejor calidad en comparación con aquellos elaborados manualmente, (4) se mejora el nivel de utilización de las aulas, y (5) para la institución de educación superior del caso de estudio, la implementación de este modelo permitirá distribuir la carga de trabajo del personal hacia tareas que forman parte de las funciones sustantivas de la organización, ya sean de docencia, investigación o vinculación.

El resto del artículo está estructurado de la siguiente manera: la Sección2presenta los fundamentos teóricos de los problemas de calendarización en educación superior así como los trabajos recientes más relevantes con el problema abordado. En la Sección3se describen y explican los principales componentes del problema del caso de estudio junto con el modelo de programación lineal entera propuesto para su resolución, mientras que la Sección4presenta y discute los resultados obtenidos al resolver computacionalmente este modelo. Finalmente, la Sección5concluye este artículo y presenta algunas ideas para trabajo futuro.

2. Marco teórico

En esta sección se presentan los fundamentos teóricos que rigen los problemas de calendarización, en especial aquellos que se originan de la operación semestral de las instituciones de educación superior. Posteriormente, se explican brevemente los principales trabajos reportados en la literatura que tiene relevancia con el problema abordado en este artículo.

2.1. Fundamentos de los problemas de calendarización

Según Wren (1995), un problema de calendarización se define como la asignación, sujeta a ciertas restricciones, de los recursos a determinados objetos ubicados en un espacio y tiempo específicos, detal forma que se optimice un conjunto deseado de indicadores. El valor de los horarios que se obtienen con la resolución de estos problemas está determinado usualmente por las siguientes métricas(Lindahl y col., 2018):

• Agilidad, entendida como la capacidad de responder ante los cambios y modificar rápidamentela calendarización sin alterarla significativamente.

• Calidad, entendida como un buen ambiente de trabajo propiciado por la calendarización construida.

• Costo, entendido como el uso eficiente de los recursos de la organización.

La optimización de la calidad es el enfoque tradicional a la hora de resolver los problemas de calendarización. La meta es obtener un horario factible de alta calidad al establecer un conjunto de restricciones blandas, restricciones que no necesariamente deben cumplirse pero es ideal que se cumplan. La calidad del horario viene determinada en función del nivel de violaciones existentes sobre estas restricciones (Lindahl y col., 2018).

Por otra parte Babaei y col. (2015) y Pinedo (2016), establecen que existen varios tipos de problemas de calendarización. Una taxonomía relevante con el presente trabajo de investigación se muestra en la Figura 1. Como se verá en la Sección 3, el problema que se corresponde con la presente investigación es el Problema de Calendarización de Cursos Universitarios (UCTTP por sus siglas en inglés). El objetivo de estos problemas es encontrar un método adecuado para distribuir un conjunto de eventos en espacios de tiempo y salas predefinidos (Babaei y col., 2015). Para lograr esto varias decisiones deben considerarse:

• la asignación de los alumnos a distintas cohortes,

• la designación de los profesores de cada materia,

• la hora y el día que se dictará cada materia durante la semana,

• la asignación de las aulas de clase.

Las reglas y suposiciones que rigen estas decisiones varían de acuerdo con cada institución, su estructura y disponibilidad de recursos (Daskalaki & Birbas, 2005). En consecuencia, no existe un modelo de calendarización que pueda ser aplicado en todas las circunstancias posibles (Asratian & deWerra,2002), lo cual también dificulta que los investigadores puedan comparar sus modelos debido a que resuelven problemas diferentes (Lindahl y col., 2018).

A pesar de las grandes diferencias que pueden existir en los problemas de calendarización en distintas universidades, es posible observar un conjunto de elementos comunes a todos ellos (Babaei y col.,2015; Carter & Laporte, 1997; Feizi-Derakhshi y col., 2012; Hernández y col., 2008). Estos son:

• Los objetos o eventos tales como los profesores, los alumnos y los cursos o asignaturas.

• Los intervalo de tiempo en los cuales se deben programar los eventos.

• Los recursos que son utilizados por los eventos, tales como aulas, equipamiento, intervalos de tiempo, entre otros.

• Las restricciones que se deben satisfacer para considerar que la calendarización sea válida.

• Conflictos, entendidos como el cruce de horas entre dos o más eventos. Por ejemplo, un profesor no puede dictar dos asignaturas en el mismo intervalo de tiempo.

Las restricciones en los problemas de calendarización suelen ser de dos tipos, duras y blandas. Las restricciones duras son condiciones que deben ser satisfechas para que se acepte el horario como válido. Las restricciones blandas son aquellas condiciones que no es necesario que se cumplan pero es deseable que suceda. Las restricciones blandas se utilizan para formular la función objetivo del problema y son el principal indicador de calidad de una calendarización.

Entre las restricciones duras más comunes están:

• Un profesor no puede asistir a dos clases al mismo tiempo.

• Una materia no se puede enseñar en dos clases diferentes al mismo tiempo, salvo existan más de una sección para dicha materia.

• Un profesor enseña una única materia en una única aula en cada intervalo de tiempo.

• Para intervalo de tiempo diario, en cada aula sólo un grupo de estudiantes y un profesor pueden asistir.

• Un profesor enseña a un único grupo de estudiantes en cada intervalo de tiempo diario.

• Existe un conjunto de asignaturas que deben dictarse en determinados intervalos de tiempo.

• La capacidad de las aulas de clases debe ser proporcional a la cantidad de alumnos matriculados en una determinada materia.

• Los profesores pueden expresar sus preferencias sobre determinados intervalos de tiempo para dictar sus clases.

• Los profesores pueden solicitar un aula especial para una materia determinada.

• Los cursos se deben programar de tal forma que se minimicen los intervalos de tiempo vacíos (huecos) tanto para los docentes como para los estudiantes.

• Los cursos deben programarse de tal forma que se evite, en la medida de lo posible, el uso de intervalos de tiempo nocturnos.

• Debe existir un intervalo de tiempo para el almuerzo.

• El número máximo de horas de clases que deben atender ya sea alumnos o profesores es un valor predeterminado, por ejemplo, cuatro.

• Los horarios de clases propuestos deben evitar que tanto alumnos o profesores asistan al campus por una única clase.

Con base en lo anterior, el problema de calendarización de cursos universitarios puede definirse de la siguiente manera:

Definición 1

Dado un conjunto de materias, de aulas, de intervalos de tiempo, de profesores, y de mallas curriculares, el problema de calendarización de cursos universitarios se define como el proceso de asignar la tupla materia-profesor-aula a un intervalo de tiempo de tal forma que se cumplan todas las restricciones duras y se optimice el nivel de satisfacción de las restricciones blandas.

Los problemas de calendarización en casi todas sus formas y variantes pertenecen a la clase NP completo, es decir, que si todas las posibles combinaciones de soluciones fuesen examinadas, el tiempo para resolver problemas de tamaño razonable crecería exponencialmente (Daskalaki & Birbas, 2005; Daskalaki y col., 2004).

2.1 Trabajos recientes

Los problemas de calendarización orientados a instituciones educativas han sido estudiados desde varios años atrás, por ejemplo Gotlieb (1963), por lo cual es un área de investigación multidisciplinaria bien establecida y madura, donde convergen disciplinas como la Investigación de Operaciones, el Aprendizaje de Máquinas y las Ciencias de la Computación. Dada la importancia que tienen estos problemas en las operaciones de las instituciones educativas, varios trabajos se han publicado recientemente en la literatura científica (Akkan & Gülcü,2018; Asratian & de Werra,2002; Babaei y col., 2015; Carter & Laporte,1997; Daskalaki y col.,2004; Domenech & Lusa,2016; Feizi-Derakhshi y col., 2012; Yasari y col.,2019), por mencionar algunos. Dado que Saltos y Benavides (2019) presentan una breve revisión de la literatura relevante con este tema, en esta sección actualizaremos dicha revisión con aquellos trabajos que han sido publicados entre el 2019 y 2021.

Leite y col. (2019) proponen una nueva versión del recocido simulado para resolver el problema de calendarización de cursos universitarios pero enfocado en los horarios según los cuales se tomarán los exámenes. El enfoque principal de este trabajo no es la resolución de un caso específico en alguna universidad, sino más bien proponer un nuevo algoritmo que resuelva más rápido y con mejor precisión distintas instancias de prueba disponibles en la literatura. En la misma línea, Rezaeipanah y col. (2019) proponen un nuevo algoritmo genético paralelizado combinando los algoritmos de computación evolutiva, computación en paralelo y búsqueda local. Como resultado obtienen una nueva heurística que muestra tener un excelente rendimiento al resolver instancias diseñadas para competencias a nivel mundial.

De manera similar, Ekanayake y col. (2019) realizan una comparación exhaustiva de cuatro métodos cuantitativos para resolver tanto el problema de calendarización de cursos universitarios como el de toma de exámenes. Específicamente, comparan los algoritmos genéticos, la coloración en grafos, distintas heurísticas y la búsqueda local iterativa. Estos métodos se utilizan en distintos conjuntos de prueba determinando así cuáles funcionan mejor para cada tipo de problema. De igual manera, Elliot y col. (2020) desarrollan una nueva heurística basada en algoritmos genéticos e inteligencia computacional para resolver el problema de calendarización universitario. El objetivo del trabajo es disponer de algoritmos heurísticos rápidos y eficientes que permitan obtener soluciones factibles del problema con una calidad adecuada en un marco razonable de tiempo.

Como se puede apreciar, el común denominador de los trabajos anteriormente mencionados es el desarrollo de nuevos algoritmos heurísticos y metaheurísticos que sean capaces de resolver de manera rápida y eficiente varios problemas de calendarización estandarizados. La calidad de los algoritmos propuestos es evaluada al utilizarlos para resolver varias instancias de prueba disponibles en la literatura científica, por ejemplo, aquellas desarrolladas en Di Gaspero y col. (2007).

Entre los trabajos más recientes donde se resuelve un caso real aplicado de calendarización está el desarrollado por Romo-Franco y col. (2019) y Yáñez (2020). En el primero, se realiza una comparativa entre modelos matemáticos formulados con una sola función objetivo con aquellos que contienen varias de ellas. Los modelos propuestos son utilizados para resolver varias instancias de prueba gene- radas con datos reales del Instituto Tecnológico de León, en México. Los resultados demostraron que las formulaciones multiobjetivo producen calendarizaciones de mejor calidad que aquellas que utilizan una sola función objetivo. Por otra parte, Yáñez (2020) propone una herramienta automatizada de calendarización para la generación de los horarios de clases del Departamento de Ingeniería Civil de la Universidad de Chile, considerando al mismo tiempo, las fechas de evaluación de las materias. Los beneficios de su desarrollo apuntan a balancear de manera adecuada la carga de las evaluaciones que toman los profesores durante el semestre, la cual suele hacerse sin considerar la cantidad de materias que los estudiantes cursan, provocando que en algunos casos estos deban rendir hasta tres pruebas distintas en un mismo día.

Con base en los párrafos antecesores, la resolución del problema de calendarización de cursos universitarios sigue vigente en la actualidad, con varios estudios y revisiones de literatura publicados hasta la fecha, por ejemplo Hosny (2018), Tan y col. (2021) y Vrielink y col. (2019). Así mismo se observa que uno de los enfoques principales de las nuevas publicaciones es el computacional, es decir, buscan proponer nuevos y más veloces algoritmos que permitan resolver el problema en el menor tiempo posible y con una calidad aceptable. En el presente trabajo de investigación usamos un enfoque diferente, buscamos incorporar a la modelación nuevos elementos en la generación de estos horarios, tales como la afinidad de las aulas con las cátedras, las preferencias de los docentes, sus habilidades para dictar determinadas materias, entre otros.

3. Un nuevo modelo de calendarización de cursos universitarios

En esta sección se presenta una descripción detallada del problema del caso de estudio que se aborda en esta investigación, para posteriormente, formular un nuevo modelo de optimización matemática que permita darle una solución eficiente.

3.1. Descripción del problema

El caso de estudio que se aborda en la presente investigación corresponde al de la Escuela de Computación y Telecomunicaciones de la Facultad de Ingeniería de una prestigiosa institución privada de educación superior localizada en Ecuador. La descripción del problema es como sigue:

La institución, conforme a los reglamentos, ofrece dos periodos académicos ordinarios y un periodo académico extraordinario al año. Para cada uno de estos periodos, la dirección de la Escuela realizala predicción de la demanda de cada materia conforme a las estadísticas del sistema informático y la experiencia del director. Una vez estimada la demanda, la tarea de construir los horarios de clases para cada periodo académico es encargada a un único profesor de la Escuela, quien usualmente requiere entre 4 y 6 semanas para completarla. Con la finalidad de evitar confusiones, a continuación se explicará la terminología y algunos elementos importantes de dicha institución con respecto a la elaboración de la planificación académica.

• Dependiendo de la demanda, cada materia se puede ofrecer con una o más secciones que se pueden dictar en paralelo. Por simplicidad la institución los llama paralelos.

• La institución opera con dos tipos de profesores: profesores de tiempo completo y profesores de tiempo parcial.

• Cada profesor de tiempo completo debe dictar cierta cantidad de paralelos al año según lo establecido en su contrato.

• Los profesores de tiempo parcial son de libre contratación y remoción.

• La universidad dicta clases de lunes a jueves en modalidad espejo. Esto quiere decir que las cátedras que se dictan el lunes, se replican el miércoles mientras que las del martes, el jueves.

• Los exámenes se toman en el mismo horario que son programadas las cátedras, por cual, no es necesario construir una calendarización a parte para la toma de evaluaciones.

Las siguientes restricciones, establecidas por el Vicerrectorado Académico, deben cumplirse para que el horario de clases sea aprobado:

1. 1. A cada profesor de tiempo completo se le deben asignar tantos paralelos como lo haya dispuesto la dirección académica.
2. 2. Si se decide contratar los servicios de un profesor de tiempo parcial, se le deben asignar por los menos dos paralelos y como máximo tres.
3. 3. Para cada materia, se deben aperturar la cantidad de paralelos estimados por la dirección académica.
4. 4. No se puede asignar un paralelo cuya cantidad estimada de alumnos exceda la capacidad del aula.
5. 5. No se puede asignar un paralelo en un bloque (combinación día-hora) que no satisfaga la disponibilidad horaria y la pertinencia de los docentes, así como la jornada en la que se puede dictarla materia.
6. 6. Para cada aula de clase y por cada bloque, el aula no puede tener asignada dos o más paralelos, puesto que esto provocaría un cruce de horas impidiendo la ejecución normal de las actividades de docencia.
7. 7. Cada paralelo debe tener asignado un aula de clase en uno de los posibles bloques preestablecidos por la dirección.
8. 8. Se debe evitar la doble asignación de los recursos, es decir, un mismo profesor no puede estar asignado dos veces al mismo bloque.
9. 9. Se debe evitar la doble asignación de los recursos, es decir, un mismo profesor no puede estar asignado dos veces al mismo bloque.
10. 10. Se debe repartir de forma equitativa la carga académica a lo largo de la semana. Por ejemplo, si se abren seis paralelos de matemáticas, tres deben ser los lunes y tres los martes.

Adicionalmente, se desea satisfacer, en la medida de lo posible, las siguientes restricciones blandas:

• Se desea minimizar el uso de aulas que no pertenecen a la Escuela de Computación y Telecomunicaciones, pues esto implicaría que tanto los estudiantes como los profesores tengan que recorrer mayores distancias al cambiarse de una clase a otra.

• Se desea asignar a cada cátedra un aula que, de cierta manera, favorezca la presentación de los temas abordados. Por ejemplo, las cátedras relacionadas con electrónica deberían ser dictadas, de preferencia, en el Laboratorio de Electrónica. Las cátedras que requieren el uso constante de los proyectores y de los computadores personales de los estudiantes deberían asignarse al Laboratorio Cisco.

• Se desea que el Laboratorio Cisco tenga un mayor nivel de utilización en la jornada nocturna en contraste con las aulas tradicionales.

• Se desea que la asignación de los profesores a las cátedras se realice considerando la habilidad que estos tienen para dictarlas. Esta habilidad es estimada con base en los resultados de las evaluaciones docentes de periodos académicos anteriores.

Considerando tanto las restricciones duras como las blandas, en la siguiente sección se presenta la formulación del modelo matemático que permite resolver de forma simultánea tanto el problema de asignación de aulas como el de calendarización de los cursos.

3.2. Formulación del modelo matemático

Con base en la problemática descrita en la sección anterior, se procede a formular el modelo de programación lineal entera mixta que permitirá obtener los horarios de clases para la unidad académica en estudio. Los conjuntos (objetos/entidades) que forman parte del modelo son los siguientes:

• A es el conjunto de aulas disponibles.

• H es el conjunto con los bloques de horas disponibles para dictar las asignaturas.

• P es el conjunto de profesores disponibles en la unidad académica.

• D es el conjunto de días de la semana.

• I es el conjunto de materias o cátedras ofertados en el periodo académico.

• J es el conjunto de paralelos disponibles.

• N es el conjunto de niveles (semestres) de la malla curricular.

• C es el conjunto de carreras que se ofertan en la unidad académica.

Los parámetros del modelo (datos conocidos con anticipación) son los siguientes:

• ParMat_i es la cantidad de paralelos que se van a ofertar por cada materia i ∈ I.

• Jornadai,h toma el valor de 1 si la materia i ∈ I se puede dictar en la hora h ∈ H, toma el valor de 0 en caso contrario.

• CapAula_a es la capacidad del aula a ∈ A.

• AlumMat_i,j es la cantidad estimada de alumnos matriculados para la materia i ∈ I en el paralejo j ∈ J.

• DispHorProf_p,h,d toma el valor de 1 si el profesor p ∈ P está disponible en la hora h ∈ H el día d ∈ D, toma el valor de 0 en caso contrario.

• AfinP_p,i toma el valor de 1 si el profesor p ∈ P tiene afinidad/pertinencia para dictar la cátedra i ∈ I, toma el valor de 0 en caso contrario.

• HabP_p,i es la habilidad estimada que tiene el profesor p ∈ P para dictar la cátedra i ∈ I.

• TipoProf_p toma el valor de 1 si el profesor es de tiempo parcial, toma el valor de 0 en caso contrario.

• CantMatProf_p es la cantidad máxima de paralelos que se le deben asignar al profesor p.

• MatCar_i,c toma el valor de 1 si la materia i ∈ I pertenece a la carrera c ∈ C, 0 en caso contrario.

• MatNiv_i,n toma el valor de 1 si la materia i ∈ I pertenece al nivel n ∈ N, 0 en caso contrario.

• Fact_i,d^h,p toma el valor de 1 si la materia i puede ser dictada el día d en el bloque h por el profesor p, 0 en caso contrario.

• CantMat_c,n es la cantidad de materias que tiene la carrera c en el nivel n.

• CostAula_i,a es el costo de utilizar el aula a ∈ A para dictar la materia i ∈ I.

• CostBloque_d,h es el costo de dictar una cátedra en el día d ∈ D a la hora h ∈ H.

De los parámetros anteriores, hay cuatro que no son directos de entender. Como se mencionó anteriormente, la habilidad de un profesor es un valor numérico, usualmente entre 0 y 100, que se obtiene de las evaluaciones docentes que le han efectuado en periodos académicos previos. Otro parámetro similar es la afinidad. En Ecuador, la legislación establece que para que un profesor dicte una cátedra, su título de cuarto nivel (maestría o doctorado) debe ser afín o pertinente con la cátedra. Esto quiere decir que si un profesor cuenta con un MBA no es apto/afín para dictar la cátedra de Optimización. La estimación de este parámetro no es un problema porque la dirección académica ya cuenta con el expediente de los docentes en el que se incluye para qué cátedras son afines.

Los otros dos parámetros que restan por explicar son el costo de utilización de un aula y el costo de utilización de un bloque. El primero motiva que cada materia sea asignada al aula cuya infraestructura favorece su dictado, mientras que el segundo busca eliminar los “huecos” entre materias de los horarios generados. Ambos parámetros son cuantitativos y estimados de manera subjetiva con base en la experiencia de los autores.

Con base en todo lo anterior, las variables de decisión¹ del modelo de optimización son:

Notar que el conjunto P contiene tanto a los profesores de tiempo completo como de tiempo parcial, por lo cual el parámetro TipoProf_p permite diferenciar el tipo de relación contractual del docente. Con base en esto, la variable binaria Y_p solo se genera si el profesor p es de tiempo parcial (TipoProf_p =1) reduciendo así la presencia de variables de decisión innecesarias. También hay que resaltar queTipoProf_p = 1 no implica que Y_p = 1 debido a que no es obligación contratar a todos los profesores de tiempo parcial de la planta.

De aquí en adelante, salvo se indique lo contrario, se entenderá que i ∈ I, j ∈ J, h ∈ H, d ∈ D, p ∈ P, a ∈ A, c ∈ C y n ∈ N. El modelo de programación lineal entera mixta que permite resolver el problema de calendarización de cursos universitarios para el caso de estudio es:

s.t

La ecuación (1) es la función objetivo del modelo matemático cuyo fin es lograr que se satisfagan de la mejor manera posible las restricciones blandas del problema, es decir, que los profesores sean asignados a las cátedras que mejor dictan, que las cátedras sean asignadas a las aulas cuya infraestructura les favorece y que no hayan huecos en la programación. Por otro lado, las ecuaciones (2) y (3) garantizan, en conjunto:

• Si el profesor p de tiempo parcial (TipoProf_p = 1) es contratado (Y_p = 1), se le asignen como mínimo dos paralelos y como máximo la cantidad de paralelos especificada en el parámetro CantMatProf_p.

• Si el profesor p de tiempo parcial (TipoPro_fp = 1) no es contratado (Y_p = 0), no se le asignen paralelos.

Estas restricciones solo afectan a los profesores de tiempo parcial, por lo cual la condición TipoProf_p =1 garantiza que se generen solo para estos profesores reduciendo así la cantidad de ecuaciones del modelo.

De manera similar, la ecuación (4) garantiza que los profesores de tiempo completo reciban exactamente la cantidad de paralelos indicada por el parámetro CantMatProfp. Para el caso de estudio puntual de este trabajo, los profesores de tiempo completo tienen una carga de cinco o seis paralelos por periodo mientras que los de tiempo parcial mínimo dos y máximo 3.

Por otro parte, la restricción (5) asegura que se aperturen la cantidad de paralelos necesarios para cada materia conforme con la estimación de la demanda, mientras que la restricciones (6) y (7) impiden que se exceda la capacidad de las aulas y se respete la factibilidad horaria, respectivamente. En el mismo sentido, las ecuaciones (8) - (12) garantizan que no haya cruce de horarios ni dobles asignaciones de los recursos tanto para los docentes, las aulas, los paralelos, las materias de las mismas carreras/niveles y los bloques, respectivamente.

En todo horario de clases, no es recomendable que la carga académica esté concentrada en uno o dos días de la semana. Para evitar esto, las restricciones (13) y (14) garantizan que haya una distribución equitativa de la carga académica semanal. Finalmente, las ecuaciones (15), (16) y (17) son condiciones de sentido común que deben satisfacerse así como también indican el dominio de las variables de decisión.

4. Experiencia computacional y análisis de los resultados

En esta sección se presentan las características de la instancia que representa el caso estudio aborda- do en esta investigación. Luego se explica la implementación computacional del modelo matemático junto el análisis de los resultados obtenidos.

4.1. Características de la instancia

A la fecha de elaboración del modelo matemático propuesto en el presente artículo, la Escuela de Computación y Telecomunicaciones contaba con los recursos descritos en la Tabla1. La cantidad de paralelos que se aperturan por cada materia es variable. Históricamente, la cátedra de Matemáticas I suele ofertar entre 5 y 7 paralelos en el primer periodo académico ordinario (PAO) del año mientras que este número disminuye a 2 ó 3 para el segundo PAO. La mayoría de las cátedras de semestres superiores suelen ofertar como máximo un paralelo por PAO. Bajo condiciones normales de demanda, la Escuela oferta entre 30 y 45 paralelos por periodo académico. La capacidad de las aulas disponibles, las materias y la cantidad de paralelos que deben aperturarse para el PAO en planificación se muestra en la Tabla2.

De manera similar se dispone de la información para los demás parámetros que se requieren en la resolución del modelo matemático, sin embargo, por la magnitud de dichas tablas, no se muestran en este documento.

4.2. Análisis de los resultados

Para la implementación computacional de un modelo de optimización matemático existen varias alternativas. Una de ellas consiste en utilizar un modelizador. En el mercado existen varias opciones, entre las más conocidas están GAMS², AMPL³ y AIMMS⁴. En este trabajo se decidió utilizar AIMMS debido a las varias ventajas que ofrece sobre las demás, entre las que destacamos a continuación:

• AIMMS provee una interfaz de usuario altamente gráfica que permite ingresar los modelos matemáticos con el mínimo de conocimientos previos sobre programación. Por lo cual, no requiere un extenso aprendizaje de una sintaxis específica como en los demás modelizadores⁵

• AIMMS proporciona una interfaz gráfica intuitiva para mostrar los resultados de los modelos matemáticos de varias formas: tablas, figuras, gráficos de barras, entre otros. Los demás requieren de programación adicional para exportar los resultados de manera amigable.

• A pesar de que todos los modelizadores proporcionan licencias académicas, AIMMS la ofrece con el totalidad de las funcionalidades y sin restricciones de manera gratuita. Se la puede solicitar por medio de su página web y esta valida el estatus académico por medio de la conexión IP del campus universitario al que pertenece el solicitante. No se requiere el envío de documentación adicional.

Una vez seleccionada la herramienta computacional, se procedió a implementar el modelo en AIMMS 4.68 y a resolverlo con el solver IBM-CPLEX 12.9. El tiempo total de cómputo requerido para obtener una solución óptima fue de 10.7 segundos. Una muestra de los resultados obtenidos se aprecia en la Tabla 3.

Los horarios de clases obtenidos con el modelo matemático arrojaron los siguientes beneficios o indicadores de calidad:

1. 1. l nivel de utilización del aula G-202, la más grande y equipada de la escuela subió del 30% al 75%, de tal manera que la mayoría de las cátedras de ciencias físicas y matemáticas se dictan en dicha aula. Para evitar el desgaste de sus instalaciones, su uso se limitó durante la jornada nocturna.
2. 2. El nivel de utilización de las aulas G-201 y G203, las cuales se encuentran al frente del aula G-202, subieron en similar medida. Esto reduce la movilización de los estudiantes o de los profesores entre aulas lejanas.
3. 3. El nivel de utilización del Laboratorio CISCO aumentó un 100 % durante la jornada matutina, dada su idoneidad para el dictado de cátedras que requieren el uso constante de computadoras. Anteriormente, este pasaba desocupado en dicha jornada, siendo principalmente utilizado en la jornada nocturna.
4. 4. La satisfacción de los docentes con la asignación de los horarios de clases fue del 90 %, la cual es una mejora sustancial con respecto al indicador anterior (30%). Esto se debe a que ahora se consideran sus preferencias horarias para el dictado de sus cátedras, se reparte equitativamente la carga en la semana y no dictan más de 3 asignaturas consecutivas antes o después del almuerzo.
5. 5. Con respecto a la contratación de profesores de tiempo parcial, conforme a los resultados del modelo, se optó por no contratar a dos de los doce candidatos posibles. Esto puede deberse ya sea a problemas de afinidad o que su jornada no se ajuste con la dispuesta para el dictado de las materias.

Por otra parte, el tiempo de resolución del problema fue menor a dos minutos, lo que manualmente requería semanas de trabajo. Con esta reducción de tiempo, la dirección académica puede fácilmente actualizar el horario si aparecen restricciones o condiciones de último minuto. Esto quiere decir que el modelo favorece la ejecución de análisis ¿qué pasaría si? Los resultados de estos análisis permiten determinar cuáles recursos son críticos en la planificación académica.

5. Conclusiones y recomendaciones

En el presente trabajo de investigación se propuso un nuevo modelo de programación lineal entera para resolver de forma simultánea el problema de calendarización de cursos universitarios en el caso de estudio particular de la Escuela de Computación y Telecomunicaciones de una institución de educación superior domiciliada en Ecuador. Las principal contribución de este modelo con respecto a otros existentes en la literatura radica en la solución holística del problema considerando tanto las decisiones de asignación de recursos (aulas y profesores) como las de programación horaria de manera simultánea en un único modelo matemático. Así mismo, la función objetivo incorpora el cumplimiento de algunas restricciones blandas deseadas por la administración académica. Todo esto con el mínimo tiempo de ejecución posible, permitiendo así actualizar la planificación de forma eficiente ante cambios de último momento en el entorno, como por ejemplo, la renuncia de un profesor.

Como trabajo futuro se pueden considerar la integración horizontal total del modelo con las demás unidades académicas de la facultad o de la institución. Este es un trabajo de suma importancia dado que existen profesores o aulas que se comparten con otras unidades académicas. Adicionalmente, existen materias, como las de idiomas, que no se planifican en concordancia con los horarios de las demás facultades, lo que suele complicar el registro de los alumnos en estas materias. Un modelo de optimización integrado con el centro de idiomas permitiría producir una planificación académica que brinde mejores oportunidades de registro a los estudiantes que las que existen actualmente.

6. Referencias

Akkan, C. & Gülcü, A. (2018). A bi-criteria hybrid Genetic Algorithm with robustness objective for the course timetabling problem. Computers & Operations Research, 90, 22-32.

Asratian, A. S. & de Werra, D. (2002). A generalized class–teacher model for some timetabling pro blems. European Journal of Operational Research, 143(3), 531-542.

Babaei, H., Karimpour, J. & Hadidi, A. (2015). A survey of approaches for university course timeta bling problem. Computers & Industrial Engineering, 86, 43-59.

Blazewicz, J., Ecker, K., Pesch, E., Schmidt, G. & Weglarz, J. (2019). Handbook on Scheduling. Springer.

Carter, M. W. & Laporte, G. (1997). Recent developments in practical course timetabling. International Conference on the practice and theory of Automated Timetabling, 3-19.

Daskalaki, S. & Birbas, T. (2005). Efficient solutions for a university timetabling problem through integer programming. European Journal of Operational Research, 160(1), 106-120.

Daskalaki, S., Birbas, T. & Housos, E. (2004). An integer programming formulation for a case study in university timetabling. European Journal of Operational Research, 153(1), 117-135

Di Gaspero, L., McCollum, B. & Schaerf, A. (2007). The Second International Timetabling Competition (ITC-2007): Curriculum-based course timetabling (Track 3) (inf. téc.). Technical Report QUB- IEEE-ITC2007.

Domenech, B. & Lusa, A. (2016). A MILP model for the teacher assignment problem considering teachers’ preferences. European Journal of Operational Research, 249(3), 1153-1160.

Ekanayake, T. W., Subasinghe, P., Ragel, S., Gamage, A. & Attanayaka, S. (2019). Intelligent Timetable Scheduler: A Comparison of Genetic, Graph Coloring, Heuristic and Iterated Local Search Algorithms. 2019 International Conference on Advancements in Computing (ICAC), 85-90.

El Comercio. (2020). Corte Constitucional emite sentencia para recorte del presupuesto de universidades.https://www.elcomercio.com/actualidad/corte-constitucional-reduccion-presupuestaria-universidades.html

Elliot, M., Gbenga, F. S. & Mnisi Emmanuel, J. (2020). Enhanced Heuristic Teaching Timetabling Al- gorithm Using Genetic algorithm. International Journal of Scientific & Technology Research, 9.

Feizi-Derakhshi, M.-R., Babaei, H. & Heidarzadeh, J. (2012). A survey of approaches for university course timetabling problem. Proceedings of 8th International Symposium on Intelligent and Manufacturing Systems, 307-321.

Gotlieb, C. (1963). The construction of class-teacher timetables. IFIP Congress, 62, 73-77.

Hernández, R., Miranda, J. & Rey, P. A. (2008). Programación de horarios de clases y asignación de salas para la Facultad de Ingeniería de la Universidad Diego Portales mediante un enfoque de programación entera. Revista Ingeniería de Sistemas, 22.

Hillier, F. & Lieberman, G. (2010). Introducción a la Investigación de Operaciones (9.a ed.). McGraw-Hill.

Hosny, M. (2018). Metaheuristic Approaches for Solving University Timetabling Problems: A Review and Case Studies from Middle Eastern Universities. International Conference Europe Middle East & North Africa Information Systems and Technologies to Support Learning, 10-20.

Leite, N., Melício, F. & Rosa, A. C. (2019). A fast simulated annealing algorithm for the examination timetabling problem. Expert Systems with Applications, 122, 137-151.

Lindahl, M., Mason, A. J., Stidsen, T. & Sørensen, M. (2018). A strategic view of University Timeta- bling. European Journal of Operational Research, 266(1), 35-45.

Mühlenthaler, M. (2015). Fairness in Academic Course Timetabling. Springer

Pinedo, M. (2016). Scheduling (Vol. 29). Springer.

Rezaeipanah, A., Abshirini, Z. & Zade, M. B. (2019). Solving University Course Timetabling Problem Using Parallel Genetic Algorithm. International Journal of Scientific Research in Computer Science and Engineering, 7(5).

Romo-Franco, M., Carpio, M., Ortiz-Aguilar, L., Soria-Alcaraz, J. A., Puga, H., Lino, C. & Mancilla, L. E. (2019). Comparativa entre algoritmos Mono y Multi-objetivo aplicados al problema de calendarización de horarios universitarios. Programación Matemática y Software, 11(1).

Saltos, R. & Benavides, L. (2019). Formulación de un modelo de programación lineal entera para la asignación de aulas de clases en una Institución de Educación Superior. REVISTA CIENTÍFICA ECOCIENCIA, 6(6), 1-21

Tan, J. S., Goh, S. L., Kendall, G. & Sabar, N. R. (2021). A survey of the state-of-the-art of optimisation methodologies in school timetabling problems. Expert Systems with Applications, 165, 113943.

Vrielink, R. O., Jansen, E., Hans, E. W. & van Hillegersberg, J. (2019). Practices in timetabling in higher education institutions: a systematic review. Annals of Operations Research, 275(1), 145-160.

Wren, A. (1995). Scheduling, timetabling and rostering - A special relationship? International Conference on the Practice and Theory of Automated Timetabling, 46-75.

Yáñez, á. (2020). Desarrollo de una herramienta para la calendarización de evaluaciones universitarias.

Yasari, P., Ranjbar, M., Jamili, N. & Shaelaie, M.-H. (2019). A two-stage stochastic programming approach for a multi-objective course timetabling problem with courses cancelation risk. Computers & Industrial Engineering, 130, 650-660.

Notas