生産スケジューリング.

Presentation on theme: "生産スケジューリング."— Presentation transcript:

1 生産スケジューリング

2 スケジューリングの概念 スケジューリング問題 製造活動の３(M)要素 授業時間割表 電車運行時刻表 生産スケジューリング
配送スケジューリング 旅行スケジューリング 研修スケジューリング など 製造活動の３(M)要素 人間：作業者～能力 道具：作業順番～工程 対象：仕事～ジョブ

3 生産スケジューリングの分類 順序制約なし（巡回型） 順序制約あり（資源配置型） 配送スケジューリング 単一ジョブ（例：ＴＳＰ）
複数ジョブ（例：ＶＲＰ） 順序制約あり（資源配置型） 単一ジョブ（例：ＰＥＲＴ） 複数ジョブ 同一加工順序 例：flow shop schedulingｓ ジョブ１：①→②→③ ジョブ２：①→②→③ 異なる加工順序 例：job shop scheduling ジョブ１：①→②→③ ジョブ２：②→①→③ プロジェクト スケジューリング 加工スケジューリング

4 生産スケジューリングの目標 工程効率基準 滞留時間基準 納期基準 重み付き複合基準 稼働率 平準化 総所要時間 最大滞留時間 平均滞留時間
最大納期ずれ時間 平均納期ずれ時間 平均納期遅れ時間 重み付き複合基準

5 生産スケジューリングの制約（１） 組織目標の制約 品質目標（Ｑ） 利益目標（Ｃ） 納期目標（Ｄ） 生産数量の目標 現場の安定性目標
残業費用の目標 生産性の目標

6 生産スケジューリングの制約（２） 物理、技術的制約 稼働率、利用率の制約 機械、設備の制約 加工時間の制約 段取り時間の制約 製造方法の制約
製造順序の制約 製造品質の制約 稼働率、利用率の制約 使用資源の予約 機械故障時間 シフト

7 生産スケジューリングの制約（３） 因果関係の制約 選好に関する制約 加工の代替案 機械の代替案 必要な工具類 資材所要量 加工所要人数
搬送時間 選好に関する制約 オペレーションの選好 機械設備の選好 加工順序の選好

8 スケジューリング手法の分類 アルゴリズミックなアプローチ シミュレーション マン・マシンインタラクション 最適化アルゴリズム
ヒューリスティック・アルゴリズム シミュレーション モデリング シミュレーション分析 マン・マシンインタラクション アルゴリズムまたはモデリング パラメータ入力、変更

9 最適化アルゴリズ 汎用解法 特殊解法 構築型： 改造型： 構築型 完全列挙法、 分枝限定法
SA（アニーリング法）、タブサーチ、GA（遺伝的アルゴリズム） 特殊解法 構築型 ジョンション法 図解法

10 実行可能解法 汎用解法 構築型 盲目的探査 深さ優先探査 広さ優先探査 ヒューリスティック探査 山登り 最良優先探査 ビーム探査
フィルター付きビームサーチ

11 特殊解法 改善型 局所的最適代替案の選択 タブサーチ（ＴＳ，ＡＭＰ） アニーリン グ(SA) 遺伝的アルゴリズム(GA)
ディスパッチングルール 目標追跡法 ボトルネック指向スケジューリング セービング法 スウィープ法

12 フローショップスケジューリング

13 １．ジョンソン法 ジョンソン法 問題例： ジョブ１ ジョブ２ ジョブ３ ジョブ４ 工程１ 　１２０ ４０ ８０ １００ 工程２ ６０ 　 １４０ １２０ ８０ アルゴリズム 最小加工時間を選択する この時間が前工程であれはそのジョブを前から並べる この時間が後工程であればそのジョブを後ろから並べる。 未割り当てジョブが無くなるまでに上記３ステップを繰り返す。

14 ガントチャート (Ｇａｎｔｔ Ｃｈａｒｔ) 50 100 150 200 250 300 350 400 450 J2 J3 J4 J1
P1 P2 J2 J3 J4 J1

15 ジョンション法の応用 ２工程の時は最適性を保証 ３工程以上の時は 多工程への応用 直接応用不可能 最適性を保証しない 複合工程を作成
逐次的にジョンション法を適用

16 ジョンソン法の問題点 問題例 ジョブ１ ジョブ２ ジョブ３ ジョブ４ 工程１ ２０ １４０ ４０ １００ ジョンション法の問題点
問題例 ジョブ１ ジョブ２ ジョブ３ ジョブ４ 工程１ 　２０ 　１４０ ４０　　　１００ 　　 工程２ １８０ １２０ ４０　　　　２０ 工程３ ８０ 　４０ 　１６０ 　　 ６０ ジョンション法の問題点 工程１と２を対象にすると １ー３ー２ー４ 工程２と３を対象にすると ４ー３ー１ー２ 工程１と３を対象にすると １ー３ー４ー２

17 ２．列挙法 (Eｎｕｍｅｒａｔｉｏｎ Ｍｅｔｈｏｄ)
すべての可能性を調べる方法 １ー２ー３ー４ １ー２ー４ー３ １ー３ー２ー４ ・ ・ ・ ４ｘ３ｘ２ｘ１＝２４通り 目的関数を計算し、最適解を持つスケジュールを選択する。

18 ツリーによる列挙法 ・ ・ ・ ・ ・ ・ １ ２ ３ ４ レベル０ レベル１ レベル２ レベル３ レベル４ レベル＝深さ ０

19 ３．分枝限定法(Bｒａｎｃｈ ａｎｄ Ｂｏｕｎｄ Ｍｅｔｈｏｄ)
列挙法に基づき、次に割付可能なジョブを選択する（分枝する）。 Lower Boundを計算し、一番有望なジョブを割り付ける（枝を伸ばす）。 Upper Boundを計算する。 バックトラッキングする。 枝刈りする。 最適解を確定する。

20 例題 ジョブ１ ジョブ２ ジョブ３ ジョブ４ 工程１ ２０ １４０ ４０ １００ 工程２ １８０ １２０ ４０ ２０ 工程３ ８０ ４０ １６０ ６０

21 一回目の分枝 ０ １ ２ ３ ４ ＬＢー＞ ５４０ ６００ ４４０ ５００

22 下界（Ｌｏｗｅｒ Ｂｏｕｎｄ） Ｌｏｗｅｒ Ｂｏｕｎｄの概念
有望枝の判断基準 最小化目標関数の上限値（これより大きくならない） 計算方法：問題により異なる 計算式例 ＬＢi＝選択済みジョブの本工程までの加工完了時間 　　＋残りジョブの本工程における総加工時間 　　＋すべての後工程に対する残りジョブ加工時間和 　　　　　　　　の最小値 LB=max{ＬＢi} }

23 ＬＢの計算例（１） 問題 ジョブ１ ジョブ２ ジョブ３ ジョブ４ 工程１ ２０ １４０ ４０ １００ 工程２ １８０ １２０ ４０ ２０ 工程３ ８０ ４０ １６０ ６０ 計算例（ジョブ１を最初に割り付ける時） ＬＢ（工程１、工程２、工程３）＝ （２０、２００、２８０） ＋（２８０、１８０、２６０） ＋（８０、４０、０） ＝（３８０、４２０、５４０）～ 最大値５４０を選択

24 ＬＢの計算例（２） 問題 ジョブ１ ジョブ２ ジョブ３ ジョブ４ 工程１ ２０ １４０ ４０ １００ 工程２ １８０ １２０ ４０ ２０ 工程３ ８０ ４０ １６０ ６０ 計算例 （ジョブ２を最初に割り付ける時） ＬＢ（工程１、工程２、工程３）＝ （１４０、２６０、３００） ＋（１６０、２４０、３００） ＋（８０、４０、０） ＝（３８０、５４０、６００）～ 最大値６００を選択

25 二回目の分枝 ０ ＊ １ ２ ３ ４ ５４０ ６００ ４４０ ５００ ＊ ２ ４ １ ４４０ ５６０ ５００

26 ＬＢ計算例（３） 問題 ジョブ１ ジョブ２ ジョブ３ ジョブ４ 計算例（最初にジョブ３を選択した後）
問題 ジョブ１ ジョブ２ ジョブ３ ジョブ４ 工程１ ２０ １４０ 　　４０ １００ 工程２ １８０ １２０ 　　４０ ２０ 工程３ ８０ ４０ １６０ 　６０ 計算例（最初にジョブ３を選択した後） ジョブ１のＬＢを計算する ＬＢ（工程１、工程２、工程３） ＝（６０、２６０、３４０( )） ＋（２４０、１４０、１００） ＋（８０、４０、０） ＝（３８０、４４０、４４０）～ 最大値４４０を選択 最大値パス 選択基準

27 ガントチャートの利用 ４０＋４０＋１８０＝２６０ ４０＋２０＝６０ 工程１ 工程２ 工程３
４０＋４０＋ｍａｘ（１８０，１６０）＋８０＝３４０ ジョブ３ ジョブ１

28 計算量＝（４＋３＋２＋１）／（４＋１２＋２４＋２４）＝１／６．４ レベル０ ０ ５４０ ６００ ４４０ ５００ レベル１ １ ２ ３ ４ レベル２ ４４０ ５００ ２ ３ ４ １ ３ ４ １ ２ ４ １ ２ ３ ５６０ レベル３ ３ ４ ２ ４ ・ ・ ・ １ ３ １ ２ ２ ４ ４８０ ４６０ レベル４ ４ ３ ４ ２ ・ ・ ・ ２ ３ １ ２ １ ４６０

29 ジョブショップスケジューリング

30 1. 図解法 2製品の加工スケジュールを決める問題 工程1 工程2 工程3 工程4 製品1 M1：4 M2:2 M3:3 製品2 M1:2

31 M2:3 M1:2 M3:4 M1:2 M1:4 M2:2 M3:3 M2:2

32 2. 競合解消法 与えられたデータ ＬＢ（下界値）行列Ｃの求め方 加工経路行列Ｍ（ＪｘＭ） 加工時間行列Ｐ（ＪｘＭ） 納期ベクトルＤ（Ｊ）
ＬＢ行列Ｃ（ＪｘＭ） ＬＢ（下界値）行列Ｃの求め方

33 競合処理 競合アイテムの判断方法 Ｐを参照に、競合相手を競合加工時間分遅らせ、新しいＬＢ行列（Ｃ行列）をそれぞれ作成する。
これらのＬＢ行列に基づいて目的関数をそれぞれ計算し、最大目的関数に対応するＬＢ行列を選択する。 競合アイテムの判断方法 Ｍを参考に加工順にＬＢの実行可能性をチェックする。

34 例題 Ｍ１ Ｍ２ Ｍ３ Ｄ Ｊ１ ５（１） ３（２） ２（３） １３ Ｊ２ ２（１） ６（３） ４（２） １２ ４（２） ３（１） ４（３）
５（１） ３（２） ２（３） １３ Ｊ２ ２（１） ６（３） ４（２） １２ ４（２） ３（１） ４（３） １７ Ｊ３ Ｊ：ジョブ Ｍ：機械（工程） データ：加工時間（加工順番）

35

36 Ｃ１ Ｌ＝０ Ｃ２ Ｌ＝５ Ｃ３ Ｃ４ Ｌ＝４ Ｃ５ Ｌ＝２ Ｃ６ Ｃ７ Ｃ８ 目的関数：最大遅れを最小化すること Min. Ｌ＝∑max(0,Ci3-Di)

37 3. ディスパッチングルール(Ｄｉｓｐａｔｃｈｉｎｇ Ｒｕｌｅs)
概念 計算量が莫大であるケース 複数ジョブから一つ選択して工程に割り付けるジョブ選択の基準、ルールの総称 よく使われるＤＲ ＳＰＴ（Ｓｈｏｒｔｓｔ Ｐｒｏｃｅｓｓｉｎｇ Ｔｉｍｅ） ＬＰＴ（Largest Processing Time) ＳＬＡＣＫ（納期ー現時刻ー残加工時間） ＥＤＤ（Ｅａｒｌｉｅｓｔ Ｄｕｅ Ｄａｔｅ、残りの加工時間を考慮せず）

38 DRのアルゴリズム ステップ１： それぞれの工程（機械）で加工が終了した時点で、その工程で加工が可能となっているジョブ（加工待ちのジョブと、その時点でちょうど前の工程が終わったジョブ）を見つける。 ステップ２： そのようなジョブがない時には単位時間ずつ、加工開始可能なジョブが見つかるまで、スケジューリング時刻を進める。その間、この工程は遊休（アイドル）状態となる ステップ３： 加工開始可能なジョブが一つのとき、このジョブを工程に直ちに割り付ける。 ステップ４： 加工開始可能なジョブが複数あるとき（競合、あるいはコンフリクトという）、これらのジョブにディスパッチングルールを適用し、その内の一つを選択し、そのジョブを工程に割り付ける。 ステップ５：スケジューリング時刻を順次進め、同様手続きで各工程に対するジョブの割付を行う。

39 例題 下の表に与えられたジョブショップスケジューリング問題を、競合解消法を用いて解き、その解をガントチャートに示せ。ただし評価基準は、総完了時刻最小とする。 上記の問題にSPTルールを適用するとどのようになるか？ 上記の４つのジョブの納期は、いずれも20とする。このときジャストインタイム基準（ただし、納期遅れは許さない）で最適となる解を、ガントチャートで示せ。 ジョブ／機械 Ｍ１ Ｍ２ Ｍ３ Ｊ１ Ｊ２ Ｊ３ Ｊ４ ５（１） 　５（２） 　　２（３） ２（１） ６（３） ４（２） ４（２） 　３（１） ４（３） ３（３） ５（２） ４（１） 注：（ ）の中の数字は加工順番を表わす。

40 Ｍ＝ P＝ C＝ 5 10 15 20 J1 M1 M2 M3 M3 J2 M1 M2 J3 M2 M1 M3 J4 M3 M2 M1 C1＝ C2＝ L=max(Ci3) L1=14, L2=17

41 Ｍ＝ P＝ C1＝ J1 M1 M2 M3 5 10 15 20 J2 J3 J4 C3＝ C4＝ L=max(Ci3) L3=14, L4=18

42 Ｍ＝ P＝ C3＝ 5 10 15 20 J1 M1 M2 M3 J2 M1 M3 M2 J3 M2 M1 M3 J4 M3 M2 M1 C6＝ C5＝ L=max(Ci3) L5=19, L6=15

43 Ｍ＝ P＝ C6＝ 5 10 15 20 J1 M1 M2 M3 J2 M1 M3 M2 J3 M2 M1 M3 J4 M3 M2 M1 C8＝ C7＝ L=max(Ci3) L7=16, L8=20

44 Ｍ＝ P＝ C7＝ 5 10 15 20 J1 M1 M2 M3 J2 M1 M3 M2 J3 M2 M1 M3 J4 M3 M2 M1 C10＝ C9＝ L=max(Ci3) L9=16, L10=22

45 Ｍ＝ P＝ C9＝ 5 10 15 20 J1 M1 M2 M3 J2 M1 M3 M2 J3 M2 M1 M3 J4 M3 M2 M1 C12＝ C11＝ L=max(Ci3) L11=16, L12=22

46 Ｍ＝ P＝ C11＝ 5 10 15 20 J1 M1 M2 M3 J2 M1 M3 M2 J3 M2 M1 M3 J4 M3 M2 M1 C14＝ C13＝ L=max(Ci3) L13=22, L14=20

47 Ｍ＝ P＝ C14＝ 5 10 15 20 J1 M1 M2 M3 M2 J2 M1 M3 J3 M2 M1 M3 J4 M3 M2 M1 C16＝ C15＝ L=max(Ci3) L15=20, L16=20

48 Ｍ＝ P＝ C1＝ 5 10 15 20 J1 M1 M2 M3 J2 M1 M3 M2 J3 M2 M1 M3 J4 M3 M2 M1 5 10 15 20 M1 J2 J1 J3 J4 M2 J3 J4 J1 J2 J4 J2 M3 J3 J1

49 ＳＰＴルールの適用 J1 M1 M2 M3 5 10 15 20 J2 J3 J4 ５ ２

50 J1 M1 M2 M3 5 10 15 20 J2 J3 J4 ４ ４

51 ５ J1 M1 M2 M3 J2 M1 M3 M2 ４ J3 M2 M1 M3 J4 M3 M2 M1

52 ５ J1 M1 M2 M3 J2 M1 M3 M2 J3 M2 M1 M3 ５ J4 M3 M2 M1

53 J1 M1 M2 M3 J2 M1 M3 M2 ４ J3 M2 M1 M3 ３ J4 M3 M2 M1

54 J1 M1 M2 M3 ６ J2 M1 M3 M2 J3 M2 M1 M3 ４ J4 M3 M2 M1

55 競合発生 SPTルールで決定 ５ J1 M1 M2 M3 ６ J2 M1 M3 M2 J3 M2 M1 M3 J4 M3 M2 M1

56 J1 M1 M2 M3 J2 J3 J4 ６ ５ ４ 5 10 15 20 M1 J2 J1 J3 J4 M2 J3 J4 J1 J2 J4 J2 M3 J3 J1

57 総加工時間同じ 競合解消法 5 10 15 20 J1 M1 M2 M3 J2 M1 M3 M2 J3 M2 M1 M3 J4 M3 M2 M1 ＳＰＴ J1 M1 M2 M3 J2 M1 M3 M2 J3 M2 M1 M3 J4 M3 M2 M1