Abstract
The generalized robust colouring problem (GRCP) deals with a robust colouring for a given graph with a fixed number of colours, not necessarily the chromatic number and considers the distance between colours as the penalization of complementary edges. This problem provides a way to solve timetabling problems that consider ‘event spread constraints’ such as ‘there must be at least d days between two events’. Because this problem is NP-hard, a heuristic approach is necessary to produce good solutions in a reasonable amount of time for large instances. In this work a greedy randomized adaptive search procedure (GRASP) is proposed to solve GRCP, which was used in instances to schedule course lectures requiring from 30 to 120 h per week in total, in which the bound of the optimal solution is reached in almost every instance.
Similar content being viewed by others
References
Burke EK and Petrovic S (2002). Recent research directions in automated timetabling . Eur J Opl Res 140: 266–280.
Burke EK, Jackson K, Kingston J and Weare R (1997). Automated university timetabling: The state of the art . Comput J 40: 565–571.
Čangalović M and Schreuder JAM (1991). Exact colouring algorithm for weighted graphs applied to timetabling problems with lectures of different lengths . Eur J Opl Res 51: 248–258.
Carter MW and Laporte G (1998). Recent developments in practical course timetabling . In: Burke ER and Carter M (eds). Practice and Theory of Automated Timetabling (PATAT) II. LNCS Vol. 1408. Springer: Berlin, pp. 3–19.
Feo TA and Resende MGC (1995). Greedy randomized adaptive search procedures . J Global Optim 6: 109–134.
Lewis RA (2008). A survey of metaheuristic-based techniques for University Timetabling problems . OR Spectrum 30: 167–190.
McCollum B, Schaerf A, Paechter B, McMullan P, Lewis R, Parkes A, Di Gaspero L, Qu R and Burke E (2009). Setting the research agenda in automated timetabling: The second International Timetabling Competition, accepted for publication to INFORMS Journal on Computing, doi: 10.1287/ijoc.1090.0320.
Nandhini M and Kanmani S (2009). A survey of simulated annealing methodology for University Course Timetabling . International Journal of Recent Trends in Engineering 1: 255–257.
Ramírez J (2001). Extensiones del problema de coloración de grafos. Universidad Complutense de Madrid; Spain, ISBN 84-669-1855-8. http://www.ucm.es/BUCM/tesis/mat/ucm-t24770.pdf, accessed 17 April 2009.
Roberts FS (1991). T-colorings of graphs: Recent results and open problems . Discrete Math 93: 229–245.
de Werra D (1985). An introduction to timetabling . Eur J Opl Res 19: 151–162.
de Werra D (1996). Some combinatorial models for course scheduling . In: Burke ER and Ross P (eds). Practice and Theory of Automated Timetabling, LNCS Vol. 1153. Springer Verlag: Berlin, pp. 296–308.
Yáñez J and Ramírez J (2003). The robust coloring problem . Eur J Opl Res 148: 546–558.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Lara-Velázquez, P., López-Bracho, R., Ramírez-Rodríguez, J. et al. A model for timetabling problems with period spread constraints. J Oper Res Soc 62, 217–222 (2011). https://doi.org/10.1057/jors.2009.173
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1057/jors.2009.173