Heuristic algorithms for the marking construction problem of Petri nets
Satoshi Taoka, Toshimasa Watanabe · 2010
The marking construction problem (MCP) of Petri nets is defined as follows: “Given a Petri net N, an initial marking Miand a target marking Mt, construct a marking that is closest to Mtamong those which can be reached from Miby 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. This paper proposes two algorithms: MCA for (i) and MC _feideq_a for (ii), and compares their capability based on computing experiments.