Abstract: Petri nets are used to model the concurrent execution and the deadlock problem in a flexible manufacturing system(FMS). With the number of reachable states in the controlled system being the criterion, an idea of the optimal set of elementary siphons is illustrated. A set of siphons can be used to optimize the dynamical behavior of the resultant system if their corresponding dependant siphons are all strictly dependant ones. Furthermore, the integer programming method is exploited as the mathematical tool for the generation of a polynomial algorithm producing the optimal set elementary siphons. Experimental results show that the optimal set of elementary siphons ensures more permissive behavior with fewer controlling places in the controlled net system when the same deadlock control policy is applied.

Key words: Petri net, deadlock prevention, optimal set of elementary siphons, flexible manufacturing system(FMS)