| 講演名 | 2008-01-29 トランジションの超過発火を許したペトリネットの発火系列探索法(コンカレント工学一般、及び、CSTソリューションコンペティション2007発表会) 片山 幸喜, 田岡 智志, 渡邉 敏正, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 本稿ではペトリネットにおける下限制約発火系列問題(LBFS)に対する発見的解法を提案する。これは、よく知られた最大発火系列問題(MAX-LFS)を、スケジューリング問題への応用を考慮して拡張した問題である。まず、MAX-LFSにおける探索の局所化回避のために、新しいトランジション選択指標を提案する。その指標を導入したアルゴリズム(FEIDEQ+と呼ぶ)に入力データ900例を適用し、既存手法のうちで最も高性能な解法FEIDEQよりも解精度が約5%向上したことを示す。次に、LBFSの解法として、FEIDEQ+をLBFS用に改良したLB-1を提案し、計算機実験によりその性能評価を行う。 |
| 抄録(英) | In this paper, we propose a heuristic algorithm LB-1 for the Lower-Bounded Firing Sequence problem of Petri nets (LBFS for short). The problem is extended from the Maximum Legal Firing Sequence problem of Petri nets (MAX-LFS for short) so that it may be applied to the scheduling problems. First, for MAX-LFS, we propose a new selection rule of transitions to be fired so that local maxima may be avoided in searching firing sequences. Let FEIDEQ+ denote the algorithm in which this new rule is incorporated. Experiment results oftained by applying FEIDEQ+ to 900 test problems show that its sharpness of solutions is about 5% higher than that of FEIDEQ is known to have the heighest capability among the existing ones. Secondly, for LBFS, we propose a new algorithm LB-1 utilizing an improved version of FEIDEQ+, and evaluates it through computating experiment. |
| キーワード(和) | ペトリネット / 発火系列問題 / 超過発火 / 発見的解法 |
| キーワード(英) | Petri nets / legal firing sequence problems / excess firing of transitions / heuristic algorithms |
| 資料番号 | CST2007-54 |
| 発行日 |
| 研究会情報 | |
| 研究会 | CST |
|---|---|
| 開催期間 | 2008/1/22(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Concurrent System Technology (CST) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | トランジションの超過発火を許したペトリネットの発火系列探索法(コンカレント工学一般、及び、CSTソリューションコンペティション2007発表会) |
| サブタイトル（和） | |
| タイトル（英） | Finding Legal Firing Sequences Permitting Excess Firing of Transitions in Petri Nets |
| サブタイトル（和） | |
| キーワード(1)（和/英） | ペトリネット / Petri nets |
| キーワード(2)（和/英） | 発火系列問題 / legal firing sequence problems |
| キーワード(3)（和/英） | 超過発火 / excess firing of transitions |
| キーワード(4)（和/英） | 発見的解法 / heuristic algorithms |
| 第 1 著者 氏名（和/英） | 片山 幸喜 / Koki KATAYAMA |
| 第 1 著者 所属（和/英） | 広島大学大学院工学研究科情報工学専攻 Graduate School of Engineering, Hiroshima University |
| 第 2 著者 氏名（和/英） | 田岡 智志 / Satoshi TAOKA |
| 第 2 著者 所属（和/英） | 広島大学大学院工学研究科情報工学専攻 Graduate School of Engineering, Hiroshima University |
| 第 3 著者 氏名（和/英） | 渡邉 敏正 / Toshimasa WATANABE |
| 第 3 著者 所属（和/英） | 広島大学大学院工学研究科情報工学専攻 Graduate School of Engineering, Hiroshima University |
| 発表年月日 | 2008-01-29 |
| 資料番号 | CST2007-54 |
| 巻番号（vol） | vol.107 |
| 号番号（no） | 472 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |