The Marking Construction Problem of Petri Nets and Its Heuristic Algorithms
Summary :
The marking construction problem (MCP) of Petri nets is defined as follows: “Given a Petri net N, an initial marking Mi and a target marking Mt, construct a marking that is closest to Mt among those which can be reached from Mi by firing transitions.” MCP includes the well-known marking reachability problem of Petri nets. MCP is known to be NP-hard, and we propose two schemas of heuristic algorithms: (i) not using any algorithm for the maximum legal firing sequence problem (MAX LFS) or (ii) using an algorithm for MAX LFS. Moreover, this paper proposes four pseudo-polynomial time algorithms: MCG and MCA for (i), and MCHFk and MC_feideq_a for (ii), where MCA (MC_feideq_a, respectively) is an improved version of MCG (MCHFk). Their performance is evaluated through results of computing experiment.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E94-A No.9 pp.1833-1841
- Publication Date
- 2011/09/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.E94.A.1833
- Type of Manuscript
- PAPER
- Category
- Concurrent Systems
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Satoshi TAOKA, Toshimasa WATANABE, "The Marking Construction Problem of Petri Nets and Its Heuristic Algorithms" in IEICE TRANSACTIONS on Fundamentals,
vol. E94-A, no. 9, pp. 1833-1841, September 2011, doi: 10.1587/transfun.E94.A.1833.
Abstract: The marking construction problem (MCP) of Petri nets is defined as follows: “Given a Petri net N, an initial marking Mi and a target marking Mt, construct a marking that is closest to Mt among those which can be reached from Mi by firing transitions.” MCP includes the well-known marking reachability problem of Petri nets. MCP is known to be NP-hard, and we propose two schemas of heuristic algorithms: (i) not using any algorithm for the maximum legal firing sequence problem (MAX LFS) or (ii) using an algorithm for MAX LFS. Moreover, this paper proposes four pseudo-polynomial time algorithms: MCG and MCA for (i), and MCHFk and MC_feideq_a for (ii), where MCA (MC_feideq_a, respectively) is an improved version of MCG (MCHFk). Their performance is evaluated through results of computing experiment.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E94.A.1833/_p
Copy
@ARTICLE{e94-a_9_1833,
author={Satoshi TAOKA, Toshimasa WATANABE, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={The Marking Construction Problem of Petri Nets and Its Heuristic Algorithms},
year={2011},
volume={E94-A},
number={9},
pages={1833-1841},
abstract={The marking construction problem (MCP) of Petri nets is defined as follows: “Given a Petri net N, an initial marking Mi and a target marking Mt, construct a marking that is closest to Mt among those which can be reached from Mi by firing transitions.” MCP includes the well-known marking reachability problem of Petri nets. MCP is known to be NP-hard, and we propose two schemas of heuristic algorithms: (i) not using any algorithm for the maximum legal firing sequence problem (MAX LFS) or (ii) using an algorithm for MAX LFS. Moreover, this paper proposes four pseudo-polynomial time algorithms: MCG and MCA for (i), and MCHFk and MC_feideq_a for (ii), where MCA (MC_feideq_a, respectively) is an improved version of MCG (MCHFk). Their performance is evaluated through results of computing experiment.},
keywords={},
doi={10.1587/transfun.E94.A.1833},
ISSN={1745-1337},
month={September},}
Copy
TY - JOUR
TI - The Marking Construction Problem of Petri Nets and Its Heuristic Algorithms
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1833
EP - 1841
AU - Satoshi TAOKA
AU - Toshimasa WATANABE
PY - 2011
DO - 10.1587/transfun.E94.A.1833
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E94-A
IS - 9
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - September 2011
AB - The marking construction problem (MCP) of Petri nets is defined as follows: “Given a Petri net N, an initial marking Mi and a target marking Mt, construct a marking that is closest to Mt among those which can be reached from Mi by firing transitions.” MCP includes the well-known marking reachability problem of Petri nets. MCP is known to be NP-hard, and we propose two schemas of heuristic algorithms: (i) not using any algorithm for the maximum legal firing sequence problem (MAX LFS) or (ii) using an algorithm for MAX LFS. Moreover, this paper proposes four pseudo-polynomial time algorithms: MCG and MCA for (i), and MCHFk and MC_feideq_a for (ii), where MCA (MC_feideq_a, respectively) is an improved version of MCG (MCHFk). Their performance is evaluated through results of computing experiment.
ER -
English
