| 講演名 | 2012-03-09 PBILと厳密解法の融合による繰返しスケジューリング問題の解法 粟國 信治, 森林 官, 名嘉村 盛和, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 組合せ最適化問題に対するアプローチとして,計算時間はかかっても厳密解を求める厳密解法と,短い時間で近似解を求めるヒューリスティクス解法がある.本論文では,これらの2つを組合わせて,解の質と計算時間のトレードオフを考慮しながら問題を解く方法を検討している.具体的には,定式化された混合整数計画問題においてメタヒューリスティクスにより,変数の一部分を固定することにより問題の次元を下げ,次元を下げた問題において,厳密解を求めるものである.本研究では,組み合わせ最適化問題として,繰り返しジョブショップスケジューリング問題(Cyclic Job Shop Scheduling Problem (CJSSP))を扱う. |
| 抄録(英) | For combinational optimization problems, we have two approaches; the exact methods and the approximated methods. The exact methods may require lots of computation time to get the exact solution even though the algorithms try to reduce the searching space, while metaheuristics can obtain approximated solutions within reasonable computation time. This paper proposes a hybrid method based on the exact method and metaheuristics for mixed integer programming problems. We can control in our hybrid method the tradeoff between the quality of approximated solutions and the computation time by adjusting the ratio of decision variables to be determined by metaheuristics to the ones by the exact method. We apply our hybrid method to cyclic job-hop scheduling problems and computational experiment shows the effectiveness of our proposed method. |
| キーワード(和) | 厳密解法 / ハイブリッドアプローチ / PBIL / 繰り返しスケジューリング問題 / 焼き鈍し法 |
| キーワード(英) | Exact methods / Metaheuristics / Hybrid approach / Population Based Incremental Learning (PBIL) / Cyclic Job Shop Scheduling Problem (CJSSP or CJSP) / Simulated Annealing (SA) |
| 資料番号 | MSS2011-86 |
| 発行日 |
| 研究会情報 | |
| 研究会 | MSS |
|---|---|
| 開催期間 | 2012/3/1(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Mathematical Systems Science and its applications(MSS) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | PBILと厳密解法の融合による繰返しスケジューリング問題の解法 |
| サブタイトル（和） | |
| タイトル（英） | A Hybrid Approach to Cyclic Scheduling Problems based on PBIL and Exact Algorithms |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 厳密解法 / Exact methods |
| キーワード(2)（和/英） | ハイブリッドアプローチ / Metaheuristics |
| キーワード(3)（和/英） | PBIL / Hybrid approach |
| キーワード(4)（和/英） | 繰り返しスケジューリング問題 / Population Based Incremental Learning (PBIL) |
| キーワード(5)（和/英） | 焼き鈍し法 / Cyclic Job Shop Scheduling Problem (CJSSP or CJSP) |
| 第 1 著者 氏名（和/英） | 粟國 信治 / Shinji AGUNI |
| 第 1 著者 所属（和/英） | 琉球大学大学院理工学研究科 Faculty of Engineering, Ryukyu University |
| 第 2 著者 氏名（和/英） | 森林 官 / Guan SENLIN |
| 第 2 著者 所属（和/英） | 琉球大学大学院理工学研究科 Faculty of Engineering, Ryukyu University |
| 第 3 著者 氏名（和/英） | 名嘉村 盛和 / Morikazu NAKAMURA |
| 第 3 著者 所属（和/英） | 琉球大学大学院理工学研究科 Faculty of Engineering, Ryukyu University |
| 発表年月日 | 2012-03-09 |
| 資料番号 | MSS2011-86 |
| 巻番号（vol） | vol.111 |
| 号番号（no） | 453 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |