大学補講時間割作成問題に対する列生成法に基づく対話型逐次最適化手法

カテゴリ: 部門大会

論文No: PS4-9

グループ名: 【C】平成28年電気学会電子・情報・システム部門大会講演論文集

発行日: 2016/08/31

タイトル(英語): Interaction based optimization techniques using column generation heuristics for timetabling problems in university makeup courses

著者名: 小牧 泰斗(富山県立大学),榊原 一紀(富山県立大学),松本 卓也(神戸大学)

著者名(英語): Hiroto Komaki|Kazutoshi Sakakibara|Takuya Matsumoto

キーワード: 時間割作成|人間機械系|列生成|数理計画|timetabling|man-machine interaction|column generation|mathematical programming

要約(日本語): スケジューリング問題の一種である時間割作成問題に対する研究は古く，従来より様々な研究が行われてきた．その中でも大学補講時間割に着目すると，学生の授業履修が確定した後での時間割作成となるため，学生一人ひとりの履修状況を反映した時間割が求められる点において，実行可能な時間割を求めることが非常に困難となる，という特徴を有する．本研究では，富山県立大学の補講時間割作成問題に着目し，列生成法を用いた数理計画法に基づく最適化システムを開発する．ここでは良質な時間割を低負荷で導出することを目的とする．具体的には，対象問題を列生成アプローチに基づいて定式化し，集合分割モデルを示す. 次に，この列生成アプローチを導入した補講時間割作成法を用いて，実際の大学補講時間割データを使用した問題で時間割作成を行い，その精度や計算時間について，数理モデルをそのまま解く従来の作成法と比較・検証する．

PDFファイルサイズ: 267 Kバイト