シミュレーション学講義　第＊＊回スケジューリング問題とＪＳＳＰ.

Slides:

Advertisements

Similar presentations

多目的ＧＡに対するパレート最適個体の分布制御九州大学大学院工学府知能機械システム専攻徳井宏司.

Advertisements

情報基盤アルゴリズムとしてのメタヒューリスティクスの研究茨木俊秀、巳波弘佳、藤原洋志、千葉英史、関口良行（関西学院大学）、藤重悟（京都大学）、柳浦睦憲（名古屋大学）、野々部宏司（法政大学）、梅谷俊治（電気通信大学）

シミュレーション論Ⅰ 第 12 回様々なシミュレーション手法. 第１１回のレポート回答例（例）講義に出席するかどうかのシミュレーション・セルオートマトン法を用いて、ある講義の出席人数をシミュレーションする・各セルを受講者とし、隣接するセルを各自の友人と考え、「自分の友人のうち半数がサボったら自分も講義を休む」

三木光範（同志社大学工学部）廣安知之（同志社大学工学部）花田良子（同志社大学工学部学部生）水田伯典（同志社大学大学院）ジョブショップスケジューリング問題への分散遺伝的アルゴリズムの適用 Distributed Genetic Algorithm for Job-shop.

MicroAVS 超入門赤塚浩太. MicroAVS とは Visualization Tool Excel Java 膨大，高度なデータ処理が困難高度なプログラミング能力必要誰でも簡単に可視化できるツールの必要性 Micro AVS.

遺伝的アルゴリズムにおけるランドスケープによる問題のクラス分類

リフレッシュ型分散遺伝的アルゴリズムの組み合わせ最適化問題への適用

到着時刻と燃料消費量を同時に最適化する船速・航路計画

区間グラフにおける区間表現からMPQ-treeを効率よく構成するアルゴリズム

正規表現からのDFA直接構成.

　　スケジュール管理手法PERT－Time 　　　　　解　説　　　“最早開始時間計算のアルゴリズム”

第2回　プロセス管理ジョブ、プロセスとは？プロセスの状態遷移プロセス制御ブロックスケジューリング.

ヒープソートの演習第13回.

生産スケジューリング.

遺伝的アルゴリズム　新川　大貴.

対話型遺伝的アルゴリズムを用いた室内レイアウトシステムの開発

On the Enumeration of Colored Trees

遺伝的アルゴリズム概説 An Outline of Parallel Distributed Genetic Algorithms

ＰＣクラスタにおける２個体分散遺伝的アルゴリズムの高速化

群論とルービックキューブ白柳研究室　水野貴裕.

Problem G : Entangled Tree

モード付き並列機械におけるオンラインスケジューリング

遺伝アルゴリズムによる NQueen解法 ~遺伝補修飾を用いた解探索の性能評価~

分散遺伝的アルゴリズムによる各種クラスタのベンチマーク

情報工学科 05A2301 樽美澄香（Tarumi Sumika)

システム開発実験No.７　　　　　　　解　説　　　　　　“論理式の簡略化方法”.

データ構造とアルゴリズム第6回の2 木～データ構造（3）～.

第11講: 平成18年12月 8日 (金) 4限 E352教室グラフ (1).

ヒープソートの復習.

ロジスティクス工学第9章スケジューリングモデル補助資料：OptSeqによるスケジューリング入門 logopt

スケジューリング最適化エンジン ― RCPSPによるアプローチ

MPIを用いた並列処理～GAによるTSPの解法～

遺伝的アルゴリズムへの統計力学的アプローチ大阪大学大学院理学研究科鈴木譲 CISJ2005 於早稲田大学理工学部

電気・機械・情報概論 VBAプログラミング第2回 2018年7月2日

前回の練習問題.

オペレーティングシステムJ/K (仮想記憶管理)

レジスタの割付け中田育男著コンパイラの構成と最適化朝倉書店, 1999年第１２章５節.

遺伝的アルゴリズムを用いた構造物の最適形状探索のプログラムの作成

第9回優先度つき待ち行列，ヒープ，二分探索木

日程計画 (scheduling) 大規模なプロジェクトの日程を計画し、その進行を管理する手法。

スケジューリング最適化システム WebSeqのご紹介

スケジューリング最適化システム OptSeq II 補助資料：OptSeq II によるスケジューリング入門トライアルバージョン

A Simple Algorithm for Generating Unordered Rooted Trees

連続領域におけるファジィ制約充足問題の反復改善アルゴリズムによる解法 Solving by heuristic repair Algorithm of the Fuzzy Constraint Satisfaction Problems with Continuous Domains 北海道大学.

or-3. 作業リスト，スケジューリング，PERT図（オペレーションズリサーチを Excel で実習するシリーズ）

Genetic Algorithm-based Partial Least Squares GAPLS Genetic Algorithm-based Support Vector Regression GASVR 明治大学理工学部応用化学科データ化学工学研究室金子弘昌.

需要点,供給点,辺容量を持つ木の分割アルゴリズム

高度プログラミング演習（０１）.

アルゴリズムとデータ構造 --- 理論編 --- 山本真基

配送計画最適化システム WebMETROのご紹介

Data Clustering: A Review

遺伝アルゴリズムによる NQueen解法 ~問題特性に着目した突然変異方法の改善~

第9回優先度つき待ち行列，ヒープ，二分探索木

遺伝的アルゴリズム (GA) を活用したスペクトルの波長選択および時系列データにおけるプロセス変数かつその時間遅れ (ダイナミクス) の選択明治大学理工学部応用化学科データ化学工学研究室金子弘昌.

アルゴリズムとデータ構造 2012年7月2日

アルゴリズムとデータ構造 2011年6月28日

ヒープソートの復習第12回.

アルゴリズムとデータ構造 2013年7月2日

表紙分散遺伝的アルゴリズムのための新しい交叉法.

アルゴリズムとデータ構造 --- 理論編 --- 山本真基

or-6. 待ち行列シミュレーション（オペレーションズリサーチを Excel で実習するシリーズ）

情報工学科 05A2301 樽美澄香（Tarumi Sumika)

ヒープソート.

分散遺伝的アルゴリズムにおけるパラメータの検討

情報A 第１９回授業 06情報伝達の工夫プレゼンテーションソフトウェア

スケジューリングってなんだ？－やり方ひとつで大きく変わる

グラフの列挙中野　眞一　　　（群馬大学） 2019/9/14 列挙学校.

点素パス問題に対するアルゴリズム小林佑輔東京大学大学院情報理工学系研究科組合せ最適化セミナー 2012 年 7月 13日

アノテーションガイドラインの管理を行うアノテーションシステムの提案

各種荷重を受ける中空押出形成材の構造最適化

Presentation transcript:

シミュレーション学講義　第＊＊回スケジューリング問題とＪＳＳＰ

スケジューリング問題ＪＳＳＰ（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 ..

ディスパッチング・ルール Jobの割付の優先規則コンフリクトの起こったときの解消方法 Rules: SPT: Shortest processing time EDD: Earliest due date SLACK FIFO RANDOM ... ect. Our research topics include … As you can see, the keyword ..

GAによる解法 GTYPE → PTYPE ：いかにデザインするか？適合度はどうするか？各種パラメータ集団数最大世代数交叉率突然変異率 Our research topics include … As you can see, the keyword ..

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 ..

GYTPE2：順序表現遺伝子→次にどのジョブを優先して配置するかを指定するジョブ番号を機械の数分並べる例：　３３３２１１２１２　　：　３ジョブｘ３マシン遺伝子の左から出現する番号を優先する作業時間を考慮しガントチャートに配置する交叉の工夫が必要 Our research topics include … As you can see, the keyword ..

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 ..

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 ..

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 ..

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 ..

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: １２２２２３・・・機械　　割付スケジュール 1 2 3 4 5 6 7 8 Ｍ１：J1 J1 J1 Ｍ２：J2 J2 Ｍ３：Ｍ４： Our research topics include … As you can see, the keyword ..

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: １２２２２３・・・機械　　割付スケジュール 1 2 3 4 5 6 7 8 Ｍ１：J1 J1 J1 Ｍ２：J2 J2 Ｍ３：Ｍ４： J2 J2 Our research topics include … As you can see, the keyword ..

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: １２２２２３・・・機械　　割付スケジュール 1 2 3 4 5 6 7 8 Ｍ１：J1 J1 J1 Ｍ２：J2 J2 Ｍ３： J2 Ｍ４： J2 J2 Our research topics include … As you can see, the keyword ..

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: １２２２２３・・・機械　　割付スケジュール 1 2 3 4 5 6 7 8 Ｍ１：J1 J1 J1 J2 J2 J2 Ｍ２：J2 J2 Ｍ３： J2 Ｍ４： J2 J2 Our research topics include … As you can see, the keyword ..

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: １２２２２３・・・機械　　割付スケジュール 1 2 3 4 5 6 7 8 Ｍ１：J1 J1 J1 J3 J3 J2 J2 J2 Ｍ２：J2 J2 Ｍ３： J2 Ｍ４： J2 J2 Our research topics include … As you can see, the keyword ..

GYTPE2：交叉の工夫親１の染色体：１2 3 2 ……… 親２の染色体： 3 3 1 3 ……… 親１の染色体：　１2 3 2 ……… 親２の染色体：　3 3 1 3 ……… Our research topics include … As you can see, the keyword ..

GYTPE2：交叉の工夫 ① ② ③ ④ 親１の染色体：親２の染色体：ランダムに部分を選ぶ親１の染色体：　親２の染色体：　 ① ② ③ ④ ランダムに　　　　部分を選ぶ Our research topics include … As you can see, the keyword ..

GYTPE2：交叉の工夫 ① ② ③ ④ ① ② ③ ④ 親１の染色体：親２の染色体：以外の部分を子の染色体の対応部へコピーする親１の染色体：　親２の染色体：　 ① ② ③ ④ 　　　　以外の部分を子の染色体の対応部へコピーする Our research topics include … As you can see, the keyword .. 子１の染色体：　子２の染色体：　 ① ② ③ ④

GYTPE2：交叉の工夫 ① ② ③ ④ ① ② ③ ④ 親１の染色体：親２の染色体：の部分を特別に処理してを構成する親１の染色体：　親２の染色体：　 ① ② ③ ④ 　　　　の部分を特別に処理して　　　　を構成する Our research topics include … As you can see, the keyword .. 子１の染色体：　子２の染色体：　 ① ② ③ ④

GYTPE2：交叉の工夫 Step1：同一遺伝子に印（＊）を付ける親１： 1 7 3 3 1 5 4 親１：　 1 7 3 3 1 5 4 親２： 2 7 3 1 4 7 6 Our research topics include … As you can see, the keyword ..

GYTPE2：交叉の工夫 Step1：同一遺伝子に印（＊）を付ける親１： 1 7 3 3 1 5 4 * * * x1 x2 x3 * 親１：　 1 7 3 3 1 5 4 * * * x1 x2 x3 * 親２： 2 7 3 1 4 7 6 y1 * * * * y2 y3 Our research topics include … As you can see, the keyword ..

GYTPE2：交叉の工夫 Step2：印（＊）のついた遺伝子を子の部分染色体へ、位置を保存してうつす親１： 1 7 3 3 1 5 4 親１：　 1 7 3 3 1 5 4 * * * x1 x2 x3 * 親２： 2 7 3 1 4 7 6 y1 * * * * y2 y3 子１：　 - 7 3 1 4 - - 子２： 1 7 3 - - - 4 Our research topics include … As you can see, the keyword ..

GYTPE2：交叉の工夫 Step3：残りの遺伝子を移す親１： 1 7 3 3 1 5 4 * * * x1 x2 x3 * 親１：　 1 7 3 3 1 5 4 * * * x1 x2 x3 * 親２： 2 7 3 1 4 7 6 y1 * * * * y2 y3 子１：　 3 7 3 1 4 1 5 子２： 1 7 3 2 7 6 4 Our research topics include … As you can see, the keyword ..

GYTPE2：突然変異操作親の染色体：１2 3 2 ……… Our research topics include … 親の染色体：　１2 3 2 ……… Our research topics include … As you can see, the keyword ..

GYTPE2：突然変異操作(2) 親の染色体：１2 3 2 ……… ランダムに位置を決める親の染色体：　１2 3 2 ……… ランダムに位置を決める Our research topics include … As you can see, the keyword ..

GYTPE2：突然変異操作(3) 親の染色体：１2 3 2 ……… 遺伝子を交換する子の染色体：１2 3 2 ……… 親の染色体：　１2 3 2 ……… 遺伝子を交換する Our research topics include … As you can see, the keyword .. 子の染色体：　１2 3 2 ………

GYTPE3： PERTにおけるバイナリ表現コンフリクトの解消方向を０，１とする GTYPE:上の解消方向をアーク数分並べたもの交叉の工夫が必要ない Our research topics include … As you can see, the keyword ..

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 ..

GYTPE3： PERTにおけるバイナリ表現 : 機械に関する作業間の選択対 E.g.　 Our research topics include … As you can see, the keyword ..

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

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

GYTPE3： PTYPEへの変換すべての選択辺対を未解消にする現在のグラフに対して未解消の辺を除去したスケジュールに対してクリティカルパスを求めるコンフリクトが起こっていなければ終了さもなければ、最も早いコンフリクトをGTYPEを参照して解消して２へもどる Our research topics include … As you can see, the keyword ..

GYTPE3：PERT (a) 2 8 4 ０ 4 10 9 6 2 3 解消される選択対最早開始時刻－ 0 4 12 0 4 14 0 6 8 23 4 8 16 0 4 14 0 6 8 23 4 8 16 0 4 14 14 20 22 25 4 8 16 0 4 14 18 24 26 29 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

GYTPE3：PERT (b) 2 8 4 ０ 4 10 9 6 2 3 解消される選択対最早開始時刻－ 0 4 12 0 4 14 0 6 8 23 4 8 16 0 4 14 0 6 8 23 4 8 16 0 4 14 14 20 22 25 4 8 16 0 4 14 18 24 26 29 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

GYTPE3：PERT (c) 2 8 4 ０ 4 10 9 6 2 3 解消される選択対最早開始時刻－ 0 4 12 0 4 14 0 6 8 23 4 8 16 0 4 14 0 6 8 23 4 8 16 0 4 14 14 20 22 25 4 8 16 0 4 14 18 24 26 29 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

GYTPE3：PERT (d) 2 8 4 ０ 4 10 9 6 2 3 解消される選択対最早開始時刻－ 0 4 12 0 4 14 0 6 8 23 4 8 16 0 4 14 0 6 8 23 4 8 16 0 4 14 14 20 22 25 4 8 16 0 4 14 18 24 26 29 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

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 ..

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 ..

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 ..

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 ..

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 ..

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 2 * * 2 * * * * Our research topics include … As you can see, the keyword ..

GYTPE4： GTYPE1での交叉の工夫 P1: 3 3 3 2 1 1 2 1 2 P2: 2 2 1 3 2 3 1 1 3 C1: 1 3 3 2 1 1 2 3 2 C2: 2 2 3 3 2 3 1 1 1 Our research topics include … As you can see, the keyword ..

レポート課題 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 ..