Optimal legal firing sequence of Petri nets using linear programming

Petri nets (PNs) are a reliable graphical and mathematical modeling tool for the formal modeling and validation of systems. Applications of PNs include discrete event dynamic systems that are recognized are being concurrent, asynchronous, distributed, parallel, and/or nondeterministic. It is also a powerful formal method for the analysis of concurrent, embedded, and distributed finite state systems. The reachability analysis of PNs is strategically significant as it captures the dynamic behavior of the system as well as providing efficient verification of the correctness of the model. Few linear programming (LP)-based methods can be found that address the reachability problem, and some of these are suitable for optimal control problems. However, due to an inherent state explosion they are difficult to implement; other methods run easily into deadlock as they lack appropriate mechanisms to avoid the firing of critical transitions. In this paper an improved and easy to implement method is proposed that combines the Optimality Principle and Linear Programming (OP+LP) techniques to find an Optimal Legal Firing Sequence in PNs. This method can be applied to ordinary PNs with self-loops, avoids deadlocks, and can also be used for general PNs having cycles.