臺灣博碩士論文加值系統

彈性製造系統系由一整合電腦控制且能進行多種加工程序的製造系統。本論文專注於派屈網路理論於彈性製造系統的應用，其應用有三:塑模問題、效能問題、死結問題。在塑模方面本論文首先建構PN-Based單元控制器(Cell Controller)，接著利用兩階層式概念建立PN-Editor核心部分，階層ㄧ為派屈網路場景模式塑模，階層二為廣義隨機派屈網路(GSPN, Generalized Stochastic Petri Net)塑模。然後在系統效能方面，先研究紅綠燈交通控制系統，接著利用交通控制的概念來增進彈性製造系效能。最後針對無可避免的派屈網路建模過程中常會遇到的死結問題，本論文亦提出一套新的死結避免策略。

A flexible manufacturing system (FMS) is a computer-controlled configuration where different operations can be processed. This dissertation focuses on FMS modeling, performance, and deadlock prevention using the Petri net theory. First, a new simulated environment for flexible manufacturing is proposed. Second, this dissertation uses the concept of two levels of hierarchy in order to design the PN-editor of the simulated environment and calculate the system performance. The first level is the scenario modeling method and the second level is the generalized stochastic Petri net modeling method. Third, a module of the basic traffic system with a signal timing plan for a day is successfully developed. Subsequently, the concept of traffic light controller is used in the improvement of the performance of FMS. Finally, this dissertation proposed a new deadlock prevention policy to solve the system deadlock problem.

誌謝 ii
摘要 iii
ABSTRACT iv
目錄 v
表目錄 viii
圖目錄 ix
1. 緒論 1
1.1 研究動機與目的 1
1.2 文獻回顧 2
1.3 論文架構 4
2. 方法論 5
2.1 派屈網 5
2.1.1 派屈網路理論 6
2.1.2 派屈網路狀態空間(State Space) 8
2.1.3 派屈網路線性代數(Linear Algebra) 9
2.1.4 派屈網路圖形結構(Graph-Based Structural) 10
2.2 廣義隨機派屈網 14
2.3 顏色時間派屈網 15
3. 彈性製造系統塑模與效能分析 17
3.1 可勾構彈性製造系統單元控制器設計 17
3.2 場景模式塑模方法 26
3.3 廣義隨機派屈網塑模方法 34
3.4 彈性製造系統效能分析 41
4. 紅綠燈控制系統塑模暨其應用於彈性製造系統 48
4.1 紅綠燈控制系統塑模 48
4.1.1 交通訊號控制時間安排之描述 48
4.1.2 交通訊號時間安排之塑模 49
4.1.3 交通訊號時間安排系統模型分析與驗證 54
4.2 紅綠燈控制系統應用於彈性製造系統 63
4.2.1 基本交通控制策略 63
4.2.2 實際案例實現 67
5. 彈性製造系統死結避免 75
5.1 TS3PR模型塑模與分析 75
5.2 基於可達樹技巧之死結避免 78
6. 結論與展望 89
6.1 結論 89
6.2 展望 90
參考文獻 92
論文發表 101
自 傳 102

參考文獻
[1]Murata, T., “Petri Nets: Properties, Analysis and Applications,” In Proc. IEEE, April, pp. 541-580, IEEE, 1989.
[2]Peterson, J.L., Petri Net Theory and the Modeling of Systems Prentice Hall, Englewood Cliffs, NJ, 1981.
[3]Molly, M.K., “Performance Analysis Using Stochastic Petri Nets,” IEEE Trans. on Computers, Vol. C-31, pp. 913-917, 1982.
[4]Marsan, M.A., Balbo, G., Conte, G., “A Class of Generalized Stochastic Petri Nets for the Performance Analysis of Multiprocessor Systems,” ACM Transactions on Computer Systems, 2(1), pp. 93-122, 1984.
[5]Molly, M.K, “Discrete Time Stochastic Petri Nets,” IEEE Trans. on Software Engineering, Vol. SE-11, pp. 417-423, 1985.
[6]Marsan M.A., “Stochastic Petri Nets: An Elementary Introduction. In Advances in Petri Nets,” Lecture Notes in Computer Science, pp. 1-29, Springer-Verlag, 1989.
[7]Marsan, M.A., Balbo, G., and Conte, G., “Petri Nets in Performance Analysis: An Introduction,” Lecture Notes in Computer Science, Vol. 1491, pp. 211-256, 1996.
[8]Hass, P.J., “Stochastic Petri Nets for Modeling and Simulation,” Proceedings of the Winter Simulation Conference, pp.101-112, 2004.
[9]Wang, J.C., Timed Petri Nets: Theory and Application, Kluwer Academic Publishers. Boston, 1998.
[10]Jensen K., Coloured Petri Nets. vol. 1, Springer-Verlag, 1997.
[11]Jensen K., Coloured Petri Nets. vol. 2, Springer-Verlag, 1997.
[12]Bause, F. and Kritzinger, P.S., Stochastic Petri Nets: An Introduction to The Theory, Vieweg Verlag, Germany, 2002.
[13]Marsan, M.A., Balbo, G., Conte, G., Donatelli, S., and Franceschinis, G., Modeling with Generalized Stochastic Petri Nets, Wiley Series in Parallel Computing, 1995.
[14]Behera, T.K., Mishra, B.S., Patnaik, L.M., and Girault, C., “Modelling and Performance Evaluation of Flexible Manufacturing Systems Using Deterministic and Stochastic Timed Petri Nets,” In Proc. Fourth International Conference on Factory 2000 - Advanced Factory Automation, United Kingdom, pp. 362-368, 1994.
[15]Crockett, D., Desrochers, A., DiCesare, F., and Ward, T., “Implementation of A Petri Net Controller for A Machining Workstation,” In Proc. IEEE International Conference on Robotics Automation, Raleigh, NC, pp. 1861-1867, 1987.
[16]Camurri, A., and Franchi, P., “An Approach to The Design and Implementation of The Hierarchical Control System of FMS, Combining Structured Knowledge Representation Formalisms And High-Level Petri-Nets,” In Proc. IEEE International Conference on Robotics and Automation, Vol. 1, pp. 520-525, 1990.
[17]Fanti, M. P., Maione, B., Piscitelli, G., and Turchiano, B., “System Approach to Design Generic Software for Real-Time Control of Flexible Manufacturing Systems,” IEEE Trans. on Systems, Man, and Cybernetics, Part A: Systems and Humans, Vol. 26, Issue: 2, pp. 190-202, 1996.
[18]Gonzalez, F.G. and Davis, W.J., “A Simulation-Based Controller for A Flexible Manufacturing Cell,” IEEE International Conference on Systems, Man and Cybernetics, Vol. 4, pp. 3642-3647, 1997.
[19]Gonzalez, F.G., Davis, W.J., “Developing A Physical Emulator for A Flexible Manufacturing System,” IEEE International Conference on Systems, Man and Cybernetics, Vol. 1, pp. 710-715. IEEE Piscataway, New Jersey, 1998.
[20]Huang, H. P., and Chang, P. C., “Specification, Modeling and Control of A Flexible Manufacturing Cell,” International Journal of Production Research, Vol. 30, Issue: 11, pp. 2515-2543, 1992.
[21]Huang, Y.S., “A Simulation-Based Equipment Environment for Flexible Manufacturing Systems,” 12th IFAC Symposium on Information Control Systems in Manufacturing, Vol.2, pp. 131-136, 2006.
[22]Jianhua, Y., Fujimoto, Y., “Modeling, Implementation and Simulation of Virtual Factory Based on Colored Timed Petri Net,” In Proceeding of the Emerging Technologies and Factory Automation. vol.1, pp. 574-579 , 2003.
[23]Moyne, J. R., and McAfee, L.C., “A Generic Cell Controller for The Automated VLSI Manufacturing Facility,” IEEE Trans. on Semiconductor Manufacturing, Vol.5, pp.77-87, 1992.
[24]Moore, K.E., and Gupta, S. M., “Petri Net Models of Flexible and Automated Manufacturing Systems: A Survey,” International Journal of Production Research, Vol.34, No. 11, pp. 3001-3035, 1996.
[25]Sun, T. H., Chen, C. W. and Fu L. C., “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, 1994.
[26]Uchitel, S., Kramer, J., and Magee, J., “Synthesis of Behavorial Models From Scenarios,” IEEE Trans on Software Engineering, Vol.29, pp. 99-115, 2003.
[27]Yep, C.K., Boey, S.H., and Goh, J., “A Framework for A Knowledge-Based Cell Controller For Flexible Manufacturing Systems,” In Proc. of the Emerging Technologies and Factory Automation, pp. 257-264, 1993.
[28]Yan, P., Zhou, M.C., Hu, B., and Feng, Z., “Modeling and Control of The FMS Workstation Level Information Flow by A Modified Petri Net,” In Proc. 6th ETFA Int. Conf., pp. 321-326, 1997.
[29]Balbo, G., Chiola, G., Franceschinis, G., and Roet, G.M., “Generalized Stochastic Petri Nets for the Performance Evaluation of FMS,” In Proc. IEEE International Conference on Robotics and Automation, Raleigh, NC, pp. 1013-1018, 1987.
[30]Holliday, M. A., and Vernon, M. K., “A Generalized Timed Petri Net Model for Performance Analysis,” IEEE Trans. on Software Engineering, Vol.13, and Issue: 12, pp. 181-190, 1987.
[31]Dotoli, M., Fanti, M.P., and Lacobellis, G., “Validation of an Urban Traffic Network Model Using Colored Timed Petri Nets,” IEEE International Conference on Systems, Man and Cybernetics, Waikoloa, HI, U.S., pp. 1347-1352, 2005.
[32]Davison, E.J., Ozguner U., “Decentralized Control of Traffic Networks,” IEEE Trans. on Automatic Control, 28, pp. 677-688, 1983.
[33]Febbraro A.D., Giglio D., and Sacco N., “Urban Traffic Control Structure Based on Hybrid Petri Nets,” IEEE Trans. on Intelligent Transportation Systems, Vol. 5, Issue: 4, pp. 224-237, 2004.
[34]Gartner, N.H., “OPAC: A Demand-Responsive Strategy for Traffic Signal Control,” IEEE Trans. Research Record, Issue: 906, pp. 75-81, 1983.
[35]Hung, Y.S., Chung, T.H., and Chen, C.T., “Modeling Traffic Signal Control Systems Using Timed Colour Petri Nets,” In Proc. IEEE International Conference on Systems, Man, and Cybernetics, Vol. 2, pp. 2530-2535, 2005.
[36]Little, J.D.C., “The Synchronization of Traffic Signals by Mixed Integer-Linear-Programming,” Massachusetts Instute of Technology, Technical Report No. 19, 1965.
[37]Lim, J.H., Hwang, S.H., Suh, I.H., and Bien, Z., “Hierarchical Optimal Control of Oversaturated Urban Traffic Networks,” International Journal of Control, Vol. 33, No. 4, pp. 727-737, 1981.
[38]Lin, L., Nan, T., Xiangyang, M., and Fubing, S., “Implementation of Traffic Lights Control Based on Petri Nets,” In Proceedings of IEEE Intelligent Transportation Systems, Shanghai, China, pp.1087-1090, 2003.
[39]List G.F., and Cetin M., “Modeling Traffic Signal Control Using Petri Nets,” IEEE Trans. on Intelligent Transportation Systems, Vol. 5, pp. 177- 187, 2004.
[40]Papageorgiou M., Diakaki, C., Dinopoulou, V., Kotsialos, A., and Wang, Y., “Review of Road Traffic Control Strategies,” In Proc. IEEE, Dec., pp. 2043-2067, 2003.
[41]Tolba C., Thomas P., ElMoudni, A., and Lefebvre, D., “Performances Evaluation of the Traffic Control in A Single Crossroad by Petri Nets,” In Proceedings of IEEE Emerging Technologies and Factory Automation, Lisbon, Portugal, pp. 157-160, 2003.
[42]Wang, H., List, G.F., and DiCesare, F., “Modeling and Evaluation of Traffic Signal Control Using Timed Petri Nets,” In Proceedings of IEEE Systems, Man and Cybernetics, Le Touquet, France, pp. 180-185, 1993.
[43]Wang, J.C., Jin, C., and Deng, Y., “Performance Analysis of Traffic Networks Based on Stochastic Timed Petri Net Models,” In Proceedings of IEEE Engineering of Complex Computer Systems, Las Vegas, NE, U.S., pp.77-85, Oct. 1999.
[44]Banaszak, Z.A., and Krogh, B.H., “Deadlock Avoidance in Flexible Manufacturing Systems with Concurrently Competing Process Flows,” IEEE Trans. on Robotics and Automation, Vol. 6, No. 6, pp. 724-734, 1990.
[45]Coffman, E.G., Elphick, M.J., and Shoshani, A., “System Deadlocks,” Couputing Surveys, Vol.3, No 2, pp. 67-78, 1971.
[46]Chao, D.Y., “An Incremental Approach to Extracting Minimal Bad Siphons,” Journal of Information Science and Engineering, Vol. 23, pp. 203-214, 2007.
[47]Chao, D. Y., “A Graphic-Algebraic Computation of Elementary Siphons of BS3PR,” Journal of Information Science and Engineering, Vol. 23, 1817-1831, 2007.
[48]Ezpeleta, J., Colom, J.M., and Martinez, J., “A Petri Net Based Deadlock Prevention Policy for Flexible Manufacturing Systems,” IEEE Trans. on Robotics and Automation, Vol. 11, No2, pp.173-184, Apr., 1995.
[49]Ezpeleta, J., Tricas, F., Garc´ıa-Vall´es, F., and Colom, J., “A Banker’s Solution for Deadlock Avoidance in FMS with Flexible Routing and Multisource States,” IEEE Trans. on Robotics and Automation, Vol. 18, No. 4, 621-625, 2002.
[50]Ezpeleta, J., and Recalde, L., “A Deadlock Avoidance Approach for Non Sequential Resource Allocation Systems,” IEEE Trans. on Systems, Man, and Cybernetics, Part A: Systems and Humans, Vol. 34, No. 1, pp. 93-101, 2004.
[51]Huang, Y.S., Jeng, M.D., Xie, X.L., and Chung, T.H., “Deadlock Prevention Policy Based on Petri Nets and Siphons,” International Journal of Production Research, Vol. 39, No. 3, pp. 283-305, 2001.
[52]Huang, Y.S., Jeng, M.D., Xie, X.L., and Chung T.H., “A Siphon-Based Deadlock Prevention Policy for Flexible Manufacturing Systems,” IEEE Trans. on Systems, Man, and Cybernetics, Part A: Systems and Humans, Vol. 36, No. 6, pp. 2152-2160, 2006.
[53]Huang, Y.S., “Design of Deadlock Prevention Supervisors Using Petri Nets,” International Journal of Advanced Manufacturing Technology, Vol. 35, No.3-4, pp. 349-362, 2007.
[54]Iordache, M.A., and MAntsaklis, P.J., “Design of T-liveness Enforcing Supervisors in Petri Nets,” IEEE Trans. on Automatic Control, 48(11), 1962-1974, 2003.
[55]Jeng, M. D., and DiCesare, F., “Synthesis Using Resource Control Nets for Modeling Share-Resource Systems,” IEEE Trans. on Robotics and Automation, Vol. 11, No. 3, pp. 317-327, 1995.
[56]Lawley, M. A., “Deadlock Avoidance for Production Systems with Flexible Routing,” IEEE Trans. on Robotic and Automation, Vol. 15, pp. 497-509, 1999.
[57]Li, Z.W., Zhou, M.C., “Elementary Siphons of Petri Nets and Their Application to Deadlock Prevention in Flexible Manufacturing Systems,” IEEE Trans. on Systems, Man, and Cybernetics, Part A: Systems and Humans, Vol. 34, No. 1, pp. 38-51, 2004.
[58]Li, Z.W., and Zhou, M.C., “Two-Stage Method for Synthesizing Liveness-Enforcing Supervisors for Flexible Manufacturing Systems Using Petri Nets,” IEEE Trans. On Industrial Informatics, Vol. 2, No. 4, pp. 313-325, November, 2006.
[59]Li, Z.W., Zhou, M.C., and Uzam, M., “Deadlock Control Policy for A Class of Petri Nets Without Complete Siphon Enumeration,” IET Control Theory & Applications, pp. 1594-1605, 2007.
[60]Li, Z.W., Zhou, M.C., and Jeng, M.D., “A Maximally Permissive Deadlock Prevention Policy for FMS Based on Petri Net Siphon Control and the Theory of Regions,” IEEE Trans. On Automation Science and Engineering, Vol. 5, No. 1, pp. 182-188, January, 2008.
[61]Li, Z.W., Zhou, M.C., and Wu, N.O., “Control of Elementary and Dependent Siphons in Petri Nets and Their Application,” IEEE Trans. on Systems, Man, Cybernetics, Part C: Systems and Humans, Vol. 38, No. 1, pp. 133-148, January, 2008.
[62]Li, Z.W., and Zhao, M., “On Controllability of Dependent Siphons for Deadlock Prevention in Generalized Petri Nets,” IEEE Trans. on Systems, Man, Cybernetics, Part A: Systems and Humans, Vol. 38, No. 2, pp. 369-384, March, 2008.
[63]Li, Z.W., and Zhou, M.C., “A Survey and Comparison of Petri Net-Based Deadlock Prevention Policies for Flexible Manufacturing Systems,” IEEE Trans. on Systems, Man, Cybernetics, Part A: Systems and Humans, Vol. 38, No. 2, pp. 173-188, March, 2008a.
[64]Li, Z.W. and Zhou, M.C., “On Siphon Computation for Deadlock Control in A Class of Petri Nets,” IEEE Trans. on Systems, Man, Cybernetics, Part A: Systems and Humans, Vol. 38, No. 3, pp. 667-679, May, 2008b.
[65]Uzam, M. and Zhou, M.C., “An Iterative Synthesis Approach to Petri Net-Based Deadlock Prevention Policy for Flexible Manufacturing Systems,” IEEE Trans. on Systems, Man, Cybernetics, Part A: Systems and Humans, Vol. 37, No. 3, pp. 362-371, May. 2007.
[66]Viswanadham, N., Narahari, Y., and Johnson, T.L., “Deadlock Prevention and Deadlock Avoidance in Flexible Manufacturing Systems Using Petri Net Models,” IEEE Trans. on Robotics and Automation, Vol. 6, No. 6, pp. 713-723, 1990.
[67]Zhou, M.C., DiCesare, F., and Guo, D., “Modeling and Performance Analysis of A Resource-Sharing Manufacturing System Using Stochastic Petri Nets,” In Proc. IEEE Int. Conf. Intelligent Control, Vol. 2, pp. 1005-1010, 1990.
[68]Zhou, M.C., DiCesare, F., “Parallel and Sequential Mutual Exclusions for Petri Net Modeling for Manufacturing Systems,” IEEE Trans. On Robotics and Automation, Vol. 7, pp. 515-527, 1991.
[69]Zhou, M.C., Mcdermott, K., and Pael, P.A., “Petri Net Synthesis and Analysis of a Flexible Manufacturing System Cell,” IEEE Trans. On Systems, Man and Cybernetics, Vol. 23, Issue: 2, pp. 523-531, 1993.
[70]Berthomieu, B. and Vernadat, F., “Time Petri Nets Analysis with TINA,” IEEE Computer Society Press, pp. 123-124, 2006.
[71]Zimmermann, A., and Freiheit, J., “TimeNET/Sub MS/-An Integrated Modeling and Performance Evaluation Tool for Manufacturing Systems,” IEEE International Conference on Systems, Man and Cybernetics, Vol. 1, pp. 535-540, 1998.
[72]http://wiki.daimi.au.dk/cpntools/cpntools.wiki, Computer Tool for Coloured Petri Nets
[73]http://en.wikipedia.org/wiki/Petri_net, Petri Net