Results for the University Examination Timetabling Problem

Computer Systems Laboratory
University of Patras

Last Update: 02/01/2009

CSL Timetabling Team
Gogos Christos MSc	Dr. Alefragis Panayiotis	Goulas George	Prof. Housos Efthymios

Download solution validation source code in Java for ITC07

Introduction

Examination timetabling for Universities is a well studied problem mainly due to its practical importance. The goal of the research effort undertaken by our team was to address the problem in an attempt to investigate ways in which the gap between research and practice can be bridged. During our involvement with the problem the second international timetabling competition (ITC07) was in progress and included a special track about examination timetabling.

Our partticipation in ITC07 qualified second amongst competitors Winner of the examination track was Tomas Muller. Results can be found in http://www.cs.qub.ac.uk/itc2007/winner/finalorder.htm. The paper "A multi staged algorithmic process for the solution of the examination timetabling problem" (pdf) was submitted in PATAT08.

Details about the publicly available datasets used for benchmarking competitors can be seen in the following table.

ITC07-DATASETS
	Exams	Students	Periods	Rooms	Two In A Row Penalty	Two In A Day Penalty	Period Spread	Number Of Mixed Durations Penalty	Number Of Largest Exams	Number Of Last Periods To Avoid	Frontload Penalty	Conflict Density
Dataset 1	607	7891	54	7	7	5	5	10	100	30	5	5.05%
Dataset 2	870	12743	40	49	15	5	1	25	250	30	5	1.17%
Dataset 3	934	16439	36	48	15	10	4	20	200	20	10	2.62%
Dataset 4	273	5045	21	1	9	5	2	10	50	10	5	15.00%
Dataset 5	1018	9253	42	3	40	15	5	0	250	30	10	0.87%
Dataset 6	242	7909	16	8	20	5	20	25	25	30	15	6.16%
Dataset 7	1096	14676	80	15	25	5	10	15	250	30	10	1.93%
Dataset 8	598	7718	80	8	150	0	15	25	250	30	5	4.55%

Our involvement with the problem continued and after the completion of the competition. We present in the following table our newest results under the column Gogos, Alefragis, Housos (2) while in column Muller (2) are the best results that Muller reports in his paper (pdf) for PATAT08 .

	Muller (1)	Gogos, Alefragis, Housos (1)	Atsuta, Konobe, Ibaraki	De Smet	Pillay	Muller (2)	Gogos, Alefragis, Housos (2)
Dataset 1	4.370	5.905	8.006	6.670	12.035	4.356	4.775
Dataset 2	400	1.008	3.470	623	3.074	390	385
Dataset 3	10.049	13.771	17.669	infeasible	15.917	9.568	8.996
Dataset 4	18.141	18.674	22.559	infeasible	23.582	16.591	16.204
Dataset 5	2.988	4.139	4.714	3.848	6.860	2.941	2.929
Dataset 6	26.585	27.640	29.155	27.815	32.250	25.775	25.740
Dataset 7	4.213	6.572	10.473	5.429	17.666	4.088	4.087
Dataset 8	7.742	10.521	14.317	infeasible	16.184	7.565	7.777

Our newest results are significantly better than our previous one. A high level view of our improved approach is depicted in the following figure.

	dataset1	dataset2	dataset3	dataset4	dataset5	dataset6	dataset7	dataset8
Two Exams in a Row	154	0	1.620	5.859	0	3.740	25	0
Two Exams in a Day	0	10	1.610	4.290	0	0	0	0
Wider Spreads	2.716	0	4.926	3.925	1.259	19.900	3.602	6.872
Period Penalties	320	0	100	2.000	200	450	0	365
Room Penalties	1.050	375	0	0	0	1.200	0	135
Mix Duration Penalties	280	0	0	0	0	75	0	0
Front Load Penalties	255	0	740	130	1.470	375	460	405
Total Penalty	4.775	385	8.996	16.204	2.929	25.740	4.087	7.777

Solution files per dataset

dataset1 (cost=4.775)
dataset2 (cost=385)
dataset3 (cost=8.996)
dataset4 (cost=16.204)
dataset5 (cost=2.929)
dataset6 (cost=25.740)
dataset7 (cost=4.087)
dataset8 (cost=7.777)

The above results are included in the paper "An improved multi-staged algorithmic process for the solution of the examination timetabling problem" that is currently under review in the Special Issue of Annals of OR on the Practice and Theory of Automated Timetabling.

Cost trajectory per dataset (construction cost/improvement cost)