Deadlocks must be considered and resolved in control system design of automated manufacturing system. In some cases, a part or the whole system halts caused by deadlocks can not only lead to the deterioration of productivity but heavy economic losses and even fatal results. There are four necessary conditions for the occurrences of deadlocks in resource allocation systems, which are mutual exclusion, hold and wait, no preemption and circular wait. A fair amount of research has shown that the first three in a real-world manufacturing system are always true. Therefore, deadlock inhibition in automated manufacturing systems is realized through avoiding circular wait in resource allocation policies. Petri nets are one of commonly used mathematical tools for modeling and analysis of discrete event systems. Deadlock resolution methods in automated manufacturing systems using Petri nets are classified into three strategies: deadlock detection and recovery, deadlock avoidance, and deadlock prevention. A deadlock detection and recovery approach permits the occurrence of deadlocks. When a deadlock occurs, it is detected and then the system is put back to a deadlock-free state by simply reallocating resources. In deadlock avoidance, at each system state an on-line resource allocation policy is used to keep the system away from deadlock states. Deadlock prevention is usually achieved by using an off-line computational mechanism to control the request for resources to ensure that deadlocks never occur. This dissertation aims to model and analyze automated manufacturing systems and presents a number of deadlock prevention policies using two subclasses of generalized Petri nets, System of Sequential Systems with Shared Resources (S4PR) and G-systems. The main results of this research are as follows.First, a deadlock prevention policy based on elementary siphons is proposed. Elementary siphon can be derived in a given set of strict minimal siphons of a Petri net system, control places are added only for elementary siphon, the controllability of dependent ones can be ensured by adjusting the control depth variables. Thereby, a liveness-enforcing Petri net supervisor is obtained. The advantage of this method is that the number of control places can be effectively reduced, that is, the system structural complexity decreases accordingly such that the system can play better dynamic performance. Second, an optimized explicit control policy based on elementary siphon theory is presented. In the first place, control places are added for net system using the elementary siphon theory, then rearrangement of output arcs of the monitors is applied to the supervisor such that permissive behaviors of the controlled system is optimized.Third, it is an optimized implicit control of deadlock prevention policy. No control place is needed through this method, and a liveness-enforcing supervisor can be obtained by properly setting initial tokens relations between resource and idle places, and solving the constraints to get the optimal solution.Finally, two deadlock control strategies are developed using a mixed integer programming (MIP), which can avoid the complete siphon enumeration and lead to better computional efficiency. The first strategy finds a maximal deadly siphon by an MIP-based deadlock detection approach, from which a strict minimal siphon can be derived. Based on the concept of elementary siphons, it adds control places only for elementary siphons and uncontrolled dependent ones. Therefore, a liveness-enforcing supervisor with less control places and arcs can be obtained after a few iterations. The second strategy is a two-stage iteration policy for the design of a liveness-enforcing controller, which includes a siphon control stage and an augmented siphon control stage. After that, there is no maximal deadly siphon in controlled system such that the liveness can be preserved.This research is of significance to the theory of Petri nets and the supervisory control of discrete event systems in a Petri net formalism.
|