| 講演名 | 2009-01-29 トークン供給フロー制御と競合トランジションに基づく後退操作によるペトリネット発火系列探索法の性能強化 波多野 開悟, 田岡 智志, 渡邉 敏正, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | ペトリネットの最大発火系列問題(MAX-LFS)は「ペトリネットN,初期マーキングM_0,発火回数ベクトルXが与えられたとき,M_0から順次発火可能で各トランジションtがX(t)回を越えない回数出現するようなできるだけ長い発火系列を求めよ」と定義される.MAX-LFSの最適解(各トランジションtが丁度X(t)回出現する発火系列)を求めることは一般にNP-困難問題で,様々な発見的解法が提案されている.本稿では,(i)トークン供給源探索によって発火不能トランジションの発生を回避すること,(ii)競合トランジションに着目して後退操作時に戻るべきマーキングを選択する指標を導入すること,によりMAX-LFS解法の高精度化を図り,FEIDEQ_p,FEIDEQ_MKなる解法を提案する.計算機実験により既存解法との性能比較を行い,提案手法が最も高精度であることを示す. |
| 抄録(英) | The Maximum Legal Firing Sequence problem of Petri nets (MAX-LFS for short) is defined as follows: "Given a Petri net N, an initial marking M_0 and a firing count vector X, find a firing sequence δ that is legal on M_0 with respect to some X' with X'≦X and the length is maximum." MAX-LFS is known to be NP-hard. So, some huristic algorithms have been proposed. In this paper, we propose enhanced algorithms FEIDEQ_p and FEIDEQ_MK for MAX-LFS by means of (i) avoiding the generation of nonfirable transitions by searching sources that supply tokens and (ii) introducing backtracking based on conflicting transitions. It is shonw through computing experiments that the proposed algorithms have the highest capability among existing algorithms. |
| キーワード(和) | ペトリネット / 発火系列問題 / 発見的解法 / 発火促進則 / 後退操作 |
| キーワード(英) | Petri nets / legal firing sequence problem / heuristic algorithms / promotion rules of transition firing / backtracking |
| 資料番号 | CST2008-43 |
| 発行日 |
| 研究会情報 | |
| 研究会 | CST |
|---|---|
| 開催期間 | 2009/1/22(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Concurrent System Technology (CST) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | トークン供給フロー制御と競合トランジションに基づく後退操作によるペトリネット発火系列探索法の性能強化 |
| サブタイトル（和） | |
| タイトル（英） | Enhancing an Algorithm for Finding Legal Firing Sequences of Petri Nets by Means of Controlling Token Supply Flow and Conflicting Transition-based Backtracking |
| サブタイトル（和） | |
| キーワード(1)（和/英） | ペトリネット / Petri nets |
| キーワード(2)（和/英） | 発火系列問題 / legal firing sequence problem |
| キーワード(3)（和/英） | 発見的解法 / heuristic algorithms |
| キーワード(4)（和/英） | 発火促進則 / promotion rules of transition firing |
| キーワード(5)（和/英） | 後退操作 / backtracking |
| 第 1 著者 氏名（和/英） | 波多野 開悟 / Kaigo HATANO |
| 第 1 著者 所属（和/英） | 広島大学大学院工学研究科情報工学専攻 Graduate School of Engineering, Hiroshima University |
| 第 2 著者 氏名（和/英） | 田岡 智志 / Satoshi TAOKA |
| 第 2 著者 所属（和/英） | 広島大学大学院工学研究科情報工学専攻 Graduate School of Engineering, Hiroshima University |
| 第 3 著者 氏名（和/英） | 渡邉 敏正 / Toshimasa WATANABE |
| 第 3 著者 所属（和/英） | 広島大学大学院工学研究科情報工学専攻 Graduate School of Engineering, Hiroshima University |
| 発表年月日 | 2009-01-29 |
| 資料番号 | CST2008-43 |
| 巻番号（vol） | vol.108 |
| 号番号（no） | 415 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |