A model for timetabling problems with period spread constraints

P Lara-Velázquez, R López-Bracho (), J Ramírez-Rodríguez () and J Yáñez
Additional contact information
P Lara-Velázquez: Departamento de Sistemas, Universidad Autónoma Metropolitana–Azcapotzalco
R López-Bracho: Departamento de Sistemas, Universidad Autónoma Metropolitana–Azcapotzalco
J Ramírez-Rodríguez: Departamento de Sistemas, Universidad Autónoma Metropolitana–Azcapotzalco
J Yáñez: Universidad Complutense de Madrid

Journal of the Operational Research Society, 2011, vol. 62, issue 1, 217-222

Abstract: 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.

Keywords: heuristics; lecture-timetabling; robust colouring (search for similar items in EconPapers)
Date: 2011
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1057/jors.2009.173 Abstract (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:pal:jorsoc:v:62:y:2011:i:1:d:10.1057_jors.2009.173

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/41274

DOI: 10.1057/jors.2009.173

Access Statistics for this article

Journal of the Operational Research Society is currently edited by Tom Archibald and Jonathan Crook

More articles in Journal of the Operational Research Society from Palgrave Macmillan, The OR Society
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().