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
Barra lateral del artículo
Contenido principal del artículo
Resumen
En este trabajo se propone un novedoso modelo de programación lineal entera para resolver el problema de asignación de aulas considerando como insumo fundamental la planificación académica de la Facultad de Ingeniería de una Institución de Educación Superior localizada en la provincia del Guayas, Ecuador. El modelo propuesto considera un conjunto de restricciones que deben ser satisfechas para que la asignación sea factible, que no existan cruces de materias para una misma aula en un bloque horario, no se exceda la capacidad del aula, entre otras. El modelo desarrollado fue implementado en el modelizador AIMMS Developer 4.68 y resuelto usando el solver IBM-CPLEX 12.9. La solución fue obtenida después de 3.61 segundos de ejecución satisfaciendo todas las restricciones y maximizando varios indicadores de calidad, tales como el nivel de utilización de las aulas, asignación de materias a aulas cuya infraestructura es afín con la naturaleza del contenido cubierto en la cátedra. Como conclusión se destaca la importancia de utilizar este tipo de métodos matemáticos para resolver problemas operativos propios de las Instituciones de Educación Superior dado que permiten obtener soluciones de alta calidad en mucho menos tiempo que su realización manual.
Descargas
Detalles del artículo
Esta obra está bajo una licencia internacional Creative Commons Atribución-NoComercial 4.0.
Los miembros que conforman el Comité Editorial de la Revista Científica ECOCIENCIA, realizan una labor transparente en los diferentes procesos de gestión de la misma garantizando la elevada calidad de cada uno de los artículos que quedan publicados a disposición de la comunidad académica y científica. Dicho Comité verifica que cada artículo enviado por su autor/es, carezca de plagio y para ello se emplea el software antiplagio COMPILATIO.
El reporte que URKUND envía como respuesta al editor evaluador, permite que este pueda visualizar si ha habido similitudes o plagio (en su defecto) lo cual comúnmente sucede por errores en la forma de citar o referenciar por parte del autor del artículo. Igualmente, el evaluador gracias al reporte de URKUND, puede visualizar de cuáles fuentes o documentos originales ha incurrido en plagio el autor del trabajo. Una vez que sea constatada la ausencia de plagio en cada artículo, se da inicio al proceso de revisión por parte de los pares ciegos. Si se detecta plagio en el artículo, automáticamente este es rechazado y se notifica el veredicto al autor/es.
Cuando un artículo es aprobado, el/los autor/es conservan los derechos de autor y cede(n) a la Revista Científica ECOCIENCIA, el derecho de ser la primera que pueda editarlo, reproducirlo, exhibirlo y comunicarlo mediante medios impresos y electrónicos.
La Revista Científica ECOCIENCIA opera bajo una bajo una licencia Creative Commons Reconocimiento-No Comercial 4.0 Internacional (CC-BY-NC 4.0).
BY: la dirección de la revista, así como el Comité Editorial, tienen atribución para compartir, copiar y redistribuir el material de la revista en cualquier medio o formato, así como adaptar, remezclar y transformar las secciones de la revista no causando alteración en el contenido de los artículos publicados o previo a publicar por parte de los autores.
NC: el material de la revista no puede ser manejado con fines comerciales por lo cual ninguna de sus secciones ni artículos publicados por los autores, está disponible para la venta o actividad comercial.
Se autoriza la reproducción, parcial o total, de los artículos publicados en la Revista Científica ECOCIENCIA, siempre que se cite apropiadamente la fuente y se use sin propósitos comerciales.
Citas
Al-Betar, M., Khader, A., & Zaman, M. (2012). University course timetabling using a hybrid harmony search metaheuristic algorithm. IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), 664 - 681.
Al-Yakoob, S. M., & Sherali, H. D. (2007). A mixed-integer programming approach to a class timetabling problem: A case study with gender policies and traffic considerations. European Journal of Operational Research, 1028 - 1044.
Asratian, A., & de Werra, D. (2002). A generalized class–teacher model for some timetabling problems. European journal of operational research, 531 - 542.
Babaei, H., Karimpour, J., & Hadidi, .. (2015). A survey of approaches for university course timetabling problem. Computers & Industrial Engineering, 43 - 59.
Carter, M. W., & Laporte, G. (1997). Recent Developments in Practical Course Timetabling. international conference on the practice and theory of automated timetabling, 3 - 19.
CES. (21 de 09 de 2019). Gaceta. Recuperado de gaceta.ces.gob.ec: http://gaceta.ces.gob.ec/inicio.html?id_documento=234533
Dantzig, G., & Thapa, M. (2006). Linear programming 1: introduction. Springer.
Daskalaki, S., Birbas, T., & Housos, E. (2004). An integer programming formulation for a case study in university timetabling. European Journal of Operational Research, 117 - 135.
Domenech, B., & Lusa, A. (2016). A MILP model for the teacher assignment problem considering teachers’ preferences. European Journal of Operational Research, 1153 - 1160.
El Universo. (16 de Abril de 2019a). Tiempos se acortan en carreras de tercer nivel en Ecuador. Recuperado de El Universo: https://bit.ly/2mb5HzP
El Universo. (14 de Julio de 2019b). Estudiantes y docentes se adaptan a la educación pública en línea en Ecuador. Recuperado de El Universo: https://bit.ly/2kAFc6L
El Universo. (2 de Septiembre de 2019c). 330 ítems comprende la quinta evaluación externa a 55 centros de estudios superiores del Ecuador. Recuperado de El Universo: https://bit.ly/2m9FDVN
Feizi-Derakhshi, M. R., Babaei, H., & Heidarzadeh, J. (2012). A survey of approaches for university course timetabling problem. In Proceedings of 8th international symposium on intelligent and manufacturing systems (págs. 307 - 321). Adrasan: Sakarya University Department of Industrial Engineering.
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, 873 - 888.
Gotlieb, C. C. (1963). The construction of class-teacher timetables. IFIP congress (págs. 73 - 77). IFIP.
Hernández, R., Miranda, J., y Rey, P. (2008). Programación de Horarios de Clases y Asignación de Salas para la Facultad de Ingeniería de Universidad Diego Portales mediante un Enfoque de Programación Entera. Revista Ingeniería de Sistemas, 121 - 141.
Hillier, F., Lieberman, G., y Osuna, M. (2010). Introducción a la Investigación de Operaciones. 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.
Jamili, A., Hamid, M., Gharoun, H., & Khoshnoudi, R. (2018). Developing a Comprehensive and Multi-Objectivemathematical model for university course timetabling problem: a real case study. Conference: proceedings of the international conference on industrial engineering and operations management (pág. 2108). Paris: Industrial Engineering and Operations Managemen.
June, T. L., Obit, J. H., Leau, Y. B., & Bolongkikit, J. (2019). Implementation of Constraint Programming and Simulated Annealing for Examination Timetabling Problem. Computational Science and Technology, 175 - 184.
Lewis, R. (2008). A survey of metaheuristic-based techniques for university timetabling problems. OR spectrum, 167 - 190.
Lewis, R., & Paechter, B. (2007). Finding feasible timetables using group-based operators. IEEE Transactions on Evolutionary Computation, 397 - 413.
Lindahl, M., Mason, A. J., Stidsen, T., & Sørensen, M. (2018). A strategic view of University timetabling. European Journal of Operational Research, 35 - 45.
McCollum, B. (2006). A Perspective on Bridging the Gap Between Theory and Practice in University Timetabling. International Conference on the Practice and Theory of Automated Timetabling (págs. 3 - 23). Berlin: Springer.
MirHassani, S. (2006). A computational approach to enhancing course timetabling with integer programming. Applied Mathematics and Computation, 814 - 822.
Müller, T., Rudová, H., & Barták, R. (2004). Minimal perturbation problem in course timetabling. International Conference on the Practice and Theory of Automated Timetabling (págs. 126 - 146). Heidelberg: Springer.
Nategh, M. N., Hosseinabadi, A. R., & Balas, V. E. (2018). University-timetabling problem and its solution using GELS algorithm: a case study. International Journal of Advanced Intelligence Paradigms, 368 - 377.
Obit, J. H. (2010). Developing novel meta-heuristic, hyper-heuristic and cooperative search for course timetabling problems. Nottingham: University of Nottingham.
Obit, J. H., Ouelhadj, D., Landa-Silva, D., Vun, T. K., & Alfred, R. (2011). Designing a multi-agent approach system for distributed course timetabling. 11th International Conference on Hybrid Intelligent Systems (HIS) IEEE (págs. 103 - 108). IEEE.
Phillips, A. E., Walker, C. G., Ehrgott, M., & Ryan, D. M. (2017). Integer programming for minimal perturbation problems in university course timetabling. Annals of Operations Research, 283 - 304.
Pinedo, M. (2016). Scheduling. Springer.
Sandhu, K. (2003). Automating class schedule generation in the context of a university timetabling information system. Brisbane: Griffith University.
Sarin, S. C., Wang, Y., & Varadarajan, A. (2010). A university-timetabling problem and its solution using Benders’ partitioning—a case study. Journal of Scheduling, 131 - 141.
Schaerf, A. (1999). A survey of automated timetabling. Artificial intelligence review, 87 - 127.
Song, L., Liu, S., Tang, X., Peng, X., & Chen, M. (2018). An iterated local search algorithm for the University Course. Applied Soft Computing, 597 - 608.
Vrielink, R. O., Jansen, E. A., Hans, E. W., & van Hillegersberg, J. (2019). Practices in timetabling in higher education institutions: a systematic review. Annals of operations research, 145 - 160.
Weitz, R. R., & Jelassi, M. T. (1992). Assigning students to groups: a multi‐criteria decision support system approach. Decision Sciences, 746 - 757.
Wolsey, L. (1998). Integer Programming. Wiley.
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, 650 - 660.