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

Authors

  • 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

Keywords:

Timetabling, Combinatorial Optimization, Heuristics, Genetic Algorithms

Abstract


The academic scheduling is a particular problem within the general problem of resource allocation. This scheduling problem is known as the University Timetabling Problem in the scientific community. The scheduling problems consist on generating schedules for defined tasks by pursuing the best way to specific conditions or requirements. This problem has been addressed with different methods such as Ant Colony, Tabu Search, Graph Coloring and Genetic Algorithms. In this paper we review some evolutionary algorithms that have addressed the problem of academic schedules applying different models.

Author Biography

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.

References

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.

Downloads

Published

2011-09-06

How to Cite

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

Issue

Vol. 3 No. 1 (2011): June, 2011

Section

Articles

License

Copyright (c) 2011 Programación Mtatemática y Software

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

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.