A new lower bound for curriculum-based course timetabling

V. Cacchiani, A. Caprara, Roberto Roberti, P. Toth

Research output: Contribution to journalJournal articleResearchpeer-review

193 Downloads (Pure)

Abstract

In this paper, we propose a new method to compute lower bounds for curriculum-based course timetabling (M), which calls for the best weekly assignment of university course lectures to rooms and time slots. The lower bound is obtained by splitting the objective function into two parts, considering one separate problem for each part of the objective function, and summing lip the corresponding optimal values (or, in some cases, lower bounds on these values), found by formulating the two parts as Integer Linear Programs (ILPs). The solution of one ILP is obtained by using a column generation procedure. Experimental results show that the proposed lower bound is often better than the ones found by the previous methods in the literature, and also much better than those found by other new ILP formulations illustrated in this paper. The proposed approach is able to obtain improved lower bounds on real-world benchmark instances from the literature, used in the international timetabling competitions ITC2002 and ITC2007, proving for the first time that some of the best-known heuristic solutions are indeed optimal (or close to the optimal ones). (C) 2013 Elsevier Ltd. All rights reserved.
Original languageEnglish
JournalComputers & Operations Research
Volume40
Issue number10
Pages (from-to)2466-2477
Number of pages12
ISSN0305-0548
DOIs
Publication statusPublished - 2013
Externally publishedYes

Keywords

  • COMPUTER
  • ENGINEERING,
  • OPERATIONS
  • Timetabling
  • Column generation
  • Lower bounds
  • Curricula
  • Integer programming
  • Optimization
  • Scheduling
  • Course timetabling
  • Heuristic solutions
  • Integer linear programs
  • Objective functions
  • University course
  • TIME perspective

Fingerprint Dive into the research topics of 'A new lower bound for curriculum-based course timetabling'. Together they form a unique fingerprint.

Cite this