A method for finding firing sequences for the reachability problem of Petri nets with mathematical programming technique
Yasumasa Fujii, Takashi Sekiguchi · IEEJ Transactions on Electronics Information and Systems · 1996
Petri nets have been developed by many researchers as a useful form for describing and analyzing the structure of discrete event systems. In applying Petri nets into practical systems, finding firing sequences for the reachability problem can be regarded as one of the most important issues. In general, the reachability problem has been approached with the reachability tree method or the incidence matrix method. These two different types of approaches have, however, their respective drawbacks, i.e. state space explosion in exhaustive enumeration processes, and the presence of spurious integer solutions for a net state equation.The purpose of this study is to develop a new method for finding firing sequences for the reachability problem of Petri nets. First, defining an extended incidence matrix equation, the proposed method is formulated as an optimization problem whose non-negative integer solution can provide sufficient information on the firing sequences of the transitions. Secondly, the optimization problem is solved through a well-established linear programming technique without the condition of integrity. Evaluating the reduced-costs of the respective variables, and examining whether each variable is active or inactive, we can systematically sort out of the irrelevant variables. In other words, before proceeding into a problem having combinatorial complexity, the proposed method attempts to make as much reduction as possible in the number of the variables on the basis of the algebraic properties of the incidence matrix equation.In our paper, we also discuss the usefulness of the proposed method by evaluating a simple computational example.