i, j - LOG OPT HOME

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
本研究の位置付け(1)
理論 ―――― 応用 ―――― 実用
Theory
Application
Practice
・モデルの作成
‐ 避けては通れない(避けてはならない)
‐ 現状把握,問題整理・認識,目標設定
‐ 抽象化と具体化(限定化)のバランス
・最適化 ≒ 制約充足・実現可能を目指す
COM・APS(先進的スケジューリング)研究部会 2001/12/21
本研究の位置付け(2)
生産計画 ――――― スケジューリング
planning
scheduling
・部品表・工程表は既知
・「どの製品を,どれだけ,いつまでに生産するか」
を入力として (← 需要予測,受注,在庫,…),
・「各製品を,いつ生産するか」を決定
(→ 資材調達,生産スケジュール)
・有限負荷,現場レベルでの制約を考慮
COM・APS(先進的スケジューリング)研究部会 2001/12/21
本研究の位置付け(3)
秒・分 ― 時 ―― 日 ―― 週 ――― 月 ――― 年
最小単位時間
計画期間
・問題規模: 数百個 ~ 数千個の作業(工程)
・計算時間: 数十秒 ~ 十数分 (~ 数十分)
・シミュレーションを行うだけではない
COM・APS(先進的スケジューリング)研究部会 2001/12/21
RCPSPモデル
~ 生産スケジューリングを例として~
COM・APS(先進的スケジューリング)研究部会 2001/12/21
資源制約スケジューリング: RCPSP
Resource Constrained Project Scheduling Problem
希少資源を必要とする作業に対し,資源配分,
および各作業の処理時刻を決定する問題
モデル・・・ 抽象的,汎用的
資源: 機械,設備,装置,工具,人的資源,予算,…
作業: 資源を消費する活動; 仕事,工程,タスク,…
作業によって消費または生産される
原材料,部品,製品などは陽に扱われない
COM・APS(先進的スケジューリング)研究部会 2001/12/21
例:生産計画(1)
製品A
作業4
部品
B
10h/装置c,
作業員3人
作業1
材料D
処理時間/資源
2h/装置a,
作業員2人
部品
C
作業3
2h/装置b,
作業員3人
作業2
2h/装置c,
作業員2人
材料E
COM・APS(先進的スケジューリング)研究部会 2001/12/21
先行制約
・作業 i が完了するまで作業 j を開始できない
・非巡回有向グラフで表現
(activity-on-node diagram, precedence diagram)
材料D
製品A
部品B
作業1
材料の
調達
作業4
作業2
材料E
作業3
部品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: 直前先行制約(1)
・作業 i は作業 j に先行
・再生型資源 r 上で定義
i,j ともに r を消費  作業 i 完了後,次に r を
消費する作業は j
作業 i
作業 j
×
×
○
○
COM・APS(先進的スケジューリング)研究部会 2001/12/21
RCPSP: 直前先行制約(2)
・段取り替え作業
- 本作業の直前に実行
- 従属処理モード制約と組合せ
・時間制約
- 同時開始
- オーバーラップ
- 最大遅延時間
作業 i
作業 i
オーバーラップ
ダミー
作業 j
作業 i
ダミー
作業 j
作業 j
ダミー
オーバーラップ
COM・APS(先進的スケジューリング)研究部会 2001/12/21
RCPSP: 直前先行制約(3)
・その他
- 作業 i, j 間に作業 k は処理不可,
- …
i
ダミー
処理時間0
×k
ダミー
j
・ダミー,i 間およびダミー,j 間は先行制約
・ダミー,ダミー間は仮想資源 r 上の直前先行制約
・作業 k も仮想資源 r を消費
COM・APS(先進的スケジューリング)研究部会 2001/12/21
RCPSP: 直前先行制約(4)
・処理モードとの組合せ
- 直前先行制約:再生型資源 r 上で定義
- 先行,後続作業ともに r を消費するとき有効
→ r を消費するか否かは処理モードにより定まる
→ 直前先行制約は処理モードに依存
e.g.,
- 作業 i は j, k, … のいずれかと同時に開始
- ロットまとめしたとき,それらは同時開始
- …
COM・APS(先進的スケジューリング)研究部会 2001/12/21
例:生産計画(2)
製品A
作業4
部品
B
10h/装置c,
作業員3人
作業1
材料D
処理時間/資源
2h/装置a,
作業員2人
部品
C
作業3
2h/装置b,
作業員3人
作業2
2h/装置c,
作業員2人
材料E
COM・APS(先進的スケジューリング)研究部会 2001/12/21
例:生産計画(2)
製品A
ロットサイズ 1
作業4
部品
B
1
作業1
5
材料D
4
部品
B
2
2h
装置a
作業員2人
部品
C
部品
C
1
作業3
2.5h
装置c ×4
作業員3人
作業時間
一定
作業2
4
材料E
2h ×2
装置b
作業員3
人
1h
×2
装置c
作業員2
人
COM・APS(先進的スケジューリング)研究部会 2001/12/21
例:生産計画(2)
作業1-1
作業1-2
作業1-3
作業4
作業1-4
作業2-1
作業3-1
作業2-2
作業3-2
別ロットモード
処理時間:2h
装置b
同一ロットモード
処理時間:2h
作業3-1と同時開始
COM・APS(先進的スケジューリング)研究部会 2001/12/21
例:生産計画(3)
・在庫: 基本的に先行制約で処理
・先行制約で処理できないケース:
製品A1
ロットサイズ 10
製品A2
10
部品B
30
作業A1
作業A2
作業B
20
部品
B
40
部品
B
1
・製品A1,A2 をそれぞれ50個生産
原料
C
COM・APS(先進的スケジューリング)研究部会 2001/12/21
例:生産計画(3)
製品A1
ロットサイズ 10
製品A2
10
部品B
30
作業A1
作業A2
作業B
20
部品
B
40
部品
B
1
原料
C
・作業A1,A2 をそれぞれ5回処理
→ 部品B: 全体で 300 必要
→ 作業B: 10回処理
COM・APS(先進的スケジューリング)研究部会 2001/12/21
例:生産計画(3)
作業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: 蓄積型資源
・原材料,部品,製品などを表現
・作業により消費または生産される
・在庫量  0
在
庫
量
時間
COM・APS(先進的スケジューリング)研究部会 2001/12/21
例:生産計画(3)
・蓄積型資源:
- 負の資源消費量を許す再生型資源
- 各作業は,処理開始または完了後も
資源を消費し続ける
資
源
量
時間
負の消費量
COM・APS(先進的スケジューリング)研究部会 2001/12/21
RCPSP: 評価基準
・状況に応じて変化 → 柔軟な枠組みが必要
・「最適化」よりはむしろ「制約充足」
・制約違反度(ペナルティ)を最小化
- 再生型資源制約,先行制約,
直前先行制約は必ず満たすよう指定可能
・ユーザ定義制約
処理モード,開始時刻,完了時刻に関する
線形不等式制約
e.g., 最大完了時刻最小化,
総納期遅れ和最小化,
非再生型資源制約,…
COM・APS(先進的スケジューリング)研究部会 2001/12/21
最適化の手法
COM・APS(先進的スケジューリング)研究部会 2001/12/21
代表的な解法
・シミュレーション
山積み山崩し,優先規則法,
フォワード,バックワードスケジューリング,…
・人工知能
制約伝播,遺伝アルゴリズム,…
・数理計画・OR
分枝限定法,整数計画法,
ラグランジュ緩和,…
・メタヒューリスティクス
・…
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年12月現在の最良解を最初に発見
COM・APS(先進的スケジューリング)研究部会 2001/12/21
ベンチマーク: ProGen/Max
・http://www.wior.uni-karlsruhe.de/RCPSPmax/progenmax
・最小・最大遅延時間,最大完了時刻最小化
・作業数 100,再生型資源数 5
・実験結果
#最良解を更新
#最良解を発見
下界値からの平均
56問/1059問
704問/1059問
4.44 %
計算時間: 600秒(PentiumIII 1GHz)/問
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 ρ 1 の定数)
-部品 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/)
- RCPSPへの帰着: ‘‘art’’
モデル化の指針
・高速化・大規模問題対応
- 性能,汎用性とのトレードオフ
- データ構造
COM・APS(先進的スケジューリング)研究部会 2001/12/21
今後の展開
・モデルの拡張
- 非正規評価基準 ← 凸型コスト関数
- ロットサイズの決定
切替・段取り費用と在庫費用のトレードオフ
→ 問題を複雑・大規模化
問題範囲をどこまで拡大すべきか?