number of downloads : ?
ID 5988
Title Transcription
キョクショ タンサク ト サイカネツ ヲ トモナウ ヤキナマシホウ ニヨル ダイガク ジカンワリ モンダイ ニツイテ
Title Alternative (English)
Local Search and Simulated Annealing with Reheating Schedules for the University Timetabling Problems
File
language
jpn
Attribute
Natural Science
Author
Fukushima, Makoto
Description
大学の時間割問題の解法として,焼きなまし法(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.
Subject
大学時間割編成
焼きなまし法
局所探索法
再加熱
University Timetabling
Simulated Annealing
Local Search
Reheating
Journal Title
島根大学教育学部紀要
Volume
39
Start Page
141
End Page
150
ISSN
18808581
Published Date
2006-02
NCID
AA12171265
DOI(SelfDOI)
Publisher
島根大学教育学部
NII Type
Departmental Bulletin Paper
Format
PDF
Text Version
出版社版
OAI-PMH Set
Faculty of Education
他の一覧