Optimization algorithms applied to large petri nets

Petrinets (PNs) are important modeling tools for many practical control problems which include concurrent, asynchronous systems. Analysis of reachability is important in connection to the characterization of PN models and many important properties of P-Ns are related to it. Very little work has been reported which combines optimization theory with PNs, Computation of legal firing sequences (LFSs) to decide the reachability using well-established optimization techniques is the main focus of this dissertation. The fundamental problem of deciding the reachability with a pre-specified firing count vector u and the total firing instances d = Óm ui is considered. Related computational issues are also considered.

Different optimization techniques are investigated. Some of these techniques appear to be extremely elegant. .A set of problems related to the reachability analysis in PNs are identified. Starting with the basic reachability equations, the straightforward Single step LP method which uses only one iteration of linear programming (LP) is derived. .Another important method is based on the Optimality Principle (OP) which is combined with LP to derive the OP-based LP method. With considerable problem sizes, the combinatorial state-space-explosion-problem remains as a major computational barrier for a LP method which computes a LFS in one step. From elementary net equations, the dynamic programming (DP) algorithm to compute LFSs of PNs is derived. To avoid the state-space-explosion-problem, the reversed net N~1of an original PN TV has been used and the basic DP algorithm is modified to compute on the reversed net. The original problem is subdivided into d recursive parts and each part is solved using LP This is the principle of the DP-based LP method. To improve computation time, a forward recursive DP-based LP method is derived. Firing of the sink transition in a critical siphon is a major problem for the DP-based LP method, since it deadlocks a computational process. To avoid this, an approximation algorithm which involves Pontryagin's Minimum Principle (PMP)-based LP for a known firing count vector u and the total firing instance d is introduced and discussed. The method computes on an original PN A^. A heuristic algorithm which supports the computation of the PMP-based LP method is derived. This heuristic algorithm suppresses firing of the sink transition of a potential critical siphon. The complete method avoids potential critical transitions and computes complex problems.

Analysis of complexity is important for the computer implementation of a computational method. Therefore, time and space complexities are considered in order to compute LFSs of PNs. Time complexity becomes about d~3 times to that of a single step LP method if a complete problem is subdivided into d subproblems. This technique is adopted with the FDP-based LP method, the DP-based LP method and the PMP-based LP method with known u and d. Computation time curves for the Single step LP, the DP-based LP and the PMP-based LP methods with a prespecified u and d which use the Revised Simplex DLPRS subroutine are obtained. Certain subclasses of PNs have well-defined reachability criteria. Computation time curves for these subclasses of PNs are obtained using a two-phase simplex subroutine. Some application issues are considered in this dissertation. The identified problems are addressed. Future research directions are outlined.