Page 28 - 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. 28
eduled close to each other in time. The constraints of the by Lach et al. [9], where only courses and time-slots are as-
problem belong into two different groups. signed using a binary variable, and the possible rooms for
each time-slot are described by an undirected graph. This
Hard constraints should always be respected, and a timetable approach reduces the model size, and is able to provide so-
is not allowed to violate any of them. The most common lutions for significantly bigger instances.
hard constraints are the following:
As mathematical approaches can result in a large model even
• Course assignment: The timetable must contain all for relatively small instances, various heuristic methods were
courses, and every course has to be assigned to exactly also developed for the problem. Different variations of the
one room, time-slot and teacher. local search were presented, such as the tabu search of Lu¨
and Hao [10] or the simulated annealing of Bellio et al. [3].
• Room availability: A given room cannot have more Improved versions of Dueck’s Great Deluge algorithm [7] -
than one assigned course at the same time-slot. a genetic algorithm with a philosophy close to local search -
were also been published [5]. Hybrid algorithms with multi-
• Teacher availability: A given teacher cannot be as- ple stages are also available, like Mu¨ller [11] or Shaker et al.
signed to more than one course at the same time-slot. [12], both of which are modifications of the Great Deluge.
• Room capacity: A course cannot be scheduled to a 3. A TWO-STAGE HEURISTIC
room with less capacity than the number of students
on the course. Some papers consider this as a soft In this section, we propose a two-stage heuristic for solving
constraint. the curriculum-based university course timetabling problem.
First, an initial feasible solution is created using a greedy
• Teacher availability: Teachers can have time-slots when recursive algorithm, then a local search heuristic is utilized
they are not available. Naturally, no course can be as- to improve its quality.
signed to a teacher at a time-slot where they are not
available. Some papers consider this as a soft con- We apply the following soft constraints from Section 2: Com-
straint. pactness, Room capacity, Room stability, Minimum number
of days. The reason for this is that we use the datasets of the
Soft constraints can be violated, but they come with a penalty. Curriculum-based Course Timetabling track of the Interna-
The typical soft constraints are the following: tional Timetabling Competition 2007 (ITC) [6] as evaluation
for the method, and this competition also considers the same
• Compactness: Isolated courses in a curriculum should constraints.
be avoided. A course is isolated, if no other course
of the same curriculum is scheduled in its previous or The initial solution is created using a recursive search, which
next time-slot. only considers the hard constraints of the problem. The
pseudo-code of this can be seen in Algorithm 1.
• Room stability: Courses of the same curriculum should
be assigned to the same room, if possible. Algorithm 1 Recursive algorithm for initial solution.
• Minimal number of days: Courses of the same curricu- Funct recSol(course, node, list)
lum should be spread out over the week: they should 1: if All courses are assigned then
be scheduled to a given d amount of days. 2: return TRUE
3: end if
• As it was mentioned above, some of the hard constraint 4: if No more assignment possibilities then
(room capacity, unavailability of teachers) can also be 5: return FALSE
considered as a soft constraint. 6: end if
7: if (course, node) assignment is invalid then
The objective of the problem is to create a timetable that 8: node := next (timeslot,room) pair
does not violate any hard constraint, and has a minimum 9: return recSol(course, node, list)
penalty associated to the violations of its soft constraints. 10: end if
11: if course.teacher is available az node.timeslot then
2.2 Literature overview 12: list ← (course,node) assignment
13: node := next (timeslot,room) pair
University course timetabling has been researched inten- 14: course := next free course
sively in the past decades. The problem itself is NP-complete, 15: return recSol(course, node, list)
which was proven by Even et al. [8], and as a result, many 16: else
different solution methods were considered for its solution. 17: node := next (timeslot,room) pair
A good overview of these is given by Bettinelli et al. [4] and 18: return recSol(course, node, list)
Babaei et al. [2]. In the following, we will present some the 19: end if
most important of the approaches. An early mathematical
model was given by [1], who consider it as a 3-dimensional The function requires 3 input data: the course to be consid-
assignment problem between courses, time-slots and rooms. ered (course), the proposed time-slot and room pair (node),
A more efficient, two-phase mathematical model is presented and a list of nodes corresponding to the partial solution that
is already built (list). Initially, list is empty, and course and
StuCoSReC Proceedings of the 2019 6th Student Computer Science Research Conference 28
Koper, Slovenia, 10 October
problem belong into two different groups. signed using a binary variable, and the possible rooms for
each time-slot are described by an undirected graph. This
Hard constraints should always be respected, and a timetable approach reduces the model size, and is able to provide so-
is not allowed to violate any of them. The most common lutions for significantly bigger instances.
hard constraints are the following:
As mathematical approaches can result in a large model even
• Course assignment: The timetable must contain all for relatively small instances, various heuristic methods were
courses, and every course has to be assigned to exactly also developed for the problem. Different variations of the
one room, time-slot and teacher. local search were presented, such as the tabu search of Lu¨
and Hao [10] or the simulated annealing of Bellio et al. [3].
• Room availability: A given room cannot have more Improved versions of Dueck’s Great Deluge algorithm [7] -
than one assigned course at the same time-slot. a genetic algorithm with a philosophy close to local search -
were also been published [5]. Hybrid algorithms with multi-
• Teacher availability: A given teacher cannot be as- ple stages are also available, like Mu¨ller [11] or Shaker et al.
signed to more than one course at the same time-slot. [12], both of which are modifications of the Great Deluge.
• Room capacity: A course cannot be scheduled to a 3. A TWO-STAGE HEURISTIC
room with less capacity than the number of students
on the course. Some papers consider this as a soft In this section, we propose a two-stage heuristic for solving
constraint. the curriculum-based university course timetabling problem.
First, an initial feasible solution is created using a greedy
• Teacher availability: Teachers can have time-slots when recursive algorithm, then a local search heuristic is utilized
they are not available. Naturally, no course can be as- to improve its quality.
signed to a teacher at a time-slot where they are not
available. Some papers consider this as a soft con- We apply the following soft constraints from Section 2: Com-
straint. pactness, Room capacity, Room stability, Minimum number
of days. The reason for this is that we use the datasets of the
Soft constraints can be violated, but they come with a penalty. Curriculum-based Course Timetabling track of the Interna-
The typical soft constraints are the following: tional Timetabling Competition 2007 (ITC) [6] as evaluation
for the method, and this competition also considers the same
• Compactness: Isolated courses in a curriculum should constraints.
be avoided. A course is isolated, if no other course
of the same curriculum is scheduled in its previous or The initial solution is created using a recursive search, which
next time-slot. only considers the hard constraints of the problem. The
pseudo-code of this can be seen in Algorithm 1.
• Room stability: Courses of the same curriculum should
be assigned to the same room, if possible. Algorithm 1 Recursive algorithm for initial solution.
• Minimal number of days: Courses of the same curricu- Funct recSol(course, node, list)
lum should be spread out over the week: they should 1: if All courses are assigned then
be scheduled to a given d amount of days. 2: return TRUE
3: end if
• As it was mentioned above, some of the hard constraint 4: if No more assignment possibilities then
(room capacity, unavailability of teachers) can also be 5: return FALSE
considered as a soft constraint. 6: end if
7: if (course, node) assignment is invalid then
The objective of the problem is to create a timetable that 8: node := next (timeslot,room) pair
does not violate any hard constraint, and has a minimum 9: return recSol(course, node, list)
penalty associated to the violations of its soft constraints. 10: end if
11: if course.teacher is available az node.timeslot then
2.2 Literature overview 12: list ← (course,node) assignment
13: node := next (timeslot,room) pair
University course timetabling has been researched inten- 14: course := next free course
sively in the past decades. The problem itself is NP-complete, 15: return recSol(course, node, list)
which was proven by Even et al. [8], and as a result, many 16: else
different solution methods were considered for its solution. 17: node := next (timeslot,room) pair
A good overview of these is given by Bettinelli et al. [4] and 18: return recSol(course, node, list)
Babaei et al. [2]. In the following, we will present some the 19: end if
most important of the approaches. An early mathematical
model was given by [1], who consider it as a 3-dimensional The function requires 3 input data: the course to be consid-
assignment problem between courses, time-slots and rooms. ered (course), the proposed time-slot and room pair (node),
A more efficient, two-phase mathematical model is presented and a list of nodes corresponding to the partial solution that
is already built (list). Initially, list is empty, and course and
StuCoSReC Proceedings of the 2019 6th Student Computer Science Research Conference 28
Koper, Slovenia, 10 October
