Job-shop Scheduling
例題3-1 文教工業の生産効率化
本日，文教工業には，はじめに機械Ｍ1，次に機械Ｍ2で仕上げる製品が3つある.
工場長からの質問
一番早くすべての仕上げ作業を完了するには，3つの製品をどんな順番で加工すればよいのか?
⇒総経過時間が最小となるような加工順番（最適加工順序）を求める ＝ジョブ・ショップ・スケジューリング （工程問題・加工順序問題）
例：Ａ→Ｂ→Ｃ順で加工してみる
- ガントチャートより，Ａ→Ｂ→Ｃの順で仕上げを行った場合の総経過時間は23時間
ガントチャート（Gantt chart） 各機械の使用状態の時間的経過をグラフにしたもの
演習3-1
- 例題3-1で考えられるすべての加工順に関するガントチャートを作成し,その加工順における総経過時間を算出せよ.
加工順序問題の素朴な解き方
- すべての加工順のガントチャートを作成し，総経過時間を出し，最適加工順序をみつける．
- ガントチャートの必要枚数 製品3個の時→6枚（=3!） 製品4個の時→24枚（=4!） 製品10個の時→3,628,800枚(=10!) 製品20個の時→約2,400,000,000,000,000,000枚 =約240京枚
順序の総数
ｎ個のものの並べ方はｎ!通りある. 1秒間に100万枚のガントチャートを作成し総経過時間を求められると仮定する ★製品20個の場合に計算に必要な時間 約675806113時間＝約28158588日 ＝約77146年
最適解を求める困難性
- たとえ高速のコンピューターを駆使しても，すべての順序に関して総経過時間を求めるのは，扱う製品数が少し多くなれば,事実上不可能!! ⇒ＯＲで扱う問題の多くには同様の困難さが姿を見せる. ⇒素朴な解き方ではない，工夫した効率のよい解法の開発が重要な仕事になる.
工夫したいくつかの解法
- 工程の機械が2台の場合：ジョンソン法 （最適性保証，効率の良い解法）
- 工程の機械が3台である条件を満たす場合 ：ジョンソン法
- それ以外の時:
- 分枝限定法(branch and bound)：効率はあまり良くない．最悪の場合，素朴な方法とほぼ同じ時間が必要．最適加工順序はみつける
- 近似解法：高速だが最適性の保証はない
機械が2台の時の解法 ジョンソン法
ステップ1：表中で加工時間最短の機械と製品のペアをみつける．（同じ加工時間が複数ある時は，Ｍ1・製品番号の順で優先する）
ステップ2：それがＭ1なら最初に加工する.Ｍ2なら最後に加工する．
例題3-1（続き） ジョンソン法の適用
演習3-2
まず旋盤で削って穴をあけ，次に研削盤で磨いて仕上げる製品が8個ある.各製品が必要とする旋盤および研削盤の時間は右の通りである.
8個の製品の生産を最も早く完了できる加工順序を求めて,そのガントチャートを作成せよ.
演習3-3
- 演習3-2を素朴な方法で解いた場合，ガントチャートは何枚必要だろうか?
- 演習3-2をジョンソン法で解いた場合，答えが見つかるまでに行った比較や記憶の操作回数はおおよそどのくらい必要だろうか?
- ジョンソン法において，製品数がｍ個だったら，答えが見つかるまでに行った比較や記憶の操作回数はおおよそどのくらい必要だろうか?
最適性の保証 ジョンソン法は本当に最適加工順を求めているのだろうか?
- A→B順で加工時のＭ2の遊び時間 max{a1+b1ｰa2, a1}
- B→A順で加工時のＭ2の遊び時間 max{b1+a1ｰb2, b1}
A→B順が良い⇔ max{a1+b1ｰa2, a1}≦ max{b1+a1ｰb2, b1}
⇔ min{a2,b1} ≧ min{b2,a1}
機械が3台の場合
- ジョンソン法が適用できる条件： max{M2の加工時間}≦min{M1及びM3での加工時間}
- 適用方法 2台の合成機械の問題に変形しジョンソン法を適用
演習3-4
まず旋盤で削り，次にボール盤で穴をあけ，最後に研削盤で仕上げる製品が6つある．各製品が各機械で要する加工期間は右図の通りである．
これら6製品の生産を最も早く完了させる生産順序計画を立案し，ガントチャートで示せ．
3機械以上の場合
- 厳密に最適加工順序を求めたい時 分枝限定法(Branch and Bound)
- 加工順のパターンを枝別れしながら，結果が不利になるまで網羅的に探索していく方法．
- 早い時間でより良い加工順序を知りたい （最適かどうかはわからなくても良い） 近似解法
- 経験的に良い解を出すと知られている方法を用いる．（ヒューリスティックス）
近似解法のひとつの例
- 字引式順序法
- 最初の機械の加工時間が短い製品を優先し，時間が同じ場合は次の機械の加工時間の短いほうを優先する方法．
A→F→E→B→C→Dがひとつの良い順序として提案できる． （確かめてみよう!）
演習3-5：ガントチャートを描き，近似解法での解を吟味しよう． もっと良い解はありそうか?
まとめ
- ジョブ・ショップ・スケジューリングに対して，素朴な方法（すべての実行可能解を調べる）では現実的に解決することはできない．
- 3機械以上の時は分枝限定法か，近似解法を用いてより良い生産順序を提案する．