| 講演抄録／キーワード |
| 講演名 |
2005-07-01 14:05
ペトリネット初期マーキング最小化のための動作的デッドロック回避に基づく高速発見的解法
○田岡智志（広島大）・山内雅弘（近畿大）・渡邉敏正（広島大） |
| 抄録 |
（和） |
本稿で対象とするペトリネットの最小初期マーキング問題(MIM)は、システムの最適初期資源配分に関わる問題の一つである。MIM はNP-困難であることが知られており、いくつかの発見的解法が提案されている。計算機実験比較により、(1) AAD が既存解法の中で最も性能が良いが、入力データのサイズが巨大になると計算時間が膨大となり求解が困難となる、(2) AMIM+ は二番目に性能が良く、さらに巨大サイズのデータに対しても高速に解を求めること、が示されている。そこで巨大データを考慮し AMIM+ を高精度化した改良手法を提案し、計算機実験によりその効果を検証する。 |
| （英） |
In this paper we consider the minimum initial marking problem(MIM) of Petri nets, one of optimum initial resource allocation problems for variable systems. MIM is known to be NP-hard, and some heuristic algorithms have been proposed. It is shown through computational experiments that (1) a heuristic algorithm AAD has the highest capability among existing ones and requires too much computation time to be practical as the data sizes become huge; (2) AMIM+ has the second highest capability and produces a heuristic solution very fast even if the data size is too large. Then this paper proposes improved algorithms of AMIM+ and shows that, thorugh experimental evaluation, the proposed ones have higher capability than AMIM+. |
| キーワード |
（和） |
ペトリネット / 最小初期マーキング問題 / 発火系列問題 / 発見的解法 / / / / |
| （英） |
Petri nets / minimum initial marking problems / legal firing sequence problems / heuristic algorithms / / / / |
| 文献情報 |
信学技報, vol. 105, 2005年6月. |
| 資料番号 |
|
| 発行日 |
2005-06-24 (CST) |
| ISSN |
Print edition: ISSN 0913-5685 |
| PDFダウンロード |
|
| 研究会情報 |
| 研究会 |
MSS |
| 開催期間 |
2005-06-30 - 2005-07-01 |
| 開催地（和） |
自治会館(那覇) |
| 開催地（英） |
Jichi Kaikan(Naha) |
| テーマ（和） |
コンカレントシステム、離散事象システム、ハイブリッドシステム、および一般 |
| テーマ（英） |
Concurrent Systems, Discrete Event Systems and Hybrid Systems |
| 講演論文情報の詳細 |
| 申込み研究会 |
MSS |
| 会議コード |
2005-06-CST |
| 本文の言語 |
英語（日本語タイトルあり） |
| タイトル（和） |
ペトリネット初期マーキング最小化のための動作的デッドロック回避に基づく高速発見的解法 |
| サブタイトル（和） |
|
| タイトル（英） |
Fast Heuristic Algorithms based on Avoiding Occurrence of Behavioral Deadlocks for Minimizing Initial Markings of Petri Nets |
| サブタイトル（英） |
|
| キーワード(1)（和/英） |
ペトリネット / Petri nets |
| キーワード(2)（和/英） |
最小初期マーキング問題 / minimum initial marking problems |
| キーワード(3)（和/英） |
発火系列問題 / legal firing sequence problems |
| キーワード(4)（和/英） |
発見的解法 / heuristic algorithms |
| キーワード(5)（和/英） |
/ |
| キーワード(6)（和/英） |
/ |
| キーワード(7)（和/英） |
/ |
| キーワード(8)（和/英） |
/ |
| 第1著者 氏名（和/英/ヨミ） |
田岡 智志 / Satoshi Taoka / タオカ サトシ |
| 第1著者 所属（和/英） |
広島大学 (略称： 広島大)
Hiroshima Univ. (略称： Hiroshima Univ.) |
| 第2著者 氏名（和/英/ヨミ） |
山内 雅弘 / Masahiro Yamauchi / |
| 第2著者 所属（和/英） |
近畿大学 (略称： 近畿大)
Kinki Univ. (略称： Kinki Univ.) |
| 第3著者 氏名（和/英/ヨミ） |
渡邉 敏正 / Toshimasa Watanabe / ワタナベ トシマサ |
| 第3著者 所属（和/英） |
広島大学 (略称： 広島大)
Hiroshima Univ. (略称： Hiroshima Univ.) |
| 第4著者 氏名（和/英/ヨミ） |
/ / |
| 第4著者 所属（和/英） |
(略称： )
(略称： ) |
| 第5著者 氏名（和/英/ヨミ） |
/ / |
| 第5著者 所属（和/英） |
(略称： )
(略称： ) |
| 第6著者 氏名（和/英/ヨミ） |
/ / |
| 第6著者 所属（和/英） |
(略称： )
(略称： ) |
| 第7著者 氏名（和/英/ヨミ） |
/ / |
| 第7著者 所属（和/英） |
(略称： )
(略称： ) |
| 第8著者 氏名（和/英/ヨミ） |
/ / |
| 第8著者 所属（和/英） |
(略称： )
(略称： ) |
| 第9著者 氏名（和/英/ヨミ） |
/ / |
| 第9著者 所属（和/英） |
(略称： )
(略称： ) |
| 第10著者 氏名（和/英/ヨミ） |
/ / |
| 第10著者 所属（和/英） |
(略称： )
(略称： ) |
| 第11著者 氏名（和/英/ヨミ） |
/ / |
| 第11著者 所属（和/英） |
(略称： )
(略称： ) |
| 第12著者 氏名（和/英/ヨミ） |
/ / |
| 第12著者 所属（和/英） |
(略称： )
(略称： ) |
| 第13著者 氏名（和/英/ヨミ） |
/ / |
| 第13著者 所属（和/英） |
(略称： )
(略称： ) |
| 第14著者 氏名（和/英/ヨミ） |
/ / |
| 第14著者 所属（和/英） |
(略称： )
(略称： ) |
| 第15著者 氏名（和/英/ヨミ） |
/ / |
| 第15著者 所属（和/英） |
(略称： )
(略称： ) |
| 第16著者 氏名（和/英/ヨミ） |
/ / |
| 第16著者 所属（和/英） |
(略称： )
(略称： ) |
| 第17著者 氏名（和/英/ヨミ） |
/ / |
| 第17著者 所属（和/英） |
(略称： )
(略称： ) |
| 第18著者 氏名（和/英/ヨミ） |
/ / |
| 第18著者 所属（和/英） |
(略称： )
(略称： ) |
| 第19著者 氏名（和/英/ヨミ） |
/ / |
| 第19著者 所属（和/英） |
(略称： )
(略称： ) |
| 第20著者 氏名（和/英/ヨミ） |
/ / |
| 第20著者 所属（和/英） |
(略称： )
(略称： ) |
| 講演者 |
第1著者 |
| 発表日時 |
2005-07-01 14:05:00 |
| 発表時間 |
25分 |
| 申込先研究会 |
MSS |
| 資料番号 |
CST2005-13 |
| 巻番号（vol） |
vol.105 |
| 号番号（no） |
no.160 |
| ページ範囲 |
pp.41-46 |
| ページ数 |
6 |
| 発行日 |
2005-06-24 (CST) |