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