A Literature Review of Deadlock Prevention Policy Based on Petri Nets for Automated Manufacturing Systems <s> Introduction <s> List of Figures. List of Tables. 1. Introduction. 2. Petri Nets and Manufacturing Systems. 3. Parallel Mutual Exclusions. 4. Sequential Mutual Exclusion. 5. Hybrid Synthesis of Petri Nets. 6. Illustration of Hybrid Synthesis. 7. Discrete Event Control of FMS. 8. Augmentation of Petri Nets. 9. Petri Nets: Past, Present and Future. Appendix A. Bibliography. Index. <s> BIB001 </s> A Literature Review of Deadlock Prevention Policy Based on Petri Nets for Automated Manufacturing Systems <s> Introduction <s> Over the last two decades, a great deal of research has been focused on solving deadlock problems in resource allocation systems such as computer communication systems, workflow systems, and flexible manufacturing systems, resulting in a wide variety of approaches. As a well-defined problem in resource allocation systems, deadlock prevention based on a Petri net formalism has received an enormous amount of attention in the literature. This paper intends to review and compare a variety of Petri net-based deadlock prevention policies reported in the literature. Their comparison is done in terms of structural complexity, behavior permissiveness, and computational complexity. This paper should facilitate engineers in choosing a suited method for their industrial application cases. <s> BIB002 </s> A Literature Review of Deadlock Prevention Policy Based on Petri Nets for Automated Manufacturing Systems <s> Introduction <s> Deadlock problems in flexible manufacturing systems (FMS) have received more and more attention in the last two decades. Petri nets are one of the more promising mathematical tools for tackling deadlocks in various resource allocation systems. In a system modeled with Petri nets, siphons are tied to the occurrence of deadlock states as a structural object. The book systematically introduces the novel theory of siphons, traps, and elementary siphons of Petri nets as well as the deadlock control strategies for FMS developed from it. Deadlock prevention methods are examined comparatively. The many FMS examples presented to demonstrate the concepts and results of this book range from the simple to the complex. Importantly, to inspire and motive the reader s interest in further research, a number of interesting and open problems in this area are proposed at the end of each chapter. Deadlock Resolution in Automated Manufacturing Systems is directed to control, computer, electrical, mechanical, and industrial engineers, researchers and scientists. It will be useful for designers in the automation and control disciplines in industry and academia who need to develop the control methods, tools and software to improve the performance of automated flexible manufacturing systems. <s> BIB003
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 BIB001 . 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 productivity. In recent years, with the sustainable developments of automation level, deadlock problem in FMS has become a hot spot in academic and engineering circles BIB003 . Due to the inherent characteristics of describing resource sharing, conflict, mutual exclusion, concurrency, and uncertainty, Petri net has been used as a mathematical tool to study supervisory control theory of discrete event system  . In addition, Petri nets are widely used in modeling, simulation, and supervisory control for FMS  , because Petri nets can help scholars find potential deadlocks and prevent the occurrence of deadlocks through related control policies. For a dozen of years, the results are much enriched in achieving automation of productive processes as well as optimization of system performance that is based on a Petri net formalism BIB003 BIB002 . The well-established Petri net community that mainly consists of computer scientists has developed a large family of Petri net models across many disciplines. As is known, different classes of Petri nets can represent different types of DES. S 3 PR, a class of ordinary Petri net, has been among the most frequently used models in handling deadlock problems. Many extensions to S 3 PR nets have been proposed, which can be used to model more general automated DES: AMG(augmented marked graphs), S 4 PR(system of sequential systems with shared resources), S 3 PMR (system of simple sequential processes with multiple resources), PNR(process nets with resources), RCN(resource control nets)-merged net, ERCN(extended resource control nets)-merged net, G-system, etc BIB003 . The deadlock issues derive from resource allocation systems, which could be dated back to the memory assignments in an operating system by computer scientists in the 1960s. Summarily, there are four necessary conditions for a deadlock to occur, which are known as the Coffman conditions  : mutual exclusion, hold and wait, no preemption condition, and circular-wait. It is shown that the first three conditions are decided by the physical characteristics of a system and its resources. However, the fourth one can be enforced to vary depending on request, allocation, and release of the resources in the system. All the four conditions must hold, once a deadlock occurs. That is, a deadlock will never occur if one of these conditions is not satisfied. The necessity of the four conditions for a deadlock to occur leads us to infer that negating one of them makes impossible the occurrence of deadlocks in a resource allocation system. Therefore the basic policy to solve deadlock is to ensure that not all four conditions be satisfied. Generally, these deadlock methods are classified into three strategies: deadlock detection and recovery, deadlock avoidance, and deadlock prevention. Deadlock detection and recovery is a passive approach in fact. In deadlock avoidance, at each system state an on-line control policy is used to make a correct decision to proceed among the feasible evolutions. The main purpose of this approach is to keep the system away from deadlock states. Some defects of this approach emerge that should be computed on-line. Aggressive methods usually lead to higher resource utilization and throughputs, but not totally eliminate all deadlocks for some cases. Conservative methods eliminate all unsafe states and deadlocks, and often some good states, thereby degrading the system performance. Deadlock prevention is usually achieved by using an off-line computational mechanism to control the request for resources to ensure that deadlocks never occur. Compared with the first two approaches, deadlock prevention is more efficient and adopted widely in deadlock control. This research summarizes the well-established deadlock prevention approaches and their merits and demerits in the context of AMS.