2017/3/10 スケジューリング最適化 東京海洋大学 久保　幹雄.

Presentation on theme: "2017/3/10 スケジューリング最適化 東京海洋大学 久保　幹雄."— Presentation transcript:

1 2017/3/10 スケジューリング最適化 東京海洋大学 久保　幹雄

2 意思決定レベルによる分類 生産 需要 原材料 配送拠点 輸送 配送 地点 ロジスティクス・ネットワーク最適化 長期 中期 短期
2017/3/10 意思決定レベルによる分類 原材料 調達物流 生産 工場内物流 輸送 配送拠点 配送 需要 地点 ロジスティクス・ネットワーク最適化 ストラテジック 長期　　中期　　短期 資源配分最適化 安全在庫配置 在庫方策最適化 生産計画最適化 ロットサイズ最適化 スケジューリング 最適化 配送計画最適化 配送計画 タクティカル オペレーショナル

3 スケジューリングとは 作業（活動，ジョブ，タスク）の時間軸上への配置 資源制約（機械，人，原材料などの使用可能量上限）
2017/3/10 スケジューリングとは 作業（活動，ジョブ，タスク）の時間軸上への配置 資源制約（機械，人，原材料などの使用可能量上限） 作業間の先行関係（ある作業が終了してからでないと，別の作業を開始できない）

4 2017/3/10 飛行機を早く離陸させよう！ あなたは航空機会社のコンサルタントだ．あなたの仕事は，着陸した航空機をなるべく早く離陸させるためのスケジュールをたてることだ．航空機は，再び離陸する前に幾つかの作業をこなさなければならない．まず，乗客と荷物を降ろし，次に機内の掃除をし，最後に新しい乗客を搭乗させ，新しい荷物を積み込む．さて，最短で何分で離陸できるだろうか?

5 資源制約なしのスケジューリング(PERT)
2017/3/10 資源制約なしのスケジューリング(PERT) PERT: Program Evaluation and Review Technique,第二次世界大戦のポラリス潜水艦の建造で利用 完了時刻最小化 先行制約 作業 作業１：乗客降ろし（１３分） 作業２：荷物降ろし（２５分） 作業３：機内清掃（１５分） 作業４：乗客搭乗（２７分） 作業５：荷物積み込み（２２分）

6 2017/3/10 最適化結果（ガントチャート） 資源制約つき（１人で作業）

7 2017/3/10 ピットイン時間を短縮せよ！ あなたはF1のピットクルーだ．F1レースにとってピットインの時間は貴重であり，ピットインしたレーシングカーに適切な作業を迅速に行い，なるべく早くレースに戻してやることが，あなたの使命である．いま，あなたを含めて3人のピットクルーがいて，作業を手分けして行うものとする．作業は途中で中断できないものとすると，なるべく早く最後の作業を完了させるには，誰がどの作業をどういう順番で行えばよいのだろうか?

8 ピットイン時間を短縮せよ！ 2017/3/10 ３人のピットクルー （資源制約）

9 スケジューリングモデルの解法 近視眼的ヒューリスティクス ディスパッチングルール（作業の重要度をパラメータとして入力；処理的IT） 制約論理
2017/3/10 スケジューリングモデルの解法 近視眼的ヒューリスティクス ディスパッチングルール（作業の重要度をパラメータとして入力；処理的IT） 遅れなしスケジュール生成法 有効スケジュール生成法 山崩し法 制約論理 メタ解法

10 遅れなしスケジュール生成法（１） 時刻0において 開始できる作業（適合作業） 作業１ 作業２ 作業３ 作業４ 作業１ 作業２ 作業３
2017/3/10 時刻0において 開始できる作業（適合作業） 作業１ 作業２ 作業３ 作業４ 作業１ クルー1 作業２ クルー2 クルー3 作業３ 現在時刻（０）における適合作業から作業を選択 各々の開始時刻を 0 に設定 作業１，２，３が活動中の作業（ピンク色の作業）

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

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

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

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

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

16 2017/3/10 作業を改善（？）方法 作業時間を１秒縮める ピットクルーを4人に増やす 先行制約をすべて外す

17 作業時間短縮による改善？ ->２秒 ->10秒 ->1秒 ->3秒 ->1秒 ->1秒 ->1秒
2017/3/10 ->２秒 ->10秒 ->1秒 ->3秒 ->1秒 ->1秒 ->1秒

18 作業時間をすべて１秒縮めた場合（１） 時刻0において 開始できる作業（適合作業） 作業１ 作業１ ２ ３
2017/3/10 時刻0において 開始できる作業（適合作業） 作業１ 作業２ 作業３ 作業４ 作業１ クルー1 ２ クルー2 クルー3 ３ 現在時刻（０）における適合作業から作業を選択 各々の開始時刻を 0 に設定 作業１，２，３が活動中の作業（ピンク色の作業）

19 作業時間をすべて１秒縮めた場合（２） 時刻 2 における 適合作業 作業４ 作業１ ２ ４ ３ クルー1 クルー2 クルー3
2017/3/10 作業時間をすべて１秒縮めた場合（２） 時刻 2 における 適合作業 作業４ 作業１ クルー1 ２ ４ クルー2 クルー3 ３ 作業完了時刻の最早のもの（作業2,3）の完了時刻を現在時刻（1）とする． 活動作業から作業2,3を除く． 時刻 2 における適合作業から作業４を選択．開始時刻を 1 に設定．

20 作業時間をすべて１秒縮めた場合（3） 作業９ 作業５ 作業６ 時刻 2 における 適合作業 作業７ 作業８ 作業１ 作業５ ２ ４ 作業６
2017/3/10 作業９ 作業５ 作業６ 時刻 2 における 適合作業 作業７ 作業８ 作業１ 作業５ クルー1 ２ ４ 作業６ クルー2 クルー3 ３ 作業７ 現在時刻を 2 に進め，時刻 2 における適合作業から，作業5,6,7 を順に選択．作業5,6,7の開始時刻を2に設定．

21 作業時間をすべて１秒縮めた場合（4） 時刻 6 における 適合作業 作業８ 作業９ 作業１ 作業５ 作業８ ２ ４ 作業６ 作業９ ３
2017/3/10 時刻 6 における 適合作業 作業８ 作業９ 作業１ 作業５ 作業８ クルー1 ２ ４ 作業６ 作業９ クルー2 クルー3 ３ 作業７ 現在時刻を 5 に進め，時刻 5 における適合作業から，作業8,9 を順に選択．作業8,9の開始時刻を 5 に設定．

22 作業時間をすべて１秒縮めた場合（5） 時刻 6 における 適合作業 作業10 作業１ 作業５ 作業８ 作業10 ２ ４ 作業６ 作業９ ３
2017/3/10 時刻 6 における 適合作業 作業10 作業１ 作業５ 作業８ 作業10 クルー1 ２ ４ 作業６ 作業９ クルー2 クルー3 ３ 作業７ 最後に，作業 10 を選択して完了！作業時間１をすべて１秒 縮めたにも関わらず，完了時刻は１５秒と１秒増加！

23 ピットクルーを増やすことによる改善？ 2017/3/10 4人のピットクルー （資源制約） ３人のピットクルー （資源制約）

24 ピットクルーを4人に増やした場合（１） 時刻0において 開始できる作業（適合作業） 作業１ 作業２ 作業３ 作業４ 作業１ 作業２ 作業３
2017/3/10 時刻0において 開始できる作業（適合作業） 作業１ 作業２ 作業３ 作業４ 作業１ クルー1 作業２ クルー2 作業３ クルー3 クルー4 作業４ 現在時刻（０）における適合作業から作業を選択 各々の開始時刻を 0 に設定 作業１，２，３，４が活動中の作業（ピンク色の作業）

25 ピットクルーを4人に増やした場合（2） 作業５ 作業６ 作業７ 作業８ 作業１ 作業２ 作業５ 作業３ 作業６ 作業４ 作業７
2017/3/10 作業５ 作業６ 作業７ 作業８ 作業１ クルー1 作業２ 作業５ クルー2 作業３ 作業６ クルー3 クルー4 作業４ 作業７ 現在時刻（2）における適合作業から作業 5,6,7 を選択 各々の開始時刻を 2 に設定

26 ピットクルーを4人に増やした場合（3） 作業９ 作業８ 作業１ 作業８ 作業２ 作業５ 作業３ 作業６ 作業４ 作業７
2017/3/10 作業９ 作業８ 作業１ 作業８ クルー1 作業２ 作業５ クルー2 作業３ 作業６ クルー3 クルー4 作業４ 作業７ 現在時刻（3）における適合作業から作業 8 を選択 作業8の開始時刻を 3 に設定

27 ピットクルーを4人に増やした場合（4） 作業９ 作業１ 作業８ 作業２ 作業５ 作業９ 作業３ 作業６ 作業４ 作業７
2017/3/10 作業９ 作業１ 作業８ クルー1 作業２ 作業５ 作業９ クルー2 作業３ 作業６ クルー3 クルー4 作業４ 作業７ 現在時刻（6）における適合作業から作業 9 を選択 作業9の開始時刻を 6 に設定

28 ピットクルーを4人に増やした場合（5） 作業10 作業１ 作業８ 作業10 作業２ 作業５ 作業９ 作業３ 作業６ 作業４ 作業７
2017/3/10 作業10 作業１ 作業８ 作業10 クルー1 作業２ 作業５ 作業９ クルー2 作業３ 作業６ クルー3 クルー4 作業４ 作業７ 最後に作業10を入れて完了． 1人増やしたにも関わらず，完了時刻は１７秒と２秒も増加！

29 先行制約を無視した場合 作業１ 作業６ 作業９ 作業２ 作業４ 作業７ 作業10 作業３ 作業５ 作業８
2017/3/10 作業１ 作業６ 作業９ クルー1 作業２ 作業４ 作業７ 作業10 クルー2 クルー3 作業３ 作業５ 作業８ 完了時刻 18 のスケジュールの完成！

30 改善活動が改悪になる！ 作業時間を１秒縮める ->完了時刻１５秒に増加！（もとは１４秒）
2017/3/10 改善活動が改悪になる！ 作業時間を１秒縮める ->完了時刻１５秒に増加！（もとは１４秒） ピットクルーを4人に増やす ->完了時刻17秒に増加！ 先行制約をすべて外す ->完了時刻18秒に増加！ 近視眼的ヒューリスティクスを用いているとしばしば改善のための工夫が改悪につながる！

31 スケジューリング最適化システム WebSeqのデータ項目
2017/3/10 スケジューリング最適化システム WebSeqのデータ項目 作業データ：作業の属性を保管するデータ 作業ID，作業名，作業時間，リリース時刻，納期，最終納期，納期遅れペナルティ，開始時刻 資源データ：資源の属性を保管するデータ 資源ID，資源名，上限 作業・資源データ：作業の資源への割り当てに関するデータ 作業ID，資源ID，使用量 作業対データ：作業間の先行関係に関するデータ 先行作業ID，後続作業ID，段取り時間下限，段取り時間上限，先行制約のタイプ

32 作業対（先行制約）データ 先行作業ID: 先行する作業番号 後続作業ID：後続する作業番号 段取り時間下限 段取り時間上限 先行制約のタイプ
2017/3/10 先行作業ID: 先行する作業番号 後続作業ID：後続する作業番号 段取り時間下限 段取り時間上限 先行制約のタイプ ＝１：終了 ->開始 ＝２：終了->終了 ＝３：開始->開始 ＝４：開始->終了 終了 開始 先行作業 後続作業 段取り時間下限 段取り時間上限

33 同時開始，同時終了 作業２，３の間に「開始-開始」の先行制約 ＋最小段取り＝０，最大段取り＝０
2017/3/10 同時開始，同時終了 作業２，３の間に「開始-開始」の先行制約 　　＋最小段取り＝０，最大段取り＝０ 作業４，５の間に「終了-終了」の先行制約 　　＋最小段取り＝０，最大段取り＝０

34 2017/3/10 納期遅れを最小にしよう！ あなたは売れっ子作家だ．あなたは，A, B, C, D の4社から原稿を依頼されており，それぞれ，どんなに急いで書いても 1日，2日，3日，4日かかるものと思われる．各社に約束した納期は，それぞれ 5日後，9日後，6日後，4日後であり，納期から 1日遅れるごとに 1万円の遅延ペナルティを払わなければならない．どのような順番で原稿を書けば，支払うペナルティ料の合計を最小にできるだろうか?

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

36 2017/3/10 最適化の結果

37 2017/3/10 ロットサイズ最適化

38 ロットサイズ最適化 （基本となるトレード・オフ関係）
2017/3/10 ロットサイズ最適化 （基本となるトレード・オフ関係） まとめて処理するのか？すぐに処理するのか？

39 2017/3/10 ロットサイズ最適化（在庫費用） 在庫費用=品目を次の期に持ち越すときにかかる費用 保管比率（投資額利率＋保険料率＋陳腐化率＋税率）に品目の価値を乗じることによって計算 ロットサイズ在庫（サイクル在庫），作り置き在庫も最適化する． （安全在庫，輸送中在庫などは他の最適化システムで考慮）

40 サプライ・チェイン最適化 における位置づけ
2017/3/10 サプライ・チェイン最適化 における位置づけ タクティカル（中期，戦術）レベル 段取り費用（時間）を加味した多期間生産計画・在庫計画モデル オペレーショナル（短期）レベル 在庫とロットまとめを組み込んだスケジューリングモデル

41 １品目の例題 期（日，週，月，時間）：１，２，３，４，５ （５日分） 生産 段取り 段取り費用： ３万円
2017/3/10 １品目の例題 期（日，週，月，時間）：１，２，３，４，５ （５日分） 生産 段取り 段取り費用： ３万円 需要量 ： 5,7,3,6,4 （日あたりの必要量；トン） 在庫費用 ： 1日あたり１万円 生産費用 ： 1,1,3,3,3万円（１トンあたり）

42 １品目の例題 一度に生産：段取り(3)+生産(25)+在庫(20+13+10+4)=75
2017/3/10 １品目の例題 一度に生産：段取り(3)+生産(25)+在庫( )=75 ＪＩＴ生産：段取り(15)+生産(51)+在庫(0)=66 最適生産：段取り(9)+生産(33)+在庫(15)=57

43 １品目の例題 （ヒューリスティクスとの比較）
2017/3/10 １品目の例題 （ヒューリスティクスとの比較） Silver-Mealヒューリスティクス 単位期間あたりの費用が最小になるようにロットまとめ 段取り(9)+生産(45)+在庫(7)=61 最小単位費用ヒューリスティクス(least-unit cost heuristics) 単位需要量あたりの費用が最小になるようにロットまとめ 段取り(9)+生産(51)+在庫(14)=74

44 複数品目の例題 段取りと在庫のトレード・オフの他に 資源（工程）の生産時間上限の複数の品目にどう配分するか？ も決める．
2017/3/10 複数品目の例題 段取りと在庫のトレード・オフの他に 資源（工程）の生産時間上限の複数の品目にどう配分するか？ も決める． 期：１０週分，５品目 資源（工程）の稼働時間上限= 1021ｈ/週（６期目は0h) 段取り費用　（品目１）： 5000 ，4050，1250 ，5000．．．． 需要量（品目１） ：92，97，107，107，104，．．．． 在庫費用=1 変動費用=1

45 2017/3/10 複数品目の例題 １期 ２期 ３期 ４期 ５期 品目 ６期 ７期 ８期 ９期 １０期 品目 WebLotで求解（2秒）

46 2017/3/10 多段階モデル 複数品目の親子関係 組み立て産業：部品展開表 BOM（Bill Of Materials） 　　MRPは段取りや資源容量を考慮していない 装置産業：製品レシピ（Product Recipes） 副生成物1 ハードディスク 製品1 本体 原料1 中間製品 製品2 PCキット 基盤 原料2 モニタ 副生成物2 BOMの例 レシピの例

47 多段階の例題 段取り費用 1万円，時間 10時間 在庫費用 1円 変動費用 10円，時間 0.12分 在庫費用 8円 在庫費用 2円
2017/3/10 段取り費用 1万円，時間 10時間 変動費用 10円，時間 0.12分 在庫費用 8円 在庫費用 1円 在庫費用 2円 段取り費用 1万円，時間 5時間 変動費用 円，時間 0.24分 在庫費用 9円 資源１ 生産工程（２４h/日稼働）

48 多段階の例題 段取り費用 6万円，時間 3時間 変動費用 2円，時間 1.8分 在庫費用 54円 段取り費用 5万円，時間 2時間
2017/3/10 段取り費用 6万円，時間 3時間 変動費用 2円，時間 1.8分 在庫費用 54円 段取り費用 5万円，時間 2時間 変動費用 円，時間 2.4分 在庫費用 円 資源２ 包装工程（２４h/日稼働）

49 2017/3/10 多段階の例題（需要量と結果） 　需要 　需要

50 ロットサイズ最適化システム WebLotのデータ項目
2017/3/10 ロットサイズ最適化システム WebLotのデータ項目 品目データ 品目ID，品目名称，段取り費用，段取り時間，変動費用， 在庫費用 資源データ 資源ID，資源名称，生産時間上限 品目・期データ 品目ID，期，需要量，段取り費用，段取り時間，変動費用，在庫費用，在庫量，生産量， 段取り回数 品目・資源データ 品目ID，資源ID，資源使用量 品目対データ 子品目ID，親品目ID，必要量

51 まとめ スケジューリングモデル オペレーショナルレベルの意思決定
2017/3/10 まとめ スケジューリングモデル オペレーショナルレベルの意思決定 PERT (Program Evaluation and Review Technique）の例 ガントチャート 近視眼的ヒューリスティクスの危険性 ロットサイズ決定モデル タクティカルレベルの意思決定