モード付き並列機械における オンラインスケジューリング 　　　　　　　　　　　　管理工学研究グループ 学生番号　Ａ0571139 　　氏名　　杉本　敦紀

現実的かつ効率の良いスケジューリングモデルの構築が必要不可欠 背景 顧客満足度の向上 利益の減少 今日の市場...世界規模の不況 株価暴落 これからの市場...コスト削減，納期厳守　など．．． 　リストラ 現実的かつ効率の良いスケジューリングモデルの構築が必要不可欠

効率よく現場に適用できるスケジューリングモデル 目的・概要 効率よく現場に適用できるスケジューリングモデル モード付きスケジューリングモデル 　　　　　　　　　　　　　 ＋ オンラインスケジューリングの適用

モード付きスケジューリング モードとは・・・ その場の状況に応じて適切なジョブの処理の仕方 を選択する選択肢 　その場の状況に応じて適切なジョブの処理の仕方 を選択する選択肢 　各ジョブが複数の機械処理ルートを所有 どのようなときも高い生産性を維持 例えば・・・ 4

モード付き並列機械スケジューリング 機械1 機械2 機械3 機械4 機械5 5

モード付き並列機械スケジューリング ジョブ1 ジョブ2 (ジョブ2が1→2→3しか選べない場合) 機械1 機械2 機械3 17 (ジョブ2が1→2→3しか選べない場合) (ジョブ2が1→2→3と2→1→3のどちらかを選べる場合) 機械1 機械2 機械3 14 ジョブ1 ジョブ2 6

効率よく現場に適用できるスケジューリングモデル 目的・概要 効率よく現場に適用できるスケジューリングモデル モード付きスケジューリングモデル 　　　　　　　　　　　　　 ＋ オンラインスケジューリングの適用 7

オンラインスケジューリング問題 オンラインスケジーリングとは・・・ 製造現場で，無差別に予期しない出来事が発生 　製造現場で，無差別に予期しない出来事が発生 　到着するジョブのデータが分からないスケジューリ ング ・・・オンラインスケジューリング 　例えば・・・ ・現存のスケジューリングを改正 ・リスケジューリング 8

従来研究との比較 文献 EDR NAE ML LZS 本研究 発表年度 2007 1990 2000 2005 2009 問題の種類 単一機械 JSP モード付き並列機械 機械選択の 有無 ○ 機械順序の 制約 × リスケジューリング手法 イベント 稼働 定期的 最適化の 手法 FIFO MIP GA TS ・Vieira，Herrmann,Lin，International Journal of Production Research，2000． ・Nasr and Elsayed，International Journal of Production Research，1990． ・ Li，Zh，Song ，Advances in Natural Computation，2005．

タブーサーチの特徴 確定的探索手法 タブーリストを持っており， 探索解の特徴を長期間記憶 他のメタヒューリスティクスに比べて， 近似最適解の探索が早い

本研究のタブーサーチの基本事項 近傍範囲・・・ 実行可能な選択肢の半分 評価値・・・ 納期遅れ最小 タブーリスト ・・・ に記載する値 タブーリスト　・・・ に記載する値 暫定解，移動した後の最良解， 評価値 終了条件・・・ 規定反復回数(5 or 10)

工程数 n 1 2 ・・・・ ｎ ジョブ数 L 機械種類 K 機械台数 M ・ ・ 本研究のスケジューリングモデル 　　　　　　　　　　　　　　　　　　　　　　　　　　　 　　工程数　 n 　　　　　　　　　　　　 1　　　　　 2　・・・・　ｎ 　 ジョブ数　L 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 機械種類　K 機械台数　M 　　・ 　　　　　　　　　　　　　　　　　　　・ 機械 Ａ Ｂ 　　　・

従来研究との比較 文献 EDR NAE ML LZS 本研究 発表年度 2007 1990 2000 2005 2009 問題の種類 単一機械 JSP モード付き並列機械 機械選択の 有無 ○ 機械順序の 制約 × リスケジューリング手法 イベント 稼働 定期的 最適化の 手法 FIFO MIP GA TS ・Vieira，Herrmann,Lin，International Journal of Production Research，2000． ・Nasr and Elsayed，International Journal of Production Research，1990． ・ Li，Zh，Song ，Advances in Natural Computation，2005．

定期的稼動とイベント稼動 ＊定期的稼動リスケジューリング．．． 固定周期で，定期的にリスケジューリング 著者 文献情報 モデル 方法 タイミング ・Vieira ・Herrman ・Lin International Jounal of Production Research　 １機械 スケジューリング 定期的 イベント 移動 Jobの到着 ＊定期的稼動リスケジューリング．．． 固定周期で，定期的にリスケジューリング ＊イベント稼動リスケジューリング．．． 周期を固定せず，累積遅延がある値に到達したら， リスケジューリング 14

数値実験 ・定期的稼動とイベント稼動の比較実験 ・リスケジューリングの有効性を示す実験 15

比較実験の設定値 問題の具体例・・・3工程，4ジョブ，6機械のモード付き並列機械スケジューリング問題 16

従来研究との比較 文献 EDR NAE ML LZS 本研究 発表年度 2007 1990 2000 2005 2009 問題の種類 単一機械 JSP モード付き並列機械 機械選択の 有無 ○ 機械順序の 制約 × リスケジューリング手法 イベント 稼働 定期的 最適化の 手法 FIFO MIP GA TS ・Vieira，Herrmann,Lin，International Journal of Production Research，2000． ・Nasr and Elsayed，International Journal of Production Research，1990． ・ Li，Zh，Song ，Advances in Natural Computation，2005．

比較実験の設定値 問題の具体例・・・ 3工程，4ジョブ，6機械のモード付き並列機械スケジューリング問題 目的関数は納期遅れ最小 ジョブ数を20，40，100とする ジョブ1 ジョブ2 ジョブ3 ジョブ4 到着間隔 0.075 0.068 0.091 0.093 　納期 25 30 35 18

ジョブ数に伴う 各リスケジューリングの目的関数値 ジョブ数 目的関数値 定期的 イベント稼動 20 67.8 78.2 40 1349.71 1061.79 100 7293.84 8009.11 19

結果と考察 ジョブのデータに応じて，定期的稼動とイベント稼動の有効性が異なっていた 　ジョブのデータに応じて，定期的稼動とイベント稼動の有効性が異なっていた 　定期的稼動よりイベント稼動の振動が激しい 　安定した値を取り続ける定期的リスケジューリングのほうがあらゆる状況で遅れを確実に減少させ，高い生産性を生み出す 20

数値実験 ・定期的稼動とイベント稼動の比較実験 ・リスケジューリングの有効性を示す実験 21

リスケジューリングの有効性を示す実験の設定値 工程数 3 機械の種類 6 機械台数 各工程3台 ジョブの種類 4 ジョブ数 20，40，80 到着率 0.081，0.0912，0.0955，0.0716 各機械の処理能力 3.2，4.1，2.8，3.5，4.2，3.7 各ジョブのサイズ 10，7，8，16 納期 14，16，32，20 リスケジューリング周期 1～100 22

実験で使用するスケジューリングモデル Ａ Ｂ Ｃ Ｄ ？ 4 ？ 1 ？ 工程数 3 1 2 3 機械台数 各3台 ・ ・ 機械1 機械2 　　　　　　　　　　　　　　　　　　　　　　　　　　　 工程数　　 3 　　　　　　　　　　　　 1　　　　　 2　 　 3 機械台数 各3台 　　・ 　　　　　　　　　　　　　　　　　　　・ ？ 4 Ａ ？ 1 機械1 機械2 機械1 ？ Ｂ 機械2 機械4 機械3 機械3 機械5 機械6 Ｃ Ｄ 23

各ジョブの機械選択モードの値と 処理順序制約 ジョブ1 モード1 2 4 1 モード2 3 モード3 5 6 機械2，3，5のどれかで処理 機械同士での処理順序制約 機械1，4，6のどれかで処理 24

実験を行う上で，最適な固定周期を決定 評価関数値 滞留時間 段取り頻度 リスケジューリング頻度 25

最小 Cost=22.84[$/time unit] , h=15 45 40 35 30 25 20 15 10 5 1 　11 　21 　31 　 41 　 51 61 71 　　81 91 26

ジョブに伴う目的関数値 27

結果と考察 36 全体でおよそ ％，遅れが改善 過去の文献で使用したモード付き並列機械スケジューリングの他の具体例を用いて，数値実験 　全体でおよそ　　％，遅れが改善 　過去の文献で使用したモード付き並列機械スケジューリングの他の具体例を用いて，数値実験 　全てのデータにおいて，遅れが改善され，リスケジューリングの優位性を示すことができた 28

結論と今後の課題 　モード付きオンラインスケジューリング問題において，本研究で行った定期的リスケジューリング手法により生産工程の遅れに改善が見られ，生産性をより高くした結果を得ることができた ・実際のデータを使用して，様々な状況化での理論と現場の融合を試みる ・資源に制限をつけ，在庫コストとの関連を考慮に入れる 29

ご静聴ありがとうございました

結論と今後の課題 　モード付きオンラインスケジューリング問題において，本研究で行った定期的リスケジューリング手法により生産工程の遅れに改善が見られ，生産性をより高くした結果を得ることができた ・実際のデータを使用して，様々な状況化での理論と現場の融合を試みる ・資源に制限をつけ，在庫コストとの関連を考慮に入れる 31