| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2009-01-29 14:15 MAX-LFS解法と後処理の改良により性能強化されたペトリネットのマーキング構成問題解法 ○石井稔久・田岡智志・渡邉敏正（広島大）  CST2008-44 |
|
| 抄録 | （和） | ペトリネットのマーキング構成問題(MCP: Marking Construction Problem)は, 「ペトリネット $N$, 初期マーキング $M_i$, 目標マーキング $M_t$ が与えられた時,$M_i$からトランジションの発火により遷移可能なマーキングのうちで$M_t$に最も近いマーキングを求めよ」という問題である. MCPは一般にNP-困難であり, ２種類の解法の枠組みとして， (i) MAX-LFS解法を利用した解法, (ii) MAX-LFS解法を利用しない解法がある． $MCHF_k$または$MCGT_k$がそれぞれの枠組みの解法の中で高精度である ($k$はある整数). 本稿では，(i)に関して$MCHF_1$の改良版である$MC\_feideq\_gt_k$を提案する． また，(ii)に関しては発火トランジションの新しい選択指標{\em access}値を導入し，これに基づく解法$MCA$を提案する． さらに$MC\_feideq\_gt_k$の後処理$MCGT_k$を$MCA$に置き換えた解法 $MC\_feideq\_a$を提案する． 既存解法と3つの提案解法を計算機実験により性能比較をする. |
| （英） | The marking construction problem ({\bf MCP}) of Petri nets is defined as follows. ``Given a Petri net $N$, an initial marking $M_i$ and a target marking $M_t$, find a marking that is closest to $M_t$ among those which can be reached from $M_i$ by firing transitions.'' MCP is known to be NP-hard, and two schemas of algorithm design are known depending on whether any algorithm for MAX-LFS is utilized or not. $MCHF_k$ in the first schema and $MCGT_k$ is the second one are known to have the highest capability in each schema. As for the first schema, an algorithm $MC\_feideq\_gt_k$ is proposed as an improved version of $MCHF_1$. As for the second schema, we introduce a new measure {\em access} to be used in selecting on enable transition for rational firing, and an algorithm $MCA$ is proposed by incorporating {\em access} value. Furthermore, an algorithm $MC\_feideq\_a$ is proposed by replacing the post-processing $MCGT_k$ of $MC\_feideq\_gt_k$ with $MCA$. The three proposed algorithms are implemented and we compare their capability with existing algorithms through computing experiments. |
|
| キーワード | （和） | ペトリネット / マーキング構成問題 / 可達問題 / 発見的解法 / 計算機実験 / / / |
| （英） | Petri nets / marking construction problems / reachability problems / heuristic algorithms / computing experiments / / / | |
| 文献情報 | 信学技報, 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-44 |
|
| 研究会情報 | |
| 研究会 | MSS |
| 開催期間 | 2009-01-29 - 2009-01-30 |
| 開催地（和） | 神奈川県産業振興センター会議室(第一会議室) |
| 開催地（英） | Kanagawa Industrial Promotion Center |
| テーマ（和） | コンカレント工学一般 |
| テーマ（英） | Concurrent Systems |
| 講演論文情報の詳細 | |
| 申込み研究会 | MSS |
| 会議コード | 2009-01-CST |
| 本文の言語 | 日本語 |
| タイトル（和） | MAX-LFS解法と後処理の改良により性能強化されたペトリネットのマーキング構成問題解法 |
| サブタイトル（和） | |
| タイトル（英） | An Algorithm for the Marking Construction Problem of Petri Nets Enhanced by a MAX-LFS Algorithm and Improvement of Post-processing |
| サブタイトル（英） | |
| キーワード(1)（和/英） | ペトリネット / Petri nets |
| キーワード(2)（和/英） | マーキング構成問題 / marking construction problems |
| キーワード(3)（和/英） | 可達問題 / reachability problems |
| キーワード(4)（和/英） | 発見的解法 / heuristic algorithms |
| キーワード(5)（和/英） | 計算機実験 / computing experiments |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 石井 稔久 / Toshihisa Ishii / イシイ トシヒサ |
| 第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 14:15:00 |
| 発表時間 | 25分 |
| 申込先研究会 | MSS |
| 資料番号 | CST2008-44 |
| 巻番号（vol） | vol.108 |
| 号番号（no） | no.415 |
| ページ範囲 | pp.17-22 |
| ページ数 | 6 |
| 発行日 | 2009-01-22 (CST) |
[研究会発表申込システムのトップページに戻る]