事例に基づくスケジュール最適化
スポンサーリンク
概要
- 論文の詳細を見る
スケジューリング問題は、組み合わせ最適化の代表的な問題として、主としてOR分野で広く研究されてきた。その結果、大規模なスケジューリング問題を解く際の計算量の課題に対応するために、数理解析的手法だけではなく、様存なデイスパッチングルールを用いた近似的手法が開発されてきた。しかし、デイスパツチングルールを用いるスケジューリングは、効率的に計算できる半面、最適化における有効性が限定的である欠点を持つ。その欠点を補うために、近年スケジューリング問題への各種の近隣探索手法の適用が提案されている。[Baker92] 近隣探索手法とは、適当な方法で得られた初期解を種として系統的にその近傍の解を生成し、その解の評価に応じて解を置き換えていく手法である。近隣探索手法はあらゆる組み合わせ最適化問題に適用可能であるが、その効果的な適用に当たっては、・明確な目的関数・局所最適化を避けながら、効率良く探索するための探索制御戦略の2種類の問題固有の、情報が必要である。しかし、現実のスケジューリング問題において、これらを明示することはスケジューリングの専門家にとっても容易なことではないことは[Mckay88] により議論されている。本稿では、近隣探索手法の適用に必要な上記の2種類の知識を、ユーザとの協調的問題解決を通じて事例として自動的に獲得し、それらを新たな問題の解決に再利用するスケジューリングシステムCABINSの枠組みを提案し雨実験を通じてスケジュール最適化におけるその有効性を確認する。
- 一般社団法人情報処理学会の論文
- 1993-03-01
著者
関連論文
- 事例に基づくスケジューリング知識の獲得
- 知識ベーススケジューリングシステム構築における知識獲得手法
- スケジュール最適化問題における事例に基づく探索制御知識の獲得
- 事例に基づくリアクティブなスケジュール修正方式
- 事例に基づくスケジュール最適化
- ダイナミックスケジューリングシェルDYNAMICS (Dynamic Scheduler)
- 組込み型プロダクションシステムの開発