Extended elementary siphon-based deadlock prevention policy for a class of generalised Petri nets

Abstract

This paper develops a novel deadlock prevention policy for a class of generalised Petri nets, namely S⁴PR that can well model flexible manufacturing systems (FMS). The analysis of generalised Petri nets leads us to characterise deadlock situations in terms of insufficiently marked siphons. The theory of elementary siphons guides our efforts towards the development of structurally simple liveness-enforcing supervisors. Therefore, insufficiently marked siphons can be classified into elementary ones and dependent ones. The controllability of a dependent siphon can be ensured by properly supervising its elementary ones. In order to find a compact and proper set of elementary siphons for S⁴PR, the concept of augmented siphons is proposed. Then, the concept of max′-controlled siphons is employed, which can relax the siphon controllability condition. By explicitly controlling elementary siphons via adding monitors, a liveness-enforcing controlled system can be found. In addition, the liveness-enforcing supervisor with more permissive behaviour is obtained through the rearrangement of the output arcs of the monitors. Finally, an FMS case study is utilised to demonstrate the proposed method.

Keywords:

• flexible manufacturing system
• Petri net
• deadlock prevention
• elementary siphon

Acknowledgements

This work was supported in part by the National Natural Science Foundation of China under Grant No. 61074035 and 61104110, the Fundamental Research Funds for the Central Universities under Grant No. JY10000904001 and K50510040012, the National Research Foundation for the Doctoral Program of Higher Education, the Ministry of Education, P. R. China, under Grant No. 20090203110009.