題名 | トークンの余剰を考慮した解の存在判定法に基づくペトリネット発火系列探索法の性能強化 |
著者 | *竹歳 裕一郎 (広島大学大学院工学研究科), 山内 雅弘 (近畿大学工学部工学電子情報工学科), 田岡 智志, 渡邉 敏正 (広島大学大学院工学研究科) |
Page | pp. 169 - 170 |
Keyword | ペトリネット, 発火系列問題 |
Abstract | ペトリネットの発火系列問題(LFS)はペトリネットに関連する諸問題に含まれる基本的な 問題であるが,一般にNP-困難である.そこで,LFSを近似的に解く目的で,最大発火系列問題MAX-LFS:「ペトリネット,初期マーキング,発火回数ベクトルが与えられたとき,初期マーキングから順次発火可能で各トランジションが指定された発火回数を超えない回数出現するようなできるだけ長い発火系列を求めよ」に対する発見的解法がいくつか提案されている.本研究は,トークン増減によるトランジション選択法を適用した発見的アルゴリズムを提案して実験的に性能 評価を行う. |
題名 | 最小初期マーキング問題解法のトランジション選択とトークン付加の指標改良による性能強化 |
著者 | *落岩 諭 (広島大学工学部), 田岡 智志, 渡邉 敏正 (広島大学大学院工学研究科) |
Page | pp. 171 - 172 |
Keyword | ペトリネット, MIM |
Abstract | ペトリネットはシステムの解析などに広く利用されている強力なモデリングツールである.その基本的な問題の1つに最小初期マーキング問題(MIM)があり,本稿では提案されているMIMの発見的解法の中で最も高精度であることが知られているAAD+に着目して,さらなる高精度化を組み込んだ発見的解法AADOを提案し,計算機実験によりその有用性を示す. |
題名 | ペトリネットのサイフォン・トラップに基づく効率的インバリアント算出法 |
著者 | *吉川 ヤマト (広島大学工学部), 近田 智宏, 田岡 智志, 渡邉 敏正 (広島大学大学院 工学研究科) |
Page | p. 173 |
Keyword | ペトリネット, インバリアント, サイフォン・トラップ |
題名 | 動的環境における巡回セールスマン問題の解法に関する検討 |
著者 | *井原 健一, 堀内 匡 (松江工業高等専門学校) |
Page | pp. 174 - 175 |
Keyword | 巡回セールスマン問題, 動的環境, 最適化 |
題名 | Well-Structured WFネットに対する最長パスに着目した並列度のヒューリスティックな計算について |
著者 | *金子 侑史, 山口 真悟 (山口大学大学院理工学研究科), 葛 崎偉 (山口大学教育学部), 田中 稔 (山口大学大学院理工学研究科) |
Page | pp. 176 - 177 |
Keyword | WFネット, well-structured, PARAdeg, 最長パス, ヒューリスティックアルゴリズム |
Abstract | ワークフローの解析や性能評価には、ワークフローをモデル化したペトリネットであるWFネットが広く用いられており、構造的に良いWFネットであることを保証する重要なサブクラスとしてwell-structuredがある。これまでにWFネットの並列性を評価する尺度として並列度PARAdegを定義し、well-structured WFネットの並列度PARAdegの計算は手に負えないことが明らかにしており、条件分岐構造の入れ子構造を利用したヒューリスティックアルゴリズムを提案している。しかしこのアルゴリズムは、最悪の場合、一番PARAdegの値が低くなる発火系列を選択してしまう問題がある。本稿では最長パスに着目してこの問題を軽減するヒューリスティックアルゴリズムを提案する。 |