生産スケジューリング
スケジューリングの概念

スケジューリング問題
授業時間割表
 電車運行時刻表
 生産スケジューリング
 配送スケジューリング
 旅行スケジューリング
 研修スケジューリング
など


製造活動の3(M)要素



人間:作業者~能力
道具:作業順番~工程
対象:仕事~ジョブ
生産スケジューリングの分類

順序制約なし(巡回型)



単一ジョブ(例:TSP)
複数ジョブ(例:VRP)
順序制約あり(資源配置型)


配送スケジューリング
単一ジョブ(例:PERT)
複数ジョブ

同一加工順序


プロジェクト
スケジューリング
例:flow shop schedulings
ジョブ1:①→②→③
ジョブ2:①→②→③
異なる加工順序

例:job shop scheduling
ジョブ1:①→②→③
ジョブ2:②→①→③
加工スケジューリング
生産スケジューリングの目標

工程効率基準



滞留時間基準




総所要時間
最大滞留時間
平均滞留時間
納期基準




稼働率
平準化
最大納期ずれ時間
平均納期ずれ時間
平均納期遅れ時間
重み付き複合基準
生産スケジューリングの制約(1)

組織目標の制約







品質目標(Q)
利益目標(C)
納期目標(D)
生産数量の目標
現場の安定性目標
残業費用の目標
生産性の目標
生産スケジューリングの制約(2)

物理、技術的制約







機械、設備の制約
加工時間の制約
段取り時間の制約
製造方法の制約
製造順序の制約
製造品質の制約
稼働率、利用率の制約



使用資源の予約
機械故障時間
シフト
生産スケジューリングの制約(3)

因果関係の制約







加工の代替案
機械の代替案
必要な工具類
資材所要量
加工所要人数
搬送時間
選好に関する制約



オペレーションの選好
機械設備の選好
加工順序の選好
スケジューリング手法の分類

アルゴリズミックなアプローチ



シミュレーション



最適化アルゴリズム
ヒューリスティック・アルゴリズム
モデリング
シミュレーション分析
マン・マシンインタラクション


アルゴリズムまたはモデリング
パラメータ入力、変更
最適化アルゴリズ

汎用解法

構築型:



改造型:


完全列挙法、
分枝限定法
SA(アニーリング法)、タブサーチ、GA(遺伝的アルゴリズム)
特殊解法

構築型


ジョンション法
図解法
実行可能解法

汎用解法

構築型








盲目的探査
深さ優先探査
広さ優先探査
ヒューリスティック探査
山登り
最良優先探査
ビーム探査
フィルター付きビームサーチ

改善型





局所的最適代替案の選択
タブサーチ(TS,AMP)
アニーリン
グ(SA)
遺伝的アルゴリズム(GA)
特殊解法





ディスパッチングルール
目標追跡法
ボトルネック指向スケジューリング
セービング法
スウィープ法
フローショップスケジューリング
1.ジョンソン法

ジョンソン法
工程1
工程2

問題例:
ジョブ1 ジョブ2 ジョブ3 ジョブ4
120
40
80
100
60
140
120
80
アルゴリズム
最小加工時間を選択する
 この時間が前工程であれはそのジョブを前から並べる
 この時間が後工程であればそのジョブを後ろから並べる。
 未割り当てジョブが無くなるまでに上記3ステップを繰り返す。

ガントチャート (Gantt Chart)
50
P1
P2
J2
100 150
J3
200
250
J4
J2
300
350
400
J1
J3
J4
J1
450
ジョンション法の応用


2工程の時は最適性を保証
3工程以上の時は
直接応用不可能
 最適性を保証しない


多工程への応用
複合工程を作成
 逐次的にジョンション法を適用

ジョンソン法の問題点

問題例
ジョブ1 ジョブ2 ジョブ3 ジョブ4
工程1 20
140
40
100
工程2 180
120
40
20
工程3 80
40 160
60

ジョンション法の問題点
工程1と2を対象にすると
1ー3ー2ー4
 工程2と3を対象にすると
4ー3ー1ー2
 工程1と3を対象にすると
1ー3ー4ー2

2.列挙法

すべての可能性を調べる方法






(Enumeration Method)
1ー2ー3ー4
1ー2ー4ー3
1ー3ー2ー4
・
・
・
4x3x2x1=24通り
目的関数を計算し、最適解を持つスケジュールを選
択する。
ツリーによる列挙法
レベル=深さ
レベル0
0
レベル1
1
レベル2
2
3
4
4
3
3
2
4
4
2
1
3
3
4
1
4
2
4
1
2
4
レベル3
・ ・ ・ ・ ・ ・
1
2
レベル4
・ ・ ・ ・ ・ ・
3
3
3
1
1 2
2 1
3.分枝限定法(Branch and Bound Method)

列挙法に基づき、次に割付可能なジョブを選択する
(分枝する)。

Lower Boundを計算し、一番有望なジョブを割り付
ける(枝を伸ばす)。

Upper Boundを計算する。

バックトラッキングする。

枝刈りする。

最適解を確定する。
例題
ジョブ1
工程1 20
工程2 180
工程3 80
ジョブ2 ジョブ3 ジョブ4
140
40
100
120
40
20
40
160 60
一回目の分枝
0
1
LBー>
540
2
600
3
440
4
500
下界(Lower Bound)

Lower Boundの概念




有望枝の判断基準
最小化目標関数の上限値(これより大きくならな
い)
計算方法:問題により異なる
計算式例
LBi=選択済みジョブの本工程までの加工完了時間
+残りジョブの本工程における総加工時間
+すべての後工程に対する残りジョブ加工時間和
の最小値
LB=max{LBi} }
LBの計算例(1)

問題
ジョブ1 ジョブ2
工程1 20
140
工程2 180
120
工程3 80
40

ジョブ3 ジョブ4
40
100
40
20
160
60
計算例(ジョブ1を最初に割り付ける時)
LB(工程1、工程2、工程3)=
(20、200、280)
+(280、180、260)
+(80、40、0)
=(380、420、540)~ 最大値540を選択
LBの計算例(2)

問題
ジョブ1 ジョブ2 ジョブ3 ジョブ4
工程1 20
140
40
100
工程2 180
120
40
20
工程3 80
40
160
60

計算例
(ジョブ2を最初に割り付ける時)
LB(工程1、工程2、工程3)=
(140、260、300)
+(160、240、300)
+(80、40、0)
=(380、540、600)~ 最大値600を選択
二回目の分枝
0
1
2
540
3
*
600
4
440
*
1
2
440
560
500
4
500
LB計算例(3)

問題
ジョブ1 ジョブ2 ジョブ3 ジョブ4
工程1 20
140
40 100
工程2 180
120
40
20
工程3 80
40
160
60

計算例(最初にジョブ3を選択した後)

ジョブ1のLBを計算する
LB(工程1、工程2、工程3)
=(60、260、340(40+40+180+80)) 最大値パス
+(240、140、100)
選択基準
+(80、40、0)
=(380、440、440)~ 最大値440を選択
ガントチャートの利用
40+20=60
40+40+180=260
工程1
工程2
工程3
40+40+max(180,160)+80=340
ジョブ3
ジョブ1
計算量=(4+3+2+1)/(4+12+24+24)=1/6.4
レベル0
0
540
1
レベル1
レベル2
2
3
4
1
600
2
3
440
3
440
4
1
2
560
500
4
500
4
1
2
3
レベル3
3
4
2
・ ・ ・
4
480
2
4
460
1
3
1
2
2
1
レベル4
4
3
4
2
・ ・ ・
2
460
3
1
ジョブショップスケジューリング
1. 図解法

2製品の加工スケジュールを決める問題
工程1 工程2 工程3 工程4
製品1 M1:4 M2:2
M3:3
M2:2
製品2 M1:2
M1:2
M2:3
M3:4
M2:3
M1:2
M3:4
M1:2
M1:4
M2:2
M3:3
M2:2
2. 競合解消法

与えられたデータ





加工経路行列M(JxM)
加工時間行列P(JxM)
納期ベクトルD(J)
LB行列C(JxM)
LB(下界値)行列Cの求め方
Cij 
j
P
ik
k 1

競合処理



Pを参照に、競合相手を競合加工時間分遅らせ、
新しいLB行列(C行列)をそれぞれ作成する。
これらのLB行列に基づいて目的関数をそれぞ
れ計算し、最大目的関数に対応するLB行列を選
択する。
競合アイテムの判断方法

Mを参考に加工順にLBの実行可能性をチェック
する。
例題
M1
M2
M3
D
J1
5(1)
3(2)
2(3)
13
J2
2(1)
6(3)
4(2)
12
J3
4(2)
3(1)
4(3)
17
J:ジョブ
M:機械(工程)
データ:加工時間(加工順番)
1
M  1


2
C0 
C1 
C3 
C5 
C7 
5
2


4
7
2


4
7
2


4
7
2


4
7
2


4
2
3
1
8
8
7
10
8
7
10
8
10
10
8
10
10
8
10
3
3
2
5
13



2 P 
2
6
4 D  12







3
3
4

4

17

10
12

11

12
8
10
5


12 C2 
7
13
17





11
4
7
11



12
15
17
12


12 C4 
2
8
12





14
4
7
11



12
15
17
5


14 C6 
2
8
12





14
4
10
14



12
10
16
7


14 C8 
2
8
14





16
4
10
14



目的関数:最大遅れを最小化すること
Min. L=∑max(0,Ci3-Di)
C1
L=0
C4
L=4
C3
L=0
C5
L=2
C7
L=2
C6
L=4
C8
L=5
C2
L=5
3. ディスパッチングルール(Dispatching Rules)

概念
計算量が莫大であるケース
 複数ジョブから一つ選択して工程に割り付けるジョブ
選択の基準、ルールの総称


よく使われるDR




SPT(Shortst Processing Time)
LPT(Largest Processing Time)
SLACK(納期ー現時刻ー残加工時間)
EDD(Earliest Due Date、残りの加工時間を考慮せず)
DRのアルゴリズム





ステップ1: それぞれの工程(機械)で加工が終了した時点で、その
工程で加工が可能となっているジョブ(加工待ちのジョブと、その時
点でちょうど前の工程が終わったジョブ)を見つける。
ステップ2: そのようなジョブがない時には単位時間ずつ、加工開始
可能なジョブが見つかるまで、スケジューリング時刻を進める。その
間、この工程は遊休(アイドル)状態となる
ステップ3: 加工開始可能なジョブが一つのとき、このジョブを工程に
直ちに割り付ける。
ステップ4: 加工開始可能なジョブが複数あるとき(競合、あるいはコ
ンフリクトという)、これらのジョブにディスパッチングルールを適用し、
その内の一つを選択し、そのジョブを工程に割り付ける。
ステップ5:スケジューリング時刻を順次進め、同様手続きで各工程
に対するジョブの割付を行う。
例題



下の表に与えられたジョブショップスケジューリング問題を、
競合解消法を用いて解き、その解をガントチャートに示せ。た
だし評価基準は、総完了時刻最小とする。
上記の問題にSPTルールを適用するとどのようになるか?
上記の4つのジョブの納期は、いずれも20とする。このとき
ジャストインタイム基準(ただし、納期遅れは許さない)で最
適となる解を、ガントチャートで示せ。
ジョブ/機械
J1
J2
J3
J4
M1
M2
5(1)
2(1)
4(2)
3(3)
5(2)
6(3)
3(1)
5(2)
M3
2(3)
4(2)
4(3)
4(1)
注:( )の中の数字は加工順番を表わす。
1
1
2
3
M=
2
3
1
2
3
2
3
1
5
2
3
4
P=
5
J1
M1
J3
M2
J4
M2
M3
C=
15
M3
M2
M1
M3
C1=
2
6
4
3
10
M1
J2
5
4
4
5
M3
M2
7
2
3
4
12
6
7
9
L=max(Ci3)
14
12
11
12
M1
C2=
L1=14, L2=17
5
7
3
4
10 12
11 17
7 11
9 12
5
2
3
4
10
6
7
9
12
12
11
12
20
1
1
2
3
M=
2
3
1
2
3
2
3
1
5
2
3
4
P=
5
J1
J2
J3
J4
M2
M3
M3
M2
M1
M3
M2
7
2
3
4
C1=
15
M2
M3
C3=
2
6
4
3
10
M1
M1
5
4
4
5
12
8
7
9
L=max(Ci3)
14
14
11
12
M1
C4=
L3=14, L4=18
7 12 14
2 6 12
3 7 11
10 15 18
7
2
3
4
12
6
7
9
14
12
11
12
20
1
1
2
3
M=
2
3
1
2
3
2
3
1
5
2
3
4
P=
5
J1
J2
J3
J4
M3
M1
M3
C5=
L=max(Ci3)
M3
M2
M3
M2
17
8
7
9
C3=
15
M2
M1
12
2
3
4
2
6
4
3
10
M1
M2
5
4
4
5
19
14
11
12
M1
C6=
L5=19, L6=15
7
2
3
4
12 14
8 14
11 15
9 12
7
2
3
4
12
8
7
9
14
14
11
12
20
1
1
2
3
M=
2
3
1
2
3
2
3
1
5
2
3
4
P=
5
J1
J2
J3
J4
M3
15
M3
M2
M1
M3
M2
7
2
3
4
14
8
11
9
L=max(Ci3)
C6=
M2
M2
C7=
2
6
4
3
10
M1
M1
5
4
4
5
16
14
15
12
M3
M1
C8=
L7=16, L8=20
7
2
3
4
12 14
8 14
11 15
17 20
7
2
3
4
12 14
8 14
11 15
9 12
20
1
1
2
3
M=
2
3
1
2
3
2
3
1
5
2
3
4
P=
5
J1
J2
J3
J4
M3
15
M2
7
2
3
4
14
8
11
9
L=max(Ci3)
16
15
15
12
M3
M2
M1
M3
C7=
M2
M2
C9=
2
6
4
3
10
M1
M1
5
4
4
5
M3
M1
C10=
L9=16, L10=22
7
2
3
4
14 16
8 14
11 15
19 22
7
2
3
4
14 16
8 14
11 15
9 12
20
1
1
2
3
M=
2
3
1
2
3
2
3
1
P=
5
2
3
4
5
J1
J2
J3
J4
C9=
15
M2
M3
M2
M2
7
2
3
4
14
8
11
9
L=max(Ci3)
16
15
15
14
M3
M2
M1
M3
C11=
2
6
4
3
10
M1
M1
5
4
4
5
M3
M1
C12=
L11=16, L12=22
7
2
3
4
14 16
8 15
18 22
9 12
7
2
3
4
14 16
8 15
11 15
9 12
20
1
1
2
3
M=
2
3
1
2
3
2
3
1
5
2
3
4
P=
5
J1
J2
J3
J4
M3
15
M3
M2
7
2
3
4
20
8
11
9
L=max(Ci3)
22
15
15
14
M3
M2
M1
M3
C11=
M2
M2
C13=
2
6
4
3
10
M1
M1
5
4
4
5
M1
C14=
L13=22, L14=20
7
2
3
4
14 16
8 20
11 15
9 14
7
2
3
4
14 16
8 15
11 15
9 14
20
1
1
2
3
M=
2
3
1
2
3
2
3
1
5
2
3
4
P=
5
J1
J2
J3
J4
15
M2
M1
M3
M2
7
2
3
4
L=max(Ci3)
14
8
11
9
17
20
15
14
M1
C16=
L15=20, L16=20
7
2
3
4
14 16
8 20
11 20
9 14
14 16
8 20
11 15
9 14
20
M3
M3
M3
7
2
3
4
C14=
M2
M2
C15=
2
6
4
3
10
M1
M1
5
4
4
5
1
1
2
3
M=
2
3
1
2
3
2
3
1
5
2
3
4
P=
5
J1
J2
J3
J4
2
6
4
3
M1
M1
M3
J2
M2
J3
M1
10
J3
J4
J4
J2
20
M3
M2
J1
14 17
8 20
11 15
9 14
M3
M2
M3
M2
M1
15
M2
M1
7
2
3
4
C1=
10
5
M3
5
4
4
5
15
20
J4
J1
J2
J3
J1
SPTルールの適用
5
J1
J2
J3
J4
5
2
10
M1
M1
M2
M3
M2
M3
M3
M2
M1
M3
M2
M1
15
20
5
J1
J2
M1
M1
4
M2
J3
J4
10
4
M3
M2
M3
M3
M2
M1
M3
M2
15
M1
20
5
J1
J2
J3
J4
M1
M1
M2
M3
M2
M3
4
M1
M3
M2
M3
M2
M1
J1
J2
J3
J4
5
M1
M1
M3
M2
M3
M2
M3
M2
M1
5
M2
M3
M1
J1
J2
J3
J4
M1
M1
M2
M3
4
M2
M3
M2
M2
M1
M3
3
M1
M3
J1
J2
J3
J4
M1
M1
M2
M3
M2
M3
6
M1
4
M2
M2
M3
M1
M3
競合発生
SPTルールで決定
J1
J2
J3
J4
5
M1
M1
M2
M3
6
M3
M1
M2
M2
M3
M2
M3
M1
J1
J2
J3
J4
5
M1
M1
6
M1
5
M3
J2
M1
M2
J3
M3
10
J1
J3
J4
J4
J2
M2
M3
M2
5
M1
M3
M3
M2
4
M2
15
20
J4
J1
J2
J3
J1
総加工時間同じ
競合解消法
J1
J2
J3
5
10
M1
M1
M2
M3
M2
J4
15
M1
M3
20
M3
M2
M3
M2
M1
SPT
J1
J2
J3
J4
M1
M1
M2
M3
M2
M3
M2
M1
M2
M3
M3
M1
ダウンロード

スケジューリング(1)