ジョブスケジュール

ジョブスケジューリングとは、複数のジョブ（加工処理）、ａ、ｂ、ｃ・・・を複数の機械、Ｘ、Ｙ、Ｚ・・・で加工するとき、どのような順序で行えば、全体の処理時間を最小にできるかというような問題を取り扱う技法です。
　すべてのジョブが、Ｘ→Ｙ→Ｚの順で処理するように作業順序が一定の場合をフローショップ型といい、個々のジョブで順序が異なる場合をジョブショップ型、処理順序が指定されていない場合をオープンショップ型といいます。

一般的に、ジョブスケジュールの問題は、組み合わせの問題になり、短時間で計算する適切なアルゴリズムはないのですが、機械が２つの場合、フローショップ型ではジョンソンの方法、ジョブショップ型ではジャクソンの方法があります。

ジョンソンの方法

ジョンソンの方法は、機械が２台のフローショップ型のジョブスケジュールの最適解の一つを得る方法です。

●例題
　５つのジョブａ、ｂ、ｃ、ｄ、ｅは、２つの機械ＸとＹで、Ｘ→Ｙの順序で加工される。各々の加工時間が下表のように与えられているとき、全作業が完了するまでの時間を最小にするには、ａ～ｅをどの順序で行えばよいか。
　　　　　　　Ｘ　　Ｙ
　　　　ａ　　４　　７　単位（分）
　　　　ｂ　　５　　５
　　　　ｃ　　７　　４
　　　　ｄ　　７　　２
　　　　ｅ　　３　　６

いくつかを例示すると次の図になります。
　　ａ→ｂ→ｃ→ｄ→ｅの順　３２分
　　　　　０　　　　５　　　　10　　　　15　　　　20　　　　25　　　　30　32
　　　　　├────┼────┼────┼────┼────┼────┼─┤
　　　　　│
　　　　　│　ａ　　　ｂ　　　　　　ｃ　　　　　　ｄ　　　　ｅ
　　　Ｘ　┝━━━╋━━━━╋━━━━━━╋━━━━━━╋━━┫
　　　　　│
　　　　　│　　　　　　　ａ　　　　　ｂ　　　ｃ　　　　　ｄ　　　　ｅ
　　　Ｙ　│　　　┣━━━━━━╋━━━━╋━━━┫　　┣━┫┣━━━━━┫
　　　　　│
　　ｅ→ａ→ｂ→ｃ→ｄの順　２８分
　　　　　０　　　　５　　　　10　　　　15　　　　20　　　　25　　28
　　　　　├────┼────┼────┼────┼────┼──┤
　　　　　│
　　　　　│　ｅ　　ａ　　　ｂ　　　　　　ｃ　　　　　　ｄ
　　　Ｘ　┝━━╋━━━╋━━━━╋━━━━━━╋━━━━━━┫
　　　　　│
　　　　　│　　　　　ｅ　　　　　　ａ　　　　　ｂ　　　ｃ　　　ｄ
　　　Ｙ　│　　┣━━━━━╋━━━━━━╋━━━━╋━━━┫┣━┫
　　　　　│

●解法
ジョンソンの方法は、次のステップで、最適解を求めます。

1. 全体のなかで最小値（最も作業時間が短い作業）を探す。
2. それが、Ｘ（前工程の機械）側の作業ならは、そのジョブを最初に処理し、
   Ｙ（後工程の機械）側の作業であれば最後に処理する。
3. 処理順序の決定したジョブを除く。
4. 順序の決定していないジョブが存在すれば「１」に戻る。
   すべてのジョブの順序が決定したら完了する。

上の例題を、これに従って解いてみましょう。

1. まず、全体の作業のうち最小時間の作業は、２（ｄ，Ｙ）です。これはＹの作業なので、ｄを最後にします。
   　　　　　？→？→？→？→ｄ
2. 表からｄを削除すると、最小時間は３（ｅ，Ｘ）であり、Ｘの作業なので、ｅを先頭にします。
   　　　　　ｅ→？→？→？→ｄ
3. ｄとｅ以外での最小時間は、（ａ，Ｘ）と（ｃ，Ｙ）の４です。たまたまＸとＹの作業なので、ａが先頭、ｃが最後になります。（注）
   　　　　　ｅ→ａ→？→ｃ→ｄ
4. 残ったものはｂだけだから、
   　　　　　ｅ→ａ→ｂ→ｃ→ｄ
   として、完了します。

（注）場合によっては、Ｘ（Ｙ）に複数の最小値が存在することがあります。その場合は、どちらを選んでもよいのですが、
　　　Ｘの場合は、Ｙが小さいほうのジョブを先頭にする
　　　Ｙの場合は、Ｘが大きいほうのジョブを最後にする
のが適切です。
　このように、ジョンソンの方法は、一つの最適解を得ることはできますが、これ以外にも最適解がある場合もあります。例えば、ｅ→ａ→ｃ→ｂ→ｄでも２８分になります。

ジョンソンの方法の３機械への拡張

機械が３台以上のときには一般的な解法はないのですが、
　　　ｍａｘ（Ｙでの加工時間）≦ｍｉｎ（Ｘでの加工時間）
　　　ｍａｘ（Ｙでの加工時間）≦ｍｉｎ（Ｚでの加工時間）
のいずれかの条件が満足される場合には、
　　　α＝Ｘ＋Ｙ、β＝Ｚ＋Ｙ
という仮想機械を想定して、２機械でのジョンソンの方法を適用することができます。

　　　　　　　Ｘ　　Ｙ　　Ｚ　　　　α＝Ｘ＋Ｙ　　β＝Ｚ＋Ｙ
　　　　ａ　　６　　１　　８　　　　７＝６＋１　　９＝８＋１
　　　　ｂ　　８　　４　　４　　　１２＝８＋４　　８＝４＋４
　　　　ｃ　　２　　２　　７　　　　４＝２＋２　　９＝２＋７
　　　　ｄ　　８　　３　　６　　　１１＝８＋３　　９＝３＋６

左表の場合では、
　　　ｍａｘ（Ｙでの加工時間）＝ｍａｘ（１，４，２，３）＝４
　　　ｍｉｎ（Ｘでの加工時間）＝ｍｉｎ（６，８，２，８）＝２
　　　ｍｉｎ（Ｚでの加工時間）＝ｍｉｎ（８，４，７，６）＝４
なので、
　　　ｍａｘ（Ｙでの加工時間）≦ｍｉｎ（Ｘでの加工時間）は成立しないが、
　　　ｍａｘ（Ｙでの加工時間）≦ｍｉｎ（Ｚでの加工時間）は成立する
ので、上表の右のように変形することにより、ジャクソンの方法が使えます。

1. 全体での最小値は４（ｃ，α）⇒　ｃ→？→？→？
2. ｃを除いた最小値は７（ａ，α）⇒　ｃ→ａ→？→？
3. ｃとａを除いた最小値は８（ｂ，β）⇒　ｃ→ａ→？→ｂ
4. 最適解は、ｃ→ａ→ｄ→ｂ

●練習問題
　　　　　　Ｘ　　Ｙ　　Ｚ
　　　ａ　　８　　２　　６
　　　ｂ　　８　　３　　７
　　　ｃ　　６　　４　１１
　　　ｄ　　９　　６　１０
　　　ｅ　　４　　５　　８
（解答）

ジャクソンの方法

ジャクソンの方法は、機械が２台のジョブショップ型のジョブスケジュールの最適解の一つを得る方法です。
●例題
　ジョブａ～ｌは、２つの機械ＸとＹで加工される。その順序と加工時間が下表のように与えられているとき、全作業が完了するまでの時間を最小にするには、どの順序で行えばよいか。
　　　　　　　Ｘ　 順序 　Ｙ
　　　　ａ　　２　　←　　１　単位（分）
　　　　ｂ　　２　　→　　１
　　　　ｃ　　１
　　　　ｄ　　４　　→　　３
　　　　ｅ　　１　　←　　２

●解法
　ジャクソンの方法は、次のステップで、最適解を求めます。

1. ジョブを次のグループに分ける。
   　　　Ｇ_Ｘ：Ｘだけのジョブ　例題では　ｃ
   　　　Ｇ_Ｙ：Ｙだけのジョブ　　　　　　なし
   　　　Ｇ_ＸＹ：Ｘ→Ｙのジョブ　　　　　　ｂ，ｄ
   　　　Ｇ_ＹＸ：Ｙ→Ｘのジョブ　　　　　　ａ，ｅ
2. Ｇ_ＸＹについて、ジョンソンの方法により順序づける。
   　　　ｄ→ｂ
3. Ｇ_ＹＸについて、ジョンソンの方法により順序づける。
   このとき、Ｙ→Ｘなので、最小値がＹのとき先頭、Ｘのとき最後にすることに注意すること！
   　　　ａ→ｅ
4. Ｘでは、Ｇ_ＸＹ→Ｇ_Ｘ→Ｇ_ＹＸ の順に並べる。
   Ｇ_Ｘに複数のジョブがあるときは、このなかの順序は任意でよい。
   　　　ｄ→ｂ→ｃ→ａ→ｅ
5. Ｙでは、Ｇ_ＹＸ→Ｇ_Ｙ→Ｇ_ＸＹ の順に並べる。
   Ｇ_Ｙに複数のジョブがあるときは、このなかの順序は任意でよい。
   　　　ａ→ｅ→ｄ→ｂ

　これをガントチャートにすると、図のように、完了時間は１０分になります。

　　　　　０　１　２　３　４　５　６　７　８　９　10
　　　　　├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
　　　　　│
　　　　　│　　　ｄ　　　　　ｂ　　ｃ　　ａ　　e
　　　Ｘ　┝━━━━━━━╋━━━╋━╋━━━╋━┫
　　　　　│
　　　　　│ａ　　ｅ　　　　　 ｄ　　　ｂ
　　　Ｙ　┝━╋━━━┫　┣━━━━━╋━┫
　　　　　│

●練習問題
　　　　　　Ｘ　 順序 　Ｙ
　　　ａ　　６　　→　　７
　　　ｂ　　８　　←　　５
　　　ｃ　　７　　→　　４
　　　ｄ　　　　　　　　６
　　　ｅ　　４　　←　　８
（解答）