Diseño de metaheurística y modelo matemático para asignación de horarios en el programa de ingeniería industrial en la PUJ Cali
Loading...
Date
2024
Director
Journal Title
Journal ISSN
Volume Title
Publisher
Pontificia Universidad Javeriana Cali
Abstract
La asignación de horarios (Timetabling) es un problema combinatorio, desafiante, laborioso y repetitivo en distintos sectores; este trata de ordenar una cantidad finita de personal, espacios o recursos a bloques horarios. En el University Course Timetabling (UCT) los cursos deben tomar lugar y distribuir las sesiones académicas evitando cruces lógicos como: un profesor no puede dictar dos materias a la misma hora, un estudiante no puede asistir a dos clases simultáneamente, entre otros. Las universidades e instituciones educativas de nivel superior en Colombia optan por resolver estos problemas de manera manual mediante la prueba y error. Debido a la volátil calidad de las soluciones y complejidad de tipo NP-Hard, la metodología actual en las instituciones usualmente resulta en soluciones lejanas al óptimo. Para abordar este problema en del Programa de Ingeniería industrial en la PUJ como caso aplicado, se diseñó un algoritmo de dos etapas: una metaheurística de tipo búsqueda local iterativa y un método de inicialización a partir de un modelo de programación lineal entera-mixta. Mediante un diseño de experimentos Taguchi se establecieron los parámetros para optimizar el desempeño del algoritmo. Como objetivo se maximizaron las preferencias cumplidas por profesor y la reducción de cruces entre materias que se pueden adelantar o atrasar, a su vez que se eliminaron conflictos entre asignaturas que comparten semestre, profesor y salón. Como consecuencia de la implementación, se redujo en un 99,37% el tiempo asociado al proceso de asignación de horarios semestral, como también un aumento del 14,8% respecto a las preferencias de los profesores. De esta forma la institución obtiene una mayor eficiencia implementando herramientas de automatización y optimización al mismo tiempo que se consideran factores sociales como las preferencias.
Description
item.page.descriptioneng
Timetabling is a combinatorial, challenging, laborious and repetitive problem in different industries. It consists of ordering a finite amount of personnel, rooms, or resources to hourly blocks. In University Course Timetabling (UCT) courses must take a location and distribute the academic sessions avoiding lecture conflicts such as: a professor cannot lecture two classes at the same time, a student cannot attend two classes simultaneously, among others. Universities and higher education institutions in Colombia opt to solve these problems manually through trial and error. Due to the problem’s NP-Hard complexity and the volatile quality of solutions, current university methodologies usually result in infeasible solutions. In the PUJ’s Industrial Engineering Program a two-stage algorithm was designed to address this problem: an iterative local search type metaheuristic with an initialization method based on a mixed-integer linear programming model. Through a Taguchi design of experiments, the parameters were established to optimize the performance of the algorithm. As an objective the preferences fulfilled by the teacher were maximized and the crossovers between subjects that can be viewed in advanced or delayed were reduced. Situations that include conflicts between subjects that share the same semester, teacher and classroom were eliminated. Because of the implementation the time associated with the semester scheduling process was reduced by 99.37%, as well as an increase of 14.8% regarding the preferences of the professors. In such a way the institution obtains greater efficiency by implementing automation and optimization tools while considering social factors such as preferences.
Keywords
Asignación, Metaheurística, Optimización, Timetabling, Schedules, Metaheuristic, Optimization