DOI:
https://doi.org/10.14483/2322939X.6478Publicado:
2013-12-11Número:
Vol. 10 Núm. 2 (2013)Sección:
Actualidad TecnológicaProblema del school timetabling y algoritmos genéticos: una revisión
Timetabling School problem and genetic algorithms: a review
Palabras clave:
Timetabling, computational complexity, metaheuristics algorithms, genetic algorithms (en).Palabras clave:
Timetabling, Complejidad computacional, algoritmos metaheuristicos, Algoritmos Genéticos. (es).Descargas
Resumen (es)
En este artículo se presenta de manera general el problema “School Timetabling”, se parte de una definición del mismo, su clasificación, su complejidad computacional, para luego entrar a revisar las diferentes técnicas con las cuales se puede solucionar el mismo y como último se entra a revisar una de estas técnicas como son los algoritmos genéticos (AG) que fue la escogida para darle solución.
Resumen (en)
This paper shows an overview of the problem, “School Timetabling”, it treats first a definition of this problem, their classification, their computational complexity, and then it makes a review the different techniques which can be solved and the last one review one of these techniques such as genetic algorithms (GA), which was chosen to solution it.
Referencias
Lü, Z. &Hao, J.-K.: Adaptive tabu search for course timetabling. In: European Journal of Operational Research 200 (2010), Nr. 1, S. 235—244
Wren, A.: Scheduling, timetabling and rostering --- A special relationship?. In: Burke, E. & Ross, P. (Hrsg.): Springer Berlin Heidelberg. 1153: Practice and Theory of Automated Timetabling.,
, S. 46-75
Automated Scheduling, Optimisation and Planning (ASAP) Research Group. http://www.asap.cs.nott.ac.uk/sites/default/files/ASAP_Brochure
Cabezas Garcia, J. X.: Diseno e implementacion de una heurística para resolver el problema de calendarización de horarios para universidades, Dissertation (), Escuela Superior Politécnica Del Litoral,
Schönberger, J.; Mattfeld, D. &Kopfer, H.: Memetic Algorithm timetabling for non-commercial sport leagues. In: European Journal of Operational Research 153 (2004), Nr. 1, S. 102 – 116
Leone, R.; Festa, P. &Marchitto, E.: A Bus Driver Scheduling Problem: a new mathematical model and a GRASP approximate solution. In: Journal of Heuristics 17 (2011), S. 441-466
Barnhart, C.: Airline Schedule Optimization:John Wiley & Sons, Ltd. :The Global Airline Industry., 2009, S. 183—211
Rangel-Valdez, N. & Torres-Jimenez, J.:Solving Employee Timetabling in a Call Center of a Telecommunications Company in Mexico with Simulated Annealing. In:: . : Artificial Intelligence, 2009. MICAI 2009. Eighth Mexican International Conference on., 2009, S. 170 -175
Bai, R.; Burke, E.; Kendall, G.; Li, J. & Mc-Collum, B.: A Hybrid Evolutionary Approach to the Nurse Rostering Problem. In: Evolutionary Computation, IEEE Transactions on 14 (2010), Nr. 4, S. 580-590
Adamuthe, A. &Bichkar, R.: Tabu search for solving personnel scheduling problem. In: Communication, Information Computing Technology (ICCICT), 2012
International Conference on, 2012, S. 1-6
Larrosa J, Meseguer P. Restricciones Blandas: Modelos y Algoritmos. Inteligencia Artificial. Revista Iberoamericana de Inteligencia Artificial2003;7 Disponible en:http://redalyc.uaemex.mx/redalyc/src/inicio/ArtPdfRed.
jsp?iCve=92572006. Consultado el 1 de febrero de 2013.
Hansen, I.: State-of-the-art of railway operations research. In: Timetable Planning and Information Quality (2010), S. 35
de Werra, D.: An introduction to timetabling. In: European Journal of Operational Research 19 (1985), Nr. 2, S. 151—162. Disponible en: http://www.sciencedirect.com/science/article/pii/0377221785901675
Glover, F. & Laguna, M.: Tabu Search, Norwell, MA, USA: Kluwer Academic Publishers., 1997 Disponible en: http://dl.acm.org/citation.cfm?id=549765
Burke, E. K.; Kendall, G.; Mısır, M.; Özcan, E.; Burke, E.; Kendall, G.; Özcan, E. &Mısır, M.: Applications to timetabling. In: :Handbook of Graph Theory, chapter 5.6., 2004 Disponible en:http://citeseerx.ist.psu.edu/viewdoc/
summary?doi=10.1.1.188.1458
Diaz Fernández, A. &Dowsland, K.: Diseño de heuristicas y fundamentos del recocido simulado. In: Inteligencia artificial: Revista Iberoamericana de Inteligencia Artificial 7 (2003), Nr. 19, S. 93—102. Disponible en: http://sci2s.ugr.es/docencia/metaheuristicas/Enfriamiento-simulado.pdf
Vázquez Espi, M.: Recocido simulado: un nuevo algoritmo para la optimización de estructuras. In: (1994) Disponible en: http://oa.upm.es/968/
Gómez Toro, J. A.; Vanegas Castellanos, J. D. & Zuluaga Gómez, N.: Diseño e implementación de un algoritmo para dar solución al problema de asignación de
salones (Timetabling) usando el método de colonia de hormigas. (2009) Disponible en: http://repositorio.utp.edu.
co/dspace/handle/11059/1320
Glover, F.: Tabu Search - Part I. In: ORSA Journal on Computing 1 (Summer 1989), Nr. 3, S. 190-206
Disponible en:http://joc.journal.informs.org/content/
/3/190.short
Restrepo, G. & Moreno, L.: Modelo para la Asignación de Recursos Académicos en Instituciones Educativas Utilizando Técnicas Metaheurísticas. In: Avances en Sistemas e Informática 8 (2012), Nr. 3. Disponible en: http://digital.unal.edu.co/index.php/avances/article/
view/22350
Dorigo, M.; Birattari, M. &Stutzle, T.:Ant colony optimization. In: ComputationalIntelligence Magazine, IEEE 1 (Nov.), Nr. 4, S. 28-39. Disponible en: http://ieeexplore.ieee.org /xpls/abs_all.jsp?arnumber=4129846
Diaz, A. & Fernández, J. L. G.: Optimización
heuristica y redes neuronales: Paraninfo., 1996
Metropolis, N., Rosenbluth, A.W.,Rosenbluth, M.N., Teller, A.H., Teller, E.: Equation of state calculation by fast
computing machines. Journal of Chemistry Physics, 21: 1087-1091, 1953.
ABRAMSON, David; KRISHNAMOORTHY, Mohan; DANG, Henry. Simulated annealing cooling schedules for the school timetabling problem. Asia Pacific Journal of Operational Research,1999, vol. 16, p. 1-22.Disponible en: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.35.994
ABRAMSON, David. Constructing school timetables using simulated annealing: sequential and parallel algorithms.Management Science, 1991, vol. 37, no 1, p. 98-113.Disponible en:http://citeseerx.ist.psu.edu/viewdoc/
summary?doi=10.1.1.17.302
Abel Franco Flores.Estudio comparativo de Algoritmos Genéticos y Algoritmos de Búsqueda Tabú para la resolución del Flow Shop Problem.
SUÁREZ, Joseph Gallart; MANCHEGO, Fernando Alva; NICHO, Anthony Alama Nole3 Gissella Bejarano. Generación Inteligente de Horarios empleando
heurísticas GRASP con Búsqueda Tabú para la Pontifica Universidad Católica del Perú. Disponible en: http://www.
revistas.pucp.edu.pe/rii/sites/revistas.pucp.edu.pe.rii/files/Joseph_Gallart.pdf
CARDEMIL, Andrés. Optimización de fixtures deportivos: Estado del arte y un algoritmo tabusearch para el travelingtournamentproblem.MasterÕsthesis,
Universidad de Buenos Aires, Departamento de Computación, Buenos Aires, 2002. Disponible en: http://
old.dii.uchile.cl/~gduran/docs/tesis/tesis_andres.pdf
Toro Ocampo, E. M., Tabares Espinosa, P., & Granada Echeverry, M. (2004). Método de colonia de hormigas aplicado a la solución del problema de asignación
generalizada. Revista Tecnura, 8(15), 66-76. Disponible en: http://tecnura.udistrital.edu.co/ojs/index.php/revista/article/view/151
Feo, T.A.; Resende, M.G.C. (1989). A probabilistic heuristic for a computationally difficult set covering problem. Operations Research Letters, Vol. 8, No.
, pp. 67-71.
González, Fernando Pérez. Una metodología de solución basada en la metaheurística Grasp para el problema de diseño de red con incertidumbre. Disponible
en: http://pisis.fime.uanl.mx/ftp/pubs/thesis/msc/2006-fernando_perez/tesis-fer-2006.pdf
Pino, R., Martínez, C., Villanueva, V., Priore, P., &Fernández, I. Application of GRASP methodology to Vehicle Routing Problem (VRP).Disponible en: http://elrond.informatik.tu-freiberg.de/papers/WorldComp2012/ICA6018.pdf
Raúl Esteban Naupari Quiroz, GisselaKatheryn Rosales Gerónimo. Aplicación de algoritmos genéticos para el diseño de un sistema de apoyo a la generación
de horarios de clases para la Facultad de Ingeniería de Sistemas e Informática de la UNMSM. Universidad
Nacional Mayor de San Marcos. Facultad e Ingeniería de Sistemas e Informática. 2010 Lima – Perú.
Elvira Mayordomo. NP-completos. Universidad de Zaragoza. Zaragoza – España. Disponible en; http://webdiis.unizar.es/~elvira/mac/npcompletos.
Bejarano Nicho, Gissella María. Planificación
de horarios del personal de cirugía de un hospital del Estado aplicando algoritmos genéticos (Time TablingProblem).2011. Disponible en: http://tesis.pucp.edu.pe/repositorio/bitstream/handle/123456789/551/BEJARANO_NICHO_GISSELLA_MAR%C3%8DA_PLANIFICACI%C3%93N_HORARIOS_
PERSONAL_CIRUG%C3%8DA.pdf?sequence=1
Francisco J. Martínez Ruiz, Eduardo García Sánchez, Jaime Muñoz Arteaga, Carlos H. Castañeda Ramírez.
Timetabling Académico Usando Algoritmos Genéticos y Programación Celular. Universidad Autónoma de
Zacatecas. Departamento de Ingeniería en Computación. México. Disponible en: http://ingsw.ccbas.uaa.mx/sitio/
images/pdfpublicaciones/artiCoNaCi-Co05-20.pdf
Arranz de la Peña, J. Parra Truyol, A. Algoritmos Genéticos. Disponible en: http://www.it.uc3m.es/jvillena/irc/
practicas/06-07/05.pdf
2.png)
