Modelling and Control of Resource Allocation Systems within Discrete Event Systems by Means of Petri Nets -- Part 1: Invariants, Siphons and Traps in Deadlock Avoidance

keywords: Automated manufacturing systems, control synthesis, deadlocks, deadlock avoidance, discrete-event systems, flexible manufacturing systems, modelling, Petri nets, place/transition Petri nets, P-invariants, resource allocation systems, siphons, supervisor, T-invariants, traps
Solving the deadlocks avoidance problem in Resource Allocation Systems (RAS) in Discrete-Event Systems (DES) is a rife problem, especially in Flexible Manufacturing Systems (FMS), alias Automated Manufacturing Systems (AMS). Petri Nets (PN) are an effectual tool often used at this procedure. In principle, there are two basic approaches how to deal with deadlocks in RAS based on PN. They are listed and illustrated here. First of the approaches is realized by means of the supervisor based on P-invariants of PN, while the second one is realized by means of the supervisor based on PN siphons. While the first approach needs to know the reachability graph/tree (RG/RT) expressing the causality of the development of the PN model of RAS, in order to find (after its thorough analysis) the deadlocks, the second approach needs the thorough analysis of the PN model structure by means of finding siphons and traps. Next, both approaches will be applied on the same PN model of RAS and the effectiveness of the achievement of their results will be compared and evaluated. Several simple illustrative examples will be introduced. For the in-depth analysis of the problem of deadlock avoiding, next Part 2 of this paper is prepared, where the newest research will be introduced and illustrated on more complicated examples. If necessary (because of the limited length of particular papers), also the third part -- Part 3, will be prepared.
mathematics subject classification 2000: 93-C65, 93-C30
reference: Vol. 40, 2021, No. 3, pp. 648–689