Previous [ 1] [ 2] [ 3] [ 4] [ 5] [ 6] [ 7] [ 8] [ 9] [ 10] [ 11] [ 12] [ 13] [ 14] [ 15] [ 16] [ 17] [ 18]


Journal of Information Science and Engineering, Vol. 25 No. 1, pp. 167-183 (January 2009)

A Deadlock Prevention Policy for a Class of Petri Nets S3PMR*

Mingming Yan1, Zhiwu Li1,2, Na Wei1 and Mi Zhao1
1School of Electro-Mechanical Engineering
Xidian University
Xi'an, 710071 P. R. China
2Laboratory of CAD and Lifecycle Engineering
Department of Mechanical Engineering
Technion - Israel Institute of Technology
Haifa, 32000 Israel

This paper focuses on the problem of deadlocks in automated flexible manufacturing systems (FMS) where deadlocks are caused by unmarked siphons in their Petri net models. A deadlock prevention policy is proposed for a subclass of Petri nets, S3PMR that can well model a large class of FMS. We distinguish siphons in such a net model by elementary and dependent ones. For each elementary siphon, a monitor is added to the plant model such that it is invariant-controlled. The monitor addition way guarantees that no emptiable control-induced siphon is generated due to the presence of monitors in the resultant net. This novel deadlock prevention policy can usually lead to a more permissive supervisor by adding a small number of monitors and arcs than the existing methods for the design of liveness-enforcing Petri net supervisors. Experimental study indicates that the proposed policy appears to be more permissive than closely related approaches in the literature.

Keywords: FMS, deadlock prevention, Petri net, elementary siphon, S3PMR

Full Text () Retrieve PDF document (200901_09.pdf)

Received March 28, 2007; revised June 11, 2007; accepted August 3, 2007.
Communicated by Chin-Laung Lei.
* This work was partially supported by the National Nature Science Foundation of China under grant No. 60474018, and the Laboratory Foundation for the Returned Overseas Chinese Scholars, State Education Ministry of China, under grant No. 030401.