Cyclic transfers in school timetabling

Gerhard Post*, Samad Ahmadi, Frederik Geertsema

*Corresponding author for this work

Research output: Contribution to journalArticleAcademicpeer-review

10 Citations (Scopus)
64 Downloads (Pure)

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.
Original languageEnglish
Pages (from-to)133-154
Number of pages22
JournalOR Spectrum = OR Spektrum
Volume34
Issue number1
DOIs
Publication statusPublished - 2012

Keywords

  • MSC-90C59
  • Cyclic transfer
  • Scheduling
  • Timetabling
  • High school

Fingerprint

Dive into the research topics of 'Cyclic transfers in school timetabling'. Together they form a unique fingerprint.
  • Cyclic transfers in school timetabling

    Post, G., Ahmadi, S. & Geertsema, F., Nov 2009, Enschede: University of Twente. 24 p. (Memorandum / Department of Applied Mathematics; no. 1906)

    Research output: Book/ReportReportProfessional

    Open Access
    File

Cite this