2018/8/8 ロットサイズ最適化 東京海洋大学 久保　幹雄.

Presentation on theme: "2018/8/8 ロットサイズ最適化 東京海洋大学 久保　幹雄."— Presentation transcript:

1 2018/8/8 ロットサイズ最適化 東京海洋大学 久保　幹雄

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

3 ロットサイズ最適化 短期タクティカルレベルの意思決定 在庫と段取り費用のトレードオフ（最適ロットサイズの決定）
生産・輸送における規模の経済性を考慮 段取り活動を行うタイミングと一度に生産（輸送）する量の決定 在庫と段取り費用のトレードオフ（最適ロットサイズの決定） 容量制約を考慮した生産資源への品目の割り当ての最適化 スケジューリング最適化と合わせることによるAPS (Advanced Planning and Scheduling）の求解 大 期の幅 小 （在庫を考慮した） スケジューリング最適化 多期間ロジスティクス ネットワーク設計 大バケット 小バケット

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

5 大バケット問題と小バケット問題 大バケット（１月を１単位） 段取り 生産 継続期間＝１月 小バケット（１日を１単位） 段取り 生産
段取り　生産 継続期間＝１月 小バケット（１日を１単位） 段取り　生産 継続期間＝数日

6 ロットサイズ最適化の例（工場内） まとめて生産する量を決定

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

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

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

10 単一品目基本モデル(1) パラメータ dt : 第 t 期の需要量 ft : 生産（発注）固定費用 ct : 生産変動費用
2018/8/8 単一品目基本モデル(1) パラメータ T : 計画期間の数 dt : 第 t 期の需要量 ft :　生産（発注）固定費用 ct : 生産変動費用 ht : 在庫保管費用 Mt: 生産容量 First I’ll talk about the basic single item model. Here is the notation. Capital T is the number of periods. We will use small t as an index for the periods. d_t is the demand during period t. f_t is the fixed production set-up cost. c_t is the production variable cost. h_t is the holding cost in period t. M_t is the capacity of production in period t. Notice that these parameters may be time-dependent.

11 単一品目基本モデル(2) 変数 xt : 第 t 期の生産（発注）量
2018/8/8 単一品目基本モデル(2)　変数 It : t 期末の在庫量（初期在庫は０と仮定） xt : 第 t　期の生産（発注）量 yt : 段取りの有無を表す0-1 変数 =1 （xt >0のとき；生産量が正）, =0 （それ以外のとき；生産しない） Next we define the variables. I_t is the amount of inventory at the end of the period. x_t is the production amount in period t. y_t is a binary variable that is equal to 1 is the production amount x_t is positive, and is equal to 0 otherwise. y_t is sometimes called the set up variable.

12 2018/8/8 単一品目基本モデル(3) 定式化 Using the notations introduced now, I can show you a mathematical programming (more precisely a mixed integer programming) formulation of the lot-sizing model. The objective function to be minimized is the sum of fixed set-up cost, variable production cost, and inventory holding cost. The first constraint is the flow conservation equation of the inventory. The second constraint connects the production variable, x, and the set-up variable, y, and simultaneously specifies that the production upper bound is capital M_t. The third constraint defines that the initial inventory is 0.

13 基本モデルの概念図 需要 dt xt ≦ “大きな数 M” × yt [段取り変数] It-1 + xt = dt + It It 生産
2018/8/8 基本モデルの概念図 生産 xt 在庫 It-1 It t This figure represents the “flow” flow of the basic formulation. The incoming flow to the node representing period t is the inventory from the previous period, I_t-1, and the production amount in period t, x_t. The outgoing flow from the node is the demand d_t and the inventory carried to the next period, I_t. X_t is restricted by M times y_t. When M is a large number, i.e., the uncapacitated case, this constraints gives a weak lower bound, so this formulation is called a weak formulation. 需要 dt 弱い定式化 xt ≦ “大きな数 M” × yt [段取り変数] It-1 + xt = dt + It 0-1変数

14 妥当不等式 妥当不等式: (S,l)不等式 2018/8/8
To tighten the weak formulation, we can add some additional inequalities called the valid inequalities. Define captal D_{t ell} as the sum of demands from period t to period ell. Let capital L be the index set 1,…,ell, and captal S be a subset of L. Then this inequality called the (S,ell) inequality becomes a valid inequality.

15 妥当不等式，カット（切除平面），側面 弱い定式化の式 (妥当不等式) 側面 緩和解 x* 解 x 整数多面体 カット （切除平面）
2018/8/8 弱い定式化の式 (妥当不等式) 側面 緩和解 x* 解 x 整数多面体 Here I’ll show you some basic terminologies of mathematical programming, especially polyhedral theory for the guys who are not so familiar in this field. These small circles are the solutions, more precisely the feasible integer solutions. The inequality that includes all the solutions in the half space defined by the inequality is called a valid inequality. The formulation consists of the valid inequalities. These green lines define a formulation but it’s weak. The intersection of this formulation and the inter lattice is the set of solutions. The formulation gives us a relaxed solution that is an optimal solution x* of the linear programming relaxation. This blue large circle is the relaxed solution of the weak formulation. The valid inequality that does not include x*, in other words, that cuts off x*, is called a cut. This blue line is an example of a cut. The tightest or strongest cut is called a facet. This red line is an example. The ideal formulation is the one consists of facets only. That is called the integer polyhedron or integer hull ‘cause it is a convex hull of integer solusions. This black region is the integer polyhedron. カット （切除平面）

16 容量制約なしの場合の強い定式化 生産容量 Mt が十分に大きいものと仮定
2018/8/8 容量制約なしの場合の強い定式化 生産容量 Mt が十分に大きいものと仮定 Xst : 期 t の需要を満たすために期 s で生産する需要の割合 ( ) Next we consider the extended formulation that uses an additional set of variable. I’ll show you this extended formulation gives the integer polyhedron for the uncapacitated lot-sizing model, i.e., the capacity M is a large number. A new variable, capital X_{st} denotes the ratio of the amount produced in period s to satisfy the demand in period t. Also define a parameter CH_{st} that is the cost incurred when we produce in period s to satisfy the demand in period t; that includes the variable production and inventory holding costs from s to t. 期 t の需要を１単位満たすために期 s で生産したときの 費用（生産変動費用＋在庫費用） 固定費用は含まないことに注意！

17 強い定式化：施設配置定式化 dt Xst ≦ yt 期 t の需要を満たすために期 s で 生産する需要の割合 Xst Xst = 1 s
2018/8/8 強い定式化：施設配置定式化 期 t の需要を満たすために期 s で 生産する需要の割合 Xst s t This figure shows the flow model of this new extended formulation. The flow variable is the ratio of the demand in period t produced in period s. Since X_{st} is less than or equal to 1, the connection constraint of X and y becomes simpler X_{st} L= y_t. The formulation using the extended variable is called the facility local formulation ‘cause this structure of the constraints are resembles to the simple uncapacitated facility location problem. dt Xst ≦ yt Xst = 1

18 施設配置定式化 =>強い拡張定式化 射影したものが線形緩和が整数多面体と一致する！ 2018/8/8
This is a mixed integer programming formulation of the facility location formulation. This formulation can be shown to be tight. The linear programming relaxation of this formulation returns an integer feasible solution. =>強い拡張定式化 射影したものが線形緩和が整数多面体と一致する！

19 拡張定式化と射影 が X の定式化 = Q は X の拡張定式化 2018/8/8
We analyze the relationship between the extended formulation and the original formulation. Let capital X be the set of integer solutions in the n-dimensional space. Q is a formulation in an extended space expanded by a new variable z that is in R^q (q dimensional space). P tilde is the projection of Q onto the original space X that is defined as the set of all vectors x in R^n which satisfies the condition that there exists a z such that (x,z) in capital Q. P tilde is a formulation of X if and only if the intersection of P tilde and integer lattice is the set of integer solutions X. In this case, Q is called an extended formulation of X.

20 施設配置定式化：強い拡張定式化 オリジナルの定式化の 整数多面体 射影 拡張定式化 (施設配置定式化) 2018/8/8
This figure shows the idea of projection. The original space is here; on the floor. Then we extend the space into more dimensional space and derive an extended formulation. The above polyhedron or polytope is an extended formulation. If we project this polyhedron on the original space, we get an integer polyhedra. オリジナルの定式化の 整数多面体

21 定式化間の関係 変数の数 変数の数 制約数 弱い 定式化 強い定式化 制約数 =最適値 (S, l)不等式 カット T: 計画期間の数
2018/8/8 定式化間の関係 基本モデルの定式化 施設配置定式化 変数の数 変数の数 制約数 弱い 定式化 強い定式化 線形計画緩和の最適値 =最適値 制約数 (S, l)不等式 カット 追加された 不等式 I have talked about 2 type s of formulations of the lot-sizing model. The standard formulation requires O(T) constraints and O(T) variables where T denotes the number of periods. Its ’a compact formulation but unfortunately weak. By adding (S,ell) inequalities to cut off the LP optimal solutions, we get a stronger formulation. Actually, if we add all the (S,ell) inequalities whose number is an exponential order of the input size, we get the integer polyhedron. In practice we can add just a fraction of (S,ell) inequalities as a cutting plane. The facility location formulation requires O(T^2) constraints and O(T^2) variables and it gives the integer polyhedron. In practice the facility location re-formulation is much easier to implement; I recommend this re-formulation approach as a first cut. T: 計画期間の数 強い定式化

22 容量制約なしの問題に対する 動的計画 O(T2) もしくは O(T log T) 時間のアルゴリズム
2018/8/8 容量制約なしの問題に対する 動的計画 F(j) : 最初の j 期の最小費用 (初期条件 F(0)=0 ) It’ not surprising that we could get the integer polyhedron using polynomial time variables and constraints. Actually we can get an optimal solution of the uncapacitated lot-sizing problem in polynomial time. Here is an algorithm that is based on dynamic programming. Let capital F(j) denotes the minimum cost over the first j periods. Staring the initial condition F(0)=0, i.e., the minimum cost to 0 period is 0, We can derive the following recursive equation: that says; The minimum cost to period j is the sum of the minimum cost to period i (that is before j) plus the cost to produce at period i+1 and to satisfy all the demand from i+1 to j. Based on this dynamic programming recursion, we can derive an O(T^2) or much faster O(T log T) algorithm. O(T2) もしくは O(T log T) 時間のアルゴリズム

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

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

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

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

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

28 多段階の例題（需要量と結果） 　需要 　需要 エシェロン在庫を用いれば単品目と同様に（強い）定式化が可能！

29 実際問題を即座に解くには．．． 実際問題A 実際問題A’ 実際問題A’’ 実際問題B … モデルA モデリング言語 +A’ +A’’ B
メタ解法 混合整数計画（MIP）ソルバー 時々こける… アドホックな工夫 変数の制限 一部を緩和 設計者の腕に依存

30 Genetic algorithm with MIP-Merging crossover …
時々こける… MIP ベースのメタ解法 緩和固定法 MIP-近傍探索 容量スケーリング MIP-Merging Genetic algorithm with MIP-Merging crossover … 古典的アプローチ 強い定式化 列生成 切除平面法 Lagrange緩和 …

31 動的ロットサイズ決定問題への適用 緩和固定法 容量スケーリング法 問題：多期間，多資源，多段階（工程），多品目
MRPと同様のBOM，期ごとの需要量，段取り費用， 在庫費用を入力 総費用最小の段取りスケジューリング(y:0-1変数）， 各期の生産量（x:実数変数），在庫量（Inv：実数変数） を求める．

32 緩和固定法の概念図 (1)

33 緩和固定法の概念図 (2)

34 容量スケーリング法 固定費用付きの問題に対する汎用手法 線形計画緩和の解が収束するまで容量を変更
minimize cost: FixedCost*y 0-1 変数 s.t. x <=Capacity*y 実数変数 費用 固定費用 下の線形計画緩和 X Capacity×y 容量(Capacity)

35 2018/8/8 スケジューリング最適化 東京海洋大学 久保　幹雄

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

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

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

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

40 2018/8/8 最適化結果（ガントチャート） 資源制約つき（１人で作業）

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

65 スケジューリング最適化の例（工場内） いつ開始 するかを決定

66 ロット・スケジューリング問題 MIP/CP アプローチ
2018/8/8 ロット・スケジューリング問題 MIP/CP アプローチ 1.      MIP (ロットサイズ決定) : 　各期の各品目の生産量ならびにブロック(同種の機械の部分集合）への割り当てを決める． 　期は月（もしくは週）を想定． 2.      CP (スケジューリング) : 　各ブロック内での生産量が与えられたとき，使用する機械の数と種類，生産順序を決める． 　期は時間（もしくは日）を想定．

67 MIP/CPの情報のやりとり MIP (ロットサイズ決定問題） 期・品目ごとの 期・品目ごとに 生産量 品目のブロックへの 使用する機械台数
2018/8/8 MIP/CPの情報のやりとり MIP (ロットサイズ決定問題） 期・品目ごとの 生産量 品目のブロックへの 割り当て情報 期・品目ごとに 使用する機械台数 段取りの情報 CP (スケジューリング問題）

68 2018/8/8 ロットサイズ決定問題（概念図） ブロックA １期 ２期 ３期 ４期 ５期 品目 段取り ブロックB 製造量

69 スケジューリング問題（概念図） MIPの情報 品目1 を200 units 品目3を400 units 製造 ブロックA １期（＝１ヶ月）
2018/8/8 スケジューリング問題（概念図） MIPの情報 品目1 を200 units 品目3を400 units 製造 ブロックA １期（＝１ヶ月） 機械 段取り 機械A1,A2,A3を使用して品目3製造 　その後に，機械A1,A2を使用して品目1製造

70 まとめ ロットサイズ決定モデル スケジューリングモデル 例題とヒューリスティクス 強い定式化と弱い定式化 複数品目，多段階への拡張
MIPベースのメタ解法 スケジューリングモデル PERT の例 ガントチャート 近視眼的ヒューリスティクスの危険性 MIP/CPアプローチ