Cyclic transfers in school timetabling

De Montfort University Open Research Archive

Show simple item record

dc.contributor.author Post, G. en
dc.contributor.author Ahmadi, Samad en
dc.contributor.author Geertsema, F. en
dc.date.accessioned 2012-04-04T09:38:55Z
dc.date.available 2012-04-04T09:38:55Z
dc.date.issued 2010
dc.identifier.citation Post, G,, Ahmadi, S. and Geertsema, F. (2010) Cyclic transfers in school timetabling. OR Spectrum, 34 (1), pp 133-154 en
dc.identifier.issn 0171-6468
dc.identifier.uri http://hdl.handle.net/2086/5878
dc.description.abstract In this paper we propose a neighbourhood structure based on sequential/cyclic moves and a cyclic transfer algorithm for the high school timetabling problem. This method enables execution of complex moves for improving an existing solution, while dealing with the challenge of exploring the neighbourhood efficiently. An improvement graph is used in which certain negative cycles correspond to the neighbours; these cycles are explored using a recursive method. We address the problem of applying large neighbourhood structure methods on problems where the cost function is not exactly the sum of independent cost functions, as it is in the set partitioning problem. For computational experiments we use four real world data sets for high school timetabling in the Netherlands and England. We present results of the cyclic transfer algorithm with different settings on these data sets. The costs decrease by 8–28% if we use the cyclic transfers for local optimization compared to our initial solutions. The quality of the best initial solutions are comparable to the solutions found in practice by timetablers. en
dc.language.iso en en
dc.subject timetabling en
dc.subject high school en
dc.subject cyclic transfer en
dc.subject scheduling en
dc.title Cyclic transfers in school timetabling en
dc.type Article en
dc.identifier.doi http://dx.doi.org/10.1007/s00291-010-0227-y
dc.researchgroup Centre for Computational Intelligence en
dc.ref2014.selected 1367395509_0310680107233_11_1


Files in this item

Files Size Format View

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record