In: International Journal of Production Research, Vol. 39, No. 2, pages 283-305. 2001.
Abstract: This paper presents a deadlock prevention method for a class of flexible manufacturing systems where deadlocks are caused by unmarked siphons in their Petri net models. This method is an iterative approach consisting of two main stages. At each iteration, a fast deadlock detection technique developed by mixed integer programming is used to find an unmarked maximal siphon. An algorithm is formalized that can efficiently obtain an unmarked minimal siphon from the maximal siphon. The first stage, called siphon control, of the proposed method is to add, for each unmarked siphon, a control place to the original net with its output arcs to the sink transitions of the minimal siphon. The objective is to prevent a minimal siphon from being unmarked. The second stage, called augmented siphon control, is to add a control place to the modified net with its output arcs to the source transitions of the resulting net if the resource places are removed. The second stage is required since adding control places in the first stage may create new unmarked siphons. In addition, the second stage assures that there are no new unmarked siphons generated. The relation of the proposed method and the liveness and reversibility of the controlled new have been obtained. Finally, manufacturing examples are presented to illustrate the method and to allow comparison with earlier methods.
Keywords: Petri nets, deadlock prevention, flexible manufacturing systems, siphon control, unmarked siphons.