A new lower bound for curriculum-based course timetabling

In this paper, we propose a new method to compute lower bounds for curriculum-based course timetabling (CTT), 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...

Full description

Saved in:
Bibliographic Details
Published in:Computers & operations research 2013-10, Vol.40 (10), p.2466-2477
Main Authors: Cacchiani, V., Caprara, A., Roberti, R., Toth, P.
Format: Article
Language:English
Subjects:
Applied sciences
Benchmarking
Benchmarks
Colleges & universities
Column generation
Curricula
Exact sciences and technology
General aspects
Heuristic
Integer programming
Lectures
Lower bounds
Mathematical analysis
Mathematical models
Mathematical programming
Occupational training. Personnel. Work management
Operational research and scientific management
Operational research. Management science
Operations research
Optimization
Scheduling, sequencing
School schedules
Splitting
Studies
Timetabling
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this paper, we propose a new method to compute lower bounds for curriculum-based course timetabling (CTT), 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 up 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).
ISSN:0305-0548
1873-765X
0305-0548
DOI:10.1016/j.cor.2013.02.010