DOI:

https://doi.org/10.14483/2322939X.6478

Publicado:

2013-12-11

Edição:

v. 10 n. 2 (2013)

Seção:

Actualidad Tecnológica

Problema del school timetabling y algoritmos genéticos: una revisión

Timetabling School problem and genetic algorithms: a review

Autores

  • Mauricio Andres Guerra Cubillos
  • Erwin Hamid Pardo Quiroga
  • Roberto Emilio Salas Ruiz

Palavras-chave:

Timetabling, computational complexity, metaheuristics algorithms, genetic algorithms (en).

Palavras-chave:

Timetabling, Complejidad computacional, algoritmos metaheuristicos, Algoritmos Genéticos. (es).

Downloads

Resumo Métricas Disponíveis Referências Como Citar

Resumo (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.

Resumo (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.

 

Referências

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

pdf

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.

pdf

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

Como Citar

IEEE

[1]
M. A. Guerra Cubillos, E. H. Pardo Quiroga, e R. E. Salas Ruiz, “Problema del school timetabling y algoritmos genéticos: una revisión”, Rev. Vínculos, vol. 10, nº 2, p. 259–276, dez. 2013.

ACM

[1]
Guerra Cubillos, M.A. et al. 2013. Problema del school timetabling y algoritmos genéticos: una revisión. Revista Vínculos. 10, 2 (dez. 2013), 259–276. DOI:https://doi.org/10.14483/2322939X.6478.

ACS

(1)
Guerra Cubillos, M. A.; Pardo Quiroga, E. H.; Salas Ruiz, R. E. Problema del school timetabling y algoritmos genéticos: una revisión. Rev. Vínculos 2013, 10, 259-276.

APA

Guerra Cubillos, M. A., Pardo Quiroga, E. H., e Salas Ruiz, R. E. (2013). Problema del school timetabling y algoritmos genéticos: una revisión. Revista Vínculos, 10(2), 259–276. https://doi.org/10.14483/2322939X.6478

ABNT

GUERRA CUBILLOS, Mauricio Andres; PARDO QUIROGA, Erwin Hamid; SALAS RUIZ, Roberto Emilio. Problema del school timetabling y algoritmos genéticos: una revisión. Revista Vínculos, [S. l.], v. 10, n. 2, p. 259–276, 2013. DOI: 10.14483/2322939X.6478. Disponível em: https://revistas.udistrital.edu.co/index.php/vinculos/article/view/6478. Acesso em: 28 dez. 2024.

Chicago

Guerra Cubillos, Mauricio Andres, Erwin Hamid Pardo Quiroga, e Roberto Emilio Salas Ruiz. 2013. “Problema del school timetabling y algoritmos genéticos: una revisión”. Revista Vínculos 10 (2):259-76. https://doi.org/10.14483/2322939X.6478.

Harvard

Guerra Cubillos, M. A., Pardo Quiroga, E. H. e Salas Ruiz, R. E. (2013) “Problema del school timetabling y algoritmos genéticos: una revisión”, Revista Vínculos, 10(2), p. 259–276. doi: 10.14483/2322939X.6478.

MLA

Guerra Cubillos, Mauricio Andres, et al. “Problema del school timetabling y algoritmos genéticos: una revisión”. Revista Vínculos, vol. 10, nº 2, dezembro de 2013, p. 259-76, doi:10.14483/2322939X.6478.

Turabian

Guerra Cubillos, Mauricio Andres, Erwin Hamid Pardo Quiroga, e Roberto Emilio Salas Ruiz. “Problema del school timetabling y algoritmos genéticos: una revisión”. Revista Vínculos 10, no. 2 (dezembro 11, 2013): 259–276. Acessado dezembro 28, 2024. https://revistas.udistrital.edu.co/index.php/vinculos/article/view/6478.

Vancouver

1.
Guerra Cubillos MA, Pardo Quiroga EH, Salas Ruiz RE. Problema del school timetabling y algoritmos genéticos: una revisión. Rev. Vínculos [Internet]. 11º de dezembro de 2013 [citado 28º de dezembro de 2024];10(2):259-76. Disponível em: https://revistas.udistrital.edu.co/index.php/vinculos/article/view/6478

Baixar Citação

Visitas

2036

Downloads

Não há dados estatísticos.

Licença

 


Este obra está sob uma licença Creative Commons Atribuição 4.0

 

Artigos mais lidos pelo mesmo(s) autor(es)