| Presentation | 2009-01-29 Enhancing an Algorithm for Finding Legal Firing Sequences of Petri Nets by Means of Controlling Token Supply Flow and Conflicting Transition-based Backtracking Kaigo HATANO, Satoshi TAOKA, Toshimasa WATANABE, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | The Maximum Legal Firing Sequence problem of Petri nets (MAX-LFS for short) is defined as follows: "Given a Petri net N, an initial marking M_0 and a firing count vector X, find a firing sequence δ that is legal on M_0 with respect to some X' with X'≦X and the length is maximum." MAX-LFS is known to be NP-hard. So, some huristic algorithms have been proposed. In this paper, we propose enhanced algorithms FEIDEQ_p and FEIDEQ_MK for MAX-LFS by means of (i) avoiding the generation of nonfirable transitions by searching sources that supply tokens and (ii) introducing backtracking based on conflicting transitions. It is shonw through computing experiments that the proposed algorithms have the highest capability among existing algorithms. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Petri nets / legal firing sequence problem / heuristic algorithms / promotion rules of transition firing / backtracking |
| Paper # | CST2008-43 |
| Date of Issue |
| Conference Information | |
| Committee | CST |
|---|---|
| Conference Date | 2009/1/22(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Concurrent System Technology (CST) |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Enhancing an Algorithm for Finding Legal Firing Sequences of Petri Nets by Means of Controlling Token Supply Flow and Conflicting Transition-based Backtracking |
| Sub Title (in English) | |
| Keyword(1) | Petri nets |
| Keyword(2) | legal firing sequence problem |
| Keyword(3) | heuristic algorithms |
| Keyword(4) | promotion rules of transition firing |
| Keyword(5) | backtracking |
| 1st Author's Name | Kaigo HATANO |
| 1st Author's Affiliation | Graduate School of Engineering, Hiroshima University() |
| 2nd Author's Name | Satoshi TAOKA |
| 2nd Author's Affiliation | Graduate School of Engineering, Hiroshima University |
| 3rd Author's Name | Toshimasa WATANABE |
| 3rd Author's Affiliation | Graduate School of Engineering, Hiroshima University |
| Date | 2009-01-29 |
| Paper # | CST2008-43 |
| Volume (vol) | vol.108 |
| Number (no) | 415 |
| Page | pp.pp.- |
| #Pages | 6 |
| Date of Issue | |