کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
418807 681720 2009 15 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Polynomial reduction of time–space scheduling to time scheduling
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Polynomial reduction of time–space scheduling to time scheduling
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 157, Issue 7, 6 April 2009, Pages 1364–1378
نویسندگان
,