Deadlock recovery for flexible manufacturing systems modeled with Petri nets

This paper deals with deadlock problems in Petri nets by adding a set of recovery transitions. Different from traditional deadlock control methods by deploying control places for a net model to be controlled, this work adds transitions to a net model to recover all deadlock markings. First, we present an iterative approach. At each iteration step, an integer linear programming problem (ILPP) is formulated to design a recovery transition and the objective function is used to maximize the number of deadlock markings recovered by the obtained transition. The process is carried out until all deadlock markings are recovered. As a result, only a small number of recovery transitions are needed to recover all the deadlock markings, i.e., the resulting net model with recovery transitions is live. Second, we develop another ILPP to find all recovery transitions at a time. The constraints of the ILPP ensure that every deadlock marking is recovered by at least one selected recovery transition and the objective function is used to minimize the number of selected recovery transitions. Then, a minimal number of recovery transitions are obtained by solving one ILPP only. Both approaches can make a net model live with all reachable markings. Finally, serval examples are provided to demonstrate the proposed approach.