A new method for finding firing sequences for the reachability problem of Petri nets by using a linear programming technique

摘要

Finding firing sequences for the reachability problem can be regarded as one of the most important issues associated with Petri nets. The purpose of this study is to develop a new method for finding firing sequences by defining an extended state equation. The proposed method is formulated as an integer programming problem whose solution can provide sufficient information on the firing sequences. First, the optimization problem is approached with a linear programming technique. Evaluating the reduced-cost and activeness of every variable, one can systematically sort out the irrelevant variables to be neglected in the integer programming problem of the succeeding stage. In this paper, the usefulness of the proposed method is demonstrated with the evaluation of a couple of simple examples.