中学校時間割編成問題における制約条件の重み付けの自動調整(事例研究)

概要

論文の詳細を見る
本研究では,中学校を対象とした時間割編成問題に取り組んだ.この問題は複雑な制約条件を有しており,依然手作業に頼る場合が多く,その作成は非常に困難である.そのため,時間割作成者には大きな負担となっているのが現状である.この時間割編成問題に対して,タブーサーチを用いた3つの解法を提示した前報において,制約条件に設定する重み付けが探索効率に多大な影響を与えることを明らかにした.しかし,制約条件の重み付けには,複数個の値の調整が必要であり,時間割作成者にとって,その設定は容易ではないという課題が残った.そこで,まずタブーサーチによる探索途中で目的関数の値の更新が停滞したと判断するたびに,自動的に重み付けの再調整を行う方法をいくつか提示する.次に,これらの自動調整方法を用いて実際の時間割編成問題を解くことにより,実行可能解が効率的に取得できることを示す.このことは,時間割作成者が重み付けを意識しなくてもよいことを意味する.さらに,前報で提示した解法に適用した場合についても,探索効率が向上することを確認する.
2010-12-15