Page 27 - Fister jr., Iztok, Andrej Brodnik, Matjaž Krnc and Iztok Fister (eds.). StuCoSReC. Proceedings of the 2019 6th Student Computer Science Research Conference. Koper: University of Primorska Press, 2019
P. 27
wo-stage heuristic for the university course timetabling
problem
Máté Pintér ∗
University of Szeged, Institute of Informatics Balázs Dávid
Árpád tér 2 InnoRenew CoE
Szeged, Hungary, 6720 Livade 6
pmate955@gmail.com Izola, Slovenia, 6310
balazs.david@innorenew.eu
University of Primorska, FAMNIT
Glagoljaška ulica 8
Koper, Slovenia, 6000
balazs.david@famnit.upr.si
ABSTRACT Timetabling Competition. These instances are based on real
world timetables of the University of Udine, Italy.
This paper presents a two-stage solution method for the
curriculum-based university course timetabling problem. First, 2. COURSE TIMETABLING
an initial solution is created using a recursive search algo-
rithm, then its quality is improved with a local search heuris- Course timetabling is an optimization problem, where re-
tic. This method utilizes a tabu list of forbidden transfor- sources (courses, rooms, teachers) are allocated to create
mations, as well as a destructive step at the end of each a timetable that satisfies given constraints. The problem
iteration. The algorithm is tested on datasets of the 2007 schedules courses and teachers into available time-slots, while
International Timetabling Competition. trying to avoid the different types of conflicts that can arise.
Many variations exist for the course timetabling problem,
Keywords but the most important ones are the following:
University course timetabling; Local search; Heuristic • Curriculum-based Course Timetabling: courses belong
to one of several curricula, and courses of the same
1. INTRODUCTION curriculum cannot be scheduled in overlapping time-
slots.
Creating the timetable of employees is a crucial task for
any organization, and educational institutions are no excep- • Post Enrollment based Course Timetabling: the prob-
tions. While timetabling problems can sometimes be ex- lem also considers the students enrolled to the courses,
tremely hard, they are still solved manually in many cases. and introduces several constraints connected to their
This process can take a long time, and the efficiency of the attendance.
resulting timetables is not guaranteed.
• Examination Timetabling: similar to the general time-
There are several different types of timetabling problems tabling problem, but considers exam committees in-
that have to be solved in academia, mainly connected to stead of teachers, and also deals with the availability
the students or the employees. This paper will cover such a of the students for their required exams.
specific problem, namely university course timetabling.
This paper will give a solution algorithm for the curriculum-
The first section of this paper will introduce the field of based course timetabling problem. The following sections
course timetabling, and present the curriculum-based uni- will define the problem, present its necessary resources and
versity course timetabling problem in detail. After this, we constraints, and give a short literature overview of the field.
present a two-stage heuristic for the solution of the problem,
which is then tested on datasets of the 2007 International 2.1 Problem definition
∗Supervisor The curriculum-based university course timetabling problem
schedules a set C of courses over a horizon of d days to cre-
ate a timetable. Each day is divided into s time-slots, and
a course has to be assigned to one or more consecutive slots
(depending on its length). A room has to be selected where
the course will take place, and a teacher is also assigned as
the instructor. Courses can belong to different curricula, in-
troducing additional constraints to the assignment. Courses
of the same curriculum usually cannot overlap, or should be
StuCoSReC Proceedings of the 2019 6th Student Computer Science Research Conference DOI: https://doi.org/10.26493/978-961-7055-82-5.27-30 27
Koper, Slovenia, 10 October
problem
Máté Pintér ∗
University of Szeged, Institute of Informatics Balázs Dávid
Árpád tér 2 InnoRenew CoE
Szeged, Hungary, 6720 Livade 6
pmate955@gmail.com Izola, Slovenia, 6310
balazs.david@innorenew.eu
University of Primorska, FAMNIT
Glagoljaška ulica 8
Koper, Slovenia, 6000
balazs.david@famnit.upr.si
ABSTRACT Timetabling Competition. These instances are based on real
world timetables of the University of Udine, Italy.
This paper presents a two-stage solution method for the
curriculum-based university course timetabling problem. First, 2. COURSE TIMETABLING
an initial solution is created using a recursive search algo-
rithm, then its quality is improved with a local search heuris- Course timetabling is an optimization problem, where re-
tic. This method utilizes a tabu list of forbidden transfor- sources (courses, rooms, teachers) are allocated to create
mations, as well as a destructive step at the end of each a timetable that satisfies given constraints. The problem
iteration. The algorithm is tested on datasets of the 2007 schedules courses and teachers into available time-slots, while
International Timetabling Competition. trying to avoid the different types of conflicts that can arise.
Many variations exist for the course timetabling problem,
Keywords but the most important ones are the following:
University course timetabling; Local search; Heuristic • Curriculum-based Course Timetabling: courses belong
to one of several curricula, and courses of the same
1. INTRODUCTION curriculum cannot be scheduled in overlapping time-
slots.
Creating the timetable of employees is a crucial task for
any organization, and educational institutions are no excep- • Post Enrollment based Course Timetabling: the prob-
tions. While timetabling problems can sometimes be ex- lem also considers the students enrolled to the courses,
tremely hard, they are still solved manually in many cases. and introduces several constraints connected to their
This process can take a long time, and the efficiency of the attendance.
resulting timetables is not guaranteed.
• Examination Timetabling: similar to the general time-
There are several different types of timetabling problems tabling problem, but considers exam committees in-
that have to be solved in academia, mainly connected to stead of teachers, and also deals with the availability
the students or the employees. This paper will cover such a of the students for their required exams.
specific problem, namely university course timetabling.
This paper will give a solution algorithm for the curriculum-
The first section of this paper will introduce the field of based course timetabling problem. The following sections
course timetabling, and present the curriculum-based uni- will define the problem, present its necessary resources and
versity course timetabling problem in detail. After this, we constraints, and give a short literature overview of the field.
present a two-stage heuristic for the solution of the problem,
which is then tested on datasets of the 2007 International 2.1 Problem definition
∗Supervisor The curriculum-based university course timetabling problem
schedules a set C of courses over a horizon of d days to cre-
ate a timetable. Each day is divided into s time-slots, and
a course has to be assigned to one or more consecutive slots
(depending on its length). A room has to be selected where
the course will take place, and a teacher is also assigned as
the instructor. Courses can belong to different curricula, in-
troducing additional constraints to the assignment. Courses
of the same curriculum usually cannot overlap, or should be
StuCoSReC Proceedings of the 2019 6th Student Computer Science Research Conference DOI: https://doi.org/10.26493/978-961-7055-82-5.27-30 27
Koper, Slovenia, 10 October
