要員スケジュールシステムにおける探索制御手法の導入

概要

論文の詳細を見る
計画問題は幅広い応用分野に関わる問題であり、なかでもスケジューリング問題はニーズが高く特に重要なテーマの一つである。近年、このスケジューリング問題をCSP(Constraint Satisfaction Problem、制約充足問題)として定式化して解こうというアプローチが盛んであるが、CSP自体はNP完全であることが知られており、実世界の応用にその枠組を適用するためには解の導出方法に工夫が必要となる。著者らはCSPによって定式化されたスケジューリング問題を解く、汎用的なスケジューリングシステムの試作を行っている。このシステムの核となる探索ドライバでは、問題の特徴に合わせて探索の制御についてのパラメータの設定やヒューリスティックスなどを記述し、これを利用して効率の良い探索を行うことを考えている。しかしながら、現在のところ「どのような問題に対してどのような制御を行うことが効果的か」といった探索制御手法の利用技術は確立していない。本報告ではCSPとして定式化されたスケジューリング問題を解く際の探索制御手法の適用可能性を要員配置問題について検討する。また例題に対して探索制御手法を適用した場合の効果の測定結果について述べる。
1992-02-24