Deadlock Resolution in Automated Manufacturing Systems

by Li, Zhiwu; Zhou, Mengchu

• ISBN13: 9781848822436
• ISBN10: 184882243X
• Format: Hardcover
• Copyright: 2009-06-30
• Publisher: Springer Verlag

Summary

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.

Author Biography

ZhiWu Li received his B.S., M.S., and Ph.D. degrees all from Xidian University, Xi'an, China, in 1989, 1992, and 1995, respectively. He joined Xidian University, Xi'an, in 1992, where he is currently Professor of the School of Electro-Mechanical Engineering. He has over 100 publications including a book chapter in Deadlock Resolution in Computer-Integrated Systems, New York: Marcel-Dekker, 2005. From June 2002 to July 2003, he was a Visiting Professor at the Systems Control Group, Department of Electrical and Computer Engineering, University of Toronto, Canada. From February 2007 to February 2008, he was a Visiting Scientist at the Laboratory for CAD & Lifecycle Engineering, Department of Mechanical Engineering, Technion - Israel Institute of Technology, Technion City, Haifa, Israel. Dr. Li served as a member of the Program Committee of the 2005 IEEE International Conference on Networking, Sensing, and Control, 2007 IEEE International Conference on Systems, Man and Cybernetics and the 2008 International Conference on Applications and Theory of Petri Nets. He is a member of the International Advisory Committee of the 10th International Conference on Automation Technology. He is General Co-Chair of the IEEE Conference on Automation Science and Engineering. Dr. Li is a member of the Discrete Event Systems Technical Committee of IEEE Systems, Man, and Cybernetics Society. He serves as a frequent reviewer for 15+ international journals and many international conferences. He is Senior Member of IEEE and recipient of the Alexander von Humboldt Research Grant from Alexander von Humboldt Foundation, Germany.MengChu Zhou received his B.S. from Nanjing University of Science and Technology, M.S. from Beijing Institute of Technology, and Ph.D. from Rensselaer Polytechnic Institute. He joined New Jersey Institute of Technology (NJIT) in 1990, and is currently a Professor of Electrical and Computer Engineering and Director of the Discrete-Event Systems Laboratory. His interests are in computer-integrated systems, Petri nets, networks, and manufacturing. He has 300+ publications including 6 books and 120+ journal papers. He is the Managing Editor of IEEE Transactions on Systems, Man and Cybernetics (SMC), Associate Editor of IEEE Transactions on Automation Science and Engineering, IEEE Transactions on SMC: Part A and IEEE Transactions on Industrial Informatics, and Editor-in-Chief of International Journal of Intelligent Control and Systems. He has served as General and Program Chair of many international conferences. Dr. Zhou has led or participated in 36 research and education projects with a total budget over $10M, funded by NSF, DoD, and industry. He was the recipient of the CIM University-LEAD Award by the Society of Manufacturing Engineers, the Perlis Research Award by NJIT, the Humboldt Research Award for US Senior Scientists, and the Distinguished Lecturer of IEEE SMC Society. He has been invited to lecture in Australia, Canada, China, France, Germany, Hong Kong, Italy, Japan, Korea, Mexico, Taiwan, and US. He was founding chair of the Discrete Event Systems Technical Committee of the IEEE SMC Society, and Chair (founding) of the Semiconductor Manufacturing Automation Technical Committee of the IEEE Robotics and Automation Society. He is a life member of the Chinese Association for Science and Technology-USA and served as its President in 1999. He is a Fellow of the IEEE.

Table of Contents

Abbreviations	p. xxi
Introduction	p. 1
Background	p. 1
Literature Review	p. 3
Outline of the Book	p. 9
Bibliographical Remarks	p. 10
Problems	p. 10
References	p. 10
Petri Nets	p. 17
Introduction	p. 17
Formal Definitions	p. 17
Structural Invariants	p. 25
Siphons and Traps	p. 27
Subclasses of Petri Nets	p. 33
Petri Nets and Automata	p. 34
Plants, Supervisors, and Controlled Systems	p. 36
Bibliographical Remarks	p. 37
Problems	p. 38
References	p. 40
Elementary Siphons of Petri Nets	p. 45
Introduction	p. 45
Equivalent Siphons	p. 46
Elementary and Dependent Siphons	p. 49
Controllability of Dependent Siphons in Ordinary Petri Nets	p. 50
Controllability of Dependent Siphons in Generalized Petri Nets	p. 61
An Elementary Siphon Identification Algorithm	p. 68
Existence of Dependent Siphons	p. 71
Bibliographical Remarks	p. 73
Problems	p. 73
References	p. 74
Monitor Implementation of GMECs	p. 77
Introduction	p. 77
Generalized Mutual Exclusion Constraints	p. 78
Elementary and Dependent Constraints	p. 79
Implicit Enforcement of Dependent Constraints	p. 82
Application to Deadlock Prevention	p. 90
Some Further Results About S4R Nets	p. 98
Identification of Elementary Constraints	p. 101
Bibliographical Remarks	p. 102
Problems	p. 102
References	p. 103
Deadlock Control Based on Elementary Siphons	p. 107
Introduction	p. 107
Some Application Subclasses of Petri Nets	p. 107
An MIP-Based Deadlock Detection Method	p. 116
A Classical Deadlock Prevention Policy	p. 119
An Elementary Siphon-Based Deadlock Prevention Policy	p. 125
An MIP-Based Deadlock Prevention Policy	p. 132
Deadlock Prevention in S4R	p. 134
Bibliographical Remarks	p. 148
Problems and Discussions	p. 149
References	p. 154
Optimal Liveness-Enforcing Supervisors	p. 159
Background	p. 159
Optimal Supervisor Design by the Theory of Regions	p. 160
Existence of an Optimal Liveness-Enforcing Supervisor	p. 166
Synthesis of Optimal Supervisors	p. 178
An Example	p. 182
Bibliographical Remarks	p. 185
Problems	p. 185
References	p. 188
Comparison of Deadlock Prevention Policies	p. 191
Introduction	p. 191
Applications of Deadlock Prevention Methods to a Case Study	p. 192
Combination of Deadlock Prevention and Avoidance	p. 192
Modification of Initial Markings of Monitors	p. 194
Deadlock Prevention via Proper Configuration of Initial Markings	p. 195
A Selective Siphon Control Policy	p. 197
Deadlock Prevention by Complete Siphon Enumeration	p. 198
Two-Stage Deadlock Control	p. 199
Two-Stage Deadlock Control with Elementary Siphons	p. 200
A Policy Based on Elementary Siphons	p. 201
An Iterative Policy Based on Elementary Siphons	p. 202
A More Permissive Policy Based on Elementary Siphons	p. 203
A Policy of Polynomial Complexity	p. 204
An Iterative Deadlock Prevention Policy	p. 206
An Optimal Deadlock Prevention Policy Based on Theory of Regions	p. 207
A Suboptimal Deadlock Prevention Policy	p. 208
An Optimal Policy Based on Complete Siphon Enumeration	p. 210
Analysis of Deadlock Prevention Methods	p. 211
Reachability-Graph-Based Policies	p. 212
Complete-Siphon-Enumeration-Based Policies	p. 213
Partial-Siphon-Enumeration-Based Policies	p. 213
Exponential Complexity and NP-Hardness	p. 214
Bibliographical Remarks	p. 215
Problems	p. 215
References	p. 216
Conclusions and Future Research	p. 223
Problems	p. 225
References	p. 226
Symbols	p. 231
Index	p. 235
Table of Contents provided by Ingram. All Rights Reserved.