The Marking Construction Problem of Petri Nets and Its Heuristic Algorithms
The marking construction problem (MCP) of Petri nets is defined as follows: "Given a Petri net N, an initial marking M(i) and a target marking M(t), construct a marking that is closest to Mt among those which can be reached from M(i) 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 MCHF(k) and MC_feideq_a for (ii), where MCA (MC_feideq_a, respectively) is an improved version of MCG (MCHF(k)). Their performance is evaluated through results of computing experiment.
marking construction problem petri nets heuristic algorithms reachability problem computer experiments