ロジスティクス工学 第9章 スケジューリングモデル 補助資料：OptSeqによるスケジューリング入門 logopt

Presentation on theme: "ロジスティクス工学 第9章 スケジューリングモデル 補助資料：OptSeqによるスケジューリング入門 logopt"— Presentation transcript:

1 ロジスティクス工学 第9章 スケジューリングモデル 補助資料：OptSeqによるスケジューリング入門 http://www. logopt
ロジスティクス工学 第9章 スケジューリングモデル 補助資料：OptSeqによるスケジューリング入門 からpdfファイルをダウンロード可能 補助資料２：組合せ最適化短編集（朝倉書店） 東京商船大学 久保 幹雄

2 スケジューリングとは オペレーション，作業（operation），ジョブ，仕事(job)，タスク(task)，活動（activity）：遂行すべき仕事のこと．作業時間や納期の情報が付加される． 先行制約：ある作業（ジョブ，活動）がある作業（ジョブ，活動）の前に処理されなければならないことを表す制約． 資源（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} ２５ ４７
作業４の後続点の更新；最早終了時刻 56 分後！ 最早終了時刻＋後続する点の作業時間＝後続する点の最早終了時刻の枝 （->クリティカルパス：図の赤線）

8 最適解 解法：閉路をもたないグラフ上での最長路問題（組合せ最適化と アルゴリズム（共立出版）3.1.5節参照）->簡単に解ける！
横軸に時間をとって作業を並べた図->ガント図式（Gantt’s chart）

9 並列ショップスケジューリング ピットイン時間を短縮せよ！ (OptSeq 5節）
３人のピットクルー （資源制約） 資源（機械）制約 があると難しい！

10 有効スケジュール生成スキーム（１） 作業１ 作業３ 作業４ 作業２ 作業１ 作業の優先ルール によって解が異なる のでスキームとよぶ！
適合作業（ジョブ） 作業２ 作業１ クルー1 作業の優先ルール によって解が異なる のでスキームとよぶ！ クルー2 クルー3 適合作業から１つの作業を選択（たとえば作業時間の長いもの） ->ピットクルー1に割り付け（作業１の開始時刻を0に設定）

11 有効スケジュール生成スキーム（２） 作業９ 適合作業 作業２ 作業３ 作業４ 作業１ 作業９ 作業２ 作業４ 作業３
作業１がスケジュール されたので適合作業 に入る 適合作業 作業２ 作業３ 作業４ 作業１ 作業９ クルー1 クルー2 作業２ 作業４ 作業３ クルー3 同様に適合作業から作業を選択し，開始可能な最早時刻に 割り付け（作業2,3の開始時刻を0に，作業4の開始時刻を2に， 作業９の開始時刻を3に設定）

12 有効スケジュール生成スキーム（３） 作業４がスケジュールされたので適合作業に追加 適合作業 作業５ 作業６ 作業７ 作業８ 作業１ 作業９
クルー1 クルー2 作業２ 作業４ 作業５ 作業７ 作業６ 作業８ 作業３ クルー3 適合作業から作業を選択し，開始可能な最早時刻に割り付け

13 有効スケジュール生成スキーム（４） 作業5,6,7,8がスケジュールされたので適合作業に追加 適合作業 作業10 作業１ 作業９ 作業２
クルー1 クルー2 作業２ 作業４ 作業５ 作業７ 作業10 作業６ 作業８ 作業３ クルー3 残った作業10を開始可能な最早時刻に割り付け （完了時刻＝14のスケジュールの完成！）

14 有効スケジュール生成スキームの性質 作業の選択順（優先ルール）によって色々なスケジュールが得られる．
有効スケジュール（active schedule：他の作業の開始時刻を遅らせることなしに，いかなる作業の開始時刻を早めることができないスケジュール）を生成する． 作業を早く開始する方が良いスケジューリング問題に対しては，最適解は必ず有効スケジュールになる．

15 遅れなしスケジュール生成スキーム（１） 作業１ 作業２ 作業３ 作業４ 作業１ 作業２ 作業３
時刻0における 適合作業（ジョブ） 作業１ 作業２ 作業３ 作業４ 作業１ クルー1 作業２ クルー2 クルー3 作業３ 現在時刻（０）における適合作業から作業を選択して，開始時刻 を 0 に設定（作業4は資源がないので適合作業から除かれる．） 作業１，２，３が活動作業（ピンク色）

16 遅れなしスケジュール生成スキーム（２） 作業４ 作業１ 作業２ 作業４ 作業３ 時刻 2 における 適合作業（ジョブ） クルー1 クルー2
クルー3 作業３ 作業完了時刻の最早のもの（作業2,3）の完了時刻を現在時刻（2）とする． 活動作業から作業2,3を除く． 時刻 2 における適合作業から作業４を選択．開始時刻を2に設定．

17 遅れなしスケジュール生成スキーム（３） 作業９ 作業１ 作業９ 作業２ 作業４ 作業３
時刻 3 における 適合作業（ジョブ） 作業９ 作業１ 作業９ クルー1 作業２ 作業４ クルー2 クルー3 作業３ 現在時刻を 3 に進め，時刻 3 における適合作業（作業9）を選択． 作業9の開始時刻を3に設定．

18 遅れなしスケジュール生成スキーム（４） 作業５ 作業６ 作業７ 作業８ 作業１ 作業９ 作業２ 作業４ 作業５ 作業３ 作業６
時刻 4 における 適合作業（ジョブ） 作業７ 作業８ 作業１ 作業９ クルー1 作業２ 作業４ 作業５ クルー2 クルー3 作業３ 作業６ 現在時刻を 4 に進め，時刻 4 における適合作業（作業5,6,7,8）から 適当な優先ルールにしたがって作業を選択． 作業5,6の開始時刻を4に設定．

19 遅れなしスケジュール生成スキーム（５） 作業７ 作業８ 作業１ 作業９ 作業２ 作業４ 作業５ 作業７ 作業３ 作業６ 作業８
時刻 8 における 適合作業（ジョブ） 作業７ 作業８ 作業１ 作業９ クルー1 作業２ 作業４ 作業５ 作業７ クルー2 クルー3 作業３ 作業６ 作業８ 現在時刻を 8 に進め，時刻 8 における適合作業（作業7,8）から 適当な優先ルールにしたがって作業を選択． 作業7,8の開始時刻を 8 に設定．

20 遅れなしスケジュール生成スキーム（６） 作業10 作業１ 作業９ 作業２ 作業４ 作業５ 作業７ 作業10 作業３ 作業６ 作業８
時刻 12 における 適合作業（ジョブ） 作業10 作業１ 作業９ クルー1 作業２ 作業４ 作業５ 作業７ 作業10 クルー2 クルー3 作業３ 作業６ 作業８ 現在時刻を 12 に進め，時刻 12 における適合作業（作業10）選択． 作業 10 の開始時刻を 12 に設定． 完了時刻 14 のスケジュールの完成！

21 遅れなしスケジュール生成スキームの性質 作業の選択順（優先ルール）によって色々なスケジュールが得られる．
遅れなしスケジュール（nondelay schedule：作業の途中中断を許したとしても，他の作業の完了時刻を遅らせることなしに，いかなる作業の開始時刻を早めることができないスケジュール）を生成する． 作業を早く開始する方が良いスケジューリング問題に対しても最適解を含むとは限らない． 遅れなしスケジュールの集合は，有効スケジュールの集合に含まれる．

22 練習問題 9-1 以下ように条件を変えたとき，有効スケジュール生成スキームと遅れなしスケジュール生成スキームで生成せよ．（ただし，作業の番号が小さいもの先に割り付ける優先ルールを用いるものとする．） ピットクルー（作業員）を4人に増やした場合 作業時間をすべて１秒減らした場合 先行制約をすべて外した場合

23 優先ルール（priority rule,dispatching rule）
適合作業（ジョブ）から作業を選択するためのルール SPT（shortest processing time）ルール：作業時間の短い順 EDD（earliest due date）ルール：納期の早い順 先行制約における後続する作業数の多い順 ．．．．問題に依存してたくさんある！

24 資源制約付きスケジュールング お家を早く造ろう！（OptSeq 7節）
作業時間＝２日 １日目１人，２日目２人の資源 が必要！ １人の作業員休暇 ２人

25 最適解 資源制約付きスケジューリングは一般的なモデル （ジョブショップ，並列ショップスケジューリングを特殊形として含む．）

26 １機械スケジュールング 納期遅れを最小にしよう！（OptSeq 8節）
完了時刻最小化（メイクスパン）以外の目的関数の例 納期遅れ最小化 納期ずれ最小化 納期遅れした作業（ジョブ）数最小化 納期遅れの最大値の最小化 上の指標の重み付きの尺度最小化 ．．．． 会社名 A社 B社 C社 D社 作業時間 1日 2日 3日 4日 納期 5日後 9日後 6日後 4日後

27 最適解

28 フローショップスケジューリング 車メーカーの生産ライン（OptSeq 12節）
ジョブ（一連の作業） セダン 作業時間 スポーツカー バン 組み立て 塗装 タイヤ取り付け 機械（工程） フローショップ->すべてのジョブの機械順が同じ

29 最適解のGantt図式 機械別に表示（ジョブ別に表示する方法もある）

30 ジョブショップスケジューリンング ジョブごとに機械（工程）順が異なっても良い！ ジョブ 作業 機械 ８分 ５分 ３分 ７分 ２分 ６分 ５分
４分

31 離接グラフ表現 有向枝 離接枝 終了 開始 離接（disjunctive）＝「または（or）」の意味

32 離接グラフ上での解の表現 離接枝に(閉路ができないように）向きをつける． ＝各機械上での作業の順番の決定． 5 5 3 8 7 2 6 3
9 5 離接枝に(閉路ができないように）向きをつける． ＝各機械上での作業の順番の決定．

33 クリティカルパス（最長路） 5 5 3 8 7 2 6 3 9 5 離接枝を決定->クリティカルパスを求める！＝１つの近似解