最大納期遅れを最小にする1機械処理順序問題に対する6種の近似解法の評価 : 準備時間のある場合

概要

論文の詳細を見る
つぎの1機械処理順序問題を考える。i)J={1、2、……、n}を1機械で処理すべきn種の仕事とする。各j∈Jには処理開始前に必要な準備の時間(整数)、処理時間(正整数)また納期(整数)が明示されている。ii)仕事の分割処理は許されない。iii)各仕事の納期遅れ(=終了時間-納期)の最大を最小にする仕事の処理順序を見出すことが望まれる。この問題は、準備時間が無いと簡単に解けるにもかかわらず、強NP完全である事が知られている。強NP完全はこの問題がnの多項式程度の計算量で解けない事を強く示唆する。よって簡単に実行でき、かつ精度の保証される近似解法を見出す事は実用上重要である。r(j)、p(j)、d(j〕、j=1、2……、nをそれぞれ準備時間、処理時間および納期とする問題に対して準備時間を-d(j)、処理時間をp(j)、納期を-r(j)とする問題を逆問題という。また、処理順序π=(π_1、π_2。……。π_n)に対してπ^^^=(π_n、π_<n-1>、……、π_1)をπの逆順序という。提案された6種の近似解法の概要を以下に示す。近似解法J:納期の小さい順に処理。近似解法J:準備時間の小さい順に処理。近似解法mJ:処理順序JとJの良い方を選ぶ。近似解法S1準備のできた仕事のうち最小納期の仕事をつぎに処理する。近似解法S:逆問題に解法Sを適用して得られた順序の逆順序を処理順序とする。近似解法mS:処理順序SとSの良い方を選ぶ。近似解法の精度を示す評価関数として相対偏差(L_π-L_ω)/(L_ω-R_<min>+D_<max>)を用いる。ここで、L_π、L_ωはそれぞれ近似解πと最適解ωの最大納期遅れを示す。また、R_<min>=min_<j∈J>r(j)、D_<max>=max_<i∈J>d(j)である。この相対偏差についてつぎの定理が得られる。定理:各近似解法に対する相対偏差の到達可能な上限は下表で与えられる。ただし、下表においてP=Σ_<i∈J>P(j)である。[table]各近似解法の平均的な挙動を調べるために多数の例題について数値実験を行なった結果、各近似解法の平均相対偏差は上記の上限よりかなり低い値をとり、特に近似解法mSの平均相対偏差は2%以下であった。
社団法人日本オペレーションズ・リサーチ学会の論文

最大納期遅れを最小にする1機械処理順序問題に対する6種の近似解法の評価 : 準備時間のある場合

スポンサーリンク

概要

著者

関連論文

スポンサーリンク