Download presentation
Presentation is loading. Please wait.
1
シミュレーション学講義 第＊＊回 スケジューリング問題とＪＳＳＰ
2
スケジューリング問題 ＪＳＳＰ（Job Shop Scheduling Problem) Example: E.g. 1 2 3 4 J1
m台のmachines, ｎ個のjobs m機械の仕事列： E.g. 1 2 3 4 J1 M1,3 M2,2 M3,4 M4,1 J2 M4,2 M3,1 J3 M1,2 M3,2 M2,1 Our research topics include … As you can see, the keyword ..
3
ディスパッチング・ルール Jobの割付の優先規則 コンフリクトの起こったときの解消方法 Rules:
SPT: Shortest processing time EDD: Earliest due date SLACK FIFO RANDOM ... ect. Our research topics include … As you can see, the keyword ..
4
GAによる解法 GTYPE → PTYPE ： いかにデザインするか？ 適合度はどうするか？ 各種パラメータ 集団数 最大世代数 交叉率
突然変異率 Our research topics include … As you can see, the keyword ..
5
GYTPE１： TSPと同じもの 交叉の工夫が不要 E.g. J1, J2, J3 のとき → mod 3 で考える
GTYPE: ４ ５ １ ９ … ↑ ↑ ↑ ↑ PTYPE: J1 J2 J1 J3 … → mod 3 で考える Our research topics include … As you can see, the keyword ..
6
GYTPE2： 順序表現 遺伝子→次にどのジョブを優先して配置するかを指定する ジョブ番号を機械の数分並べる
例： ３３３２１１２１２ ： ３ジョブｘ３マシン 遺伝子の左から出現する番号を優先する 作業時間を考慮しガントチャートに配置する 交叉の工夫が必要 Our research topics include … As you can see, the keyword ..
7
GYTPE2： JOBの割付アルゴリズム Chrom(i): GTYPEでのi番目の遺伝子の値 Msch(m):マシンmのスケジュール
Jsch(j):ジョブｊのスケジュール ProcessTime(j,m):ジョブjをマシンmで処理する場合の作業時間 Our research topics include … As you can see, the keyword ..
8
GYTPE2： JOBの割付アルゴリズム（２）
スケジュールの初期化 for i=1 ～ 総作業数（GTYPEの長さ）： J←Chrom(i), m←NextM(j),pt←ProcessTime(j,m); Msch(m)にptが挿入可能で、かつJsch(j)での最遅時間以後のもっとも早い時刻を開始時刻stとし求める Msch(m), Jsch(j)のｓｔ～st+ptの時間帯へのジョブjの現在の作業（マシンmを使う）を登録する Our research topics include … As you can see, the keyword ..
9
GYTPE2： JOBの割付アルゴリズム（３）
割付けの例 1 2 3 4 J1 M1,3 M2,2 M3,4 M4,1 J2 M4,2 M3,1 J3 M1,2 M3,2 M2,1 GTYPE: １２２２２３・・・ 機械 割付スケジュール Ｍ１： Ｍ２： Ｍ３： Ｍ４： Our research topics include … As you can see, the keyword ..
10
GYTPE2： JOBの割付アルゴリズム（３）
割付けの例 1 2 3 4 J1 M1,3 M2,2 M3,4 M4,1 J2 M4,2 M3,1 J3 M1,2 M3,2 M2,1 GTYPE: １２２２２３・・・ 機械 割付スケジュール Ｍ１：J1 J1 J1 Ｍ２： Ｍ３： Ｍ４： Our research topics include … As you can see, the keyword ..
11
GYTPE2： JOBの割付アルゴリズム（３）
割付けの例 1 2 3 4 J1 M1,3 M2,2 M3,4 M4,1 J2 M4,2 M3,1 J3 M1,2 M3,2 M2,1 GTYPE: １２２２２３・・・ 機械 割付スケジュール Ｍ１：J1 J1 J1 Ｍ２：J2 J2 Ｍ３： Ｍ４： Our research topics include … As you can see, the keyword ..
12
GYTPE2： JOBの割付アルゴリズム（３）
割付けの例 1 2 3 4 J1 M1,3 M2,2 M3,4 M4,1 J2 M4,2 M3,1 J3 M1,2 M3,2 M2,1 GTYPE: １２２２２３・・・ 機械 割付スケジュール Ｍ１：J1 J1 J1 Ｍ２：J2 J2 Ｍ３： Ｍ４： J2 J2 Our research topics include … As you can see, the keyword ..
13
GYTPE2： JOBの割付アルゴリズム（３）
割付けの例 1 2 3 4 J1 M1,3 M2,2 M3,4 M4,1 J2 M4,2 M3,1 J3 M1,2 M3,2 M2,1 GTYPE: １２２２２３・・・ 機械 割付スケジュール Ｍ１：J1 J1 J1 Ｍ２：J2 J2 Ｍ３： J2 Ｍ４： J2 J2 Our research topics include … As you can see, the keyword ..
14
GYTPE2： JOBの割付アルゴリズム（３）
割付けの例 1 2 3 4 J1 M1,3 M2,2 M3,4 M4,1 J2 M4,2 M3,1 J3 M1,2 M3,2 M2,1 GTYPE: １２２２２３・・・ 機械 割付スケジュール Ｍ１：J1 J1 J J2 J2 J2 Ｍ２：J2 J2 Ｍ３： J2 Ｍ４： J2 J2 Our research topics include … As you can see, the keyword ..
15
GYTPE2： JOBの割付アルゴリズム（３）
割付けの例 1 2 3 4 J1 M1,3 M2,2 M3,4 M4,1 J2 M4,2 M3,1 J3 M1,2 M3,2 M2,1 GTYPE: １２２２２３・・・ 機械 割付スケジュール Ｍ１：J1 J1 J1 J3 J3 J2 J2 J2 Ｍ２：J2 J2 Ｍ３： J2 Ｍ４： J2 J2 Our research topics include … As you can see, the keyword ..
16
GYTPE2： 交叉の工夫 親１の染色体： １2 3 2 ……… 親２の染色体： 3 3 1 3 ………
親１の染色体： １2 3 2 ……… 親２の染色体： ……… Our research topics include … As you can see, the keyword ..
17
GYTPE2： 交叉の工夫 ① ② ③ ④ 親１の染色体： 親２の染色体： ランダムに 部分を選ぶ
親１の染色体： 親２の染色体： ① ② ③ ④ ランダムに 部分を選ぶ Our research topics include … As you can see, the keyword ..
18
GYTPE2： 交叉の工夫 ① ② ③ ④ ① ② ③ ④ 親１の染色体： 親２の染色体： 以外の部分を子の染色体の対応部へコピーする
親１の染色体： 親２の染色体： ① ② ③ ④ 以外の部分を子の染色体の対応部へコピーする Our research topics include … As you can see, the keyword .. 子１の染色体： 子２の染色体： ① ② ③ ④
19
GYTPE2： 交叉の工夫 ① ② ③ ④ ① ② ③ ④ 親１の染色体： 親２の染色体： の部分を特別に処理して を構成する
親１の染色体： 親２の染色体： ① ② ③ ④ の部分を特別に処理して を構成する Our research topics include … As you can see, the keyword .. 子１の染色体： 子２の染色体： ① ② ③ ④
20
GYTPE2： 交叉の工夫 Step1： 同一遺伝子に印（＊）を付ける 親１： 1 7 3 3 1 5 4
親１： 親２： Our research topics include … As you can see, the keyword ..
21
GYTPE2： 交叉の工夫 Step1： 同一遺伝子に印（＊）を付ける 親１： 1 7 3 3 1 5 4 * * * x1 x2 x3 *
親１： * * * x1 x2 x3 * 親２： y1 * * * * y2 y3 Our research topics include … As you can see, the keyword ..
22
GYTPE2： 交叉の工夫 Step2： 印（＊）のついた遺伝子を子の部分染色体へ、位置を保存してうつす 親１： 1 7 3 3 1 5 4
親１： * * * x1 x2 x3 * 親２： y1 * * * * y2 y3 子１： 子２： Our research topics include … As you can see, the keyword ..
23
GYTPE2： 交叉の工夫 Step3： 残りの遺伝子を移す 親１： 1 7 3 3 1 5 4 * * * x1 x2 x3 *
親１： * * * x1 x2 x3 * 親２： y1 * * * * y2 y3 子１： 子２： Our research topics include … As you can see, the keyword ..
24
GYTPE2： 突然変異操作 親の染色体： １2 3 2 ……… Our research topics include …
親の染色体： １2 3 2 ……… Our research topics include … As you can see, the keyword ..
25
GYTPE2： 突然変異操作(2) 親の染色体： １2 3 2 ……… ランダムに位置を決める
親の染色体： １2 3 2 ……… ランダムに位置を決める Our research topics include … As you can see, the keyword ..
26
GYTPE2： 突然変異操作(3) 親の染色体： １2 3 2 ……… 遺伝子を交換する 子の染色体： １2 3 2 ………
親の染色体： １2 3 2 ……… 遺伝子を交換する Our research topics include … As you can see, the keyword .. 子の染色体： １2 3 2 ………
27
GYTPE3： PERTにおけるバイナリ表現
コンフリクトの解消方向を０，１とする GTYPE:上の解消方向をアーク数分並べたもの 交叉の工夫が必要ない Our research topics include … As you can see, the keyword ..
28
GYTPE3： PERTにおけるバイナリ表現
: 機械 に関する作業間 の選択対 : ジョブ i のj 番目のタスク E.g. 3 Jobs x 3 Machines 1 2 3 J1 M1,4 M2,8 M3,2 J2 M3,10 M2,9 J3 M3,6 M2,2 M1,3 Our research topics include … As you can see, the keyword ..
29
GYTPE3： PERTにおけるバイナリ表現
: 機械 に関する作業間 の選択対 E.g. Our research topics include … As you can see, the keyword ..
30
GYTPE3： PTYPEへの変換 : 機械 に関する作業間 の選択対 O12 O13 O11 O23 O21 O22 ＊ O33 O32
: 機械 に関する作業間 の選択対 O12 O13 O11 O23 O21 O22 ＊ Our research topics include … As you can see, the keyword .. O33 O32 O31
31
GYTPE3： PTYPEへの変換 O12 O13 O11 O21 O23 O22 ＊ O33 O32 O31
O21 O23 O22 ＊ Our research topics include … As you can see, the keyword .. O33 O32 O31
32
GYTPE3： PTYPEへの変換 すべての選択辺対を未解消にする
現在のグラフに対して未解消の辺を除去したスケジュールに対してクリティカルパスを求める コンフリクトが起こっていなければ終了 さもなければ、最も早いコンフリクトをGTYPEを参照して解消して２へもどる Our research topics include … As you can see, the keyword ..
33
GYTPE3：PERT (a) 2 8 4 ０ 4 10 9 6 2 3 解消される選択対 最早開始時刻 －
2 8 4 O11 O12 O13 ０ Our research topics include … As you can see, the keyword .. 4 10 O21 O23 O22 ＊ 9 6 2 3 O33 O32 O31
34
GYTPE3：PERT (b) 2 8 4 ０ 4 10 9 6 2 3 解消される選択対 最早開始時刻 －
2 8 4 O11 O12 O13 ０ Our research topics include … As you can see, the keyword .. 4 10 O21 O23 O22 ＊ 9 6 2 3 O33 O32 O31
35
GYTPE3：PERT (c) 2 8 4 ０ 4 10 9 6 2 3 解消される選択対 最早開始時刻 －
2 8 4 O11 O12 O13 ０ Our research topics include … As you can see, the keyword .. 4 10 O21 O23 O22 ＊ 9 6 2 3 O33 O32 O31
36
GYTPE3：PERT (d) 2 8 4 ０ 4 10 9 6 2 3 解消される選択対 最早開始時刻 －
2 8 4 O11 O12 O13 ０ Our research topics include … As you can see, the keyword .. 4 10 O21 O23 O22 ＊ 9 6 2 3 O33 O32 O31
37
GYTPE4： GTYPE1での交叉の工夫 P1: 3 3 3 2 1 1 2 1 2 P2: 2 2 1 3 2 3 1 1 3
Our research topics include … As you can see, the keyword ..
38
GYTPE4： GTYPE1での交叉の工夫 P1: 3 3 3 2 1 1 2 1 2 P2: 2 2 1 3 2 3 1 1 3
J1, J2, J3のうちランダムに１つを選ぶ Our research topics include … As you can see, the keyword ..
39
GYTPE4： GTYPE1での交叉の工夫 P1: 3 3 3 2 1 1 2 1 2 P2: 2 2 1 3 2 3 1 1 3
J1, J2, J3のうちランダムに１つを選ぶ 例：J2とする Our research topics include … As you can see, the keyword ..
40
GYTPE4： GTYPE1での交叉の工夫 P1: 3 3 3 2 1 1 2 1 2 P2: 2 2 1 3 2 3 1 1 3
Our research topics include … As you can see, the keyword ..
41
GYTPE4： GTYPE1での交叉の工夫 P1: 3 3 3 2 1 1 2 1 2 P2: 2 2 1 3 2 3 1 1 3
Our research topics include … As you can see, the keyword ..
42
GYTPE4： GTYPE1での交叉の工夫 P1: 3 3 3 2 1 1 2 1 2 P2: 2 2 1 3 2 3 1 1 3
C1: * * * 2 * * 2 * 2 C2: * * 2 * * * * Our research topics include … As you can see, the keyword ..
43
GYTPE4： GTYPE1での交叉の工夫 P1: 3 3 3 2 1 1 2 1 2 P2: 2 2 1 3 2 3 1 1 3
C1: C2: Our research topics include … As you can see, the keyword ..
44
レポート課題 JSSPのGAによる解法 問題例 Level2: CPM, PERT, JSSP by GA
１０ tough problems abz7, abz8, abz9 la21, la24, la25, la27 la29, la38, la40 Level2: CPM, PERT, JSSP by GA ASTROMIZER GASLAB Our research topics include … As you can see, the keyword ..
Similar presentations
