スケジューリング最適化エンジン ― RCPSPによるアプローチ

Presentation on theme: "スケジューリング最適化エンジン ― RCPSPによるアプローチ"— Presentation transcript:

1 スケジューリング最適化エンジン ― RCPSPによるアプローチ
野々部宏司 京都大学大学院情報学研究科 （茨木俊秀教授との共同研究）

2 はじめに 〈スケジューリング・エンジンの重要性〉
APS (Advanced Planning and Scheduling) ‐　生産計画（在庫計画）＋スケジューリング ‐　資材調達計画＋資源負荷計画 ‐　納期回答 ‐　… 〈スケジューリング・エンジンの重要性〉 問題を数学的に捉え（モデルの作成）， 最適化の手法を適用

3 本研究の目指すところ 実用性の高いスケジューリング・エンジンの開発 適用可能性（汎用性） ← 拡張RCPSPモデル
高性能　←　メタヒューリスティクス 　RCPSP　 　ソルバ　 汎用モデル RCPSP RCPSPに 定式化 スケジュール スケジューリング最適化エンジン

4 本研究の位置付け（１） 理論 ―――― 応用 ―――― 実用 Theory Application Practice
モデルの作成 ‐　避けては通れない（避けてはならない） ‐　現状把握，問題整理・認識，目標設定 ‐　抽象化と具体化（限定化）のバランス 最適化　≒　制約充足・実現可能を目指す

5 本研究の位置付け（２） 生産計画 ――――― スケジューリング planning scheduling 部品表・工程表は既知
「どの製品を，どれだけ，いつまでに生産するか」 　　を入力として （← 需要予測，受注，在庫，…）， 「各製品を，いつ生産するか」を決定 （→　資材調達，生産スケジュール） 有限負荷，現場レベルでの制約を考慮

6 本研究の位置付け（３） 秒・分 ― 時 ―― 日 ―― 週 ――― 月 ――― 年 問題規模： 数百個 ～ 数千個の作業（工程）
最小単位時間 計画期間 問題規模：　数百個 ～ 数千個の作業（工程） 計算時間：　数十秒 ～ 十数分 （～ 数十分） シミュレーションを行うだけではない　

7 RCPSPモデル ～ 生産スケジューリングを例として～

8 資源制約スケジューリング: RCPSP Resource Constrained Project Scheduling Problem
希少資源を必要とする作業に対し，資源配分， および各作業の処理時刻を決定する問題 モデル・・・ 抽象的，汎用的 　資源：　機械，設備，装置，工具，人的資源，予算，… 　作業：　資源を消費する活動; 仕事，工程，タスク，… 作業によって消費または生産される　　　 原材料，部品，製品などは陽に扱われない　

9 例：生産計画（１） 作業４ 作業３ 作業１ 作業２ 製品A 部品B 材料D 材料E 部品C 処理時間/資源 ２h/装置a， 作業員２人
　　　作業員２人 ２h/装置ｂ， 　　　作業員３人 ２h/装置ｃ， １０h/装置ｃ， 　　　　作業員３人 　作業４　 作業１ 作業３ 作業２

10 先行制約 作業 i が完了するまで作業 j を開始できない
非巡回有向グラフで表現 （activity-on-node diagram, precedence diagram） 材料Ｄ 材料Ｅ 製品Ａ 部品B 部品C 作業４ 作業１ 作業３ 作業２ 製品A の出荷 材料の 調達

11 RCPSP：再生型資源 再生型資源　(e.g., 設備，機械，工具，従業員，…) 各単位時間毎に利用可能量 ‐　週末は従業員の数が少ない， ‐　週末は機械を停止， ‐　装置の利用可能日が限定， ‐　… 作業員 日 機械 日

12 RCPSP：作業 作業 処理時間 (中断不可) 処理に必要な資源量 … 作業間の先行関係 装置 作業員 搬送車 作業開始 完了 作業開始
処理時間 (中断不可) 処理に必要な資源量 作業開始 完了 装置 作業開始 完了 作業員 作業開始 完了 搬送車 … 作業間の先行関係

13 現実とのギャップ 代替設備，代替資源 切替コスト，段取り時間 同時開始，同時終了，最小・最大遅延時間 （時間制約） 作業の分割，中断
同時開始，同時終了，最小・最大遅延時間 （時間制約） 作業の分割，中断 ロットまとめ 在庫 … 拡張RCPSPモデルで表現

14 RCPSP: 処理モード 作業の処理方法（＝処理時間，必要資源量） -　複数の選択肢・・・処理モード -　e.g., 性能の異なる機械， 　作業量（人×日）一定， 　特急処理， … 　RCPSP：　各作業をいつ，どの処理モードで行うかを決定

15 RCPSP: 処理モードに関する制約 非再生型資源　（e.g., 原材料，予算，…） 　　 -　スケジュール全体での利用可能量 　　 -　作業による消費量は処理モードにのみ依存 →　処理モードに関する制約 従属処理モード -　再生型資源 r 上での直前作業に依存 →　切替コスト -　作業 i は作業 j と同一の処理モード -　…

16 RCPSP: 直前先行制約（１） × 作業 i 作業 j ○ ・作業 i は作業 j に先行 ・再生型資源 r 上で定義
　i，j ともに r を消費  作業 i 完了後，次に r を 消費する作業は j 作業 i 作業 j × ○

17 RCPSP: 直前先行制約（２） 段取り替え作業 - 本作業の直前に実行 - 従属処理モード制約と組合せ
段取り替え作業 -　本作業の直前に実行 -　従属処理モード制約と組合せ 時間制約 -　同時開始 -　オーバーラップ -　最大遅延時間 作業 i 作業 j ダミー 作業 i 作業 j ダミー 作業 i 作業 j ダミー オーバーラップ

18 × RCPSP: 直前先行制約（３） その他 - 作業 i, j 間に作業 k は処理不可， - … i k ダミー j 処理時間0
作業 k も仮想資源 r を消費　

19 RCPSP: 直前先行制約（４） 処理モードとの組合せ
-　直前先行制約：再生型資源 r 上で定義 -　先行，後続作業ともに r を消費するとき有効 →　 r を消費するか否かは処理モードにより定まる →　 直前先行制約は処理モードに依存 e.g., -　作業 i は j, k, … のいずれかと同時に開始 -　ロットまとめしたとき，それらは同時開始 -　…

20 例：生産計画（２） 作業４ 作業３ 作業１ 作業２ 製品A 部品B 部品C 材料D 材料E 処理時間/資源 ２h/装置a， 作業員２人
　作業４　 ２h/装置a， 　　　作業員２人 部品B 部品C 作業３ １０h/装置ｃ， 　　　　作業員３人 ２h/装置ｂ， 　　　作業員３人 作業１ 作業２ ２h/装置ｃ， 　　　作業員２人 材料D 材料E

21 例：生産計画（２） ×２ ×４ 作業４ 作業３ 作業２ 作業１ 作業時間 一定 製品A 部品B 部品C １ ４ ２ 5 1 材料E 部品C
　作業４　 ２h 装置a 作業員２人 ロットサイズ １ ４ ２ 5 1 材料E 部品C 作業３ 作業２ ×４ ×２ ２h 装置ｂ 作業員３人 部品B 材料D 作業１ ２.5h 装置ｃ 作業員３人 １ｈ 装置ｃ 作業員２人 作業時間 一定

22 例：生産計画（２） 作業４ 作業2-1 作業2-2 作業3-1 作業3-2 作業１-1 作業１-2 作業１-3 作業１-4 別ロットモード
処理時間：2h 装置ｂ 同一ロットモード 作業3-1と同時開始

23 例：生産計画（３） 在庫： 基本的に先行制約で処理 先行制約で処理できないケース： 製品A1，A2 をそれぞれ５０個生産 作業A１ 作業A２
在庫：　基本的に先行制約で処理 先行制約で処理できないケース： 製品A1，A2 をそれぞれ５０個生産 製品A1 部品B 作業A１ ロットサイズ　１０ ２０ 製品A２ 作業A２ １０ ４０ 原料C 作業B ３０ １

24 例：生産計画（３） 製品A1 部品B 作業A１ ロットサイズ　１０ ２０ 製品A２ 作業A２ １０ ４０ 原料C 作業B ３０ １ 作業A1，A2 をそれぞれ5回処理 →　部品B：　全体で 300　必要 →　作業B：　１０回処理

25 例：生産計画（３） これでよいか？ 作業B-1 作業A1-1 作業B-2 作業A1-2 作業B-3 作業A1-3 作業B-4 作業A1-4

26 RCPSP: 蓄積型資源 原材料，部品，製品などを表現 作業により消費または生産される 在庫量　　０ 在庫量 時間

27 例：生産計画（３） 蓄積型資源： - 負の資源消費量を許す再生型資源 - 各作業は，処理開始または完了後も 資源を消費し続ける 資源量 時間
蓄積型資源： -　負の資源消費量を許す再生型資源 -　各作業は，処理開始または完了後も 　　資源を消費し続ける 資源量 負の消費量 時間

28 RCPSP: 評価基準 状況に応じて変化 → 柔軟な枠組みが必要 「最適化」よりはむしろ「制約充足」
制約違反度（ペナルティ）を最小化 -　再生型資源制約，先行制約， 　　直前先行制約は必ず満たすよう指定可能 ユーザ定義制約 処理モード，開始時刻，完了時刻に関する 線形不等式制約 e.g., 最大完了時刻最小化， 総納期遅れ和最小化， 非再生型資源制約，…

29 最適化の手法

30 代表的な解法 シミュレーション 山積み山崩し，優先規則法， フォワード，バックワードスケジューリング，…
シミュレーション 山積み山崩し，優先規則法， フォワード，バックワードスケジューリング，… 人工知能 制約伝播，遺伝アルゴリズム，… 数理計画・ＯＲ 分枝限定法，整数計画法， ラグランジュ緩和，… メタヒューリスティクス …

31 メタヒューリスティクス 基本的な発見的手法 (e.g., 欲張り法，局所探索法) 　　を融合，拡張した手法の総称 - アニーリング法 - 遺伝アルゴリズム - タブー探索法 … 実現・実装の自由度大 →　問題の構造を巧く捉えることが重要　 POP (Proximate Optimality Principle) 集中化・多様化

32 アルゴリズムの概略 リストスケジューリング ＋ バックトラック
リストスケジューリング　＋　バックトラック -　作業の順列（リスト）に従ってスケジュールを生成 -　各作業を，すべての制約を満たす最早開始時刻 　　に割付け（フォワード・スケジューリング） -　直前先行制約　←　必要の応じてバックトラック 最適なリストをタブー探索法で発見 　クリティカル・グラフに基づく近傍 　タブー期間（tabu tenure）の適応的制御

33 ベンチマーク: PSPLIB PSPLIB: Project Scheduling Problem LIBrary
先行制約，最大完了時刻最小化 ＃作業 ＃再生型 資源 ＃非再生型 資源 ＃処理 モード ＃最良解* j60.sm 60 4 1 2/480 j90.sm 90 12/480 j120.sm 120 75/600 j30.mm 30 2 3 126/550 *： 2001年１２月現在の最良解を最初に発見

34 ベンチマーク: ProGen/Max #最良解を更新 56問/1059問 #最良解を発見 704問/1059問
最小・最大遅延時間，最大完了時刻最小化 作業数　１００，再生型資源数　５ 実験結果 　#最良解を更新　 　56問/1059問 　#最良解を発見 704問/1059問 　下界値からの平均 % 　計算時間：　６００秒（PentiumIII　１GHｚ）/問

35 適用例

36 中断を考慮した生産スケジューリング ジョブショップ型のスケジューリング問題 - 複数の工程を経て製品が生産
ジョブショップ型のスケジューリング問題 - 複数の工程を経て製品が生産 - 工程: （前半）手動処理 → （後半）自動処理 - 設備資源，作業員資源 休憩時間：　手動処理を中断（割り込み不可） 　自動処理は続行

37 中断を考慮した生産スケジューリング(2) 作業の分割 手動処理 自動処理 （部分作業の継ぎ目に限り）作業の中断が可能
手動処理　　　　　　　自動処理 （部分作業の継ぎ目に限り）作業の中断が可能 連続する部分作業間に直前先行制約 → 割り込みの禁止

38 作業場所を考慮した生産スケジューリング 部品 ・クレーンで搬入  作業  搬出 ・配置場所は固定
部品 ・クレーンで搬入  作業  搬出 ・配置場所は固定 ・処理日数, 最早搬入日, 最遅搬出日： given 搬入日，搬入位置を決定 部品 i li L 搬入 搬出

39 作業場所を考慮した生産スケジューリング （長さ）×（日数）の矩形を配置する問題 日程 搬入日 xi 配置位置 搬入 位置 yi 部品 i
搬入 位置 yi L 処理日数 123 li 搬入日 xi 配置位置 日程

40 作業場所を考慮した生産スケジューリング： 搬入日の決定
・クレーン，従業員： 再生型資源 ・最早搬入日： 先行制約 （最小遅延時間指定） ・最遅搬出日： ソフト制約  違反度最小化 ・配置場所：再生型資源; 利用可能量 ρL （ρ: 0 ρ １ の定数） -部品 i による消費量: i -ρ= 1： 配置可能となるための必要条件 -ρ< 1： 必要条件よりも強い ⇒ 次段階において配置し易い

41 作業場所を考慮した生産スケジューリング： 搬入位置の決定
日　程 配置位置 yi L yi+li xi 部 品 i ・配置位置 ⇔ RCPSPの時間軸 （適当な長さで離散化） ・部品の長さ ⇔ 処理時間 ・各日 ⇔ 再生型資源 ・最大完了時刻: L 以下  実行可能配置

42 今後の展開

43 今後の展開 実用化 　スケジューリング・「エンジン」として開発 　→ ActiveXコンポーネント OptSeq ( 　ＲＣＰＳＰへの帰着：　‘‘art’’ 　モデル化の指針 高速化・大規模問題対応 　性能，汎用性とのトレードオフ -　データ構造

44 今後の展開 モデルの拡張 - 非正規評価基準 ← 凸型コスト関数 ロットサイズの決定 切替・段取り費用と在庫費用のトレードオフ
-　非正規評価基準　←　凸型コスト関数 　ロットサイズの決定 　切替・段取り費用と在庫費用のトレードオフ →　問題を複雑・大規模化 　問題範囲をどこまで拡大すべきか？