COM・APS（先進的スケジューリング）研究部会 2001/12/21 スケジューリング最適化エンジン ― RCPSPによるアプローチ 野々部宏司 京都大学大学院情報学研究科 （茨木俊秀教授との共同研究） COM・APS（先進的スケジューリング）研究部会 2001/12/21 はじめに APS (Advanced Planning and Scheduling) ‐ 生産計画（在庫計画）＋スケジューリング ‐ 資材調達計画＋資源負荷計画 ‐ 納期回答 ‐ … 〈スケジューリング・エンジンの重要性〉 ・問題を数学的に捉え（モデルの作成）， ・最適化の手法を適用 COM・APS（先進的スケジューリング）研究部会 2001/12/21 本研究の目指すところ 実用性の高いスケジューリング・エンジンの開発 ・適用可能性（汎用性） ← 拡張RCPSPモデル ・高性能 ← メタヒューリスティクス RCPSPに 定式化 汎用モデル RCPSP RCPSP ソルバ スケジュール スケジューリング最適化エンジン COM・APS（先進的スケジューリング）研究部会 2001/12/21 本研究の位置付け（１） 理論 ―――― 応用 ―――― 実用 Theory Application Practice ・モデルの作成 ‐ 避けては通れない（避けてはならない） ‐ 現状把握，問題整理・認識，目標設定 ‐ 抽象化と具体化（限定化）のバランス ・最適化 ≒ 制約充足・実現可能を目指す COM・APS（先進的スケジューリング）研究部会 2001/12/21 本研究の位置付け（２） 生産計画 ――――― スケジューリング planning scheduling ・部品表・工程表は既知 ・「どの製品を，どれだけ，いつまでに生産するか」 を入力として （← 需要予測，受注，在庫，…）， ・「各製品を，いつ生産するか」を決定 （→ 資材調達，生産スケジュール） ・有限負荷，現場レベルでの制約を考慮 COM・APS（先進的スケジューリング）研究部会 2001/12/21 本研究の位置付け（３） 秒・分 ― 時 ―― 日 ―― 週 ――― 月 ――― 年 最小単位時間 計画期間 ・問題規模： 数百個 ～ 数千個の作業（工程） ・計算時間： 数十秒 ～ 十数分 （～ 数十分） ・シミュレーションを行うだけではない COM・APS（先進的スケジューリング）研究部会 2001/12/21 RCPSPモデル ～ 生産スケジューリングを例として～ COM・APS（先進的スケジューリング）研究部会 2001/12/21 資源制約スケジューリング: RCPSP Resource Constrained Project Scheduling Problem 希少資源を必要とする作業に対し，資源配分， および各作業の処理時刻を決定する問題 モデル・・・ 抽象的，汎用的 資源： 機械，設備，装置，工具，人的資源，予算，… 作業： 資源を消費する活動; 仕事，工程，タスク，… 作業によって消費または生産される 原材料，部品，製品などは陽に扱われない COM・APS（先進的スケジューリング）研究部会 2001/12/21 例：生産計画（１） 製品A 作業４ 部品 B １０h/装置ｃ， 作業員３人 作業１ 材料D 処理時間/資源 ２h/装置a， 作業員２人 部品 C 作業３ ２h/装置ｂ， 作業員３人 作業２ ２h/装置ｃ， 作業員２人 材料E COM・APS（先進的スケジューリング）研究部会 2001/12/21 先行制約 ・作業 i が完了するまで作業 j を開始できない ・非巡回有向グラフで表現 （activity-on-node diagram, precedence diagram） 材料Ｄ 製品Ａ 部品B 作業１ 材料の 調達 作業４ 作業２ 材料Ｅ 作業３ 部品C 製品A の出荷 COM・APS（先進的スケジューリング）研究部会 2001/12/21 RCPSP：再生型資源 ・再生型資源 (e.g., 設備，機械，工具，従業員，…) 各単位時間毎に利用可能量 ‐ 週末は従業員の数が少ない， ‐ 週末は機械を停止， ‐ 装置の利用可能日が限定， ‐ … 作 機業 械員 日 日 COM・APS（先進的スケジューリング）研究部会 2001/12/21 RCPSP：作業 ・作業 処理時間 (中断不可) 処理に必要な資源量 搬 送 車 装 作置 業 員 作業開始 作業開始 作業開始 ・作業間の先行関係 完了 完了 完了 COM・APS（先進的スケジューリング）研究部会 2001/12/21 現実とのギャップ ・代替設備，代替資源 ・切替コスト，段取り時間 ・同時開始，同時終了，最小・最大遅延時間 （時間制約） ・作業の分割，中断 ・ロットまとめ ・在庫 ・… 拡張RCPSPモデルで表現 COM・APS（先進的スケジューリング）研究部会 2001/12/21 RCPSP: 処理モード ・作業の処理方法（＝処理時間，必要資源量） - 複数の選択肢・・・処理モード - e.g., 性能の異なる機械， 作業量（人×日）一定， 特急処理， … RCPSP： 各作業をいつ，どの処理モードで行うかを決定 COM・APS（先進的スケジューリング）研究部会 2001/12/21 RCPSP: 処理モードに関する制約 ・非再生型資源 （e.g., 原材料，予算，…） - スケジュール全体での利用可能量 - 作業による消費量は処理モードにのみ依存 → 処理モードに関する制約 ・従属処理モード - 再生型資源 r 上での直前作業に依存 → 切替コスト - 作業 i は作業 j と同一の処理モード - … COM・APS（先進的スケジューリング）研究部会 2001/12/21 RCPSP: 直前先行制約（１） ・作業 i は作業 j に先行 ・再生型資源 r 上で定義 i，j ともに r を消費 作業 i 完了後，次に r を 消費する作業は j 作業 i 作業 j × × ○ ○ COM・APS（先進的スケジューリング）研究部会 2001/12/21 RCPSP: 直前先行制約（２） ・段取り替え作業 - 本作業の直前に実行 - 従属処理モード制約と組合せ ・時間制約 - 同時開始 - オーバーラップ - 最大遅延時間 作業 i 作業 i オーバーラップ ダミー 作業 j 作業 i ダミー 作業 j 作業 j ダミー オーバーラップ COM・APS（先進的スケジューリング）研究部会 2001/12/21 RCPSP: 直前先行制約（３） ・その他 - 作業 i, j 間に作業 k は処理不可， - … i ダミー 処理時間0 ×k ダミー j ・ダミー，i 間およびダミー，j 間は先行制約 ・ダミー，ダミー間は仮想資源 r 上の直前先行制約 ・作業 k も仮想資源 r を消費 COM・APS（先進的スケジューリング）研究部会 2001/12/21 RCPSP: 直前先行制約（４） ・処理モードとの組合せ - 直前先行制約：再生型資源 r 上で定義 - 先行，後続作業ともに r を消費するとき有効 → r を消費するか否かは処理モードにより定まる → 直前先行制約は処理モードに依存 e.g., - 作業 i は j, k, … のいずれかと同時に開始 - ロットまとめしたとき，それらは同時開始 - … COM・APS（先進的スケジューリング）研究部会 2001/12/21 例：生産計画（２） 製品A 作業４ 部品 B １０h/装置ｃ， 作業員３人 作業１ 材料D 処理時間/資源 ２h/装置a， 作業員２人 部品 C 作業３ ２h/装置ｂ， 作業員３人 作業２ ２h/装置ｃ， 作業員２人 材料E COM・APS（先進的スケジューリング）研究部会 2001/12/21 例：生産計画（２） 製品A ロットサイズ １ 作業４ 部品 B １ 作業１ 5 材料D ４ 部品 B ２ ２h 装置a 作業員２人 部品 C 部品 C 1 作業３ ２.5h 装置ｃ ×４ 作業員３人 作業時間 一定 作業２ ４ 材料E ２h ×２ 装置ｂ 作業員３ 人 １ｈ ×２ 装置ｃ 作業員２ 人 COM・APS（先進的スケジューリング）研究部会 2001/12/21 例：生産計画（２） 作業１-1 作業１-2 作業１-3 作業４ 作業１-4 作業2-1 作業3-1 作業2-2 作業3-2 別ロットモード 処理時間：2h 装置ｂ 同一ロットモード 処理時間：2h 作業3-1と同時開始 COM・APS（先進的スケジューリング）研究部会 2001/12/21 例：生産計画（３） ・在庫： 基本的に先行制約で処理 ・先行制約で処理できないケース： 製品A1 ロットサイズ １０ 製品A２ １０ 部品B ３０ 作業A１ 作業A２ 作業B ２０ 部品 B ４０ 部品 B １ ・製品A1，A2 をそれぞれ５０個生産 原料 C COM・APS（先進的スケジューリング）研究部会 2001/12/21 例：生産計画（３） 製品A1 ロットサイズ １０ 製品A２ １０ 部品B ３０ 作業A１ 作業A２ 作業B ２０ 部品 B ４０ 部品 B １ 原料 C ・作業A1，A2 をそれぞれ5回処理 → 部品B： 全体で 300 必要 → 作業B： １０回処理 COM・APS（先進的スケジューリング）研究部会 2001/12/21 例：生産計画（３） 作業B-1 作業B-2 作業B-3 作業B-4 作業B-5 作業B-6 作業B-7 作業B-8 作業B-9 作業B-10 こ れ で よ い か ？ 作業A1-1 作業A1-2 作業A1-3 作業A1-4 作業A1-5 作業A2-1 作業A2-2 作業A2-3 作業A2-4 作業A2-5 COM・APS（先進的スケジューリング）研究部会 2001/12/21 RCPSP: 蓄積型資源 ・原材料，部品，製品などを表現 ・作業により消費または生産される ・在庫量 ０ 在 庫 量 時間 COM・APS（先進的スケジューリング）研究部会 2001/12/21 例：生産計画（３） ・蓄積型資源： - 負の資源消費量を許す再生型資源 - 各作業は，処理開始または完了後も 資源を消費し続ける 資 源 量 時間 負の消費量 COM・APS（先進的スケジューリング）研究部会 2001/12/21 RCPSP: 評価基準 ・状況に応じて変化 → 柔軟な枠組みが必要 ・「最適化」よりはむしろ「制約充足」 ・制約違反度（ペナルティ）を最小化 - 再生型資源制約，先行制約， 直前先行制約は必ず満たすよう指定可能 ・ユーザ定義制約 処理モード，開始時刻，完了時刻に関する 線形不等式制約 e.g., 最大完了時刻最小化， 総納期遅れ和最小化， 非再生型資源制約，… COM・APS（先進的スケジューリング）研究部会 2001/12/21 最適化の手法 COM・APS（先進的スケジューリング）研究部会 2001/12/21 代表的な解法 ・シミュレーション 山積み山崩し，優先規則法， フォワード，バックワードスケジューリング，… ・人工知能 制約伝播，遺伝アルゴリズム，… ・数理計画・ＯＲ 分枝限定法，整数計画法， ラグランジュ緩和，… ・メタヒューリスティクス ・… COM・APS（先進的スケジューリング）研究部会 2001/12/21 メタヒューリスティクス ・基本的な発見的手法 (e.g., 欲張り法，局所探索法) を融合，拡張した手法の総称 - アニーリング法 - 遺伝アルゴリズム - タブー探索法 … 実現・実装の自由度大 → 問題の構造を巧く捉えることが重要 ・POP (Proximate Optimality Principle) ・集中化・多様化 COM・APS（先進的スケジューリング）研究部会 2001/12/21 アルゴリズムの概略 ・リストスケジューリング ＋ バックトラック - 作業の順列（リスト）に従ってスケジュールを生成 - 各作業を，すべての制約を満たす最早開始時刻 に割付け（フォワード・スケジューリング） - 直前先行制約 ← 必要の応じてバックトラック ・最適なリストをタブー探索法で発見 - クリティカル・グラフに基づく近傍 - タブー期間（tabu tenure）の適応的制御 COM・APS（先進的スケジューリング）研究部会 2001/12/21 ベンチマーク: PSPLIB PSPLIB: Project Scheduling Problem LIBrary http://www.bwl.uni-kiel.de/Prod/psplib/ 先行制約，最大完了時刻最小化 ＃作業 ＃再生型 資源 ＃非再生型 資源 ＃処理 モード ＃最良解* j60.sm 60 4 0 1 2/480 j90.sm 90 4 0 1 12/480 j120.sm 120 4 0 1 75/600 j30.mm 30 2 2 3 126/550 *： 2001年１２月現在の最良解を最初に発見 COM・APS（先進的スケジューリング）研究部会 2001/12/21 ベンチマーク: ProGen/Max ・http://www.wior.uni-karlsruhe.de/RCPSPmax/progenmax ・最小・最大遅延時間，最大完了時刻最小化 ・作業数 １００，再生型資源数 ５ ・実験結果 #最良解を更新 #最良解を発見 下界値からの平均 56問/1059問 704問/1059問 4.44 % 計算時間： ６００秒（PentiumIII １GHｚ）/問 COM・APS（先進的スケジューリング）研究部会 2001/12/21 適用例 COM・APS（先進的スケジューリング）研究部会 2001/12/21 中断を考慮した生産スケジューリング ・ジョブショップ型のスケジューリング問題 - 複数の工程を経て製品が生産 - 工程: （前半）手動処理 → （後半）自動処理 - 設備資源，作業員資源 ・休憩時間： 手動処理を中断（割り込み不可） 自動処理は続行 COM・APS（先進的スケジューリング）研究部会 2001/12/21 中断を考慮した生産スケジューリング(2) 作業の分割 手動処理 自動処理 ・（部分作業の継ぎ目に限り）作業の中断が可能 ・連続する部分作業間に直前先行制約 → 割り込みの禁止 COM・APS（先進的スケジューリング）研究部会 2001/12/21 作業場所を考慮した生産スケジューリング 部品 ・クレーンで搬入 作業 搬出 ・配置場所は固定 ・処理日数, 最早搬入日, 最遅搬出日： given 搬入日，搬入位置を決定 搬入 搬出 部品 i 144424443 li L COM・APS（先進的スケジューリング）研究部会 2001/12/21 作業場所を考慮した生産スケジューリング （長さ）×（日数）の矩形を配置する問題 配 置 搬入 位 位置 yi 置 L 搬入日 xi 123 0 日程 li 部品 i 1442443 処理日数 COM・APS（先進的スケジューリング）研究部会 2001/12/21 作業場所を考慮した生産スケジューリング： 搬入日の決定 ・クレーン，従業員： 再生型資源 ・最早搬入日： 先行制約 （最小遅延時間指定） ・最遅搬出日： ソフト制約 違反度最小化 ・配置場所：再生型資源; 利用可能量 ρL （ρ: 0 ρ １ の定数） -部品 i による消費量: li -ρ= 1： 配置可能となるための必要条件 -ρ< 1： 必要条件よりも強い ⇒ 次段階において配置し易い COM・APS（先進的スケジューリング）研究部会 2001/12/21 作業場所を考慮した生産スケジューリング： 搬入位置の決定 ・配置位置 ⇔ RCPSPの時間軸 配置位置 0 yi L yi+li （適当な長さで離散化） ・部品の長さ ⇔ 処理時間 ・各日 ⇔ 再生型資源 日 ・最大完了時刻: L 以下 程 実行可能配置 xi 部 品 i COM・APS（先進的スケジューリング）研究部会 2001/12/21 今後の展開 COM・APS（先進的スケジューリング）研究部会 2001/12/21 今後の展開 ・実用化 - スケジューリング・「エンジン」として開発 → ActiveXコンポーネント OptSeq (http://www.logopt.com/） - ＲＣＰＳＰへの帰着： ‘‘art’’ モデル化の指針 ・高速化・大規模問題対応 - 性能，汎用性とのトレードオフ - データ構造 COM・APS（先進的スケジューリング）研究部会 2001/12/21 今後の展開 ・モデルの拡張 - 非正規評価基準 ← 凸型コスト関数 - ロットサイズの決定 切替・段取り費用と在庫費用のトレードオフ → 問題を複雑・大規模化 問題範囲をどこまで拡大すべきか？
© Copyright 2024 ExpyDoc
![リーフレット [Leaflet] - 電力中央研究所](http://s3.expydoc.com/store/data/007183643_1-829a95628c2b4899cac3c39ec5765713-250x500.png)
