|
Título:
|
A model for timetabling problems with period spread constraints
|
|
Autores:
|
Lara Velázquez, P. ;
López Bracho, R. ;
Ramírez Rodríguez, J. ;
Yáñez, Javier
|
|
Tipo de documento:
|
texto impreso
|
|
Editorial:
|
Stockton Press, 2011-01
|
|
Palabras clave:
|
Estado = Publicado
,
Materia = Ciencias: Matemáticas: Estadística matemática
,
Tipo = Artículo
|
|
Resumen:
|
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.
|
