Letter to the editor

Article Type: Letter to the editor From: Engineering Computations, Volume 11, Issue 3.

On extraction of elementary siphons in a class of generalized Petri nets using graph theory

Introduction

A siphon-based deadlock prevention policy was proposed in Hou et al. (2014) to design liveness enforcing supervisors for flexible manufacturing systems (FMS), by using their Petri net models (PNM). The number of siphons grows exponentially with respect to the size of its PNM. Therefore, to reduce the structural complexity of a supervisor, a set of elementary siphons were derived from all strict minimal siphons (SMS). The purpose of Hou et al. (2014) was to compute all SMS and a compact set of elementary siphons through fully investigating the structure of a class of generalized Petri nets, WS3PR. To achieve this goal, the concepts of initial resource weighted digraphs and restricted subgraphs were proposed based on graph theory. In addiditon, the concept of augmented siphons was proposed to extend the application of elementary siphons theory for WS3PR. To demonstrate the proposed method, an FMS example was considered. Figure 1 depicts the WS3PR (PNM) of an FMS considered in Hou et al. (2014). The PNM shown in Figure 1 suffers from deadlock problems and therefore to enforce the liveness on this PNM it is necessary to introduce a liveness enforcing mechanism. Therefore, by using the approach proposed in Hou et al. (2014) four monitors (control places) given in Table I were computed to enforce liveness on the PNM shown in Figure 1. However as it is shown in the next section the controlled (closed-loop) system containing the PNM shown in Figure 1 and four monitors given in Table I does not provide a live system.

Main results

In order to analyse both uncontrolled and the controlled PNMs, a Petri net analysis software tool called INA (2) was used. The uncontrolled PNM is obtained as an INA file as shown in Figure 2. Analysis results are obtained from INA for the uncontrolled PNM. According to the analysis results obtained from INA, the uncontrolled PNM is not live. The reachability graph of the uncontrolled PNM has 5,839 states, nine of which are deadlock states. In addition, the uncontrolled PNM is bounded (Figure 3).

The controlled PNM consists of the uncontrolled PNM shown in Figure 1 and four monitors given in Table I. The controlled PNM is obtained as an INA file as shown in Figure 4. Analysis results for the controlled PNM by using INA is obtained as shown in Figure 5. It can be seen from Figure 5 that the controlled PNM is not live. In addition, the net is not bounded. This means that there is a problem with four monitors provided in Table I.

Conclusion

This paper has shown that the liveness enforcing supervisor containing four monitors computed in Hou et al. (2014) does not provide a live behaviour as expected.

Murat Uzam

Department of Electrical and Electronics Engineering, Meliksah University, Kayseri, Turkey

Acknowledgements

This work was supported by the research grant of the Scientific and Technological Research Council of Turkey (Türkiye Bilimsel ve Teknolojik Aratrma Kurumu – TÜBITAK) under the Project No. TÜBITAK-112M229.

Reference

Hou, Y.F., Li, Z.W., Zhao, M. and Liu, D. (2014), “Extraction of elementary siphons in a class of generalized Petri nets using graph theory”, Engineering Computations, Vol. 31 No. 2, pp. 331-352

Further reading

INA (2003), “Integrated net analyzer, a software tool for analysis of Petri nets”, Version 2.2, available at: www.informatik.hu-berlin.de/~starke/ina.html (accessed 31 July 2003)