Article ID Journal Published Year Pages File Type
418807 Discrete Applied Mathematics 2009 15 Pages PDF
Abstract

We study the University Course Timetabling Problem (UCTP). In particular we deal with the following question: is it possible to decompose UCTP into two problems, namely, (i) a time scheduling, and (ii) a space scheduling. We have arguments that it is not possible. Therefore we study UCTP with the assumption that each room belongs to exactly one type of room. A type of room is a set of rooms, which have similar properties. We prove that in this case UCTP is polynomially reducible to time scheduling. Hence we solve UCTP with the following method: at first we solve time scheduling and subsequently we solve space scheduling with a polynomial O(n3)O(n3) algorithm. In this way we obtain a radical (exponential) speed-up of algorithms for UCTP. The method was applied at P.J. Šafárik University.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
,