A model for timetabling problems with period spread constraints

作者：Lara Velazquez P; Lopez Bracho R; Ramirez Rodriguez J^*; Yanez J

来源：Journal of the Operational Research Society, 2011, 62(1): 217-222.

DOI：10.1057/jors.2009.173

• heuristics
• lecture-timetabling
• robust colouring

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. Journal of the Operational Research Society (2011) 62, 217-222. doi:10.1057/jors.2009.173 Published online 27 January 2010

• 出版日期2011-1