Marking optimization of stochastic time Petri net using stochastic programming

Petri nets are important modeling tools for many practical control problems. Marking optimization arises in connection with determination of optimal buffer capacities and total cost of resources. We analyze the structure of the initial marking problem for deterministic problems. An analytical description of elementary circuits which leads to their algebraic representation by linear equations and inequalities is developed in the dissertation. Furthermore an iterative method for solving the initial marking problem based on column generation techniques. The method alternates between minimization of marking resources and identification of critical elementary circuits of Petri nets, which determine the systems performance. Another part of the analysis is focused on Petri nets with stochastic transition times. We introduce stochastic programming methods to the analysis of Petri nets, in particular to solving the initial marking problem. The problem is formulated as an optimization problem with probabilistic constraints. Further equivalent formulations of the problem leads to a large scale mixed integer programming problem with knapsack constraints. In combination with iterative column generation method, we suggest an algorithm for marking optimization, which is capable of handling large scale of Petri nets. In addition, a version of a branch and cut method that uses valid inequalities is incorporated to improve the efficiency of solving the probabilistically constrained problem.