考慮多個自動倉儲之聯合迴流式混合流程型生產排程與載具指派問題之研究

Joint Reentrant Hybrid Flowshop Scheduling and Vehicle Assignment Problem with Multiple Stockers

郭勁宏(Chin-Hung Kuo)

指導教授 ： 林春成

國立交通大學/管理學院/工業工程與管理系所/碩士(2018年)

摘要

在半導體等相關高科技製造產業中，產品製造程序趨於繁雜，且經常需要迴流至先前階段工作站之平行機台進行加工。隨著製程程序增加、機台前緩存區容量有限、與迴流次數頻率增加，當在製品阻塞且未有效規劃此類迴流式混合流程型生產之排程，將導致生產週期大幅提升。雖然過去相關研究已考慮了自動物料搬運系統（Automated Material Handling System，AMHS）中單一個自動倉儲（Stocker）來解決在製品儲存問題，然而卻未考慮更為一般化的多個獨立性自動倉儲（Multiple Independent Stockers），且未考慮實際搬運載具之指派（Vehicle Assignment），以致於忽略了載具會同時被指派至多項搬運任務之問題，亦忽略了被指派下個搬運的作業須等待當前搬運作業完成才能進行搬運之問題。因此，本研究考慮有多個獨立性自動倉儲、有限載具指派、以及載具搬運時間的迴流式混合流程型生產排程問題，而目標則是最小化最大完工時間。而過去研究已證實混合流程型生產排程問題為NP-hard問題，因此本研究問題亦為NP-hard。因此本研究進一步提出協同共演化式混合型和聲搜尋與基因演算法（Cooperative Coevolutionary Hybrid Harmony Search and Genetic Algorithm，CHSGA）進行求解。協同共演化機制（Cooperative Coevolution）過去研究已證實能有效解決高維度複雜之最佳化問題，其概念是將高維度複雜問題簡化成多個低維度複雜子問題後求解，並提升各子問題之求解多樣性。雖然過去研究已將協同共演化機制結合和聲搜尋演算法，然而一般而言和聲搜尋演算法在局部搜索能力較差，因此本研究則進一步將局部搜尋能力較好的基因演算法結合到此演算法。最終分別針對不同工單批量大小、製程階段以及迴流次數之生產環境下，本演算法相較於過去演算法能有效規劃生產排程來降低生產週期，並在適當的時機有效分配空缺的載具來進行在製品搬運。

關鍵字

迴流式製程 ； 生產排程 ； 自動倉儲 ； 協同共演化 ； 和聲搜尋演算法

並列摘要

In the related high-tech manufacturing industries such as semiconductors. The manufacturing process of products tends to be complicated, and it is often necessary to return to the parallel machine of the workstation in the previous stage for processing. As the number of process programs increases, the capacity of buffer area is limited, and the frequency of reentrant times increases, when the WIPs are obstructed and the scheduling of reentrant hybrid flowshop production processes is not effectively planned, the production cycle will be significantly increased. Although past related research has considered a single stocker in the automatic material handling system to solve WIP storage problems. However, it did not consider the more generalized multiple independent stockers and did not consider the Vehicle Assignment of the transport vehicle. Thus, the problem that the vehicle is assigned to multiple transportation tasks at the same time is neglected, and the problem of assigning the next transportation operation to wait for the completion of the current transportation operation is also ignored. Therefore, this study considers the issue of multiple independent stockers, limited vehicle assignment, and transport time of vehicle for the reentrant hybrid flowshop scheduling problem, with the goal of minimizing the maximum makespan. However, the research has confirmed that the hybrid flowshop scheduling problem is NP-hard. Therefore, this research problem is also NP-hard. Therefore, this study proposes a Cooperative Coevolutionary Hybrid Harmony Search and Genetic Algorithm (CHSGA). Cooperative coevolution has been proven in the past to effectively solve the high-dimensional optimization complexity problem. The concept is to simplify high-dimensional and complex problems into multiple low-dimensional complex sub-problems, and improve the solution diversity of each sub-problem. Although in the past research has combined the cooperative coevolution with the harmony search algorithm. In general, the harmony search algorithm has poor local search ability. Therefore, this study further integrates a genetic algorithm with a better local search ability. Finally, the production environments with different job batch sizes, process stages, and reentrant times, CHSGA can effectively plan production schedules to reduce production cycles than previous algorithms, and effectively allocate empty vehicles handing WIP at the right time.

並列關鍵字

reentrant process ； production scheduling ； stocker ； cooperative coevolution ； harmony search algorithm

參考文獻

Agrawal, G. K., & Heragu, S. S. (2006). A survey of automated material handling systems in 300-mm SemiconductorFabs. IEEE Transactions on Semiconductor Manufacturing, 19(1), 112-120.

Chen, J. S., Pan, J. C. H., & Lin, C. M. (2008). A hybrid genetic algorithm for the re-entrant flow-shop scheduling problem. Expert systems with applications, 34(1), 570-577.

Cho, H. M., Bae, S. J., Kim, J., & Jeong, I. J. (2011). Bi-objective scheduling for reentrant hybrid flow shop using Pareto genetic algorithm. Computers & Industrial Engineering, 61(3), 529-541.

Chamnanlor, C., Sethanan, K., Chien, C. F., & Gen, M. (2014). Re-entrant flow shop scheduling problem with time windows using hybrid genetic algorithm based on auto-tuning strategy. International Journal of Production Research, 52(9), 2612-2629.

Chamnanlor, C., Sethanan, K., Gen, M., & Chien, C. F. (2017). Embedding ant system in genetic algorithm for re-entrant hybrid flow shop scheduling problems with time window constraints. Journal of Intelligent Manufacturing, 28(8), 1915-1931.