| 講演名 | 2000/5/25 CST2000-8 ペトリネット発火系列問題とその関連問題に対する発見的アルゴリズム 阿波 賢, 田岡 智志, 渡邉 敏正, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 本論文はペトリネットの最大発火系列問題(MAX LFSと略記)に対する性能の良い発見的アルゴリズムFSDBを提案し, それらの性能を実験的に評価する.FSDBは発火系列問題(LFSと略記)に対する既存解法FSDに後退操作を組込むことによって改良したものである.実験では, 解δの存在が保証されている2495個の入力例に対してFSDBを適用した.その結果, FSDBは1621個(65.0%)の入力例について実際にδを見つけ, FSDと比べて, 約8%改善された.さらに, MAX LFSを部分問題として内包している5つの関連問題に対しても, FSDBを組込んだ発見的解法を与え, その性能の良さを実験結果により示した. |
| 抄録(英) | The paper proposes a heuristic algorithm FSDB for the Maximum Legal Firing Sequence problem of Petri nets (MAX LFS for short) and evaluates it experimentally. FSDB is an improved version of the existing one FSD for LFS:backtracking operation is incorporated. As experimental evaluation, FSDB is applied to 2495 test problems to each of which existence of an exact solution is guaranteed, and it has produced an optimum solution to each of 1621 (65.0%) test problems, showig about 8% improvement from FSD. Furthermore, for five related problems each of which contains MAX LFS as a subproblem, we propose five heuristic algorithms in which MAX LFS is to be solved by FSDB. It is experimentally shown that capability of these algorithms is superior to existing ones. |
| キーワード(和) | ペトリネット / 発火系列問題 / サイフォン / 発見的アルゴリズム / バックトラッキング操作 |
| キーワード(英) | Petri nets / legal firing sequence problems / siphons / heuristic algorithms / backtracking operations |
| 資料番号 | CST2000-8 |
| 発行日 |
| 研究会情報 | |
| 研究会 | CST |
|---|---|
| 開催期間 | 2000/5/25(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Concurrent System Technology (CST) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | CST2000-8 ペトリネット発火系列問題とその関連問題に対する発見的アルゴリズム |
| サブタイトル（和） | |
| タイトル（英） | CST2000-8 Heuristic Algorithms for the Legal Firing Sequence and Related Problems of Petri Nets |
| サブタイトル（和） | |
| キーワード(1)（和/英） | ペトリネット / Petri nets |
| キーワード(2)（和/英） | 発火系列問題 / legal firing sequence problems |
| キーワード(3)（和/英） | サイフォン / siphons |
| キーワード(4)（和/英） | 発見的アルゴリズム / heuristic algorithms |
| キーワード(5)（和/英） | バックトラッキング操作 / backtracking operations |
| 第 1 著者 氏名（和/英） | 阿波 賢 / Ken Awa |
| 第 1 著者 所属（和/英） | 広島大学大学院工学研究科情報工学専攻 Graduate School of Engineering, Hiroshima University |
| 第 2 著者 氏名（和/英） | 田岡 智志 / Satoshi Taoka |
| 第 2 著者 所属（和/英） | 広島大学工学部第二類回路システム工学講座 Department of Circuits and Systems, Faculty of Engineering, Hiroshima University |
| 第 3 著者 氏名（和/英） | 渡邉 敏正 / Toshimasa Watanabe |
| 第 3 著者 所属（和/英） | 広島大学工学部第二類回路システム工学講座 Department of Circuits and Systems, Faculty of Engineering, Hiroshima University |
| 発表年月日 | 2000/5/25 |
| 資料番号 | CST2000-8 |
| 巻番号（vol） | vol.100 |
| 号番号（no） | 103 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |