ダウンロード数 : ?
タイトルヨミ
キョクショ タンサク ト サイカネツ ヲ トモナウ ヤキナマシホウ ニヨル ダイガク ジカンワリ モンダイ ニツイテ
タイトル別表記
Local Search and Simulated Annealing with Reheating Schedules for the University Timetabling Problems
ファイル
言語
日本語
著者
福島 誠
内容記述(抄録等)
大学の時間割問題の解法として,焼きなまし法(Simulated Annealing)に局所探索法(Local Search)を導入した効果について検討し,さらに局所解らの脱出のための焼きなまし法の温度の再加熱(Reheating)効果についても報告している.時間割問題は,ITC(International Timetabling Competition)で公開されている例題(Instance)の一部を採用した.結果として,焼きなまし法に局所探索法を組み入れることで,効率よく実行可能な時間割の解が得られることがわかったが,再加熱の効果については特に顕著な効果は認められなかった.また,最適な時間割を得るための結果を,2002 年度のITC参加者の結果と比較すると,全問題数の半数についての比較ではあるが,最良値の場合では上位6位程度の結果になることがわかった.

A method for solving the university timetabling problems by simulated annealing(SA)with local search algorithms and reheating schedules for escaping local minima is presented. Half of the university timetabling instances presented by ITC(International Timetabling Competition)are adopted for evaluating our algorithm. From the experimental results, it is found that SA with local search is effective to obtain a feasible timetable that satisfies the hard constraints of the timetabling, but the reheating schedules are not so effective. Although only half of 20 instances have been used in our experiment, we have compared our results with those of the participants of ITC on the reduction of the penalties of the soft constraints and found that our best result has placed in 6th among the results of ITC2002 participants.
主題
大学時間割編成
焼きなまし法
局所探索法
再加熱
University Timetabling
Simulated Annealing
Local Search
Reheating
掲載誌名
島根大学教育学部紀要
39
開始ページ
141
終了ページ
150
ISSN
18808581
発行日
2006-02
NCID
AA12171265
出版者
島根大学教育学部
資料タイプ
紀要論文
ファイル形式
PDF
著者版/出版社版
出版社版
部局
教育学部
このエントリーをはてなブックマークに追加