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

摘要

Finding firing sequences for the reachability problem can beregarded as one of the most important issues associated with Petri nets.The purpose of this study is to develop a new method for finding firingsequences by defining an extended state equation. The proposed method isformulated as an integer programming problem whose solution can providesufficient information on the firing sequences. First, the optimizationproblem is approached with a linear programming technique. Evaluatingthe reduced-cost and activeness of every variable, one cansystematically sort out the irrelevant variables to be neglected in theinteger programming problem of the succeeding stage. In this paper, theusefulness of the proposed method is demonstrated with the evaluation ofa couple of simple examples