| 講演名 | 2007-01-26 well-structured WFネットの構造解析とPARAdegの近似計算について(コンカレントシステム,一般) 金子 侑史, 山口 真悟, 葛 崎偉, 田中 稔, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 本稿では,与えられたWFネットがwell-structuredであるかどうかを多項式時間で判定するアルゴリズムを明らかにする.これはWFネットのノード間の経路数と最大フローの値が一致する性質を利用し,well-stuructured WFネットの定義を満たしているかどうかによって判定する.well-structured WFネットはacyclicでさえ,その並列度PARAdegを計算する問題は手に負えない(intractable)ことが知られている.そこで我々はそのヒューリステックアルゴリズムを提案する.そして150個のネットに対して,提案したアルゴリズムを用いてPARAdegを計算し,その値と真値との比較を行った.提案したアルゴリズムは,その精度が90%以上であることから,有効であるといえる. |
| 抄録(英) | In this paper, we give a polynomial algorithm to decide whether a given WF-net is well-structured. This algorithm is based on the max-flow min-cut technique. It is known that even if a given well-structured WF-net is acyclic, the problem of computing its PARAdeg is intractable. Therefore we propose a heuristic algorithm to compute its PARAdeg. Then we evaluated our heuristic algorithm through the computaiton of PARAdeg for 150 nets. We can say from the evaluation results that our heuristic algorithm is efficient because its accuracy is more than 90%. |
| キーワード(和) | ワークフローネット / well-structured / PARAdeg / ヒューリスティックアルゴリズム |
| キーワード(英) | workflow net / well-structured / PARAdeg / heuristic algorithm |
| 資料番号 | CST2006-40 |
| 発行日 |
| 研究会情報 | |
| 研究会 | CST |
|---|---|
| 開催期間 | 2007/1/19(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Concurrent System Technology (CST) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | well-structured WFネットの構造解析とPARAdegの近似計算について(コンカレントシステム,一般) |
| サブタイトル（和） | |
| タイトル（英） | On Structure Analisis and Approximate Computation of PARAdeg for Acyclic Well-Structured Work flow Nets |
| サブタイトル（和） | |
| キーワード(1)（和/英） | ワークフローネット / workflow net |
| キーワード(2)（和/英） | well-structured / well-structured |
| キーワード(3)（和/英） | PARAdeg / PARAdeg |
| キーワード(4)（和/英） | ヒューリスティックアルゴリズム / heuristic algorithm |
| 第 1 著者 氏名（和/英） | 金子 侑史 / Yuji KANEKO |
| 第 1 著者 所属（和/英） | 山口大学大学院理工学研究科 Graduate School of Science and Engineering, Yamaguchi University |
| 第 2 著者 氏名（和/英） | 山口 真悟 / Shingo YAMAGUCHI |
| 第 2 著者 所属（和/英） | 山口大学大学院理工学研究科 Graduate School of Science and Engineering, Yamaguchi University |
| 第 3 著者 氏名（和/英） | 葛 崎偉 / Qi-Wei GE |
| 第 3 著者 所属（和/英） | 山口大学教育学部 Faculty of Education, Yamaguchi University |
| 第 4 著者 氏名（和/英） | 田中 稔 / Minoru TANAKA |
| 第 4 著者 所属（和/英） | 山口大学大学院理工学研究科 Graduate School of Science and Engineering, Yamaguchi University |
| 発表年月日 | 2007-01-26 |
| 資料番号 | CST2006-40 |
| 巻番号（vol） | vol.106 |
| 号番号（no） | 502 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |