制約分類に基づく多次元資源割り付けアルゴリズム自動生成方式

概要

論文の詳細を見る
スケジューリング問題を含む人工知能分野の多くの問題は,制約充足問題(Constrant Satisfaction Problems)として定式化される.しかし,制約充足問題はNP完全であり,多項式時間で解決する万能の解法は存在しない.そこで,制約充足問題の限られた範囲の問題に対して有効な解決戦略の研究が進められている.特に,制約充足問題の変数をノード,変数間の制約をアークに持つグラフ(制約グラフと呼ぶ)の形状に基づいた解法が研究されており,グラフの形状が木に近い問題に対して顕著な成果が現れている.しかし,応用問題を制約充足問題として表現した場合,その制約グラフの形状が木になるとは限らない.例えば,スケジューリング問題は,与えられた資源をタスクに排他的に割り付ける問題であり,その多くは制約充足問題として定式化可能である.しかし,これらは同一の資源を異なるタスクに割り付けてはならない排他制約を持つため,制約グラフが完全グラフを成し,グラフの形状という観点からは最も難しい種類の制約充足問題に属す.このため,制約グラフの形状に基づく解法は有効ではない.筆者らは,スケジューリング問題という応用領域の立場から制約充足問題の部分集合を定め,この問題に対して有効な解法を考案した.対象とする問題は,多次元の配列で表現可能な資源をタスクに割り付けるスケジューリング問題(多次元資源割り付け問題と呼ぶ)であり,多くの応用がある.また,制約充足問題には万能な解法が存在しないことから,問題が異なれば適当な解法も異なるとの見方から,与えられた問題に対してその問題の性質に応じた適当な解法を選択する方法を検討した.その結果,問題が持つ個々の制約を分類することにより問題と解法との対応付けに成功し,宣言的記述言語により記述されたスケジューリング問題から,その解法を自動的に作成する手法を考案,試作を行なった.本稿では,多次元資源割り付け問題の解法,および,制約の分析に基づいた割り付けアルゴリズム自動生成方式について報告する.
一般社団法人情報処理学会の論文
1991-02-25

制約分類に基づく多次元資源割り付けアルゴリズム自動生成方式

スポンサーリンク

概要

著者

関連論文

スポンサーリンク