LOG OPT HOME

資源制約スケジューリング問題
―メタヒューリスティクスによるアプ
ローチ
野々部宏司
法政大学デザイン工学部
背景


組合せ（最適化）問題： “離散的”な集合を扱う問題

計算の複雑さの理論： NP困難性

現実には，多くの場合において厳密解を求めることは困難
実用上の要請




解きたい問題（問題例）に対して，一定時間内に実務上許容可能な解が実際
に得られること
比較的良質の解で満足 近似解法，発見的手法
高性能アルゴリズム

問題構造を巧く利用

適用範囲限定
汎用近似アルゴリズム

性能と汎用性のトレードオフ
本研究の目指すところ

実用性の高いスケジューリング・エンジンの開発

適用可能性（汎用性）：拡張RCPSPモデル

高性能：メタヒューリスティクス
RCPSPに
定式化
スケジュール
汎用モデル
RCPSP
RCPSP
ソルバ
スケジューリング最適化エンジン
理論 ―――― 応用 ―――― 実用
Theory
Application
Practice
モデル
RCPSP
(Resource Constrained Project Scheduling Problem)



資源 r ∈ R

機械，工具，マンパワー，…

各時間 Kr まで利用可能
作業（仕事，工程） i ∈ I

処理時間： di （中断不可）

必要資源量： ki,r

開始時刻（決定変数, 非負整数）： si
r ∈ Ri
先行制約 i → j


for
si + di  sj
評価基準

最大完了時刻，フロー時間，最大納期遅れ，…
ガントチャート
ki,r
3
di
4
2
5
1
1
2
3
i
4
5
6
7
8
9 10 11 12
t
ガントチャート
資源 r
ki,r
6
i
5
3
Kr = 4
di
4
3
2
1
3
2
4
5
4
1
1
2
3
4
5
6
7
8
9 10 11 12
t
拡張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
si
sj
t
時間制約
sj – si  dij

dij  0 の場合

最大遅延時間，納期
i
dji < 0
j
si
sj
t
時間制約
sj – si  dij

時間枠の設定なども可能
i
dji < 0
dij  0
j
sj
j の i に対する時間枠
t
時間制約スケジューリング

Activity-on-node project network

作業間の先行関係（時間制約）を表現
1
1
2
–3
4
0
0
1 6
0
0
0
–1
3
2
5


4
–4
0
8

2
3
–5
i
2
j
si + dij  sj
6
4
dij
10
dist(0, i): 最早開始時刻
8
i から j への最長路を dist(i, j) とすれば，si + dist(i, j)  sj
実行可能スケジュールが存在することは，長さ正の閉路が存在しないこ
とに対応
（全点間）最長路問題： O(n (m + n log n)) 時間
Multiple 処理モード


作業の処理方法（＝処理時間，必要資源量）

処理モードとして，複数の選択肢を設定可能

例

性能の異なる機械

作業量（人×日）一定

特急処理


MRCPSP（Multi-mode RCPSP）

各作業をいつ，どの処理モードで行うかを決定
Multiple 処理モード

作業 i の処理モード集合 Mi

0-1 変数 xi,m を用いて作業 i の処理モードを表現


xi,m =1 ⇔ 作業 i を処理モード m で処理

m∈Mi


xi,m = 1, for all i
処理モード割当て： x = (xi,m | i ∈ I, m ∈ Mi)
非再生資源制約 s ∈ Rnon

スケジュール全体での利用可能量に制限
例：原材料，予算，...

  hm,s xi,m  Hs
i

m
処理モードのみに関する制約
作業の中断
作業は中断後, 再処理可能

作業 i （処理時間 d）を d個の小作業 iτ (1  τ  d) に分解
d
作業 i
1 2 …
作業 i
t …
it
d
作業の中断
作業は中断後, 再処理可能

作業 i （処理時間 d）を d個の小作業 iτ (1  τ  d) に分解

小作業間で中断可能

iτ, iτ+1 間の最大中断時間 b(τ) を設定可能
1 2 …
作業 i
中断
t
it
t+1
it+1
 b(t)
dm
作業の中断
作業は中断後, 再処理可能

作業 i （処理時間 d）を d個の小作業 iτ (1  τ  d) に分解

小作業間で中断可能

iτ, iτ+1 間の最大中断時間 b(τ) を設定可能
1 2 …
作業 i
t
it
t+1
it+1

各作業の開始時刻ベクトル si = (sit | 1  t  di) を決定

中断中も資源を消費可能
dm
例：勤務時間を考慮した生産スケジュー
リング
ジョブショップ型のスケジューリング問題

各製品は複数の工程を経て生産

工程は，手動処理（前半） + 自動処理（後半）

設備資源は工程全体を通して，作業員資源は手動処理においてのみ必要

休憩時間，シフト間においては，

手動処理を中断，自動処理は続行

割り込み不可
手動処理
8
12
自動処理
18
24
6
時
例：勤務時間を考慮した生産スケジュー
リング
ジョブショップ型のスケジューリング問題

各製品は複数の工程を経て生産

工程は，手動処理（前半） + 自動処理（後半）

設備資源は工程全体を通して，作業員資源は手動処理においてのみ必要

休憩時間，シフト間においては，

手動処理を中断，自動処理は続行

割り込み不可
手動
8
手動
12
手動自動処理
18
24
割り込み禁止（中断中も設備資源を消費）
6
時
作業の並列処理
小作業を並列処理可能

資源集合 R を，消費のされ方によって Rsum, Rmax に分割
作業 i
1 2 …t …
i1 i2
it
d
 p(t): 最大並列数
it
例：配員計画を含む生産スケジューリン
グ


大きな構造物が対象

作業：溶接，研磨，塗装など

資源：構造物の配置場所，工員
総仕事量のみが与えられ，詳細な計画なし
溶接
研磨
塗装
t
例：配員計画を含む生産スケジューリン
グ


大きな構造物が対象

作業：溶接，研磨，塗装など

資源：構造物の配置場所，工員
総仕事量のみが与えられ，詳細な計画なし
溶接
研磨
塗装
t
例：配員計画を含む生産スケジューリン
グ


大きな構造物が対象

作業：溶接，研磨，塗装など

資源：構造物の配置場所，工員
総仕事量のみが与えられ，詳細な計画なし
溶接
研磨
作業の並列処理
塗装
t

「工員」資源 ∈ Rsum：各小作業が消費する資源量の合計が必要
「配置場所」資源 ∈ Rmax：小作業が消費する資源量の中で最大のものが
必要
アルゴリズム
局所探索法
1. 適当な初期解 x を何らかの方法で生成
2. 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”
i
4
j
i
...
j
t
1
2
3
4
5
6
7
8
9 10 11 12
リストスケジューリング：バッ
クトラック
入力：解 (x, ℓ)
出力：実行可能スケジュール (x, s) or “failure”
i
-4
j
i
...
j
t
1
2
3
4
5
6
7
8
9 10 11 12
リストスケジューリング：バッ
クトラック
入力：解 (x, ℓ)
出力：実行可能スケジュール (x, s) or “failure”

バックトラック回数に制限
i
-4
j
i
... j
t
1
2
3
4
5
6
7
8
9 10 11 12
解空間の縮小
Activity-on-node project network の利用

以下の条件を満たす解 (x, ℓ) のみ探索
1.
dist(i, j) < , dist( j, i) =   リスト ℓ において，i は j に先行
2.
同一強連結成分内の作業はリスト ℓ 中連続して出現
1
0
0
1
0
–1
–3
2
3
5
–5
4
6
4
–4
2
8
2
6
4
2
初期解
初期解 (x0, ℓ0)

初期処理モード割当て x0



実行可能性判定（すべての非再生可能資源制約を満たすことができるかどう
かの判定）がNP困難
制約充足問題に対するメタヒューリスティクス（TabuCSP）
初期リスト ℓ0

ランダムもしくは発見的手法
近傍

近傍 N(x, ℓ)

解 (x, ℓ) に対し, 以下のいずれかひとつの操作を適用することで得られる解
の集合
1. ChangeMode(i, m)
2. ShiftForward(i, j)
近傍

近傍 N(x, ℓ)

解 (x, ℓ) に対し, 以下のいずれかひとつの操作を適用することで得られる解
の集合
1. ChangeMode(i, m)



作業 i の処理モードを m∈ Mi に変更
その結果，x が非再生可能資源制約に違反するようであれば， x を初期解と
して TabuCSP を実行
TabuCSP は，ある定められた反復回数で打ち切り
2. ShiftForward(i, j)
近傍

近傍 N(x, ℓ)

解 (x, ℓ) に対し, 以下のいずれかひとつの操作を適用することで得られる解の集合
1. ChangeMode(i, m)
2. ShiftForward(i, j)

作業 i が作業 j に先行し，かつ以下の 2条件を満たすようリスト ℓ を修正
1. dist(i, j) < , dist( j, i) =   リスト ℓ において，i は j に先行
2. 同一強連結成分内の作業はリスト ℓ 中連続して出現
近傍

近傍 N(x, ℓ)

解 (x, ℓ) に対し, 以下のいずれかひとつの操作を適用することで得られる解の集合
1. ChangeMode(i, m)
2. ShiftForward(i, j)

クリティカルパスによる近傍の縮小
計算実験
ベンチマーク問題： MRCPSP

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
30 秒
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

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
30 秒
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上で実行

Download Report