フローショップのスケジューリング(2工程) メイクスパンの最小値

2工程(追い越しなし)のスケジューリングに関わる問題は、
技術士(経営工学部門)で頻繁に出題されます。
簡単に解けますので、勉強しておきましょう。

この問題は、
 ・2工程で、
 ・ジョブがたくさんあるとき、
 ・どの順序でジョブをこなせば、
 ・もっとも短い時間でジョブを全完了できるか

を計算する問題と考えてください。

【解き方】
(1)ジョブリストの中から、最小の作業時間を見つける
(2)その時間が1工程目であれば、
 そのジョブを順序の最初に持ってくる。
 2工程目であれば(3)へ進む
(3)最小時間が、2工程目の場合は、
 そのジョブを最後の順序に持ってくる。
(4)当該ジョブをリストから削除する
(5) (1)から(4)を繰り返す。
(6)ジョブリストのすべての順番が確定したら、
  図を描いてメイクスパンを計算する。

それでは実際に解いてみましょう(平成28年度の問題抜粋)。

【問】
2工程のフローショップを考える。各ジョブ各工程の加工時間(時間)が以下の表のように与えられたとき、メイクスパンの最小値として最も適切なものはどれか。
1.jpg

【解答】
まず、表中から最小の作業時間を見つけます。
すると、ジョブAの2工程(2時間)であることが分かります。
2.jpg
最小の作業時間が2工程である場合には、
そのジョブを一番最後に持って行きます。
つまりジョブAは一番最後(3番目)に処理されることが分かります。
3.jpg
ジョブAの順序は決まりましたので、表からジョブAを削除します。
4.jpg

次の最小時間は、ジョブCの第1工程(3時間)です。

第1工程の場合は、順序の先頭に持っていきますので、
ジョブCは一番最初(1番目)に処理されることが分かります。
5.jpg

ジョブCの順序は決まりましたので、表からジョブCを削除します。
6.jpg

残ったジョブBは必然的に2番目に処理されることになります。
7.jpg

これで、ジョブの処理順番が、

C → B → A であるこことが分かりました。

ここからは図を描いて、整理してみます。
各ジョブとも、1工程が終わらないと、2工程へは進めません。
このため、2工程は待ちが発生します。
赤い点線は、待ち時間を示しています。

8.jpg

PERT図のクリティカルパスと似たような考え方ですね。

最小の処理時間は、2工程に着目して、

3+4+1+5+1+2=16時間

となります。

つまり、16時間がメイクスパンの最小値となります。

簡単ですよね。



この記事へのコメント