資源制約スケジューリング問題 ―メタヒューリスティクスによるアプローチ 野々部宏司 法政大学デザイン工学部

背景 組合せ（最適化）問題： “離散的”な集合を扱う問題 実用上の要請 高性能アルゴリズム 汎用近似アルゴリズム 計算の複雑さの理論： NP困難性 現実には，多くの場合において厳密解を求めることは困難 実用上の要請 解きたい問題（問題例）に対して，一定時間内に実務上許容可能な解が実際 に得られること 比較的良質の解で満足 近似解法，発見的手法 高性能アルゴリズム 問題構造を巧く利用 適用範囲限定 汎用近似アルゴリズム 性能と汎用性のトレードオフ

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

モデル

RCPSP (Resource Constrained Project Scheduling Problem) 資源 r ∈ R 機械，工具，マンパワー，… 各時間 Kr まで利用可能 作業（仕事，工程） i ∈ I 処理時間： di　（中断不可） 必要資源量： ki,r 　for　r ∈ Ri 開始時刻（決定変数, 非負整数）： si 先行制約 i → j si + di  sj 評価基準 最大完了時刻，フロー時間，最大納期遅れ，…

ガントチャート 2 1 3 4 5 6 7 8 9 10 11 12 i ki,r di t

ガントチャート 2 1 3 4 5 6 7 8 9 10 11 12 t 資源 r i ki,r di 3 4 Kr = 3 2 4 5 4

拡張RCPSP 資源供給量が時間の経過とともに変化 作業による資源消費量が処理の経過とともに変化 時間制約（一般化先行制約） 資源供給量： Kr  Kr,t (t = 1, 2, …) 作業による資源消費量が処理の経過とともに変化 資源消費量： ki,r  ki,r,t (t = 1, 2, …, di) 時間制約（一般化先行制約） Multiple 処理モード 作業の中断，並列処理

時間制約 sj – si  dij dij  0 の場合 最小遅延時間，最早開始時刻 i dij  0 j t si sj

時間制約 sj – si  dij dij  0 の場合 最大遅延時間，納期 i dji < 0 j t si sj

時間制約 sj – si  dij dij  0 i dji < 0 j t sj 時間枠の設定なども可能

時間制約スケジューリング si + dij  sj dij i j Activity-on-node project network 作業間の先行関係（時間制約）を表現 i から j への最長路を dist(i, j) とすれば，si + dist(i, j)  sj 実行可能スケジュールが存在することは，長さ正の閉路が存在しないこ とに対応 （全点間）最長路問題： O(n (m + n log n)) 時間 si + dij  sj i j dij 1 –3 –1 2 –4 4 8 –5 3 5 6 1 3 10 8 dist(0, i): 最早開始時刻

Multiple 処理モード 作業の処理方法（＝処理時間，必要資源量） MRCPSP（Multi-mode RCPSP） 処理モードとして，複数の選択肢を設定可能 例 性能の異なる機械 作業量（人×日）一定 特急処理  MRCPSP（Multi-mode RCPSP） 各作業をいつ，どの処理モードで行うかを決定

Multiple 処理モード 作業 i の処理モード集合 Mi 0-1 変数 xi,m を用いて作業 i の処理モードを表現 xi,m =1 ⇔ 作業 i を処理モード m で処理  xi,m = 1, for all i m∈Mi 処理モード割当て： x = (xi,m | i ∈ I, m ∈ Mi) 非再生資源制約 s ∈ Rnon スケジュール全体での利用可能量に制限 例： 原材料，予算，...   hm,s xi,m  Hs i m 処理モードのみに関する制約

作業の中断 d 作業 i 1 2 … t … d it 作業 i 作業は中断後, 再処理可能 作業 i （処理時間 d） を d個の小作業 iτ (1  τ  d) に分解 d 作業 i 1 2 … t … d it 作業 i

作業の中断 1 2 … t dm 作業 i t+1 it it+1  b(t) 中断 作業は中断後, 再処理可能 作業 i （処理時間 d） を d個の小作業 iτ (1  τ  d) に分解 小作業間で中断可能 iτ, iτ+1 間の最大中断時間 b(τ) を設定可能 1 2 … t dm 作業 i t+1 it it+1  b(t) 中断

作業の中断 1 2 … t dm 作業 i t+1 it it+1 作業は中断後, 再処理可能 作業 i （処理時間 d） を d個の小作業 iτ (1  τ  d) に分解 小作業間で中断可能 iτ, iτ+1 間の最大中断時間 b(τ) を設定可能 各作業の開始時刻ベクトル si = (sit | 1  t  di) を決定 中断中も資源を消費可能 1 2 … t dm 作業 i t+1 it it+1

例：勤務時間を考慮した生産スケジューリング ジョブショップ型のスケジューリング問題 各製品は複数の工程を経て生産 工程は，手動処理（前半） + 自動処理（後半） 設備資源は工程全体を通して，作業員資源 は手動処理においてのみ必要 休憩時間，シフト間においては， 手動処理を中断，自動処理は続行 割り込み不可 8 12 18 24 6 自動処理 手動処理 時

例：勤務時間を考慮した生産スケジューリング ジョブショップ型のスケジューリング問題 各製品は複数の工程を経て生産 工程は，手動処理（前半） + 自動処理（後半） 設備資源は工程全体を通して，作業員資源 は手動処理においてのみ必要 休憩時間，シフト間においては， 手動処理を中断，自動処理は続行 割り込み不可 8 12 18 24 6 自動処理 手動 割り込み禁止（中断中も設備資源を消費） 時

作業の並列処理 1 2 … t … d it i1 i2 it 作業 i p(t): 最大並列数 小作業を並列処理可能 資源集合 R を，消費のされ方によって Rsum, Rmax に 分割 1 2 … t … d it 作業 i i1 i2 p(t): 最大並列数 it

例： 配員計画を含む生産スケジューリング 大きな構造物が対象 総仕事量のみが与えられ，詳細な計画なし 作業： 溶接，研磨，塗装など 資源： 構造物の配置場所，工員 総仕事量のみが与えられ，詳細な計画なし 溶接 研磨 塗装 t

例： 配員計画を含む生産スケジューリング 大きな構造物が対象 総仕事量のみが与えられ，詳細な計画なし 作業： 溶接，研磨，塗装など 資源： 構造物の配置場所，工員 総仕事量のみが与えられ，詳細な計画なし 溶接 研磨 塗装 t

例： 配員計画を含む生産スケジューリング 大きな構造物が対象 総仕事量のみが与えられ，詳細な計画なし 作業： 溶接，研磨，塗装など 資源： 構造物の配置場所，工員 総仕事量のみが与えられ，詳細な計画なし 「工員」資源 ∈ Rsum： 各小作業が消費する資源量の合計が必要 「配置場所」資源 ∈ Rmax： 小作業が消費する資源量の中で最大のものが必要 塗装 研磨 溶接 作業の並列処理 t

アルゴリズム

局所探索法 適当な初期解 x を何らかの方法で生成 x に対して，局所的な変更を加えて得られる解の集合（近傍） N(x) の中に x よりもよい解 x が存在すれば，x := x として （x から x に移動して）2. に戻る 存在しなければ終了 N(x) x x

タブー探索法 局所探索法の拡張 改悪解への移動を許可 近傍内の最良解へ（改悪であっても）移動 過去の探索履歴を基に，近傍を制限

アルゴリズムの概略 基本的枠組みはタブー探索 解 (x, ℓ) 実行可能処理モード割当て x = (xi,m | i∈I, m∈Mi) 非再生可能資源制約をすべて満足 作業リスト （作業の順列） ℓ = (ℓ1, ℓ2,…, ℓ|I|): リストスケジューリングによって，解 (x, ℓ) からスケジュール (x, s) を生成 s = (si | i ∈ I ) si = (siτ | 1  τ  di,m) : 作業 i の開始時刻ベクトル リストスケジューリングにより得られるスケジュールで解を評価

リストスケジューリング 入力： 解 (x, ℓ) 出力： 実行可能スケジュール (x, s) or “failure” 各作業の開始時刻ベクトル si（各小作業の開始時刻）をリストの順に決定 si ： すべての制約を満たす最早開始時刻（最小ベクトル） フォワード・スケジューリング 実行可能な開始時刻ベクトルが存在しない場合は，バックトラック

リストスケジューリング： バックトラック 入力： 解 (x, ℓ) 出力： 実行可能スケジュール (x, s) or “failure” 2 1 3 4 5 6 7 8 9 10 11 12 4 i j i ... j t

リストスケジューリング： バックトラック 入力： 解 (x, ℓ) 出力： 実行可能スケジュール (x, s) or “failure” 2 1 3 4 5 6 7 8 9 10 11 12 -4 i j i ... j t

リストスケジューリング： バックトラック 入力： 解 (x, ℓ) 出力： 実行可能スケジュール (x, s) or “failure” バックトラック回数に制限 2 1 3 4 5 6 7 8 9 10 11 12 -4 i j i ... j t

解空間の縮小 Activity-on-node project network の利用 以下の条件を満たす解 (x, ℓ) のみ探索 1. 　dist(i, j) < , dist( j, i) =   リスト ℓ において，i は j に先行 2. 　同一強連結成分内の作業はリスト ℓ 中連続して出現 1 –3 –1 2 –4 4 8 –5 3 5 6

初期解 初期解 (x0, ℓ0) 初期処理モード割当て x0 初期リスト ℓ0 実行可能性判定（すべての非再生可能資源制約を満たすことができるかどうかの 判定）がNP困難 制約充足問題に対するメタヒューリスティクス（TabuCSP） 初期リスト ℓ0 ランダムもしくは発見的手法

近傍 近傍 N(x, ℓ) 1. ChangeMode(i, m) 2. ShiftForward(i, j)

近傍 近傍 N(x, ℓ) 1. ChangeMode(i, m) 2. ShiftForward(i, j) 作業 i の処理モードを m∈ Mi に変更 その結果，x が非再生可能資源制約に違反するようであれば， x を初期解として TabuCSP を実行 TabuCSP は，ある定められた反復回数で打ち切り 2. ShiftForward(i, j)

近傍 近傍 N(x, ℓ) 1. ChangeMode(i, m) 2. ShiftForward(i, j) 1. 　dist(i, j) < , dist( j, i) =   リスト ℓ において，i は j に先行 2. 　同一強連結成分内の作業はリスト ℓ 中連続して出現

近傍 近傍 N(x, ℓ) 1. ChangeMode(i, m) 2. ShiftForward(i, j) クリティカルパスによる近傍の縮小

計算実験

ベンチマーク問題： MRCPSP Tabu search1 30 秒 95/270 284.07% Multi-mode RCPSP (資源制約,　先行制約) PSPLIB [Kolisch and Sprecher, 1997] j20: 554 個の問題例 |R| = |Rnon| = 2, | I | = 20, |Mi| = 3 アルゴリズム 　　計算時間 #実行可能 最良値からの平均誤差 Tabu search1 30 秒 95/270 284.07% Priority-rule method2 270/270 180.05% Our tabu search3 10 秒 269/270 95.88% 1. [De Reyck and Herroelen, 1999] 333MHz PC 上で実行 2. [Heilmann, 2001] 333MHz PC上で実行 3. 1GHz PC上で実行

ベンチマーク問題： MRCPSP/max Tabu search1 30 秒 95/270 284.07% Multi-mode RCPSP with minimum and maximum time lags ProGen/max [Schwindt, 1998] 270 個の問題例: |R| = |Rnon| = 3, | I | = 100, |Mi| = 3, 4 or 5 アルゴリズム 　　計算時間 #実行可能 最良値からの平均誤差 Tabu search1 30 秒 95/270 284.07% Priority-rule method2 270/270 180.05% Our tabu search3 10 秒 269/270 95.88% 1. [De Reyck and Herroelen, 1999] 333MHz PC 上で実行 2. [Heilmann, 2001] 333MHz PC上で実行 3. 1GHz PC上で実行