%0 Journal Article
%A Lara Velázquez, Pedro
%A López Bracho, Rafael
%A Ramírez Rodríguez, Javier
%A Yáñez, Javier
%T A model for timetabling problems with period spread constraints
%D 2011
%@ 0160-5682
%U https://hdl.handle.net/20.500.14352/43672
%X 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.
%~