Implementación de un algoritmo GRASP para el problema de coloración de grafos aplicado a la calendarización de exámenes en una institución educativa

Erwin Delgado

Erwin Delgado Escuela Superior Politécnica del Litoral

Resumen

Una de las tareas que enfrentan las instituciones educativas cada año, es la planificación de los horarios de clases y exámenes. Su dificultad radica en que diversas restricciones operativas surgen en el momento de la planificación. Dada la naturaleza del problema descrito anteriormente, la calendarización de exámenes pertenece al conjunto de problemas de optimización combinatoria categorizado NP-Duro por lo que resulta complejo resolverlo por métodos exactos. La ventaja es que la calendarización de exámenes es un problema operativo por lo que bastaría con obtener soluciones factibles de gran calidad, no necesariamente la óptima, en tiempos computacionalesrazonables. Una de las herramientas utilizadas para el efecto, es la construcción de heurísticas basadas en metaheurísticas por la fortaleza en la exploración inteligente en el espacio de soluciones. Con base en lo anterior, en el presente trabajo se desarrollará un algoritmo heurístico basado en la metodología GRASP el mismo que se lo aplicará en la confección de horarios de exámenes sujetos a un conjunto de restricciones de diversas índoles.

Citas

DING-ZHUE DU, PANOS M. PARDALOS. (2005), "Handbook of combinatoria/ optimization". Volumen B, Springer.

BARRY MCCOLLUM, PAUL MCMULLAN. (2007), "The Second International Timetabling Competition: Examination Timetabling Traclc'. Techinical Report. Queen's University Belfast.

E. DELGADO, "Diseño e implementación de un algoritmo GRASP para el problema de coloración de grafos".

DING-ZHUE PARDALOS. DU, (2005). PANOS M. "Handbook of combinatorial optimization", Volumen B, Springer.

ZHIPENG LU, JIN-KAO HAO. (2009). "A memetic algorithm for graph coloring'', European Journal of Operations Research, ELSEVIER.

CÉDRIC AVANTHAY, ALAIN HERTZ, NICOLAS ZUFFEREY. (2003). "A variable neighborhood search for graph coloring". European Journal of Operational Research, ELSEVIER.

A. HERTZ, D. DE WERRA. (1987). "Using Tabu Search Techniques for Graph Coloring". Computing by Springer-Verlag.

C.LUCET, F. MENDES, A. MOUKRIM. (2004). "An Exact method for graph coloring".Computer & Operations Research, ELSEVIER.

ISABEL MÉNDEZ, PAULA ZABALA. (2007). "A cutting plane algorithmfor graph coloring' '. Discrete Applied Mathematics. ELSEVIER.

A. EIBEN, J. VAN DER HAUW, J. VAN HENNERT. "Graph Coloring with Adaptive Evo/utionary Algorithms". Journal of Heuristics, volume 4: 1.

HANS BODLAENDER, DIETER KRATSCH. (2006). "An exact algorithm for graph coloring with polynomial memory". Utrecht University.

DAVID JOHNSON, CECILIA ARAGÓN, LYLE MCGEOCH, CATHERINE SCHEVON, (1990).
"Optimization by simulated annealing: An Experimental Evaluation ; Part IL Graph Coloring and Number Partition ",Operations Research Society of America.

ERIC SOPENA, (2001). "Oriented Graph Coloring' ',ELSEVIER.

WERRA, D. (1990). "Heuristics for Graph Coloring'', Computational Graph Theory, Comput. Suppl. 7, Springer, Vienna, 191-208

BRÉLAZ, D., (1979). "New methods to color the vertices of a graph" , Communications of the Assoc. of Comput. Machinery 22, 251-256.

JOHNSON, D. S., ARAGON, C. R., MCGEOCH, L. A., AND SCHEVON, C. "Optimization by simulated annealing: An experimenta/ eva/uation" ; part ii, graph coloring and number partitioning. Operations Research, 39(3):378406.

RESENDE M., RIBEIRO C., (2002). Greedy Randomized Adaptive Search Procedures, AT&T Labs Research Technical Report. Hanbook in Metaheuristic, Fred Glover.

GLOVER FRED, KOCHENBERGER. (2003). "HandBook of Metaheuristics'', Intemational Series in Operations Research & Management Science.

TALBI EL-GHAZALI. (2009). Metaheristics from design to implementaction, John Wiley & Sons, Inc., Hoboken, New