スケジュール問題2                         戻る

 当HPの「スケジュール問題」では、ある作品を完成させるための作業工程の最適化を考
えた。

 最近ある大学の経営工学がご専門の先生から、「これからはプランニング技術が重視さ
れる時代になるだろう」というお話しを伺った。

 例えば、2つの機械M、Nをこの順に使い、3つの製品A、B、Cを作る場合、それぞれの
製品の加工に要する時間が均一なら特段の問題もなく、任意の順序で作業すればいいわ
けだが、それぞれの加工時間に差違がある場合は、作業順序の考察が必要になってくる。
これがプランニング技術である。

例 3つの製品A、B、Cの2つの機械M、Nによる加工時間が次の表のようになっているも
  のとする。各製品は機械Mの加工を経た後、機械Nの加工により完成する。

 
  製品A 製品B 製品C
機械M
機械N

 この場合、何も考えずに、製品A→製品B→製品Cの順番で作業をすると、製品完成まで、
18時間を要する。

 果たして、これが最善だろうか?答えは、否である。

 実は、最適なプランニングをするために、ジョンソン法というものが知られている。

 (→参考:「3機械フローショップのスケジューリング」(東京理科大学))

 このジョンソン法に従えば、次のようにして簡便に最適加工順序が求められる。

(1) 加工時間の最小は、機械Mによる製品Cの加工である。よって、加工順位は1番。

(2) 製品Cを除いて、加工時間の最小は、機械Nによる製品Aの加工である。よって、加
   工順位は3番。

(3) 製品A、Cを除いて、加工時間の最小は、機械Mによる製品Bの加工である。よって、
   加工順位は2番。

  以上から、製品C→製品B→製品Aの順番で作業をすると、13時間で製品が完成する。
 製品A→製品B→製品Cの順番に比べて、5時間の短縮になっている。工場の現場では
 この5時間の差は大きい。

  プランニング技術がいかに大切かが理解できるというものだ。

 ジョンソン法により本当に最適加工時間は求められているのだろうか?

 最も単純な場合に限定して確かめてみよう。製品1、製品2の機械M、機械Nによる加工
時間が下記の表のようになっているものとする。

 
  製品1 製品2
機械M 1 2
機械N 1 2

 ここで、4つの数 a1、a2、b1、b2 のうち、a1 が最小値で、a2、b2 のうち、b2 が最小値に
なっているものとする。

 今、製品1→製品2の順番で作業をするとき、x1、x2 をそれぞれ b1、b2 の前の機械N
の遊休時間とすれば、これらは、a1、a2、b1、b2 を用いて表される。

 すなわち、 x1=a1 、 x2=max(a2−b1,0) である。

 よって、機械Nの遊休時間の総和は、 max(a1+a2−b1,a1 で与えられる。

 同様にして、製品2→製品1の順番で作業をするとき、機械Nの遊休時間の総和は、

max(a1+a2−b2,a2 で与えられる。

 よって、製品1→製品2の順番で作業をするのが最適加工順序であるための必要十分条
件は、
     max(a1+a2−b1,a1)≦max(a1+a2−b2,a2

 両辺から a1 を引いて、 max(a2−b1,0)≦max(a2−b2,a2−a1

 両辺から a2 を引いて、 max(−b1,−a2)≦max(−b2,−a1

 すなわち、 −min(b1,a2)≦−min(b2,a1) より、 min(b1,a2)≧min(b2,a1

 これは、a1、b2 が表中最小であることを示す。

(コメント) 厳密な証明ではないが、何となく納得するには十分であろう。