Skip to main content
Log in

A model for timetabling problems with period spread constraints

  • Technical Note
  • Published:
Journal of the Operational Research Society

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

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.

    Article  Google Scholar 

  • Burke EK, Jackson K, Kingston J and Weare R (1997). Automated university timetabling: The state of the art . Comput J 40: 565–571.

    Article  Google Scholar 

  • Č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.

    Article  Google Scholar 

  • 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.

    Chapter  Google Scholar 

  • Feo TA and Resende MGC (1995). Greedy randomized adaptive search procedures . J Global Optim 6: 109–134.

    Article  Google Scholar 

  • Lewis RA (2008). A survey of metaheuristic-based techniques for University Timetabling problems . OR Spectrum 30: 167–190.

    Article  Google Scholar 

  • 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.

    Google Scholar 

  • 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.

    Article  Google Scholar 

  • de Werra D (1985). An introduction to timetabling . Eur J Opl Res 19: 151–162.

    Article  Google Scholar 

  • 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.

    Chapter  Google Scholar 

  • Yáñez J and Ramírez J (2003). The robust coloring problem . Eur J Opl Res 148: 546–558.

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to J Ramírez-Rodríguez.

Rights and permissions

Reprints 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

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1057/jors.2009.173

Keywords

Navigation