Programación de horario escolar con multi-localización y preferencias docentes. [School course timetable with multi location and preferences of teachers]

Linda Lucia Esquivel Trujillo, Juan Pablo Orejuela C

Resumen


Esta investigación aborda el problema de programación del horario escolar en Instituciones Educativas, con dos jornadas y con múltiples sedes, que exigen el desplazamiento de algunos maestros entre estas. El problema se resuelve mediante un modelo de programación lineal entera que minimiza el traslado de docentes entre sedes. La metodología planteada consideró dos tipos de restricciones: las obligatorias, pertenecientes al marco legal e institucional, y los requerimientos del cuerpo docente, que no son de estricto cumplimiento. El modelo se validó y se desarrollaron experimentos computacionales en varias instancias usando Lingo ® 14. Adicionalmente, para conocer su comportamiento, se realizó un análisis de estructura en dos escenarios. En todas las instancias se obtuvo un mínimo de desplazamientos de los docentes.

Palabras clave: Gestión de horarios, Programación de horarios de clase para colegios, Preferencias de Horario de los docentes, Programación lineal entera.

 

Abstract

In this research is arises the problem of building the school timetable an Educational Institution (EI’s) with multiple headquarters that provide classes in morning and afternoon, forcing than during the school day some teachers must move between headquarters. The problem is tackled by using an integer lineal programming model (ILP) as tool solution. According to the above, the model has, as one of its objectives minimize transfers of teachers between different headquarters. The proposed methodology considers two types of constraints, mandatory (hard) belonging to the legal and institutional framework concerning the Institutional Education Project (IEP), and faculty requirements (soft) that are not strict obedience. The proposed model was validated in a case study, and computational experiments were developed in several instances using Lingo ® 14. Additionally, to know its behavior, a structure analysis was performed in two scenarios. In all instances, a minimum of teacher displacement was obtained.

Keywords: Management of schedules, School Course Timetabling, Teacher Schedule Preferences, Integer Linear Programming.

Resumo

Esta pesquisa aborda o problema da programação de horários escolares em Instituições Educacionais, com dois dias e múltiplos locais, que exigem o deslocamento de alguns professores entre eles. O problema é resolvido por todo um modelo de programação linear que minimiza a transferência de professores entre os locais. A metodologia proposta considerou dois tipos de restrições: obrigatória, pertencente ao arcabouço legal e institucional, e os requisitos do corpo docente, que não são rigorosamente cumpridos. O modelo foi validado e experimentos computacionais foram desenvolvidos em várias instâncias utilizando o Lingo 14. Além disso, para conhecer seu comportamento, foi realizada uma análise estrutural em dois cenários. Em todos os casos, foi obtido um mínimo de deslocamento do professor.

Palavras-chave: Gestão de horários, programação de horários de aulas para escolas, agendamento de preferências de professores, programação linear inteira.


Palabras clave


Gestión de horarios, Programación de horarios de clase para colegios, Preferencias de Horario de los docentes, Programación lineal entera

Texto completo:

PDF HTML

Referencias


Ahmed, L., Özcan, E., & Kheiri, A. (2015). Solving high school timetabling problems worldwide using selection hyper-heuristics. Expert Systems with Applications, 42(13), 5463–5471. https://doi.org/10.1016/j.eswa.2015.02.059

Al-Yakoob, S., & Sherali, H. (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

Babaei, H., Karimpour, J., & Hadidi, A. (2014). 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

Badoni, R., Gupta, D., & Mishra, P. (2014). A new hybrid algorithm for university course timetabling problem using events based on groupings of students. Computers & Industrial Engineering, 78, 12–25. https://doi.org/10.1016/j.cie.2014.09.020

Beligiannis, G., Moschopoulos, C., Kaperonis, G., & Likothanassis, S. (2008). Applying evolutionary computation to the school timetabling problem: The Greek case. Computers and Operations Research, 35(4), 1265–1280. https://doi.org/10.1016/j.cor.2006.08.010

Bellio, R., Ceschia, S., Di Gaspero, L., Schaerf, A., & Urli, T. (2016). Feature-based tuning of simulated annealing applied to the curriculum-based course timetabling problem. Computers and Operations Research, 65, 83–92. https://doi.org/10.1016/j.cor.2015.07.002

Brito, S., Fonseca, G., Toffolo, T., Santos, H., & Souza, M. (2012). A SA-VNS approach for the High School Timetabling Problem. Electronic Notes in Discrete Mathematics, 39, 169–176. https://doi.org/10.1016/j.endm.2012.10.023

Burke, E., Marecek, J., Parkes, A., & Rudová, H. (2012). A branch-and-cut procedure for the Udine Course Timetabling problem. Annals of Operations Research, 194(1), 71–87. https://doi.org/10.1007/s10479-010-0828-5

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 and Operations Research, 39(7), 1615–1624. https://doi.org/10.1016/j.cor.2011.09.014

Chávez, Ó., Pozos, P., & Gómez, J. (2014). Búsqueda Tabú con criterio de aspiración probabilístico aplicada a la generación de horarios escolares.

Cifuentes, J. (2012). Programación de estudiantes un caso de estudio (Universidad Central). CLAIO-SBPO, 1080–1091.

Crovo, A., Oliva, C., Martin, S., & Rojas, L. (2007). Modelos De Programacion Entera Para Un Problema De Models of Integer Programming for an University Timetabling Problem, 15, 245–259.

Del Barco, R. (2010). Formulación de un modelo de programación matemática para la asignación de horarios escolares. https://doi.org/10.1007/s13398-014-0173-7.2

Dorneles, Á., De Araújo, O., & Buriol, L. (2014). A fix-and-optimize heuristic for the high school timetabling problem. Computers and Operations Research, 52(PART A), 29–38. article. https://doi.org/10.1016/j.cor.2014.06.023

Enriquez, E., Tellez, E., & Enriquez, E. (2007). Uso de una Colonia de Hormigas para resolver Problemas de Programacion de Horarios. Laboratorio Nacional de informática avanzada A.C., Xalapa, México.

Gunawan, A., Ng, K., & Poh, K. (2012). A hybridized Lagrangian relaxation and simulated annealing method for the course timetabling problem. Computers and Operations Research, 39(12), 3074–3088. https://doi.org/10.1016/j.cor.2012.03.011

Hao, J., & Benlic, U. (2011). Lower bounds for the ITC-2007 curriculum-based course timetabling problem. European Journal of Operational Research, 212(3), 464–472. https://doi.org/10.1016/j.ejor.2011.02.019

Katsaragakis, I., Tassopoulos, I., & Beligiannis, G. (2015). A comparative study of modern heuristics on the school timetabling problem. Algorithms, 8(3), 723–742. https://doi.org/10.3390/a8030723

Kingston, J. (2012). Resource assignment in high school timetabling. Annals of Operations Research, 194(1), 241–254. https://doi.org/10.1007/s10479-010-0695-0

Lewis, R., & Thompson, J. (2014). Analysing the effects of solution space connectivity with an effective metaheuristic for the course timetabling problem. European Journal of Operational Research, 240(3), 637–648. https://doi.org/10.1016/j.ejor.2014.07.041

Mahiba, A., & Durai, C. (2012). Genetic algorithm with search bank strategies for university course timetabling problem. Procedia Engineering, 38, 253–263. https://doi.org/10.1016/j.proeng.2012.06.033

Méndez-Díaz, I., Zabala, P., & Miranda-Bront, J. (2016). An ILP based heuristic for a generalization of the post-enrollment course timetabling problem. Computers and Operations Research, 76, 195–207. https://doi.org/10.1016/j.cor.2016.06.018

MirHassani, S. (2006). Improving paper spread in examination timetables using integer programming. Applied Mathematics and Computation, 179(2), 702–706. https://doi.org/10.1016/j.amc.2005.11.125

Nurmi, K., & Kyngäs, J. (2007). A Framework for School Timetabling Problem. Mista, 386–393.

Papoutsis, K.;Valouxis C.; Housos, E. (2003). A Column Generation Approach for the Timetabling Problem of Greek High Schools, 54(3), 230–238.

Papoutsis, K., Valouxis, C., & Housos, E. (2003). A Column Generation Approach for the Timetabling Problem of Greek High Schools, 54(3), 230–238.

Pillay, N. (2014). A survey of school timetabling research. Ann Oper Res, (218), 261–293.

Pillay, N. (2014). A survey of school timetabling research. Annals of Operations Research, 218(1), 261–293. https://doi.org/10.1007/s10479-013-1321-8

Qu, R., He, F., & Burke, E. (2009). Hybridizing Integer Programming Models with an Adaptive Decomposition Approach for Exam Timetabling Problems, (August), 10–12.

República, S. D. La. (2001). Ley 715 de Diciembre 21 de 2001, 357(diciembre 21), 46.

Santos, H., Uchoa, E., Ochi, L., & Maculan, N. (2012). Strong bounds with cut and column generation for class-teacher timetabling. Annals of Operations Research, 194(1), 399–412. https://doi.org/10.1007/s10479-010-0709-y

Sarmiento, A. (2014). Estudio del problema de ruteo de vehículos con balance de carga : Aplicación de la meta-heurística Búsqueda Tabú .

Sarmiento, A., Torres, C., Quintero, C., & Montoya, J. (2012). Programación y asignación de horarios de clases universitarias: un enfoque de programación entera, July 23-27.

Skoullis, V., Tassopoulos, I., & Beligiannis, G. (2017). Solving the high school timetabling problem using a hybrid cat swarm optimization based algorithm. Applied Soft Computing Journal, 52, 277–289. https://doi.org/10.1016/j.asoc.2016.10.038

Soria-Alcaraz, J., Ochoa, G., Swan, J., Carpio, M., Puga, H., & Burke, E. (2014). Effective learning hyper-heuristics for the course timetabling problem. European Journal of Operational Research, 238(1), 77–86. https://doi.org/10.1016/j.ejor.2014.03.046

Veenstra, M., & Vis, I. (2016). School timetabling problem under disturbances. Computers and Industrial Engineering, 95, 175–186. https://doi.org/10.1016/j.cie.2016.02.011

Zhang, D., Liu, Y., M’Hallah, R., & Leung, S. (2010). A simulated annealing with a new neighborhood structure based algorithm for high school timetabling problems. European Journal of Operational Research, 203(3), 550–558. https://doi.org/10.1016/j.ejor.2009.09.014




DOI: http://dx.doi.org/10.22335/rlct.v11i1.621

Enlaces refback

  • No hay ningún enlace refback.




Copyright (c) 2019 Revista Logos Ciencia & Tecnología

Licencia de Creative Commons
Este obra está bajo una licencia de Creative Commons Reconocimiento 4.0 Internacional.

Revista Científica indexada e indizada en:

                                   Resultado de imagen para erih plus logos               

 

 Emerging Sources Citation Index       SRG-Index


       

 


Backfiles en:

    SHERPA/RoMEO Logo 

     

 

 

     

 

 

ISSN de la revista (versión impresa) 2145-549X
ISSN de la revista (versión electrónica) 2422-4200



BY. Todos los contenidos de la Revista, a menos de que se indique lo contrario, están bajo la licencia de Creative Commons Attribution 

 

 

Revista Logos Ciencia & Tecnología
Policía Nacional de Colombia
Trv. 33 No. 47A - 35 Sur• Bogotá, D.C., Colombia

Código Postal: 110611-Código Postal Ampliado: 110611001

 

Teléfono: (57-1) 515 9000 Ext. 9854
Correo: dinae.logosct@policia.gov.co

 

 

 

 

 

 

POLICÍA NACIONAL DE COLOMBIA
Carrera 59 Nº 26 - 21, CAN, Bogotá DC.
Atención administrativa de lunes a viernes de 8:00 am a 12:00 pm y de 2:00 pm a 5:00 pm - Requerimientos ciudadanos 24 horas
Línea de Atención al Ciudadano Bogotá: (571) 315 91 11 / 91 12 - Resto del país: 018000 910 600 FAX (571) 315 95 81 E -mail: lineadirecta@policia.gov.co
Centro de mediaciones Pedagógicas y Tecnológicas
Copyright © www.policia.gov.co - 2014