Download presentation
Presentation is loading. Please wait.
1
スケジューリング最適化システム OptSeq II 補助資料：OptSeq II によるスケジューリング入門 トライアルバージョン
2
スケジューリングモデルとは（OptSeq ２節）
作業（activity；活動）：遂行すべき仕事のこと．別名，オペレーション（operation），ジョブ，仕事(job)，タスク(task)．作業時間や納期の情報が付加される． 先行（時間）制約（precedence (time) constraint）：ある作業（ジョブ，活動）がある作業（ジョブ，活動）の前に処理されなければならないことを表す制約． 資源（resource）：作業を行うときに必要とされるもので，その量に限りがあるもの．機械(machine）はジョブによって占有される資源．その他，人員，材料，お金なども全部資源．
3
航空機を早く離陸させよう！(OptSeq 3節）
PERT: Program Evaluation and Review Technique,第二次世界大戦のポラリス潜水艦の建造で利用．（ORの古典） 完了時刻最小化 先行制約 作業 作業１：乗客降ろし（１３分） 作業２：荷物降ろし（２５分） 作業３：機内清掃（１５分） 作業４：乗客搭乗（２７分） 作業５：荷物積み込み（２２分） 点が作業（活動）のグラフ->点上活動図式
4
航空機を早く離陸させよう！（１） ０＋１３＝１３ ０分 ０＋２５＝２５ ダミー作業 （作業開始）
ダミーの開始作業を追加．最早終了時刻を０とする． ダミーの開始作業の後続する点の作業終了時刻を更新． その後，ダミーの開始作業をグラフから除く．
5
航空機を早く離陸させよう！（２） １３ ２８＝１３＋１５ ５２＝２５＋２７ ２５ ４７＝２５＋２２
先行する点がない点から順に，後続する点の最早終了時刻を更新． （大きいものに置き換える！）：作業１，作業２の後続点を更新．
6
航空機を早く離陸させよう！（３） 55=max{28+27，52} １３ ２８ 47=47+0 ２５ ４７
先行する点がない点から順に，後続する点の最早終了時刻を更新． （大きいものに置き換える！）：作業３，作業５の後続点の更新
7
航空機を早く離陸させよう！（４） ５５ １３ ２８ 55=max{55+0,47} ２５ ４７
作業４の後続点の更新；最早終了時刻 55 分後！ 最早終了時刻＋後続する点の作業時間＝後続する点の最早終了時刻の枝 （->クリティカルパス：図の赤線）
8
最適解 解法：閉路をもたないグラフ上での最長路問題->簡単に解ける！
横軸に時間をとって作業を並べた図->ガントチャート（Gantt’s chart）
9
OptSeqによるモデル記述（１） 作業の記述法
納期も追加可能（省略可） activity 作業名 duedate 納期 mode duration 作業時間 作業の記述法 作業は複数のモード（mode）をもつことも できる（後述）；1つのときは作業内に記述可 たとえば，作業時間13分のact1という名前の作業を 追加するには： activity act1 mode duration 13
10
OptSeqによるモデル記述（2） 時間制約の記述法
temporal 先行作業 後続作業 たとえば，作業act1の後に，作業act2を行わなければ ならないことを追加するには： temporal act1 act2
11
OptSeqによるモデル記述（3） 目的関数の記述法
最後の作業が完了する時刻を最小化 すべての作業に後続するダミーの作業 sink の 納期を最小化する！ activity 作業名 duedate 納期 mode duration 作業時間 作業の記述法 activity sink duedate 0
12
OptSeqの実行と結果 optseq -time 1 < 入力ファイル名 制限時間1秒で求解 計算結果（一部）
--- best solution 最良解 source ---: 0 0 ダミーの始点の開始時刻が０ sink ---: ダミーの終点の開始時刻が５５（完了時刻） activity[1] ---: 作業１は０に開始されて１３に終了 activity[2] ---: 作業２は０に開始されて２５に終了 activity[3] ---: 作業３は１３に開始されて２８に終了 activity[4] ---: 作業４は２８に開始されて５５に終了 activity[5] ---: 作業５は２５に開始されて４７に終了 objective value = 55 目的関数値は５５ cpu time = 0.00/3.00(s) 計算時間 iteration = 1/ 反復回数
13
PERT（作業員が1人のとき） 資源制約を使ってみよう！ (OptSeq 4節）
resource 資源名 interval 時刻1 時刻2 capacity 供給量 ... 資源の記述法
14
OptSeqによるモデル記述 worker（作業員） 資源を0から無限大（inf） まで1人使用可能
resource worker interval 0 inf capacity 1 activity 作業名 資源名 interval 区間 requirement 使用量 interval 区間 requirement 使量量 ... 作業が資源を 使用する量の 記述法 作業actが 資源workerを 1単位使用 activity act1 mode duration 13 worker interval 0 13 requirement 1
15
OptSeqの実行結果とガントチャート 計算結果（一部） source ---: 0 0 sink ---: 102 102
activity[1] ---: activity[2] ---: activity[3] ---: activity[4] ---: activity[5] ---: objective value = 102 cpu time = 0.00/3.00(s) iteration = 0/64983
16
並列ショップスケジューリング ピットイン時間を短縮せよ！ (OptSeq 5節）
３人のピットクルー （資源制約） 資源（機械）制約 があると難しい！
17
OptSeqによるモデル記述 （供給量3の資源を用いる場合）
3人の作業員 資源の定義 resource worker interval 0 inf capacity 3 activity prepare mode duration 3 worker interval 0 3 requirement 1 ．．． 作業の定義 temporal prepare oil temporal jackup tire1 ．．． 時間制約の 定義 最大完了時刻 の最小化 activity sink duedate 0
18
OptSeqによる計算結果 とガントチャート
source ---: 0 0 sink ---: 14 14 prepare ---: water ---: front ---: jackup ---: tire1 ---: tire2 ---: tire3 ---: tire4 ---: oil ---: jackdown ---: objective value = 14 cpu time = 0.00/3.00(s) iteration = 0/37644
19
並列ショップスケジューリング 2 -モードの概念と使用法-（OptSeq 6節）
モード：作業を行うための処理方法 例： 作業 「ジュースを買う」 コンビニモード： 作業時間 20 分，お金資源 120 円，人資源 1人 自販機モード： 作業時間 5 分，お金資源 120 円，人資源 1人 スーパーモード： 作業時間 40 分，お金資源 100 円，人資源 1人，車資源 1 台
20
モードの記述法 (1) モードの記述法 mode 処理モード名 duration 処理時間
資源名 interval 区間 requirement 使用量 interval 区間 requirement 使用量 ... 作業にモード を追加 activity 作業名 モード名 モード名
21
モードの記述法 (2) たとえば，作業時間が1,2,3の3つのモードを追加するには： mode m1 duration 3
worker interval 0 3 requirement 1 mode m2 duration 2 worker interval 0 2 requirement 2 mode m3 duration 1 worker interval 0 1 requirement 3 activity prepare m1 m2 m3 ３つのモードを作業 prepareに追加
22
OptSeqによる計算結果 とガントチャート
--- best solution --- source ---: 0 0 sink ---: 13 13 prepare m3: water ---: front ---: jackup ---: tire1 ---: tire2 ---: tire3 ---: tire4 ---: oil ---: jackdown ---: objective value = 13 cpu time = 0.00/3.00(s) iteration = 7/23318
23
資源制約付きスケジュールング お家を早く造ろう！（OptSeq 7節）
作業時間＝２日 １日目１人，２日目２人の資源 が必要！ １人の作業員休暇 ２人
24
最適解 資源制約付きスケジューリングは一般的なモデル （ジョブショップ，並列ショップスケジューリングを特殊形として含む．）
25
OptSeqによるモデル記述 (1) resource worker interval 0 2 capacity 2
interval 3 inf capacity 2 時刻によって変化する 資源供給量の入力 １ ０ ２ ３
26
OptSeqによるモデル記述(2) activity first mode duration 3 作業の時刻によって
worker interval 0 1 requirement 2 worker interval 1 3 requirement 1 作業の時刻によって 変化する資源使用量 の入力
27
１機械スケジュールング 納期遅れを最小にしよう！（OptSeq 8節）
完了時刻最小化（メイクスパン）以外の目的関数の例 納期遅れ最小化 納期ずれ最小化 納期遅れした作業（ジョブ）数最小化 納期遅れの最大値の最小化 上の指標の重み付きの尺度最小化 ．．．． 会社名 A社 B社 C社 D社 作業時間 1日 2日 3日 4日 納期 5日後 9日後 6日後 4日後
28
OptSeqによるモデルの記述 activity A duedate 5 mode duration 1
writer interval 0 1 requirement 1 activity B duedate 9 mode duration 2 writer interval 0 2 requirement 1 ．．． 作業後との 納期の記述
29
最適解 会社名 A社 B社 C社 D社 作業時間 1日 2日 3日 4日 納期 5日後 9日後 6日後 4日後
--- best solution --- source ---: 0 0 sink ---: 10 10 A ---: B ---: C ---: D ---: objective value = 3 cpu time = 0.00/3.00(s) iteration = 0/57376 会社名 A社 B社 C社 D社 作業時間 1日 2日 3日 4日 納期 5日後 9日後 6日後 4日後
30
航空機をもっと早く離陸させよう!（OptSeq 9節）
クリティカルパス法 （critical path method，略してCPM） 作業時間を費用をかけることによって短縮できる 作業1：乗客降ろし 13分．10分に短縮可能で，1 万円必要． 作業2：荷物降ろし 25分．20 分に短縮可能で，1万円必要． 作業3：機内清掃 15 分．10分に短縮可能で， 1万円必要． 作業4：新しい乗客の搭乗 27 分．25分に短縮可能で，1万円必要． 作業5： 新しい荷物積み込み 22 分．20分に短縮可能で， 1万円必要．
31
再生可能資源と再生不能資源 再生可能資源 作業完了後に再び使用可能になる資源 機械や作業員など
再生不能資源 一度使うとなくなってしまう資源（計画期間内での合計に制約を設ける） お金や原材料など クリティカルパス法の予算を再生不能資源として扱う！
32
OptSeqによるモデルの記述(1) 作業 1 （乗客降ろし）に対して，13分の通常モードと，10分の短縮モードを追加するための入力
mode m[1][1] duration 13 mode m[1][2] duration 10 activity activity[1] m[1][1] m[1][2]
33
OptSeqによるモデルの記述(2) nonrenewable 消費量 (作業名,処理モード名) 再生不能資源 ... <= 供給量
... <= 供給量 再生不能資源 の記述 再生不能資源は4万ドル以下： nonrenewable +1 (activity[1],m[1][2]) +1 (activity[2],m[2][2]) +1 (activity[3],m[3][2]) +1 (activity[4],m[4][2]) +1 (activity[5],m[5][2]) <= 4
34
結果
35
時間制約（OptSeq 10節） 時間制約（先行制約の一般化）の記述法
temporal 先行作業 後続作業 type 制約タイプ delay 時間ずれ Completion Start A B 後続作業 先行作業 作業Aの完了後に 作業Bの開始 temporal A B type CS delay 0
36
制約タイプ（type） type SS type SC type CC Start Start A B Start Completion A
37
時間ずれ（delay） delay 10 delay -10 Completion Start A B 10 作業Bの開始可能時間帯
38
時間制約の応用 1（同時開始） temporal A B type SS delay 0 AとBの同時開始
temporal B A type SS delay 0 AとBの同時開始 Aの開始+0 ≦ Bの開始 Aの開始=Ｂの開始 Bの開始+0 ≦ Aの開始
39
時間制約の応用 2（開始時間固定） Aの開始を50に temporal source A type SS delay 50 固定
temporal A source type SS delay -50 ダミーの始点（source）の開始+50 ≦ Aの開始 Aの開始-50 ≦ダミーの始点（source）の開始 sourceの開始時刻は0 Aの開始=50
40
時間制約の応用 3 （最大・最小段取り時間） Aの完了後最小 10分最大30分で temporal A B type CS delay 10
temporal B A type SC delay -30 Aの終了+10 ≦ Bの開始 Bの開始-30 ≦Aの終了 Bの開始≦ Aの終了+30 Bの開始はAの終了+[10,30]
41
作業の途中中断（OptSeq 11節） 作業（モード）の break interval 区間 max 最大中断時間 途中中断の
記述法 break interval 区間 max 最大中断時間 interval 区間 max 最大中断時間 ... 作業A（作業時間3）が，0から3の区間でそれぞれ最大1中断可能： activity A mode duration 3 break interval 0 3 max 1 開始から2時刻で中断した例
42
作業の並列処理（OptSeq 12節） 並列作業の記述法
parallel interval 開始小作業番号 終了小作業番号 max 最大並列数 interval 開始小作業番号 終了小作業番号 max 最大並列数 ... 1番目と2番目の小作業を2単位並列可能： activity A mode duration 4 parallel interval max 2 小作業1
43
並列処理の結果 1番目と2番目の小作業を2単位並列可能： activity A mode duration 4
parallel interval max 2
Similar presentations
