| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2009-01-29 13:50 トークン供給フロー制御と競合トランジションに基づく後退操作によるペトリネット発火系列探索法の性能強化 ○波多野開悟・田岡智志・渡邉敏正（広島大）  CST2008-43 |
|
| 抄録 | （和） | ペトリネットの最大発火系列問題 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 $\delta$ that is legal on $M_0$ with respect to some $X'$ with $X' \le 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 / / / | |
| 文献情報 | 信学技報, vol. 108, 2009年1月. | |
| 資料番号 | ||
| 発行日 | 2009-01-22 (CST) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | CST2008-43 |
|
| 研究会情報 | |
| 研究会 | MSS |
| 開催期間 | 2009-01-29 - 2009-01-30 |
| 開催地（和） | 神奈川県産業振興センター会議室(第一会議室) |
| 開催地（英） | Kanagawa Industrial Promotion Center |
| テーマ（和） | コンカレント工学一般 |
| テーマ（英） | Concurrent Systems |
| 講演論文情報の詳細 | |
| 申込み研究会 | MSS |
| 会議コード | 2009-01-CST |
| 本文の言語 | 日本語 |
| タイトル（和） | トークン供給フロー制御と競合トランジションに基づく後退操作によるペトリネット発火系列探索法の性能強化 |
| サブタイトル（和） | |
| タイトル（英） | 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 |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 波多野 開悟 / Kaigo Hatano / ハタノ カイゴ |
| 第1著者 所属（和/英） | 広島大学 (略称： 広島大) Hiroshima University (略称： Hiroshima Univ.) |
| 第2著者 氏名（和/英/ヨミ） | 田岡 智志 / Satoshi Taoka / タオカ サトシ |
| 第2著者 所属（和/英） | 広島大学 (略称： 広島大) Hiroshima University (略称： Hiroshima Univ.) |
| 第3著者 氏名（和/英/ヨミ） | 渡邉 敏正 / Toshimasa Watanabe / ワタナベ トシマサ |
| 第3著者 所属（和/英） | 広島大学 (略称： 広島大) Hiroshima University (略称： Hiroshima Univ.) |
| 講演者 | 第1著者 |
| 発表日時 | 2009-01-29 13:50:00 |
| 発表時間 | 25分 |
| 申込先研究会 | MSS |
| 資料番号 | CST2008-43 |
| 巻番号（vol） | vol.108 |
| 号番号（no） | no.415 |
| ページ範囲 | pp.11-16 |
| ページ数 | 6 |
| 発行日 | 2009-01-22 (CST) |
[研究会発表申込システムのトップページに戻る]