Revisión de Algoritmos Genéticos Aplicados al Problema de la Programación de Cursos Universitarios

Autores/as

  • Mireya Flores Pichardo CIICAp, Universidad Autónoma del Estado de Morelos Av. Universidad 1001, Chamilpa, 62209, Cuernavaca Morelos, MÉXICO

DOI:

https://doi.org/10.30973/progmat/2011.3.1/5

Palabras clave:

Programación de Horarios, Optimización Combinatoria, Heurísticas, Algoritmos Genéticos.

Resumen

La programación de horarios académicos es un problema particular que se encuentra dentro del problema general de asignación de recursos. Este problema de horarios, se conoce en la comunidad científica como Problema de Programación de Horarios Universitarios. Los problemas de programación de horarios consisten en generar horarios para tareas definidas, buscando cumplir de la mejor manera con condiciones o requerimientos específicos. Este problema ha sido tratado con diferentes métodos, por ejemplo Colonia de Hormigas, Búsqueda Tabú, Coloreo de grafos y Algoritmos Genéticos. En éste trabajo se hace una revisión de algunos algoritmos evolutivos que han abordado el problema de horarios académicos aplicando diferentes modelos.

Biografía del autor/a

Mireya Flores Pichardo, CIICAp, Universidad Autónoma del Estado de Morelos Av. Universidad 1001, Chamilpa, 62209, Cuernavaca Morelos, MÉXICO

Licenciada en informática egresada de la Facultad de contaduría, administración e informática (UAEM). Maestría en Ciencias en Ciencias de la Computación con especialidad en Ingeniería de Software. “Estudio empírico para la transformación gramatical de código en lenguaje COBOL hacia lenguaje Java”. Centro Nacional de Investigación y Desarrollo Tecnológico (CENIDET). Actualmente estudiante de Doctorado en Ingeniería y Ciencias Aplicadas con especialidad optimización combinatoria Área: asignación de recursos - programación de cursos universitarios.

Citas

K. Banczyk; T. Boinski; H. Krawczyk: Parallelisation of Genetic Algorithms for Solving University Timetabling Problems PAR ELEC. Pgs.:325 – 330 2006. https://doi.org/10.1109/PARELEC.2006.64

A. Saldaña Crovo; C. Oliva San Martín,; L. Pradenas Rojas: Modelos de programación entera para un Problema de Programación de Horarios para Universidades Ingeniare. Revista chilena de ingeniería, Vol. 15 No.3, pp.245-259 2007

S. Even, A. Itai and A. Shamir: On the Complexity of Timetable and Multicommodity Flow Problems. SIAM Journal on Computing, Vol. 5, No.4 pags 691-703 1976. https://doi.org/10.1109/SFCS.1975.21

A. Díaz, F. Glover, H.M. Ghaziri. Optimización Heurística y Redes Neuronales. Madrid, Paraninfo. 1996

A. Chaudhuri and K. De: Fuzzy Genetic Heuristic for University Course Timetable Problem 2010

D. Beasly, D.R. Bull, R. Martin: An Overview of Genetic Algorithms: Part 1 Fundamentals. 1993

A. Colorni, M. Dorigo and V. Maniezzo: A genetic algorithm to solve the timetable problem, Technical Report No. 90-060 Politecnico di Milano, Italy 1992

Y. Enzhe and S. Ki-Seok: A genetic algorithm for a university weekly courses timetabling problem International Federation of Operational Research Societies, 2002.

D. S. Calogero and A. G. B. Tettamanzi: An Evolutionary Algorithm for Solving the School Time-Tabling Problem EvoWorkshop LNCS 2037. pgs. 452-462 2001 https://doi.org/10.1007/3-540-45365-2_47

E. Burke, R. Weare and D. Elliman: A hybrid Genetic Algorithm for Highly Constrained Timetabling Problems Computer Science Technical Report No. NOTTCS-TR-1995-8 1995

R. Raghavjee and N. Pillay: An Application of Genetic Algorithms to the School Timetabling Problem SAICSIT 2008. https://doi.org/10.1145/1456659.1456682

K. Smith, D. Abramson, and D. Hopfield Duke. Neural Networks for Timetabling: Formulations, Methods and Comparative Timetabling. Computers and Industrial Engineering, 4(2). 2003, 283-305. 2003

M. Randall, D. Abramson, and C. Wild.: A Meta-Heuristic Based Solver for Combinatorial Optimization Problems. Technical, Report, TR99-01, School of Information Technology, Bold University, Australia 1999

S. Abdullah, E. K. Burke and B. McCollum: A Hybrid Evolutionary Approach to the University Course Timetabling Problem. IEEE Congress on Evolutionary Computation, ISBN: 1-4244- 1340-0. Singapore, 25-28 September, pp 1764-1768 2007. https://doi.org/10.1109/CEC.2007.4424686

K. Socha, J. Knowles, M. Samples, A Max-Min Ant System for the University Course Timetabling Problem. In: The Proceedings of the 3rd International Workshop on Ant Algorithms, ANTS 2002, Springer Lecture Notes in Computer Science Vol.2463, Springer-Verlag, 1-13. 2002. https://doi.org/10.1007/3-540-45724-0_1

S. Abdullah, E.K. Burke, B. McCollum, Using a Randomized Iterative Improvement Algorithm with Composite Neighborhoods Structures for the University Course Timetabling Problem. Accepted for publication in the Metaheuristics International Conference (MIC’2005), Vienna, Austria, August 22nd-26th, post conference volume (eds. Karl Doerner, Michel Gendreau, Walter Gutjahr, Peter Greistorfer, Richard Hartl, Marc Reimann), to appear 2007. https://doi.org/10.1007/978-0-387-71921-4_8

S. Abdullah, E.K. Burke, B. McCollum, An Investigation of a Variable Neighborhoods Search Approach for Course Timetabling. In: The Proceedings of the 2nd Multidisciplinary International Conference on Scheduling: Theory and Applications (MISTA 2005), New York, USA, July 18th 21st, 413-427, 2005.

E.K. Burke, G. Kendall, E. Soubeiga, A Tabu-Search Hyperheuristic for Timetabling and Rostering. Journal of Heuristics, Volume 9, No.6, 451- 470 2003. https://doi.org/10.1023/B:HEUR.0000012446.94732.b6

E.K. Burke, B. McCollum, A. Meisels, S. Petrovic, R. Qu, A Graph-Based Hyper Heuristic for Educational Timetabling Problems. European Journal of Operational Research 176(1), 177-192. 2007. https://doi.org/10.1016/j.ejor.2005.08.012

H. Asmuni, E.K. Burke, J.M. Garibaldi, Fuzzy Multiple Heuristic Ordering for Course Timetabling. In: The Proceedings of the 5th United Kingdom Workshop on Computational Intelligence (UKCI05), London, UK, September 5th-7th, 302-309, 2005.

Descargas

Publicado

06-09-2011

Cómo citar

Flores Pichardo, M. (2011). Revisión de Algoritmos Genéticos Aplicados al Problema de la Programación de Cursos Universitarios. Programación matemática Y Software, 3(1), 49–65. https://doi.org/10.30973/progmat/2011.3.1/5

Número

Vol. 3 Núm. 1 (2011): Junio de 2011

Sección

Artículos

Licencia

Derechos de autor 2011 Programación Mtatemática y Software

Creative Commons License

Esta obra está bajo una licencia internacional Creative Commons Atribución 4.0.

Usted es libre de:

Compartir — compartir y redistribuir el material publicado en cualquier medio o formato.
Adaptar — combinar, transformar y construir sobre el material para cualquier propósito, incluso comercialmente.

Bajo las siguientes condiciones:

Atribución — Debe otorgar el crédito correspondiente, proporcionar un enlace a la licencia e indicar si se realizaron cambios. Puede hacerlo de cualquier manera razonable, pero de ninguna manera que sugiera que el licenciador lo respalda a usted o a su uso.
  Sin restricciones adicionales: no puede aplicar términos legales o medidas tecnológicas que restrinjan legalmente a otros a hacer cualquier cosa que permita la licencia.