制約充足問題解決手法を用いたスケジューリングシステムの一提案

概要

論文の詳細を見る
スケジューリング問題は物流分野における日々の原料・製品の配送スケジューリングや,生産分野における生産スケジューリングなど,日々定常的に問題の解決が要求されている問題であり,その自動化による効果は大きい.一方,人工知能の様々な問題を制約充足問題の特別な場合として定式化できることが知られている.そこで,スケジューリング問題を制約充足問題として定式化し,制約充足アルゴリズムを用いることにより解を得ることができる.しかし,一般にスケジューリング問題は規模が大きいため,探索空間が広くなり解を見つけ出すために非常に多くの時間を要する.また,短期的なスケジューリングを必要とする場合は,時間をかけて最適なスケジューリングを行なうよりも,望まれる時間内で解として受け入れられる近似解を得ることが要求されると思われる.そしてまた,スケジューリング問題では全ての制約を満たす解を得られるとは限らない.そこで,本研究では,この様なスケジューリングをするために,制約を種類分けすることにより解として受け入れられる近似解を得る方法について提案を行い,また,その有効について検証を行う.
1995-09-20