کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
418807 | 681720 | 2009 | 15 صفحه PDF | دانلود رایگان |

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.
Journal: Discrete Applied Mathematics - Volume 157, Issue 7, 6 April 2009, Pages 1364–1378