| 講演名 | 2006-06-23 試問予定表作成問題の計算複雑さ 清成 悠貴, 宮野 英次, 宮崎 修一, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 本稿では,試問予定表作成問題と呼ばれる大学における時間割表作成問題を考える.この問題では,m人の審査員の集合,2n人の学生の集合,各学生について審査する複数の審査員の担当割当(例えば各学生を3人ずつの審査員が担当)が与えられる.審査はn人ずつ2つの部屋で同時に行われるため,学生と担当審査員の組は,n個の時刻と2つの部屋から成るn×2行列に割り当てられる必要がある.ここで,同じ審査員が担当する異なる2人の学生は異なる時刻に割り当てられなければならない.さらに,すべての審査員が2つの部屋を移動する回数の合計をできるだけ少なくしたい.本問題は,実際に京都大学の試問予定表作成時に起きた問題を形式化したものである.この問題について2つの制約付きモデルを提案し,それらの計算複雑さについて調査する. |
| 抄録(英) | 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. It requires to assign these students to an n×2 array, consisting of n timeslots and two rooms, so that two students sharing the same referee must be assigned to different timeslots. Furthermore, we want to minimize the total number of movements of all referees between two rooms. This is a problem actually having arisen in the interview timetabling in Kyoto University. We propose two restricted models of this problem, and investigate their time complexity. |
| キーワード(和) | 試問予定表作成問題 / 最適化問題 / 計算複雑さ |
| キーワード(英) | Interview timetabling / optimization problem / computational complexity |
| 資料番号 | COMP2006-18 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2006/6/16(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 試問予定表作成問題の計算複雑さ |
| サブタイトル（和） | |
| タイトル（英） | On the Computational Complexity of Interview Timetabling Problems |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 試問予定表作成問題 / Interview timetabling |
| キーワード(2)（和/英） | 最適化問題 / optimization problem |
| キーワード(3)（和/英） | 計算複雑さ / computational complexity |
| 第 1 著者 氏名（和/英） | 清成 悠貴 / Yuuki KIYONARI |
| 第 1 著者 所属（和/英） | 九州工業大学情報工学研究科 Department of Systems Innovation and Informatics, Kyushu Institute of Technology |
| 第 2 著者 氏名（和/英） | 宮野 英次 / Eiji MIYANO |
| 第 2 著者 所属（和/英） | 九州工業大学情報工学部 Department of Systems Innovation and Informatics, Kyushu Institute of Technology |
| 第 3 著者 氏名（和/英） | 宮崎 修一 / Shuuichi MIYAZAKI |
| 第 3 著者 所属（和/英） | 京都大学学術情報メディアセンター Academic Center for Computing and Media Studies, Kyoto University |
| 発表年月日 | 2006-06-23 |
| 資料番号 | COMP2006-18 |
| 巻番号（vol） | vol.106 |
| 号番号（no） | 128 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |