Preferential Optimization of University Students’ Timetables

No Thumbnail Available
Journal Title
Journal ISSN
Volume Title
School of Science | Master's thesis
Checking the digitized thesis and permission for publishing
Instructions for the author
Date
2011
Major/Subject
Tietojenkäsittelyteoria
Mcode
T-119
Degree programme
Language
en
Pages
v + 58
Series
Abstract
University timetabling problem is a variant of a scheduling problem. The scheduling problem is the problem of determining a schedule, i.e., an allocation of the resources to the activities that is both reasonable and efficient with respect to the performance requirements or the objectives. The resources, the activities, and the objectives can take many different forms depending on the particular problem. There exist a wide variety of approaches for solving the scheduling problem, such as linear programming, clustering methods, heuristic search algorithms, or multi criteria approaches. Each approach has its own strong points and disadvantages. In this thesis, we aim to solve a particular variant of university timetabling problem: course and examination timetabling problem from the students' perspective. We also consider a number of criteria for optimizing the resulting timetable. The problem can be stated as follows: given a set of courses of the student's interest and a fixed timetable representing assignments of the course events to time slots, find a subset of courses such that their events from a timetable satisfying the student's requirements. There is a wide variety of possible optimization criteria, i.e., requirements, and here we will consider four of them: the total number of events, the number of conflicts between the events, the number of events that are in favourable and unfavourable time slots defined by the student. For solving the problem, we use a constraint-based approach with preferential optimization. In particular we are using answer set programming (ASP), a declarative programming paradigm that is based on the stable model semantics of logic programs. The goal of this thesis is to find an efficient way of expressing the problem using rules and constraints as well as representing the optimization criteria and applying the approach to practical use cases. We have implemented an ASP interface based on our ASP encoding. By using ASP, we wish to benefit from the advances of answer set solvers such as CLASP. Since we use parameters for expressing the weights of optimization criteria of the problem, experiments are used to study the effect of the parameters on the quality of the resulting timetables. Based on the experimental results we are able to figure out a fine range of the values for the parameters which help to ensure the resulting timetables have desired properties. Moreover, experiments with the implementation show that the approach works really well for the expected number of courses (up to 10 courses selected by the student) and becomes unfeasible when the number of courses exceeds 50. A demo system for automated timetabling for university student called CUTE has been implemented based on the ASP encoding developed in this work. The demonstration of CUTE is also presented in this thesis.
Description
Supervisor
Janhunen, Tomi
Thesis advisor
Oikarinen, Emilia
Keywords
scheduling problem, timetable design problem, university timetabling problem, preferential optimization, answer set programming
Other note
Citation