処理時間から分離された付加的な時間を有する2および3機械フロー・ショップ総所要時間スケジューリング問題
スポンサーリンク
概要
- 論文の詳細を見る
この論文では、2機械および3機械問題それぞれに対して、処理時間から分離された順序に独立な時間を有する、フロー・ショップ総所要時間スケジューリング問題を考える。2機械問題では、5つの独立な時間、すなわち、段取り時間、後始末時間、機械1での処理と機械2での処理との間の開始時間遅れと終了時間遅れ、機械間の運搬所要時間、とを有するものとする。この場合、一般には、機械1上での処理順序と機械2上での処理順序とが異なる、つまり追い抜きを許した方が総所要時間が短くなる。そのことを例題を通じて示す。次に、順列スケジュールに限定して、最適順序を得るための基準を導く。これはS。M。Johonsonの基準の一般化となり、よく知られた結果を特別な場合として含むことになる。NP完全な3機械順列問題では、段取り時間のみをもつ場合に対して、多項式時間O(n log n)で解けるための十分条件をいくつか与え、それらの間の関係を明らかにする。3機械問題を近似的に2機械問題に帰着させて最適化する、S。M。Johnsonによる、最適順列への近似順列に類似な順列を考え、それがどんな条件のもとで最適になるかという観点から、いくつかの十分条件を導いた。段取り時間をゼロとおけば、段取り時間が処理時間に含まれたことになり、これらはすべて通常の3機械問題の場合に帰着する。通常の3機械問題に対してはすでにS。M。Johnson(1954)、 M。Raghavachari(1969)、 W。Szwarc(1974)、 F。Burn and J。Rooker(1978)が独立にいくつかの十分条件を導いているが、我々が考えた条件は、それらを含み、さらにいくつかを付加して、相互の強さの関係を得た。さらに、m(≧4)機械への拡張や、時間遅れ、運搬時間、適切に制約された後始末時間等を含んだ場合への拡張も可能である。
著者
関連論文
- アンケート : あなたにとってDPとは(動的計画法)
- 処理時間から分離された付加的な時間を有する2および3機械フロー・ショップ総所要時間スケジューリング問題
- 経営科学への応用(動的計画法)
- 3機械フローショップ総所要時間問題における2つの簡単な場合 : 独立な段取り時間と後始末時間を持つ場合への拡張