Skip to main content

Research Repository

Advanced Search

A constructive approach to examination timetabling based on adaptive decomposition and ordering

Abdul-Rahman, Syariza; Burke, Edmund; Bargiela, Andrzej; McCollum, Barry; Özcan, Ender

Authors

Syariza Abdul-Rahman

Edmund Burke

Andrzej Bargiela

Barry McCollum



Abstract

In this study, we investigate an adaptive decomposition and ordering strategy that automatically divides examinations into difficult and easy sets for constructing an examination timetable. The examinations in the difficult set are considered to be hard to place and hence are listed before the ones in the easy set in the construction process. Moreover, the examinations within each set are ordered using different strategies based on graph colouring heuristics. Initially, the examinations are placed into the easy set. During the construction process, examinations that cannot be scheduled are identified as the ones causing infeasibility and are moved forward in the difficult set to ensure earlier assignment in subsequent attempts. On the other hand, the examinations that can be scheduled remain in the easy set. Within the easy set, a new subset called the boundary set is introduced to accommodate shuffling strategies to change the given ordering of examinations. The proposed approach, which incorporates different ordering and shuffling strategies, is explored on the Carter benchmark problems. The empirical results show that the performance of our algorithm is broadly comparable to existing constructive approaches.

Journal Article Type Article
Publication Date Jul 1, 2014
Journal Annals of Operations Research
Print ISSN 0254-5330
Electronic ISSN 1572-9338
Publisher Humana Press
Peer Reviewed Peer Reviewed
Volume 218
Issue 1
APA6 Citation Abdul-Rahman, S., Burke, E., Bargiela, A., McCollum, B., & Özcan, E. (2014). A constructive approach to examination timetabling based on adaptive decomposition and ordering. Annals of Operations Research, 218(1), doi:10.1007/s10479-011-0999-8
DOI https://doi.org/10.1007/s10479-011-0999-8
Keywords timetabling, decomposition, graph colouring, heuristic, grouping
Publisher URL http://link.springer.com/article/10.1007%2Fs10479-011-0999-8
Copyright Statement Copyright information regarding this work can be found at the following address: http://eprints.nottingh.../end_user_agreement.pdf
Additional Information The final publication is available at Springer via http://dx.doi.org/10.1007/s10479-011-0999-8

Files

Decom.pdf (734 Kb)
PDF

Copyright Statement
Copyright information regarding this work can be found at the following address: http://eprints.nottingham.ac.uk/end_user_agreement.pdf





You might also like



Downloadable Citations

;