| Presentation | 2000/5/25 CST2000-8 Heuristic Algorithms for the Legal Firing Sequence and Related Problems of Petri Nets Ken Awa, Satoshi Taoka, Toshimasa Watanabe, |
|---|---|
| PDF Download Page | PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | The paper proposes a heuristic algorithm FSDB for the Maximum Legal Firing Sequence problem of Petri nets (MAX LFS for short) and evaluates it experimentally. FSDB is an improved version of the existing one FSD for LFS:backtracking operation is incorporated. As experimental evaluation, FSDB is applied to 2495 test problems to each of which existence of an exact solution is guaranteed, and it has produced an optimum solution to each of 1621 (65.0%) test problems, showig about 8% improvement from FSD. Furthermore, for five related problems each of which contains MAX LFS as a subproblem, we propose five heuristic algorithms in which MAX LFS is to be solved by FSDB. It is experimentally shown that capability of these algorithms is superior to existing ones. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Petri nets / legal firing sequence problems / siphons / heuristic algorithms / backtracking operations |
| Paper # | CST2000-8 |
| Date of Issue |
| Conference Information | |
| Committee | CST |
|---|---|
| Conference Date | 2000/5/25(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 | ENG |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | CST2000-8 Heuristic Algorithms for the Legal Firing Sequence and Related Problems of Petri Nets |
| Sub Title (in English) | |
| Keyword(1) | Petri nets |
| Keyword(2) | legal firing sequence problems |
| Keyword(3) | siphons |
| Keyword(4) | heuristic algorithms |
| Keyword(5) | backtracking operations |
| 1st Author's Name | Ken Awa |
| 1st Author's Affiliation | Graduate School of Engineering, Hiroshima University() |
| 2nd Author's Name | Satoshi Taoka |
| 2nd Author's Affiliation | Department of Circuits and Systems, Faculty of Engineering, Hiroshima University |
| 3rd Author's Name | Toshimasa Watanabe |
| 3rd Author's Affiliation | Department of Circuits and Systems, Faculty of Engineering, Hiroshima University |
| Date | 2000/5/25 |
| Paper # | CST2000-8 |
| Volume (vol) | vol.100 |
| Number (no) | 103 |
| Page | pp.pp.- |
| #Pages | 8 |
| Date of Issue | |