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


Journal of Information Science and Engineering, Vol. 23 No. 1, pp. 215-231 (January 2007)

Deadlock Prevention for Sequence Resource Allocation Systems*

Yi-Sheng Huang
Department of Electrical and Electronic Engineering
Chung Cheng Institute of Technology
National Defense University
Taoyuan, 335 Taiwan

This paper presents a deadlock prevention algorithm for the class of sequential resource allocation system for flexible manufacturing systems, which allows for multiple resources flexible routings. Two classes of Petri nets Extended from Systems of Simple Sequential Processes with Resources (ES3PR) and Systems of Simple Sequential Processes with General Resource Requirements (S3PGR2) whose deadlocks are related to unmarked siphons are considered. Based on the definition of ES3PR net, the original net is an ordinary Petri net. We further present a siphon-based algorithm of deadlock prevention for both classes of Petri nets. The proposed method is an iterative approach. We note that S3PGR2 net structure is a weighted generalization of the ES3PR net. Based on this reason, the proposed algorithm can be applied to S3PGR2 net if the target net is normalized to ordinary one. And this algorithm is only adding generalized control place. Finally, numerical experiments using reachability tree illustrate that the proposed algorithm appears to generate more permissive supervisors than the closely related approaches of other literatures.

Keywords: algorithm, deadlock prevention, FMS, Petri net, siphon

Full Text () Retrieve PDF document (200701_12.pdf)

Received April 18, 2005; revised October 27, 2005; accepted November 9, 2005.
Communicated by David H. C. Du.
* This paper was partially supported by the National Science Council of Taiwan, R.O.C., under grand No. NSC 92-2212-E-014-001. The earlier version of this paper was presented at 2004 IEEE International Conference on System, Man and Cybernetics, Hawaii, October 10-12, 2005.