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 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 (MAXLFS) or (ii) using an algorithm for MAXLFS. 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.
- 2011-09-01
著者
-
WATANABE Toshimasa
Graduate School of Engineering, Hiroshima University
-
Taoka Satoshi
Graduate School Of Engineering Hiroshima University
-
Watanabe Toshimasa
Graduate School Of Engineering Hiroshima Univ.
関連論文
- Time Complexity Analysis of the Legal Firing Sequence Problem of Petri Nets with Inhibitor Arcs(Concurrent Systems,Concurrent/Hybrid Systems: Theory and Applications)
- A 2-Approximation Algorithm 2-ABIS for 2-Vertex-Connectivity Augmentation of Specified Vertices in a Graph
- A (2 - 2/|L|)-Approximation Algorithm R2VS or R2ES to 2-Vertex- or 2-Edge-Connect Specified Vertices in a Graph
- Efficiently Computing Minimal-Support Nonnegative Integer Invariants of Petri Nets
- Two Enhanced Heuristic Algorithms for the Minimum Initial Marking Problem of Petri Nets
- Improved Heuristic Algorithms for Minimizing Initial Markings of Petri Nets(Concurrent/Hybrid Systems : Theory and Applications)
- Enhancing PC Cluster-Based Parallel Branch-and-Bound Algorithms for the Graph Coloring Problem
- Enhanced Approximation Algorithms for Maximum Weight Matchings of Graphs
- Performance Comparison of Algorithms for the Dynamic Shortest Path Problem(Selected Papers from the 19th Workshop on Circuits and Systems in Karuizawa)
- On Minimum k-Edge-Connectivity Augmentation for Specified Vertices of a Graph with Upper Bounds on Vertex-Degree(Selected Papers from the 18th Workshop on Circuits and Systems in Karuizawa)
- A 2-Approximation Algorithm to (k+1)-Edge-Connect a Specified Set of Vertices in a k-Edge-Connected Graph(Discrete Mathematics and Its Applications)
- A Linear Time Algorithm for Bi-Connectivity Augmentation of Graphs with Upper Bounds on Vertex-Degree Increase(Selected Papers from the 17th Workshop on Circuits and Systems in Karuizawa)
- Experimental Evaluation of Maximum-Supply Partitioning Algorithms for Demand-Supply Graphs(Selected Papers from the 18th Workshop on Circuits and Systems in Karuizawa)
- Siphon-Trap-Based Algorithms for Efficiently Computing Petri Net Invariants(Selected Papers from the 17th Workshop on Circuits and Systems in Karuizawa)
- The Marking Construction Problem of Petri Nets and Its Heuristic Algorithms
- A Fast Algorithm for Augmenting Edge-Connectivity by One with Bipartition Constraints
- Computing-Based Performance Analysis of Approximation Algorithms for the Minimum Weight Vertex Cover Problem of Graphs
- Two Heuristic Algorithms for the Minimum Initial Marking Problem of Timed Petri Nets