
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Computational Complexities of University Interview Timetabling
Naoyuki KAMIYAMA Yuuki KIYONARI Eiji MIYANO Shuichi MIYAZAKI Katsuhisa YAMANAKA
Publication
IEICE TRANSACTIONS on Information and Systems
Vol.E92D
No.2
pp.130140 Publication Date: 2009/02/01
Online ISSN: 17451361
DOI: 10.1587/transinf.E92.D.130
Print ISSN: 09168532 Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science) Category: Keyword: timetable, scheduling, optimization, computational complexity,
Full Text: PDF(602.5KB)>>
Summary:
This paper introduces a new timetabling problem on universities, called interview timetabling. In this problem, some constant number, say three, of referees are assigned to each of 2n graduate students. Our task is to construct a presentation timetable of these 2n students using n timeslots and two rooms, so that two students evaluated by the same referee must be assigned to different timeslots. The optimization goal is to minimize the total number of movements of all referees between two rooms. This problem comes from the real world in the interview timetabling in Kyoto University. We propose two restricted models of this problem, and investigate their time complexities.

