On Deadlock Prevention For Flexible Manufacturing Systems Based On Petri Net

This thesis focuses on the problem of deadlocks in flexible manufacturing systems (FMS). Based on system of sequential systems with shared resources(S4R), a class of Petri nets, an improved deadlock prevention algorithm is proposed. As a structural object of a Petri net, siphons are very important in analysis and control of deadlocks in Petri nets. However, it is quite time-consuming or even impossible to enumerate all siphons of a net, especially, when the net is very large. S4R can model complicated resource allocation systems with multiple concurrent processes, and different types of multiple resources can be requested by different processes. The existence of empty siphons or insufficiently marked ones is the reason for deadlocks in S4R. So far, most of the deadlock prevention policies are achieved by adding monitors based on the max-controllability of siphons to empty siphons or insufficiently marked ones. However, these approaches always limit the permissive behavior of net systems. Thus, the system performance is degraded.The improved algorithm proposed in this thesis is an iterative approach, it does not need to compute all strict minimal siphons(SMS) of a net. At each iteration, a non-max'-marked siphon is computed by solving an integer non-linear programming problem. Then, a monitor needs to be added to the siphon to guarantee that the siphon is max'-controlled. The algorithm terminates when there is no non-max'-marked siphon in the net. As a result, all the siphons in the net are max'-controlled. Then the net is live and it has more permissive behavior. Several examples of FMS are used to illustrate it.