隨著科技的不斷進步以及智慧工廠自動化的快速發展，各半導體廠紛紛建置智慧工廠並導入自動化物料搬運系統(Automatic material handling system，AMHS)、（Overhead Hoist Transport，OHT）來取代傳統人力。然而隨著製程規模的擴大和複雜度的增加，OHT所對應的設備也越來越多樣化，由於各設備的穩定性不同，其所造成的異常因子也呈幾何倍數的增加。其中最為常見的即是因設備異常導致大量OHT回堵壅塞，若是OHT上載有Q-Time限制的物料，則其造成的損失會相當的巨大。過去文獻大多探討如何因應設備異常，調整整體天車排程。本研究所探討之天車排程屬於NP-hard問題，此類排程問題大多的解決方案是使用啟發式演算法，獲得次優解或是近似解。然而，隨著環境變數的增加，求得一個合適解(feasible solution)所需的時間也會呈指數級增長。
本研究以減少壅塞為目的，提出一套預測天車壅塞演算法（Congestion-Prediction,CP），以判斷路段是否壅塞。若預測某天車未來之行走路徑將壅塞，則將天車將提前繞道，減低天車回堵所帶來的後續損失。根據實驗結果顯示，本演算法可根據現場情況和異常事件，有效且即時地改變天車路徑，減少OHT壅塞現象，完成實質上提升整體天車排程系統的效率。

With the continuous advancement of technology and the rapid development of smart factory automation, many semiconductor factories are building smart factories and introducing Automatic Material Handling Systems (AMHS) and Overhead Hoist Transport (OHT) to replace traditional manual labor. However, as the scale and complexity of manufacturing processes increase, the types of equipment that the OHT interacts with are becoming increasingly diverse. Due to the varying reliability of each equipment, the potential causes of anomalies multiply geometrically. One of the most common issues is equipment malfunction leading to a large number of OHTs getting Congestion. If the OHT is carrying materials with Q-Time restrictions, the resulting losses can be significant.

Previous literature mostly discusses how to respond to equipment anomalies and adjust the OHT scheduling. The OHT scheduling problem discussed in this research is an NP-hard problem. Most solutions to this type of scheduling problem use heuristic algorithms to obtain sub-optimal or approximate solutions. However, as the number of environmental variables increases, the time required to find a feasible solution also grows exponentially.
The goal of this study is to reduce congestion and proposes a congestion-prediction algorithm (CP) to judge whether a section is congested. If it is predicted that the future path of a OHT will be congested, the OHT will be rerouted in advance to reduce subsequent losses.

Experimental results show that this algorithm can effectively and promptly change the path of the OHT according to the site conditions and abnormal events, reduce OHT congestion, and effectively improve the OHT scheduling system.

目錄
論文審定書 i
誌謝 ii
摘要 iii
Abstract iv
目錄 vi
圖次 viii
表次 ix
第一章 緒論 1
1.1 研究背景 1
1.2 研究動機 2
1.3 研究目的 4
第二章 文獻探討 6
2.1 自動化物料搬送系統研究 6
2.2 空中走行式無人搬運車 6
2.3 車輛途程問題 7
2.4 基因演算法 7
2.5 螞蟻演算法 8
2.6 機器學習 8
2.7 天車排程 9
第三章 研究方法 11
3.1 系統環境說明 11
3.2 系統架構 13
3.3 壅塞預測演算法步驟 14
第四章 研究結果分析 24
4.1 單區塊路徑測試 25
4.2 異常測試 28
4.3 全域固定初始測試 29
4.4 全域隨機測試 31
4.5 測試總結 32
第五章 結論與建議 33
參考文獻 35

Ada, C., Chengbin, C., & Feng, C. (2002). Multicyclic hoist scheduling with constant processing times. IEEE Transactions on Robotics and Automation, 18(1), 69-80. doi:10.1109/70.988976
Colorni, A., Dorigo, M., & Maniezzo, V. (1991). Distributed optimization by ant colonies. Paper presented at the Proceedings of the first European conference on artificial life.
Holland, J. H. (1992). Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence: MIT press.
ICINSIGHTS. (2018). Advanced Technology Key to Strong Foundry Revenue per Wafer. Retrieved from https://www.icinsights.com/data/articles/documents/1108.pdf
Lei, L., and Wang, T.-J. (1989). A proof: The cyclic hoist scheduling problem is NP-complete. Working paper,Rutgers University., 86-16.
Uchoa, E. (2011). Cuts over extended formulations by flow discretization. Progress in combinatorial optimization, 144-160.
王天威. (2007). 應用蟻群演算法於求解供應鏈中整合產品製造與成品配送兩階段問題. (碩士). 國立交通大學, 新竹市.
林東清. (2018). 資訊管理：e化企業的核心競爭能力(7版) (七版 ed.): 智勝.
紀碧如. (2006). 基因演算法用於增加產能的研究-以TFT-LCD廠Array製程RGV搬送為例. (碩士). 國立交通大學, 新竹市.
徐孟維. (2018). 機器學習於無人搬運車系統之派車應用. (碩士). 國立清華大學, 新竹市.
張哲偉. (2016). 用於影像辨識之擴增學習系統演算法與架構設計. (碩士). 國立臺灣大學, 台北市.
陳于風. (2013). 無人工廠興起 有利產業長期發展. CTIMES. Retrieved from https://www.ctimes.com.tw/DispArt/tw/130312120890.shtml
陳紹偉. (1999). 12吋IC代工廠自動搬運系統之系統模擬與派工法則的研究. (碩士). 國立臺灣大學, 台北市.
馮鈺琴. (2014). 敏捷式專案管理應用在工廠設施佈置專案之研究. (碩士). 國立高雄應用科技大學, 高雄市.
楊青峰. (2003). 多載量無人搬運車(AGV)運送派車法則的探討. (碩士). 國立中央大學, 桃園縣.
溫盛夫. (2010). AMHS派貨邏輯利用類神經網路結合遺傳演算法實現效能動態最佳化研究. (碩士). 國立中央大學, 桃園縣.
葉瑾瑜. (2014). Q-Time防守之排程-晶圓製造為例. (碩士). 國立雲林科技大學, 雲林縣.
韓孟儒、孫彥碩. (2017). 無塵室AGV產品發展概況. 機械工業雜誌(412期), 44-45. Retrieved from https://www.automan.tw/magazine/magazineContent.aspx?id=32
顏豪君. (2006). 快速評估12吋晶圓廠AMHS的模擬方法. (碩士). 國立交通大學, 新竹市.