Novel Local-Search-Based Approaches to University Examination Timetabling

Examination timetabling assigns examinations to a given number of time slots so that there are no conflicts. A conflict occurs if a student has to take more than one examination at the same time, or when the number of students that must take an exam exceeds the capacity of the classroom assigned. Th...

Full description

Saved in:
Bibliographic Details
Published in:INFORMS journal on computing 2008, Vol.20 (1), p.86-99
Main Authors: Caramia, Massimiliano, Dell'Olmo, Paolo, Italiano, Giuseppe F
Format: Article
Language:English
Subjects:
algorithm
Algorithms
Classrooms
Colleges & universities
Costs
Educational tests and measurements
examination timetabling
Examinations
Fines & penalties
Heuristic
local search
Management
Operations management
Schedules
Scheduling
Scheduling (Management)
Studies
Tests
Universities and colleges
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:Examination timetabling assigns examinations to a given number of time slots so that there are no conflicts. A conflict occurs if a student has to take more than one examination at the same time, or when the number of students that must take an exam exceeds the capacity of the classroom assigned. The objective is to minimize penalties from proximity constraints. We present new algorithms based on local search and report on an extensive experimental study. We consider also a variant where the concern is to produce conflict-free timetables minimizing the number of time slots, regardless of how close exams appear in the schedule. The algorithms proposed also manage the trade-off between the two objective functions and produce the best results on several standard benchmark instances, compared to the best existing algorithms.
ISSN:1091-9856
1526-5528
1091-9856
DOI:10.1287/ijoc.1070.0220