スケジュール問題２　　　　　　　　　　　　　　　　　　　　　　　　　

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

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

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

例　３つの製品Ａ、Ｂ、Ｃの２つの機械Ｍ、Ｎによる加工時間が次の表のようになっているも
　　のとする。各製品は機械Ｍの加工を経た後、機械Ｎの加工により完成する。

　この場合、何も考えずに、製品Ａ→製品Ｂ→製品Ｃの順番で作業をすると、製品完成まで、
１８時間を要する。

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

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

　（→参考：「３機械フローショップのスケジューリング」（東京理科大学））

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

（１）　加工時間の最小は、機械Ｍによる製品Ｃの加工である。よって、加工順位は１番。

（２）　製品Ｃを除いて、加工時間の最小は、機械Ｎによる製品Ａの加工である。よって、加
　　　工順位は３番。

（３）　製品Ａ、Ｃを除いて、加工時間の最小は、機械Ｍによる製品Ｂの加工である。よって、
　　　加工順位は２番。

　　以上から、製品Ｃ→製品Ｂ→製品Ａの順番で作業をすると、１３時間で製品が完成する。
　製品Ａ→製品Ｂ→製品Ｃの順番に比べて、５時間の短縮になっている。工場の現場では
　この５時間の差は大きい。

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

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

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

　ここで、４つの数 ａ₁、ａ₂、ｂ₁、ｂ₂ のうち、ａ₁ が最小値で、ａ₂、ｂ₂ のうち、ｂ₂ が最小値に
なっているものとする。

　今、製品１→製品２の順番で作業をするとき、ｘ₁、ｘ₂ をそれぞれ　ｂ₁、ｂ₂ の前の機械Ｎ
の遊休時間とすれば、これらは、ａ₁、ａ₂、ｂ₁、ｂ₂ を用いて表される。

　すなわち、　ｘ₁＝ａ₁　、　ｘ₂＝ｍａｘ（ａ₂−ｂ₁，０）　である。

　よって、機械Ｎの遊休時間の総和は、　ｍａｘ（ａ₁＋ａ₂−ｂ₁，ａ₁）　で与えられる。

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

ｍａｘ（ａ₁＋ａ₂−ｂ₂，ａ₂）　で与えられる。

　よって、製品１→製品２の順番で作業をするのが最適加工順序であるための必要十分条
件は、
　　　　　ｍａｘ（ａ₁＋ａ₂−ｂ₁，ａ₁）≦ｍａｘ（ａ₁＋ａ₂−ｂ₂，ａ₂）

　両辺から　ａ₁ を引いて、　ｍａｘ（ａ₂−ｂ₁，０）≦ｍａｘ（ａ₂−ｂ₂，ａ₂−ａ₁）

　両辺から　ａ₂ を引いて、　ｍａｘ（−ｂ₁，−ａ₂）≦ｍａｘ（−ｂ₂，−ａ₁）

　すなわち、　−ｍｉｎ（ｂ₁，ａ₂）≦−ｍｉｎ（ｂ₂，ａ₁）　より、　ｍｉｎ（ｂ₁，ａ₂）≧ｍｉｎ（ｂ₂，ａ₁）

　これは、ａ₁、ｂ₂　が表中最小であることを示す。

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