著者

大坪 正和 倉重 賢治 亀山 嘉正

出版者

社団法人日本経営工学会

雑誌

日本経営工学会論文誌 (ISSN:13422618)

巻号頁・発行日

vol.57, no.3, pp.231-242, 2006-08-15

被引用文献数

2

---

本研究では,中学校を対象とした時間割編成問題に取組んだ.この問題は複雑な制約条件を有しており,依然手作業に頼る場合が多く,その作成は非常に困難である.実際,クラス数24のある中学校では,4,5人の教師が1週間程度の時間を費やして作成しており,これらの教師には大きな負担を与えている.この時間割編成問題に対して,タブーサーチを用いた三つの解法を適用した.解法Iは,すべての科目を割り当てた初期解から,制約条件をすべて満たした実行可能解を求める基本的な方法である.一方,解法IIは,制約の強さにより対象科目を三つのグループに分類し,制約が強いグループから順に割り当てを行う方法である.まず,最初のグループの科目からなる部分解を作成するために,これらの科目のみを割り当てた初期解を生成し,制約違反がなくなるまでタブーサーチを適用する.続いて,この部分解に,次のグループの科目を加えて,新たな制約違反がなくなるまで再度タブーサーチを適用する.これらのプロセスを最終グループの科目を割り当てた実行可能解が得られるまで繰り返す.解法IIIは,解法IIで分類した最後のグループに属する科目を,さらに,学年ごとに細分化し,合計5グループに分けてから順に割り当てを行う方法である.実問題を解くことによって,解法IIの有効性を明らかにした.続いて,実行可能解の取得にかかる計算時間には,近傍解の探索クラス数や制約条件の重み付けが大きく影響することも示した.さらに,実行可能解の分布状況に関しても言及した.