臺灣博碩士論文加值系統

本論文探討彈性製造系統在設計單元控制器的過程中，所面臨的：塑模方法、死鎖分析、死鎖避免以及實現等課題。針對真實製造系統中派屈網路模型無法避免的複雜性，本論文提出以事件追蹤圖 (scenario) 作為派屈網路塑模的媒介，做為有效塑模相對應製造流程之派屈網。在此塑模基礎上，我們發覺針對彈性製造系統中滿足 S3PR類型之派屈網而言，其存活性 (liveness) 與可逆性 (reversibility) 等定性特性與虹吸 (siphon) 及陷阱 (trap) 有關的事實。再根據文獻上利用 (MIP) 快速分析死鎖的方法，本論文針對此類型系統提出以 MIP為基礎、分兩階段修改原系統的死鎖避免法則。除了能夠有效且快速的避免該派屈網路中所有的死鎖因素之外，本新提議的死鎖避免方法是目前文獻上已知對受控系統限制最少 (least restrictive) 的方法。最後，我們利用物件導向的技術實現以派屈網 (Petri nets) 為基礎的單元控制器整合發展環境，其優點是允許使用者依製造流程之特性，直接勾構及修改相對應的派屈網路模型，之後即可直接控制相對應彈性製造系統中各工件的製造與運作。為證驗本論文各理論在真實系統中之適用性，一單元控制器並已經成功地被運用在國立台灣科技大學自動化中心的計算機整合製造工廠中。

This thesis presents a Petri net-based approach to modeling, analysis, deadlock prevention, and cell controller implementation for flexible manufacturing systems (FMS’s). With all its nice modeling properties of Petri net, it is, however, hardly practical to model a complex system using Petri nets directly. As a result, scenarios that model the operation flows of a real-world FMS cell are utilized for a systematic conversion into a Petri net model of the underlying system. On top of the resultant Petri net, we are able to analyze qualitative properties of the given FMS. In particular, for the class of S3PR Petri nets, it is sufficient to check liveness property from minimal siphons and traps. In case the Petri net of the given FMS can get into a deadlock situation, we present a two-stage deadlock prevention algorithm that allows us to coordinate the resource sharing such that deadlock will not occur while maintaining maximal resource utilization. Our deadlock prevention algorithm, whose control policy consists of two main control stages: siphons control stage and augmented siphons control stage, has the least restrictive property among all algorithms reported. Finally, we present an object-oriented integrated environment that allows users to implement a cell controller by direct configuration of the modeled Petri nets without any programming efforts. To illustrate the methodology presented in this thesis, a cell controller has been successfully designed and implemented for the CIM center at the National Taiwan University of Science and Technology (NTUST).

Cover
Page
中文摘要
Abstract
Acknowledgments
Table of Contents
List of Figures
List of Tables
Chapter I Introduction
1.1 Flexible Manufacturing Systems
1.2 Background Review
1.3 Motivation and Contributions
1.3.1 New Petri net Modeling Methodology by Scenarios
1.3.2 Deadlock Analysis of Petri nets Using Siphon
1.3.3 New Deadlock Prevention Control Policy
1.3.4 New Development Environment of Cell Controllers
1.3.5 Main Contributions of the Thesis
1.4 Thesis Outline
Chapter II Background and Preliminary Results
2.1 Brief Review of Petri Nets Theory
2.2 Behavioral and Qualitative Properties of Petri Nets
2.3 Traditional Methods of Analysis for Petri Nets
2.3.1 The Coverability Tree
2.3.2 Incidence Matrix and State Equation
2.3.3 Simple Reductin Rules
2.4 Subclass of Petri Nets
2.5 Petri net Models of Shared Resource Systems
2.6 Augmented Marked Graph
2.7 Some Basic Properties of Petri Nets
Chapter III Modeling a Real-World Flexible Manufacturing System with Petri Nets
3.1 Introduction
3.2 The System Description
3.3 Layout of the Flexible Manufacturing System
3.3.1 Manufacturing Flows in the Cell Controller
3.4 The Relations of Scenarios and Petri Nets
3.5 Manufacturing Flows Mapped into Scenarios
3.6 An Augmented Marked Graph
3.7 Chapter Summaries
Chapter IV Deadlock Analysis of Petri Nets Using Siphon
4.1 Introduction
4.2 Review Properties Related to Siphons and Traps
4.3 Analysis the Model of A Cell Controller
4.4 A Deadlock System
4.5 Mixed Integer Programming Approach
4.6 Chapter Summaries
Chapter V A Deadlock Prevention Policy for A Class of Petri Nets
5.1 Introduction
5.2 Overview of A New Deadlock Prevention Control Policy
5.3 Principles and Theorems of the Deadlock Prevention Approach
5.3.1 Siphons Control
5.3.2 Augmented Siphon Control
5.4 A Deadlock Prevention Algorithm
5.5 A Production Cell
5.6 Chapter Summaries
Chapter VI A Development of Cell Controller Based on Petri Net
6.1 Introduction
6.2 Structure of the Cell Controller
6.3 Design of the Cell Controller Development Environment Using OMT
6.4 Implementation of the Cell Controller
6.5 Chapter Summaries
Chapter VII Conclusions and Future Research
7.1 Conclusion
7.2 Future Research
References
Vita
Publication List
授權書

[1] T. Agerwala and Y. Choed-Amphai, “A synthesis rule for concurrent systems,” in Proc. 15th Design Automat. Conf., Las Vegas, NV, pp. 305-311, 1978.
[2] G. Berthelot, “Checking properties of nets using transformation,” Advances In Petri nets 1985, G. Rozenberg, ED. Berlin, Germany: Springer-Verlag, pp. 19-40, 1985.
[3] E. R. Boer and T. Murata, “Generating basis siphons and taps of Petri nets using the sign incidence matrix,” IEEE Transactions on Circuits and Systems-I: Fundamental Theory and Applications, vol. 41, no. 4, pp. 266-271, April 1994.
[4] K. Barkaoui, and I. B. Abdallah, “Deadlock avoidance in FMS based on structural therory of Petri nets,” Proc. INRIA/IEEE Symposium on ETFA, vol. 2, no .4, pp. 499-510, 1995.
[5] K. Barkaoui, and I. B. Abdallah, “ A deadlock prevention method for a class of FMS,” Proc. IEEE Int. Conf. SMC, pp.4119-4124, 1995.
[6] Z. A. Banaszak and B. H. Krogh, “Deadlock avoidance in flexible manufacturing systems with concurrently competing process flows,” IEEE Trans. Robotics Automat., vol. 6, no. 6, pp. 724-734, 1990.
[7] F. Chu and X. Xie, “Deadlock analysis of Petri nets using siphons and mathematical programming,” IEEE Trans. Robotics Automat., vol. 13, no. 6, pp. 793-804, 1997.
[8] J. Campos, G. Chiola, and M. Silva, “Ergodicity and throughput bounds of Petri nets with unique consistent firing count vector,” IEEE Trans. Software Eng., vol. 17, pp. 117-125, 1991.
[9] E. G. Coffman, M. J. Elphick, and A. Shoshani, “System Deadlocks,” Computing Surveys, vol. 3, No. 2, pp. 67-78, 1971.
[10] J. Ezpeleta and J. M. Couvreur, “A new technique for finding a generating family of siphons, traps and st-components, Application to colored Petri nets,” Procs. 12th Int. Conf. on Appl. and Theory of Petri Nets, pp. 26-147, 1991.
[11] J. Ezpeleta, J. M. Colom, and J. Martinez, “A Petri net Based Deadlock Prevention Policy for Flexible Manufacturing Systems,” IEEE Trans. on Robotics and Automation, vol.11, no. 2, pp. 173-184, April 1995.
[12] M. P. Fanti, B. Maione, S. Mascolo, and B. Turchiano, “Event-based feedback control for deadlock avoidance in flexible production systems,” IEEE Trans. on Robotics and Automation, vol.13, no. 3, pp. 347-363, June 1997.
[13] M. A. Holliday and M. K. Vernon, “ A generalized timed Petri net model for performance analysis,” in Proc.1985 IEEE Int. Workshop on timed Petri nets, Torino, Italy, pp. 181-190.
[14] H. P. Huang and P. C. Chang, “Specification, modeling and control of a flexible manufacturing cell,” INT. J. Prod. Res., vol. 30, no. 11, pp. 2515-2543, 1992.
[15] F. S. Hsieh and S. C. Chang, “Dispatching-driven deadlock avoidance controller synthesis for flexible manufacturing systems,” IEEE Trans. Robotics Automat., vol. 10, no. 2, pp. 196-209, 1994.
[16] M. D. Jeng, “ Petri nets for modeling automated manufacturing systems with error recovery,” IEEE Trans. Robotics Automat., vol. 13, no. 5, pp. 752-760, 1997.
[17] M. D. Jeng and F. DiCesare, “Synthesis using resource control nets for modeling share-resource systems,” IEEE Trans. Robotics Automat., vol. 11, no. 3, pp. 317-327, 1995.
[18] M. D. Jeng and X. L. Xie, “Synthesis of resource control nets using siphons,” IEEE trans. Syst. Man. Cybern., Part A, vol. 29, no. 4, 1999.
[19] M. D. Jeng and X. L. Xie, “Synthesis of extended resource control nets using siphons,” to appear in IEEE Trans. Robotics Automat., 1999.
[20] M. D. Jeng and X. L. Xie, “Analysis of modularly composed nets by siphons”, IEEE Trans. Systems, Man, and Cybernetics-Part A: Systems and Humans, vol. 29, no. 4, pp. 399-406, 1999.
[21] M. D. Jeng, M. Y. Peng and Y. S. Huang, “An algorithm for calculation minimal siphons and traps of Petri nets,” International Journal of Intelligent Control and Systems,” Vol. 3, No. 3, pp. 263-275, 1999.
[22] I. Koh and F. DiCesare, “Modular transformation methods for generalized Petri nets and their applications in automated manufacturing systems,” IEEE Trans. Systems, Man, and Cybernetics, vol. 21, pp. 963-973, 1991.
[23] B. H. Krogh and C. L. Beck, “Synthesis of place/transition nets for simulation and control of manufacturing systems,” in Proc. 4th IFAC/IFORS Symp. Large Scale Syst., Zurich, Switzerland, pp. 661-666, 1986.
[24] M. Kinuyama and T. Mutrata, “Generating siphons and traps by Petri net representation of logic equations,” Procs. 2nd Conf. of the Net Theory SIG-IECE., pp. 93-100, 1986.
[25] K. H. Lee, J. Favrel, and P. Baptiste, “Generalized Petri net reduction method,” IEEE Trans. Systems, Man, and Cybernetics, SMC-17, pp. 297-303, 1987.
[26] M. A. Lawley, “Deadlock avoidance for production systems with flexible routing,” IEEE Trans. Robotics Automat., vol. 15, no. 3, pp. 497-509, 1999.
[27] T. Minoura and C. Ding, “A deadlock prevention method for a sequence controller for manufacturing control,” Int. J. Robotics Automat., vol. 6, no. 3, pp. 149-155, 1991.
[28] K. Lautenbach, “Linear algebraic calculation of deadlocks and traps,” Concurrency and Nets -- Advances in Petri Nets, Voss, Genrich, Rozenberg, Eds., New York: Springer-Verlag, pp. 315-336, 1987.
[29] T. Murata, “Petri Nets: Properties, analysis, and applications,” Proceedings of the IEEE, 77(4): 541 — 580, April 1989.
[30] K. E. Moore and S. M. Gupta, “Petri net models of flexible and automated manufacturing systems: a survey,” Int. J. Prod. Res., vol. 34, no. 11, pp. 3001-3035, 1996.
[31] Y. Narahari and N. Viswanadham, “ A Petri net approach to the modeling and analysis of flexible manufacturing systems,” Ann. Oper. Res., vol. 3, pp. 449-472, 1985.
[32] J. Park and S. Reveliotis, “Algebraic synthesis of efficient deadlock avoidance policies for sequential resource allocation systems,” IEEE Trans. on Robotics and Automation, vol.16, no. 2, pp. 190-195, April 2000.
[33] C. V. Ramamoorthy and G.S. Ho, “Performance evaluation of a synchronous concurrent systems using Petri nets,” IEEE Trans. Software Eng., vol. 6, no. 5, pp. 440-449, Setp. 1980.
[34] James Rumbaugh. Object-oriented modeling and design. Prentice Hall, 1991.
[35] Tien-Hsiang Sun, Chao-Weng Chen, and Li-Chen Fu, “A Petri net based approach to modeling and scheduling for an FMS and a case study,” IEEE Trans. on Industrial Electronics, vol. 41, no. 6, pp. 593-601,Dec. 1994.
[36] I. Suzuki and T. Murata, “A method for stepwise refinement and abstraction of Petri nets,” J. Comput. Syst. Sci., vol. 27, pp. 51-76, 1983.
[37] M. Tadashi, K. Saikusa, and K. Tsuji, “ The minimal number of live minimal structural traps to make an arbitrary minimal structural deadlock live in general Petri nets,” Proc. INRIA/IEEE Symposium on ISCAS, vol. 4, pp. 2217-2720, 1993.
[38] R. Valette, “ Analysis of Petri nets by stepwise refinement,” J. Comput. Syst. Sci., vol. 18, pp. 35-46, 1979.
[39] N. Viswanadham, Y. Narahari, and T. L. Johnson, “ Deadlock prevention and deadlock avoidance in flexible manufacturing systems using Petri net models,” IEEE Trans. Robotics Automat., vol. 6, no. 6, pp. 713-723, 1990.
[40] L. M. Wang and X. L. Xie, “Modular modeling using Petri nets,” IEEE Trans. Robotics Automat., vol. 12, pp. 800-809, 1996.
[41] N. Wu, “ Necessary and sufficient conditions for deadlock-free operation in flexible manufacturing systems using a colored Petri net model,” IEEE Trans. Systems, Man, and Cybernetics-Part C: Applications and reviews, vol. 29, no. 2, pp. 192-204, 1999.
[42] K. Y. Xing, B. S. Hu, and H. X. Chen, “Deadlock avoidance policy for Petri net modeling of flexible manufacturing systems with shared resources,” IEEE Trans. Automatic Control, vol. 41, no. 2, pp. 289-295, 1996.
[43] X. L. Xie and M. D. Jeng, “ERCN-merged nets and their analysis using siphons,” to appear in IEEE Trans. Robotics and Automat.
[44] M. C. Zhou, F. DiCesare, and D. Rudolph, “Design and implementation of a Petri net supervisory for a flexible manufacturing system,” Automatica, vol. 28, No. 6, pp. 1199-1208, 1992.
[45] M. C. Zhou and F. DiCesare, Petri Net Synthesis for Discrete Event Control of Manufacturing Systems, Boston, MA: Kluwer, 1993.
[46] M. C. Zhou, K. McDermott, and P. A. Patel, “Petri net systhesis and analysis of a flexible manufacturing system cell,” IEEE Trans. Systems, Man, and Cybernetics, vol. 23, pp. 523-531, 1993.
[47] M. C. Zhou and M. D. Jeng, “Modeling, analysis, simulation, scheduling, and control of semiconductor manufacturing systems: a Petri net approach,” IEEE Trans. Semicond. Manufact., vol.11, no. 3, Aug. 1998.
[48] M. C. Zhou and F. DiCesare., “Parallel and sequential mutural exclusions for Petri net modeling for manufacturing systems,” IEEE Trans. on Robotics and Automation, vol. 7, pp. 515-527, 1991.
[49] M. C. Zhou, F. DiCesare and A. A. Dosrochers, “ A top-down Modular Approach to Synthesis of Petri net Models for Manufacturing Systems,” Proc. of IEEE Robotics and Automation Conference, pp. 350-361, 1992.
[50] M. C. Zhou, F. DiCesare and A. A. Dosrochers, “ A Hybrid methodology for synthesis of Petri net models for manufacturing systems,” IEEE Trans. on Robotics and Automation, vol. 8, pp. 515-527, 1991.