WebRM Introduction

スケジューリング最適化
東京海洋大学
久保 幹雄
1
スケジューリングとは
作業(活動,ジョブ,タスク)の時間軸上への
配置


資源制約(機械,人,原材料などの使用可能量上
限)
作業間の先行関係(ある作業が終了してからでな
いと,別の作業を開始できない)
2
飛行機を早く離陸させよう!
あなたは航空機会社のコンサルタントだ.
あなたの仕事は,着陸した航空機をなるべ
く早く離陸させるためのスケジュールをた
てることだ.航空機は,再び離陸する前に
幾つかの作業をこなさなければならない.
まず,乗客と荷物を降ろし,次に機内の掃
除をし,最後に新しい乗客を搭乗させ,新
しい荷物を積み込む.さて,最短で何分で
離陸できるだろうか?
3
資源制約なしのスケジューリング(PERT)
PERT: Program Evaluation and Review Technique,第
二次世界大戦のポラリス潜水艦の建造で利用
作業1
作業3
作業4
13分
15分
27分
完了時刻最小化
ダミー作業
先行制約
作業
作業2
25分
作業5
22分
作業1:乗客降ろし(13分)
作業2:荷物降ろし(25分)
作業3:機内清掃(15分)
作業4:乗客搭乗(27分)
作業5:荷物積み込み(22分)
4
最適化結果(ガントチャート)
作業1
作業3
作業4
15分
13分
27分
作業5
作業2
25分
22分
0
時間
55
資源制約つき(1人で作業)
15分
0
作業1
作業2
作業3
25分
作業4
13分
作業5
27分
22分
時間
102
5
ピットイン時間を短縮せよ!
あなたはF1のピットクルーだ.F1レースにとって
ピットインの時間は貴重であり,ピットインした
レーシングカーに適切な作業を迅速に行い,なる
べく早くレースに戻してやることが,あなたの使命
である.いま,あなたを含めて3人のピットクルー
がいて,作業を手分けして行うものとする.作業
は途中で中断できないものとすると,なるべく早く
最後の作業を完了させるには,誰がどの作業を
どういう順番で行えばよいのだろうか?
6
ピットイン時間を短縮せよ!
gas
3秒
作業1
作業9
11
秒
R
TE
WA
3人のピットクルー
(資源制約)
2
作業2
秒
作業5
2秒
4
作業6
作業3
作業7
作業8
作業4
2
秒
秒
4
秒
4秒
4
2
秒
作業10
秒
7
スケジューリングモデルの解法
近視眼的ヒューリスティクス
ディスパッチングルール(作業の重要度をパラ
メータとして入力;処理的IT)



遅れなしスケジュール生成法
有効スケジュール生成法
山崩し法
制約論理
メタ解法
8
遅れなしスケジュール生成法(1)
時刻0において
開始できる作業(適合作業)
0
クルー1
5
作業1
作業2 作業3 作業4
10
15
作業1
クルー2 作業2
クルー3 作業3
現在時刻(0)における適合作業から作業を選択
各々の開始時刻を 0 に設定
作業1,2,3が活動中の作業(ピンク色の作業)
9
遅れなしスケジュール生成法(2)
時刻 2 における
適合作業
作業4
0
クルー1
5
10
15
作業1
クルー2 作業2 作業4
クルー3 作業3
作業完了時刻の最早のもの(作業2,3)の完了時刻を現在時刻(2)とする.
活動作業から作業2,3を除く.
時刻 2 における適合作業から作業4を選択.開始時刻を2に設定.
10
遅れなしスケジュール生成法(3)
時刻 3 における
適合作業(ジョブ)
0
クルー1
作業9
5
作業1
10
15
作業9
クルー2 作業2 作業4
クルー3 作業3
現在時刻を 3 に進め,時刻 3 における適合作業(作業9)を選択.
作業9の開始時刻を3に設定.
11
遅れなしスケジュール生成法(4)
時刻 4 における
適合作業(ジョブ)
0
クルー1
作業5
作業6
作業7
作業8
5
作業1
10
15
作業9
クルー2 作業2 作業4
作業5
クルー3 作業3
作業6
現在時刻を 4 に進め,時刻 4 における適合作業(作業5,6,7,8)から
適当な優先ルールにしたがって作業を選択.
12
作業5,6の開始時刻を4に設定.
遅れなしスケジュール生成法(5)
時刻 8 における
適合作業(ジョブ)
0
クルー1
作業7
作業8
5
作業1
10
15
作業9
クルー2 作業2 作業4
作業5
作業7
クルー3 作業3
作業6
作業8
現在時刻を 8 に進め,時刻 8 における適合作業(作業7,8)から
適当な優先ルールにしたがって作業を選択.
作業7,8の開始時刻を 8 に設定.
13
遅れなしスケジュール生成法(6)
時刻 12 における
適合作業(ジョブ)
作業10
0
クルー1
5
作業1
10
15
作業9
クルー2 作業2 作業4
作業5
作業7
クルー3 作業3
作業6
作業8
作業10
現在時刻を 12 に進め,時刻 12 における適合作業(作業10)選択.
作業 10 の開始時刻を 12 に設定.
14
完了時刻 14 のスケジュールの完成!
遅れなしスケジュール生成法
(作業時間を1秒縮めた場合)
0
5
作業1
10
15
作業5
作業6
15秒に増加!
15
他の改善(?)法
ピットクルーを4人に増やす
-> 作業時間17秒に増加!
先行制約をすべて外す
->作業時間18秒に増加!
近視眼的ヒューリスティクスを用いていると
しばしば改善のための工夫が改悪につな
がる!
16
スケジューリング最適化システム
WebSeqのデータ項目
作業データ:作業の属性を保管するデータ
作業ID,作業名,作業時間,リリース時刻,納期,最終納期,
納期遅れペナルティ,開始時刻
資源データ:資源の属性を保管するデータ
資源ID,資源名,上限
作業・資源データ:作業の資源への割り当てに関す
るデータ
作業ID,資源ID,使用量
作業対データ:作業間の先行関係に関するデータ
先行作業ID,後続作業ID,段取り時間下限,段取り時間上限,
先行制約のタイプ
17
作業対(先行制約)データ
先行作業ID: 先行する作業番号
後続作業ID:後続する作業番号
段取り時間下限
段取り時間上限
終了
先行制約のタイプ




=1:終了 ->開始
=2:終了->終了
=3:開始->開始
=4:開始->終了
開始
先行作業
後続作業
段取り時間下限
段取り時間上限
18
同時開始,同時終了
作業2,3の間に「開始-開始」の先行制約
+最小段取り=0,最大段取り=0
作業4,5の間に「終了-終了」の先行制約
+最小段取り=0,最大段取り=0
19
納期遅れを最小にしよう!
あなたは売れっ子作家だ.あなたは,A, B, C,
D の4社から原稿を依頼されており,それぞれ,
どんなに急いで書いても 1日,2日,3日,4日か
かるものと思われる.各社に約束した納期は,そ
れぞれ 5日後,9日後,6日後,4日後であり,納
期から 1日遅れるごとに 1万円の遅延ペナル
ティを払わなければならない.どのような順番で
原稿を書けば,支払うペナルティ料の合計を最
小にできるだろうか?
20
納期遅れを最小にしよう!
完了時刻最小化(メイクスパン)以外の目的関数の例





納期遅れ最小化
納期ずれ最小化
納期遅れした作業(ジョブ)数最小化
納期遅れの最大値の最小化
上の指標の重み付きの尺度最小化 ....
A社
B社
C社
D社
作業時間 1日
2日
3日
4日
9日後
6日後
4日後
会社名
納期
5日後
21
最適化の結果
作業4(D社)
作業1(A社)
作業3(C社)
納期遅れ
作業2(B社)
納期遅れ
時間(日)
0
10
A社納期
C社納期
D社納期
B社納期
22