Introduction :

The manufacturing industry provides a firm material foundation for the national economy, and possesses the principal position of industry. The development of manufacturing industry is vital to social progress, national strength, and welfare of our people. Moreover, it reflects the developmental level of scientific technology and social productive forces. Modern society features with intensive competition in market and certain fluctuation in demand. Manufacturers cannot stay competitive if they still rely on traditional mass production systems. Hence, manufacturers should hold performance parameters of all the aspects of production systems, and restructure the productive scheme constantly to remain invincible in domestic and international competitions. In order to survive and develop, an increasing number of manufacturers have gradually resorted to flexible manufacturing systems (FMS) to accelerate product process, reduce production costs, improve product quality, increase product flexibility, and enhance adaptability to the market, then leading to a better economic effect. The resources are shared highly in flexible manufacturing systems, which can cause deadlocks if there are not effective control methods [1]. Some processes will be blocked and could never be finished because of the occurrence of deadlocks. Deadlocks may lead to a whole or partial system stagnation which may results in a productivity reduction or serious economic losses even catastrophic results. Thus dealing efficiently with deadlock problems is necessary to reach higher.

Deadlock Prevention:

From literature quantitative analysis point of view, deadlock prevention for FMS is investigated extensively, iteratively, and marvelously, leading to a vast stock of results. On one hand, the previous work on deadlock control has built a solid foundation for deadlock prevention research. On the other hand, a highly automated system cannot tolerate the occurrence of deadlocks that may result in severe economic losses or even catastrophic results. This section reviews typical deadlock prevention strategies that are developed on the basis of different techniques by using Petri net as formalism.

The present of deadlock prevention:

Zhou and DiCeare [12] pioneered the study about Petri net-based deadlock prevention in FMS, in which modeling problem of FMS with sharing resources is proposed. They ensure the liveness of system by adding buffered modules and control places, or limiting the number of parts. The major weakness of this deadlock prevention is its conservativeness. As is known, a direct and remarkable consequence is that the productivity of a system can be deteriorated. In 1995, Ezpeleta [13] developed a design method of monitor-based liveness-enforcing Petri net supervisors. It is often considered to be a classical contribution that utilizes structural-analysis techniques of Petri nets to prevent deadlocks in FMS. First, a class of Petri nets, which is called S3 PR, is proposed, and the relationship between strict minimal siphons and liveness of an S3 PR is established. For each strict minimal siphon that can be empty at a reachable marking, a monitor is added such that it is controlled. After all siphons are controlled, liveness-enforcing Petri net supervisors are achieved. The significance of this approach lies in the fact that it successfully separates a plant net model and its supervisor. This work becomes such a spur that attracts much attention, and also has built a solid foundation for development and application of siphon theory. The years following 1995 have seen many siphon-based deadlock prevention policies in Petri nets proposed on the basis of this work. As gradually recognized, general deadlock prevention policies suffer from the following three kinds of defects: behavioral permissiveness, computational complexity, and structural complexity. The behavioral permissiveness problem is referred to as the fact that the permissive behavior of a plant net model is overly restricted by the deadlock prevention policy, namely that the supervisor excludes some admissible states. That’s because the output arc of added monitor points to source transition of Petri net model, which limits the number of work pieces entering system to be released into and processed to a great extent. A source transition is the output transition of an idle place, which models the entry of raw parts into the system. Computational complexity results from the complete siphon enumeration that is necessary for computing a supervisor. In theory, the number of siphons grows exponentially with respect to the size of a net model. Structural complexity refers to that the number of monitors in a liveness-enforcing supervisor is exponential with the net model size theoretically since every strict minimal siphon that can be unmarked at a reachable marking needs a monitor to prevent from being emptied. The structural complexity of a supervisor means extra cost in system verification, validation, and implementation. Since 1995, a great deal of work has focused on solving the aforementioned problems.

Deadlock prevention and siphon:

Siphons are well recognized to be tied with deadlocks in FMS, which is true in either ordinary or generalized Petri nets. The fact was adequately represented by Reveliotis [5-8]. In short, a siphon is a set of places. Once a siphon loses all its tokens, it remains unmarked under any subsequent markings that are reachable from the current marking. It is evident that if a siphon is emptied under a certain marking, some of its output transitions would never enable which leads to a local or global deadlock. In recent years, many researches about deadlock prevention have been done based on siphon, adding monitors for strict minimal siphons to achieve deadlock prevention [9,10]. As a result, the first step to design a siphon-based deadlock prevention control policy is to compute strict minimal siphons. In order to deal with the inherent complexity of computing siphons in Petri nets, Chu and Xie [14] proposed a deadlock detection method by solving a mixed integer programming (MIP) problem. It is used extensively [15-20]. Given a Petri net, Chu and Xie achieved the algorithm that computes maximum unmarked siphon by MIP. Motivated by the fact that deadlock control is usually concerned with minimal siphons in a Petri net, Huang [15,16]，Li and Liu [17] et al. Investigated minimal siphon extraction methods from a maximal unmarked siphon. The experiment data shows that MIP-based method is more efficient than any methods that depend on a complete siphon enumeration. But MIP-based method also suffers definitely from an exponential complexity problem with respect to the size of its plant net model [15-20]. It means that this method cannot be applied widely in actual large scale FMS [21]. In order to tackle the computational complexity problem of MIP-based method, Li and Zhou [22-25]pioneered in utilizing resource circuits to compute strict minimal siphons for S3 PR. By analyzing the structural characteristics of a resource circuit, the sufficient condition of which the siphons related to resource circuits are strict minimal siphons is proposed. Compared with MIP-based approach, this approach improves the computational efficiency. However, there is no complete algorithm of computing strict minimal siphons through resource circuits proposed. Wang et al.[25] proposed a sufficient and necessary condition under which the resource circuits can generate strict minimal siphons in L-S3 PR. Then they proposed a strict minimal siphons extraction method based on graph theory and resource circuits. But this method cannot compute strict minimal siphons in S3 PR, because L-S3 PR is a subclass of S3 PR. Recently, many scholars have been studying about this work, such as Xing, Wang, etc [26,27]. Wang [28] proposed the necessary and sufficient conditions for loop resource subsets to generate strict minimal siphons. A method to compute strict minimal siphons has been developed in his paper. Also, the experimental study shows that the resource circuit-based method is an effective way to compute strict minimal siphons for S3 PR. Compared with the method based on resource circuits, the resource circuit-based method has a higher computational efficiency via many randomly generated examples.

The fast calculation approaches of strict minimal siphons:

As a structural object, siphons play an important role in the analysis of structural and behavioral properties of Petri nets. An algorithm with polynomial complexity to decide whether a set of places is a minimal siphon can be found in [47]. Classical and typical siphon computation methods are presented in [48-50]. A siphon computation method that is claimed to be rather efficient is developed in [44], which can find 2×107 siphons within one hour. For a class of Petri nets, a siphon solution approach is given in [51] that is also efficient through experimental studies. A parallel solution to siphons is established by Tricas and Ezpeleta [52]. In order to apply deadlock prevention control policy into large size systems, Wang utilizes loop resource subsets to compute all the strict minimal siphons in S3 PR. From some counterexamples, some flaws in strict minimal siphons computation-based elementary siphon theory proposed by Li and Zhou can be found. One of these flaws is that some siphons derived from resource circuit are not strict minimal ones [53]. Another is that redundant strict minimal siphon can be achieved with this method. The method to compute strict minimal siphons in a class of Petri net based on loop resource subsets proposed by Wang has solved aforementioned flaws and has higher computational efficiency. Moreover, sufficient and necessary conditions for loop resource subsets to generate strict minimal siphons are established, and an algorithm is proposed to find all the strict minimal siphons in an S3 PR [28]. This approach is one of the most efficient methods to compute strict minimal siphons. However, this approach can only be available for S3 PR, and it will be no use for more general nets. Motivated by the fact that deadlock control is usually concerned with unmarked strict minimal siphons in a Petri net, some scholars investigate strict minimal siphon extraction methods from a maximal unmarked siphon and achieve a lot of new contributions. This kind of method is widely used since it fits every kind of ordinary Petri net, while it suffers from low computational efficiency. For example in [15,29], the computational efficiency of the method which can investigate strict minimal siphon extraction methods from a maximal unmarked siphon is still NP-hard. For several kinds of Petri nets, such as S3 PR, S3 PMR, S4 PR, etc., Wang investigates related theory and some algorithms to compute strict minimal siphons based on MIP and loop resource subsets. Meanwhile, the controllability problem of strict minimal siphons generated from loop resource subsets is researched. The set of elementary siphons in a Petri net is unique, so we should be cautious when choosing elementary siphons. In order to deal with this problem, Wang [54,55] classifies strict minimal siphons generated from loop resource subsets into two kinds: simple and combined ones. A siphon is called a simple one when it cannot be comprised by other strict minimal siphons. It is easy to see that the set of simple siphons is evidently unique. A siphon is called combined one when it can be comprised by other strict minimal siphons. Moreover, sufficient and necessary conditions that the controllability of combined siphons can be ensured by the optimal control of simple ones is proposed. In addition, the controllability of combined siphon comprised by two simple siphons for LS3 PR is proposed, while the problem for more general nets, such as S3 PR, S3 PMR, S4 PR, etc., is still at issue.

Conclusion:

The occurrence of deadlocks is prohibitive in high automated systems. A systematic and effective method for controlling deadlock is vital to the supporting systems of the life, nuclear plants, traffic surveillance and control system, and high automated systems, etc. For the past two decades, deadlock control problem has been a hot spot in academic and engineering circles. Many researchers have proposed a great deal of deadlock control policies, and most of them adopt Petri net models. In this paper, an increasing number of well-established deadlock control policies for manufacturing systems are proposed, especially deadlock prevention policies. At present, there are two branches of deadlock control methods based on Petri nets: siphon control method and state control method. Unfortunately, these approaches suffer from one or more of the following problems: behavioral permissiveness, computational complexity, and structural complexity. Hence, much work has been focused on solving the aforementioned problems. Recently, the policies achieve higher computational efficiency, higher behavioral permissiveness, and lower structural complexity. However, the application scope of the control methods is still limited, which can only be applied to some sub classes of Petri nets, and could not adopt to more general net models. It is necessary to find an effective deadlock control strategy to improve the limitations and restrictions of well-established policies, so that liveness-enforcing supervisor with maximal permissiveness can be attained.