| 講演名 | 2006-06-02 抑止辺を持つペトリネットにおける発火系列問題解法の実験的評価(コンカレントシステム,離散事象システム,ハイブリッドシステム,及び一般) 田岡 智志, 渡邉 敏正, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 抑止ペトリネットとは,ペトリネット(台ペトリネット)に抑止辺(発火を強制禁止する辺)を付加したものであり,そのモデル化能力はチューリングマシンと同等であることが既知である.抑止ペトリネットの発火系列問題(INLFS)とは『抑止ペトリネットIN,初期マーキングM,発火回数ベクトルXが与えられたとき,Mから順次発火可能で各トランジションtが丁度X(t)回出現する発火系列δを求めよ』と定義され、この問題はNP困難であることが知られている。本稿では、我々の既提案アルゴリズムに新たに発火トランジションの選択ルールを組み込んだ発見的解法RADQ_ODCを提案し、その性能を計算機実験に基づく比較により示す。 |
| 抄録(英) | Petri nets with inhibitor arcs are referred to as inhibitor-arc Petri nets. It is shown that modeling capability of inhibitor-arc Petri nets is equivalent to that of Turing machines. The legal firing sequence problem (INLFS) for inhibitor-arc Petri nets is defined by: "Given an inhibitor-arc Petri net IN, an initial marking M and a firing count vector X, find a firing sequence δ such that its firing starts from M and each transition t appears in δ exactly X(t) times as prescribed by X," and it is known that the problem is NP-hard. In the paper, we propose a new heuristic algorithm RADQ_ODC for INLFS. This is an improved version of an existing algorithm that we have already proposed, by incorporating a new selection rule of transition to be fired, and evaluate its capability through computational experimants. |
| キーワード(和) | ペトリネット / 抑止辺 / 抑止ペトリネット / 発火系列問題 / 発見的解法 |
| キーワード(英) | Petri nets / inhibitor arcs / inhibitor Petri nets / legal firing sequence problems / heuristic algorithms |
| 資料番号 | CST2006-6 |
| 発行日 |
| 研究会情報 | |
| 研究会 | CST |
|---|---|
| 開催期間 | 2006/5/26(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Concurrent System Technology (CST) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | 抑止辺を持つペトリネットにおける発火系列問題解法の実験的評価(コンカレントシステム,離散事象システム,ハイブリッドシステム,及び一般) |
| サブタイトル（和） | |
| タイトル（英） | Experiment-based Evaluation of Algorithms for the Legal Firing Sequence Problem of Petri Nets with Inhibitor Arcs |
| サブタイトル（和） | |
| キーワード(1)（和/英） | ペトリネット / Petri nets |
| キーワード(2)（和/英） | 抑止辺 / inhibitor arcs |
| キーワード(3)（和/英） | 抑止ペトリネット / inhibitor Petri nets |
| キーワード(4)（和/英） | 発火系列問題 / legal firing sequence problems |
| キーワード(5)（和/英） | 発見的解法 / heuristic algorithms |
| 第 1 著者 氏名（和/英） | 田岡 智志 / Satoshi TAOKA |
| 第 1 著者 所属（和/英） | 広島大学大学院工学研究科情報工学専攻 Graduate School of Engineering, Hiroshima University |
| 第 2 著者 氏名（和/英） | 渡邉 敏正 / Toshimasa WATANABE |
| 第 2 著者 所属（和/英） | 広島大学大学院工学研究科情報工学専攻 Graduate School of Engineering, Hiroshima University |
| 発表年月日 | 2006-06-02 |
| 資料番号 | CST2006-6 |
| 巻番号（vol） | vol.106 |
| 号番号（no） | 89 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |