Modelos de Programación Entera para el Problema de Aignación de Horarios en Cursos Universitarios
DOI:
https://doi.org/10.46661/rev.metodoscuant.econ.empresa.7354Palabras clave:
Programación de Horarios, programación entera, asignación de cursosResumen
La programación de horarios se clasifica como un problema combinatorio para el que existen múltiples alternativas de solución incluyendo entre ellas la programación entera. Sin embargo, el modelado de reglas operativas y el tamaño de problemas reales hace que su uso no sea común comparado con otras técnicas. El presente artículo propone un modelo de programación entera (IP), que aborda el problema de programación de horarios conformado por variables asociadas con franjas horarias, asignatura y docente asignado. También se incluyen parámetros como número de franjas horarias mínimas y máximas a impartir por el docente, tiempo de franja horaria, disponibilidad de docente, salones disponibles y costo estimado de insatisfacción generado por el horario asignado. En el modelo se integran siete restricciones duras y diecisiete blandas que proporcionan mayor calidad a la solución final de horarios. Se valida el modelo IP con una función objetivo global, en el que se reportan experimentos y resultados obtenidos en instancias reales de la Universidad de la Salle (ULS). El nuevo enfoque de solución ofrece mejoras en los horarios finales, así como la interacción con los usuarios durante su construcción. Finalmente, en las conclusiones del trabajo se discute el diseño y desarrollo de un sistema que brinda soporte a las decisiones, referenciando sugerencias para futuros desarrollos.
Descargas
Citas
Alnowaini, G. & Aljomai, A. A. (2021). Genetic Algorithm For Solving University Course Timetabling Problem Using Dynamic Chromosomes. 2021 International Conference of Technology, Science and Administration (ICTSA), 1-6. https://doi.org/10.1109/ICTSA52017.2021.9406539
Al-Yakoob, S. M. & Sherali, H. D. (2015). Mathematical models and algorithms for a high school timetabling problem. Computers & Operations Research, 61, 56-68. https://doi.org/10.1016/j.cor.2015.02.011
Asmuni, H. (2008). Fuzzy Methodologies for Automated University Timetabling Solution Construction and Evaluation [PhD Thesis]. University of Nottingham.
Assi, M., Halawi, B. & Haraty, R. A. (2018). Genetic Algorithm Analysis using the Graph Coloring Method for Solving the University Timetable Problem. Procedia Computer Science, 126, 899-906. https://doi.org/10.1016/j.procs.2018.08.024
Babaei, H., Karimpour, J. & Hadidi, A. (2015). A survey of approaches for university course timetabling problem. Computers & Industrial Engineering, 86, 43-59. https://doi.org/10.1016/j.cie.2014.11.010
Barnhart, C., Lu, F. & Shenoi, R. (1998). Integrated Airline Schedule Planning. En G. Yu (Ed.), Operations Research in the Airline Industry (Vol. 9, pp. 384-403). Springer US. https://doi.org/10.1007/978-1-4615-5501-8_13
Battiti, R. & Tecchiolli, G. (1994). The Reactive Tabu Search. ORSA Journal on Computing, 6(2), 126-140. https://doi.org/10.1287/ijoc.6.2.126
Brucker, P., Drexl, A., Möhring, R., Neumann, K. & Pesch, E. (1999). Resource-constrained project scheduling: Notation, classification, models, and methods. European Journal of Operational Research, 112(1), 3-41. https://doi.org/10.1016/S0377-2217(98)00204-5
Castillo-Salazar, J. A., Landa-Silva, D. & Qu, R. (2016). Workforce scheduling and routing problems: Literature survey and computational study. Annals of Operations Research, 239(1), 39-67. https://doi.org/10.1007/s10479-014-1687-2
Ceschia, S., Di Gaspero, L. & Schaerf, A. (2012). Design, engineering, and experimental analysis of a simulated annealing approach to the post-enrolment course timetabling problem. Computers & Operations Research, 39(7), 1615-1624. https://doi.org/10.1016/j.cor.2011.09.014
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. https://doi.org/10.1016/S0377-2217(03)00103-6
de Palma, A. & Lindsey, R. (2001). Optimal timetables for public transportation. Transportation Research Part B: Methodological, 35(8), 789-813. https://doi.org/10.1016/S0191-2615(00)00023-0
de Werra, D. (1985). An introduction to timetabling. European Journal of Operational Research, 19(2), 151-162. https://doi.org/10.1016/0377-2217(85)90167-5
Dimopoulou, M. & Miliotis, P. (2001). Implementation of a university course and examination timetabling system. European Journal of Operational Research, 130(1), 202-213. https://doi.org/10.1016/S0377-2217(00)00052-7
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. https://doi.org/10.1016/j.ejor.2015.08.057
Feizi-Derakhshi, M.-R., Babaei, H. & Heidarzadeh, J. (2012, septiembre 27). A Survey of Approaches for University Course Timetabling Problem. Proceedings of 8th International Symposium on Intelligent and Manufacturing Systems (IMS 2012).
Feng, X., Lee, Y. & Moon, I. (2017). An integer program and a hybrid genetic algorithm for the university timetabling problem. Optimization Methods and Software, 32(3), 625-649. https://doi.org/10.1080/10556788.2016.1233970
Ghalia, M. B. (2008). Particle swarm optimization with an improved exploration-exploitation balance. 2008 51st Midwest Symposium on Circuits and Systems, 759-762. https://doi.org/10.1109/MWSCAS.2008.4616910
Goh, S. L., Kendall, G. & Sabar, N. R. (2019). Simulated annealing with improved reheating and learning for the post enrolment course timetabling problem. Journal of the Operational Research Society, 70(6), 873-888. https://doi.org/10.1080/01605682.2018.1468862
Gotlieb, C. C. (1962). The Construction of Class-Teacher Time-Tables. Information Processing, Proceedings of the 2nd IFIP Congress 1962, Munich, Germany, August 27 - September 1, 1962, 73-77.
Gülcü, A. & Akkan, C. (2020). Robust university course timetabling problem subject to single and multiple disruptions. European Journal of Operational Research, 283(2), 630-646. https://doi.org/10.1016/j.ejor.2019.11.024
Hung, R. & Emmons, H. (1993). Multiple-shift Workforce Scheduling under the 3-4 compressed workweek with a Hierarchical Workforce. IIE Transactions, 25(5), 82-89. https://doi.org/10.1080/07408179308964318
Ismayilova, N. A., Sağir, M. & Gasimov, R. N. (2007). A multiobjective faculty–course–time slot assignment problem with preferences. Mathematical and Computer Modelling, 46(7-8), 1017-1029. https://doi.org/10.1016/j.mcm.2007.03.012
K. Alsmadi, M., M. Jaradat, G., Alzaqebah, M., ALmarashdeh, I., A. Alghamdi, F., Mustafa A. Mohammad, R., Aldhafferi, N. & Alqahtani, A. (2022). An Enhanced Particle Swarm Optimization for ITC2021 Sports Timetabling. Computers, Materials & Continua, 72(1), 1995-2014. https://doi.org/10.32604/cmc.2022.025077
LaGanga, L. R. & Lawrence, S. R. (2012). Appointment Overbooking in Health Care Clinics to Improve Patient Service and Clinic Performance. Production and Operations Management, 21(5), 874-888. https://doi.org/10.1111/j.1937-5956.2011.01308.x
Lewis, R. (2012). A time-dependent metaheuristic algorithm for post enrolment-based course timetabling. Annals of Operations Research, 194(1), 273-289. https://doi.org/10.1007/s10479-010-0696-z
McCollum, B., McMullan, P., Parkes, A. J., Burke, E. K. & Qu, R. (2012). A new model for automated examination timetabling. Annals of Operations Research, 194(1), 291-315. https://doi.org/10.1007/s10479-011-0997-x
Nagata, Y. (2018). Random partial neighborhood search for the post-enrollment course timetabling problem. Computers & Operations Research, 90, 84-96. https://doi.org/10.1016/j.cor.2017.09.014
Nandhini, V. (2019). A Study on Course Timetable Scheduling and Exam Timetable Scheduling using Graph Coloring Approach. International Journal for Research in Applied Science and Engineering Technology, 7(3), 1999-2006. https://doi.org/10.22214/ijraset.2019.3368
Neumann, K., Schwindt, C. & Zimmermann, J. (2003). Project Scheduling with Time Windows and Scarce Resources: Temporal and Resource-Constrained Project Scheduling with Regular and Nonregular Objective Functions. Springer Berlin Heidelberg.
https://doi.org/10.1007/978-3-540-24800-2_3
Nothegger, C., Mayer, A., Chwatal, A. & Raidl, G. R. (2012). Solving the post enrolment course timetabling problem by ant colony optimization. Annals of Operations Research, 194(1), 325-339. https://doi.org/10.1007/s10479-012-1078-5
Ribić, S. & Konjicija, S. (2010, junio). A two phase integer linear programming approach to solving the school timetable problem | IEEE Conference Publication | IEEE Xplore. Proceedings of the ITI 2010, 32nd International Conference on Information Technology Interfaces. https://ieeexplore.ieee.org/abstract/document/5546473?casa_token=8NXEYLyhBJYAAAAA:DO9jDMq4-wyY2YxPPgfUUOGBO1n4ELugtWtLZzG3WTMrYB09TAvcnX6Nkr2N0KKYHvBoQ7CY0Ect7VU
Saldaña Crovo, A., Oliva San Martín, C. & Pradenas Rojas, L. (2007). Modelos de Programación Entera para un Problema de Programación de Horarios para Universidades. Ingeniare. Revista Chilena de Ingeniería, 15(3). https://doi.org/10.4067/S0718-33052007000300005
Scheepmaker, G. M., Goverde, R. M. P. & Kroon, L. G. (2017). Review of energy-efficient train control and timetabling. European Journal of Operational Research, 257(2), 355-376. https://doi.org/10.1016/j.ejor.2016.09.044
Selim, S. M. (1988). Split Vertices in Vertex Colouring and Their Application in Developing a Solution to the Faculty Timetable Problem. The Computer Journal, 31(1), 76-82. https://doi.org/10.1093/comjnl/31.1.76
Shakibaei, S., Alpkokin, P. & Black, J. A. (2021). A multi-objective optimisation model for train scheduling in an open-access railway market. Transportation Planning and Technology, 44(2), 176-193. https://doi.org/10.1080/03081060.2020.1868085
Sörensen, K. & Glover, F. W. (2013). Metaheuristics. En S. I. Gass & M. C. Fu (Eds.), Encyclopedia of Operations Research and Management Science (pp. 960-970). Springer US. https://doi.org/10.1007/978-1-4419-1153-7_1167
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. https://doi.org/10.1016/j.eswa.2020.113943
Torres-Ovalle, C., Montoya-Torres, J. R., Quintero-Araujo, C., Sarmiento Lepesqueur, A. & Castilla Luna, M. (2014). University Course Scheduling and Classroom Assignment. Ingenieria y Universidad, 18(1), 59-76. https://doi.org/10.11144/Javeriana.IYU18-1.phaa
Vermuyten, H., Lemmens, S., Marques, I. & Beliën, J. (2016). Developing compact course timetables with optimized student flows. European Journal of Operational Research, 251(2), 651-661. https://doi.org/10.1016/j.ejor.2015.11.028
Wang, P. & Goverde, R. M. P. (2019). Multi-train trajectory optimization for energy-efficient timetabling. European Journal of Operational Research, 272(2), 621-635. https://doi.org/10.1016/j.ejor.2018.06.034
Welsh, D. J. A. (1967). An upper bound for the chromatic number of a graph and its application to timetabling problems. The Computer Journal, 10(1), 85-86. https://doi.org/10.1093/comjnl/10.1.85
Wirasinghe, S. C. (2002). Initial Planning for Urban Transit Systems. En W. H. K. Lam & M. G. H. Bell (Eds.), Advanced Modeling for Transit Operations and Service Planning (pp. 1-29). Emerald Group Publishing Limited. https://doi.org/10.1108/9780585475226-001
Zacharias, C. & Pinedo, M. (2014). Appointment Scheduling with No-Shows and Overbooking. Production and Operations Management, 23(5), 788-801. https://doi.org/10.1111/poms.12065
Zhu, K., Li, L. D. & Li, M. (2021). School Timetabling Optimisation Using Artificial Bee Colony Algorithm Based on a Virtual Searching Space Method [Preprint]. Mathematics and Computer Science. https://doi.org/10.20944/preprints202111.0215.v1
Publicado
Cómo citar
Número
Sección
Licencia
Derechos de autor 2023 Carlos A. Arango, Msc, Heriberto Felizzola, Msc, Andrés Hualpa, Msc., Paula Gomez, Eng., Carlos Mora, Eng.
Esta obra está bajo una licencia internacional Creative Commons Atribución-CompartirIgual 4.0.
El envío de un manuscrito a la Revista supone que el trabajo no ha sido publicado anteriormente (excepto en la forma de un abstract o como parte de una tesis), que no está bajo consideración para su publicación en ninguna otra revista o editorial y que, en caso de aceptación, los autores están conforme con la transferencia automática del copyright a la Revista para su publicación y difusión. Los autores retendrán los derechos de autor para usar y compartir su artículo con un uso personal, institucional o con fines docentes; igualmente retiene los derechos de patente, de marca registrada (en caso de que sean aplicables) o derechos morales de autor (incluyendo los datos de investigación).
Los artículos publicados en la Revista están sujetos a la licencia Creative Commons CC-BY-SA de tipo Reconocimiento-CompartirIgual. Se permite el uso comercial de la obra, reconociendo su autoría, y de las posibles obras derivadas, la distribución de las cuales se debe hacer con una licencia igual a la que regula la obra original.
Hasta el volumen 21 se ha estado empleando la versión de licencia CC-BY-SA 3.0 ES y se ha comenzado a usar la versión CC-BY-SA 4.0 desde el volumen 22.
