スタートページWeb教材一覧オペレーションズリサーチ

ジョブスケジュール

キーワード

ジョブスケジュール、ジョンソンの方法、ジャクソンの方法、ジョブショップ、フローショップ


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

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

ジョンソンの方法

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

●例題
 5つのジョブa、b、c、d、eは、2つの機械XとYで、X→Yの順序で加工される。各々の加工時間が下表のように与えられているとき、全作業が完了するまでの時間を最小にするには、a~eをどの順序で行えばよいか。
       X  Y
    a  4  7 単位(分)
    b  5  5
    c  7  4
    d  7  2
    e  3  6

いくつかを例示すると次の図になります。
  a→b→c→d→eの順 32分
     0    5    10    15    20    25    30 32
     ├────┼────┼────┼────┼────┼────┼─┤
     │
     │ a   b      c      d    e
   X ┝━━━╋━━━━╋━━━━━━╋━━━━━━╋━━┫
     │
     │       a     b   c     d    e
   Y │   ┣━━━━━━╋━━━━╋━━━┫  ┣━┫┣━━━━━┫
     │
  e→a→b→c→dの順 28分
     0    5    10    15    20    25  28
     ├────┼────┼────┼────┼────┼──┤
     │
     │ e  a   b      c      d
   X ┝━━╋━━━╋━━━━╋━━━━━━╋━━━━━━┫
     │
     │     e      a     b   c   d
   Y │  ┣━━━━━╋━━━━━━╋━━━━╋━━━┫┣━┫
     │

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

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

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

  1. まず、全体の作業のうち最小時間の作業は、2(d,Y)です。これはYの作業なので、dを最後にします。
         ?→?→?→?→d
  2. 表からdを削除すると、最小時間は3(e,X)であり、Xの作業なので、eを先頭にします。
         e→?→?→?→d
  3. dとe以外での最小時間は、(a,X)と(c,Y)の4です。たまたまXとYの作業なので、aが先頭、cが最後になります。(注)
         e→a→?→c→d
  4. 残ったものはbだけだから、
         e→a→b→c→d
    として、完了します。

(注)場合によっては、X(Y)に複数の最小値が存在することがあります。その場合は、どちらを選んでもよいのですが、
   Xの場合は、Yが小さいほうのジョブを先頭にする
   Yの場合は、Xが大きいほうのジョブを最後にする
のが適切です。
 このように、ジョンソンの方法は、一つの最適解を得ることはできますが、これ以外にも最適解がある場合もあります。例えば、e→a→c→b→dでも28分になります。

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

機械が3台以上のときには一般的な解法はないのですが、
   max(Yでの加工時間)≦min(Xでの加工時間)
   max(Yでの加工時間)≦min(Zでの加工時間)
のいずれかの条件が満足される場合には、
   α=X+Y、β=Z+Y
という仮想機械を想定して、2機械でのジョンソンの方法を適用することができます。

       X  Y  Z    α=X+Y  β=Z+Y
    a  6  1  8    7=6+1  9=8+1
    b  8  4  4   12=8+4  8=4+4
    c  2  2  7    4=2+2  9=2+7
    d  8  3  6   11=8+3  9=3+6

左表の場合では、
   max(Yでの加工時間)=max(1,4,2,3)=4
   min(Xでの加工時間)=min(6,8,2,8)=2
   min(Zでの加工時間)=min(8,4,7,6)=4
なので、
   max(Yでの加工時間)≦min(Xでの加工時間)は成立しないが、
   max(Yでの加工時間)≦min(Zでの加工時間)は成立する
ので、上表の右のように変形することにより、ジャクソンの方法が使えます。

  1. 全体での最小値は4(c,α)⇒ c→?→?→?
  2. cを除いた最小値は7(a,α)⇒ c→a→?→?
  3. cとaを除いた最小値は8(b,β)⇒ c→a→?→b
  4. 最適解は、c→a→d→b

●練習問題
      X  Y  Z
   a  8  2  6
   b  8  3  7
   c  6  4 11
   d  9  6 10
   e  4  5  8
(解答)

maxY(2,3,4,6,5)=6
minZ(6,7,11,10,8)=6
ジャクソンの方法が使える
      α  β
   a 10  8
   b 11 10
   c 10 15
   d 14 16
   e  9 13
全体の最小値=8(a,β)   ?→?→?→?→a
a以外の最小値=9(e,α)   e→?→?→?→a
a、e以外の最小値=10(b,β)または(c,α) e→c→?→b→a
結果として、 e→c→d→b→a

ジャクソンの方法

ジャクソンの方法は、機械が2台のジョブショップ型のジョブスケジュールの最適解の一つを得る方法です。
●例題
 ジョブa~lは、2つの機械XとYで加工される。その順序と加工時間が下表のように与えられているとき、全作業が完了するまでの時間を最小にするには、どの順序で行えばよいか。
       X  順序  Y
    a  2  ←  1 単位(分)
    b  2  →  1
    c  1
    d  4  →  3
    e  1  ←  2

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

  1. ジョブを次のグループに分ける。
       GX :Xだけのジョブ 例題では c
       GY :Yだけのジョブ      なし
       GXY:X→Yのジョブ      b,d
       GYX:Y→Xのジョブ      a,e
  2. XYについて、ジョンソンの方法により順序づける。
       d→b
  3. YXについて、ジョンソンの方法により順序づける。
    このとき、Y→Xなので、最小値がYのとき先頭、Xのとき最後にすることに注意すること!
       a→e
  4. Xでは、GXY→G→GYX の順に並べる。
    に複数のジョブがあるときは、このなかの順序は任意でよい。
       d→b→c→a→e
  5. Xでは、GYX→G→GXY の順に並べる。
    に複数のジョブがあるときは、このなかの順序は任意でよい。
       a→e→d→b

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

     0 1 2 3 4 5 6 7 8 9 10
     ├─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤
     │
     │   d     b  c  a  a
   X ┝━━━━━━━╋━━━╋━╋━━━╋━┫
     │
     │a  e     d  b
   Y ┝━╋━━━┫ ┣━━━╋━┫
     │

●練習問題
      X  順序  Y
   a  6  →  7
   b  8  ←  5
   c  7  →  4
   d        6
   e  4  ←  8
(解答)

X :なし
Y :d
XY:a,c  a→c
YX:b,e  b→e
X:a→c→b→e
Y:b→e→d→a→c