| 講演名 | 2003/7/29 ペトリネット最小初期マーキング問題に対する発見的解法AADの高速化(コンカレント工学一般) 田岡 智志, 渡邉 敏正, 西 晋一郎, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 本稿で対象とするペトリネットの最小初期マーキング問題(MIM)は、システムの最適初期資源配分に関わる問題の一つである。MIMはNP-困難であることが知られており、いくつかの発見的解法が提案され、計算機実験比較によりAADが既存解法の中で最も性能が良いことが示されている。しかしながら、入力データのサイズが巨大になると計算時間が非常に長くなり、求解が困難となることもある。よって、本稿では、AADを解精度を維持しながら高速化し、計算機実験によりその効果を検証する。 |
| 抄録(英) | In this paper we consider the minimum initial marking problem (MIM) of Petri nets, one of optimum initial resource allocation problems for variable systems. MIM is known to be NP-hard, and some heuristic algorithms have been proposed. It is shown through computational experiments that a heuristic algorithm AAD has the highest capability among existing ones. AAD, however, requires too much computation time to be practical as the data sizes become huge. This paper proposes how to shorten computation time of AAD without reducing sharpness of solutions, and shows experimental evaluation. |
| キーワード(和) | ペトリネット / 最小初期マーキング問題 / 発火系列問題 / 発見的解法 |
| キーワード(英) | Petri nets / minimum initial marking problems / legal firing sequence problems / heuristic algorithms |
| 資料番号 | CST2003-10 |
| 発行日 |
| 研究会情報 | |
| 研究会 | CST |
|---|---|
| 開催期間 | 2003/7/29(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Concurrent System Technology (CST) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | ペトリネット最小初期マーキング問題に対する発見的解法AADの高速化(コンカレント工学一般) |
| サブタイトル（和） | |
| タイトル（英） | Improving a Heuristic Algorithm AAD for the Minimum Initial Marking Problem of Petri Nets |
| サブタイトル（和） | |
| キーワード(1)（和/英） | ペトリネット / Petri nets |
| キーワード(2)（和/英） | 最小初期マーキング問題 / minimum initial marking problems |
| キーワード(3)（和/英） | 発火系列問題 / legal firing sequence problems |
| キーワード(4)（和/英） | 発見的解法 / heuristic algorithms |
| 第 1 著者 氏名（和/英） | 田岡 智志 / Satoshi TAOKA |
| 第 1 著者 所属（和/英） | 広島大学大学院工学研究科情報工学専攻 Graduate School of Engineering, Hiroshima University |
| 第 2 著者 氏名（和/英） | 渡邉 敏正 / Toshimasa WATANABE |
| 第 2 著者 所属（和/英） | 広島大学大学院工学研究科情報工学専攻 Graduate School of Engineering, Hiroshima University |
| 第 3 著者 氏名（和/英） | 西 晋一郎 / Shin'ichiro NISHI |
| 第 3 著者 所属（和/英） | DoCoMo中国 DoCoMo Chugoku |
| 発表年月日 | 2003/7/29 |
| 資料番号 | CST2003-10 |
| 巻番号（vol） | vol.103 |
| 号番号（no） | 247 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |