臺灣博碩士論文加值系統

現今自動化物料搬運系統的應用層面廣泛，從倉儲、裝配中心、傳統製造工業到半導體晶圓廠，其中以無人搬運車(Automated Guided Vehicle, AGV)最具有彈性及較多人採用。無人搬運車系統設計時必須考慮一些管理問題，避免資源衝突與鎖死情形的發生，以及在最短時間內完成搬運的工作。當無人搬運車系統發生鎖死現象時可能造成整個系統癱瘓或變成阻塞，降低整個系統的生產效能。因此，本研究針對已知環境佈置及各台搬運車需求的情況下，探討以雙向單軌網路式路徑佈置，無人搬運車避免鎖死的最短旅行時間路徑規劃的問題。本研究方法以顏色時間派翠網路模型描述無人搬運車動態行為，用以分析無人搬運車的鎖死問題和避免法則，最後依據顏色時間派翠網路模式，在考慮同步的派遣下，規劃避免鎖死及最短搬運時間的派遣順序，研究中提出以最佳優先路徑搜尋法則，搜尋出無人搬運車的派遣順序，並評估此派遣順序的績效。

The automated guided vehicle (AGV) system is the most flexible material handling system. AGV system design must consider some management issues to avoid resource conflicts and deadlock situations from occuring, and to process material handling in the shortest time to complete the work. When AGV system deadlock occurs, the system may cause paralysis or blockage, and reduce the overall system productivity. In this research, based on the given layout and job requirements of a bidirectional AGV system, we investigated a deadlock-free system and the shortest travel time path. First, the AGV coloured timed petri net (ACTPN) model is established and is used to describe the dynamic behavior of AGVs to analyze the conditions of deadlock and establish the deadlock avoidance policies. Then, according to the deadlock avoidance policies and consider synchronous mode of operation, the Best-First search (BFS) rule is introduced to find the dispatching sequences for AGVs.

摘 要 i
ABSTRACT ii
誌謝 iii
目錄 iv
表目錄 vi
圖目錄 vii
第一章、緒論 1
1.1 研究背景與動機 1
1.2研究範圍與目的 3
1.3研究流程 4
第二章、文獻探討 6
2.1 AGV系統 6
2.1.1 AGV路徑設計與佈置 7
2.1.2AGV系統交通控制的問題 12
2.2派翠網路 17
2.2.1派翠網路的圖形結構 17
2.2.2派翠網路的定義 18
2.2.3派翠網路的特性與分析 19
2.2.4派翠網路的應用 22
2.2.5派翠網路應用於AGV系統鎖死的相關研究 25
2.3 搜尋策略 32
第三章、研究方法 33
3.1問題描述及基本假設 36
3.2產生AGV最短路徑 37
3.3建立ACTPN模型 38
3.3.1 ACTPN的符號定義及行為描述 39
3.3.2ACTPN的建構 42
3.4避免鎖死的策略 44
3.4.1 ACTPN初始鎖死的解決 44
3.4.2 ACTPN環狀鎖死的解決 46
3.4.3 ACTPN循環鎖死的解決 48
3.4.4 ACTPN最終站鎖死的解決 49
3.5路徑搜尋流程 50
3.6派翠網路模擬驗證 62
第四章、實例驗證 63
4.1 範例 63
4.1.1 產生AGV最短路徑 64
4.1.2 ACTPN的建模 66
4.1.3 ACTPN的鎖死分析 67
4.1.4 最短旅行時間與避免鎖死的路徑求解 72
4.1.5 路徑與鎖死的驗證 81
4.1.6 績效評估 94
第五章、結論與建議 95
參考文獻 97

[1].曾憲雄，黃國禎，2002，人工智慧與專家系統－理論、實務、應用，旗標出版，台北。
[2].黃國卿，1995，”簡介圖論演算法”，數學傳播，19卷，3期，頁1-12，9月。
[3].Aized, T., 2009, “Modelling and performance maximization of an integrated automated guided vehicle system using coloured Petri net and response surface methods”, Computers & Industrial Engineering, vol.57, pp.822-831.
[4].Correa, A. I., Lavgevin, A., and Rousseau L. M.,2007, “Scheduling and routing of automated guided vehicles:a hybrid approach”, Computers & Operations Research, vol.34,no.6,pp.1688-1707.
[5].Dotoli, M., and Fanti, M., P., 2004,”Coloured timed petri net model for real-time control of automated guided vehicle systems”,International Journal of Production Research, vol.42, no.9, pp.1787-1814.
[6].Egbelu, P. J. and Tanchoco, J. M. A., 1984, “Characterization of automatic guided vehicle dispatching rules”, International Journal of Production Research, vol.22, no.3, pp.359-374.
[7].Fanti, M.P., 2002, “A deadlock avoidance strategy for AGV systems modeled by coloured petri nets”, Sixth International Workshop on Discrete Event Systems, pp.61-66.
[8].Ghasemzadeh, H., Behrangi, E., and Azgomi, A.,2009, “Conflict-free scheduling and routing of automated guided vehicles in mesh topologies”, Robotics and Autonomous Systems, vol.57, no.6, pp.738-748.
[9].Hsieh, S., 1998, “Synthesis of AGVS by coloured-timed petri nets”, International Journal of Computer Integrated Manufacturing, vol.11, no.4, pp.334-346.
[10].Ho, Y. C., and Liao, T. W., 2009, “Zone design and control for vehicle collision prevention and load balancing in a zone control AGV system”, Computers & Industrial Engineering, vol.56, pp.417-432.
[11].Jensen, K., 1996, Coloured petri nets : basicconcepts, analysis methods and practical use volume 1, Springer-Verlag Berlin Heidelberg.
[12].Kim, C.W., and Tanchoco, J.M.A., 1991, “Confict-free shortest-time bidirectional AGV routeing”, International Journal of Production Research, vol.29, no.12, pp.2377-2391.
[13].Kim, C.W. and Tanchoco, J.M.A .,1993, “Operational control of a bidirectional automated guided vechicle system”, International Journal of Production Research, vol.31, no.9, pp.2123-2138.
[14].Murata, T., 1989, “Petri nets: properties, analysis and application”, Proceedings of the IEEE, vol. 77, no.4, pp. 541-580.
[15].Moorthy, R. L. et al., 2003, “Cyclic deadlock prediction and avoidance for zone-controlled AGV system”, International Journal of Production Economics, vol.83, no.3, pp.309-324.
[16].Maza, S. and Castagna, P., 2005, “A performance-based structural policy for conflict-free routing of bi-directional automated guided vehicles”, Computers in Industry, vol.56, pp.719-733.
[17].Nishi, T., Audo, M. and Konishi M.,2006,”Experimental studies on a local rescheduling procedure for dynamic routing of autonomous decentralized AGV systems”, Robotics and Computer-Integrated Manufacturing, vol.22, no.2, pp.154-165.
[18].Nishi, T. and Maeno, R., 2010, “Petri net decomposition approach to optimization of route planning problems for AGV systems”, IEEE Transactions on Automation Science and Engineering, vol.7, no.3, pp.523-537.
[19].Peterson, J.L., 1977, “Petri Nets”, Computing Surveys, vol.9, no.3, pp.223-252.
[20].Peterson, J.L., 1981, Petri Net Theory and the Modeling of Systems, Prentice Hall, NJ, USA.
[21].Smolic-Rocak, N., Bogdan, S., Kovacic, Z., Petrovic, T., 2010, “Time windows based dynamic routing in multi-AGV systems”, IEEE Transactions on Automation Science and Engineering, vol.7, no.1, pp.151-155.
[22].Le, A.T. , and De, K.M.B.M., 2006, “A review of design and control of automated guided vehicle systems”, European journal of operational research, vol.171, pp.1-23.
[23].Laporte, G.,Farahani, R.Z., and Miandoabchi, E.,2006,”Designing an efficient method for tandem AGV network design problem using tabu search.”, Applied Mathematics and Computation, vol.183, no.2, pp.1410-1421.
[24].Vis, I. F.A., 2006, “Survey of research in the design and control of automated guided vehicle systems”, European Journal of Operational Research, vol.170, pp.677-709.
[25].Wu, N. and Zhou, M.C., 2007, “Shortest routing of bidirectional automated guided avoiding deadlock and blocking”, IEEE/ASME Transactions on Mechatronics, vol.12, no.1, pp.63-72.
[26].Wu, N., and Zhou, M., 2005, “Modeling and deadlock avoidance of automated manufacturing systems with multiple automated guided vehicels”, IEEE Transactions on Systems, Man, and Cybernetics—Part B: Cybernetics, vol. 35, no. 6, pp.1193-1202
[27].Zeng, L., Wang, H.P., and Jin, S., 1991, “Conflict detection of automated guided vehicles:a petri net approach”, International Journal of Production Economics,vol.29, no.5, pp.865-879.
[28].Zhou M. and Jeng M. D., 1998, “Modeling, analysis, simulation, scheduling, and control of semiconductor manufacturing systems: a petri net approach”, IEEE Transactions on Semiconductor Manufacturing, vol.11, no.3, pp.333-357.
[29].Zhou, M. and Venkatesh, K., 1999, Modeling, Simulation, and Control of Flexible Manufacturing Systems: a Petri net approach. Singapore, New York.