確率制約を伴う機械スケジューリング問題の解法

概要

論文の詳細を見る
つぎの機械スケジューリング問題を考える。i)時刻0から開始できるn種の仕事の集合J={1、2、…n}を1機械で処理する。ii)各仕事iの処理時間P_iは平均値m_i、分散v^2_iの正規分布に従う確率変数である。ただし、任意の仕事の対p、qに対して仰mp<m_q→v^2_p≦v^2_qが成立つと仮定されている。iii)各仕事iの納期d_iは既知とする。iV)仕事iの修了時刻がd_i以下である確率が与えられた正数α(<1)以上ならば、仕事iは納期を満すとする。V)必ず納期を満さねばならない仕事の部分集合Qが与えられている。Vi)各仕事iに重みw_iが与えられている。ただし、任意の仕事の対p、qに対してmp<<m_q or v^2_p<v^2_q→wpge:w_qが成立つと仮定されている。以上の仮定のもとで納期を満す仕事の重み和が最大となる仕事の処理順序を見い出したい。この問題に対して本論文はO(n^2)の計算手間で済む効率の良い厳密解法を提案し、その妥当性を証明する。本問題における平均値と分散および重みに関する2つの仮定は問題の適用範囲を極めて限定するように思われる。しかしながら、本問題は効率の良い厳密解法を持つ事が既に知られているいくつかの問題の一般化であると同時に、上記の2つの仮定のいづれかが緩和されると、NP完全になる事も知られている。この事は問題に対する効率の良い解法が存在しえない事を強く示唆する。さらに、本論文はこの問題に適用しうる1つの実際上の応用例を示す。

確率制約を伴う機械スケジューリング問題の解法

スポンサーリンク

概要

著者

関連論文

スポンサーリンク