模擬最佳化應用於半導體後段封裝廠混合流線型排程問題之研究

Simulation Optimization for Hybrid Flow Shop Scheduling Problem in Semiconductor Back-end Assembly

陳建銘(Chen, Chien Ming)

指導教授 ： 林則孟

國立清華大學/工學院/工業工程與工程管理學系/博士(2015年)

摘要

本研究為半導體後段封裝廠的混合流線型排程問題，其複雜度源自於需求的訂單特性與供給的生產環境特性。每一張訂單有其各自特定的產品型號、需求數量及來到時間；而在生產環境特性上，其為多產線、多工作站、多個等效與非等效平行機群的有限產能環境，其中黏晶、銲線與模壓為其考慮的關鍵加工站別。此三站的加工特性各有不同，因此衍生出訂單拆批與集批的生產特性，其中黏晶為整批進站生產，依拆批規則，達一定數量後，即拆批到銲線機台進行平行生產，以加快訂單生產，後再依併批規則，於模壓站進行加工，直到該訂單對應的所有子批完工，該訂單才能判定完工。生產過程必須吻合相關的加工限制，包括僅能在合格產線與機型加工、相同訂單下的子批僅限在相同產線與機型加工等特性，而各產品在不同機型上的加工時間不同，且具有隨機性，當機台上的加工產品型號改變時，則必須進行機台整備，其整備時間則依發生的站別而有所不同。
基於問題的複雜度，本研究應用模擬最佳化方法，透過較佳的產線、機型指派決策，目標為最小化的訂單加工時間。此方法整合系統模擬模式、啟發式演算法與最佳模擬資源配置技術，建構出模擬最佳化的應用架構與步驟。其中透過系統模擬，用以評估不同可行方案的績效，透過模擬資源最佳化配置技術，使其有限的模擬資源能有效分配於需要模擬的方案，減少隨機環境下的模擬次數，仍能辨別方案優劣，以便結合啟發式演算法如基因演算法或粒子演算法，使其在模擬最佳化的迭代搜尋運作中，能夠更快速地獲致較佳的方案，並透過情境分析探討不同需求水準、產品組合、或批量大小與加工時間的關係，顯現此模擬最佳化方法的可行性。根據前述的情境與應用，進一步的將批量大小設為決策變數，並比較不同啟發式演算法的績效、迭代收斂行為，結果顯示訂單加工時間持續改善且優於現行的實務法則，其驗證結果可供未來研究方向或實務應用之架構参考。

關鍵字

半導體後段封裝 ； 混合流線型排程問題 ； 拆批與集批 ； 模擬資源最佳化配置 ； 模擬最佳化

並列摘要

This study presents a simulation optimization approach for a hybrid flow shop scheduling problem in an actual semiconductor back-end assembly facility. The complexity of the problem is determined on the basis of demand and supply. Demand varies with orders, which are in turn characterized by different quantities, product types, and release times. Supply varies with the number of flexible manufacturing routes; however, this factor is constrained in a multi-line, multi-stage production system that utilizes specific types and numbers of both identical and unrelated parallel machines. This study addresses a non-deterministic polynomial-time-hard and stochastic discrete optimization problem that is subject to numerous constraints, such as product—machine dedication and lot split and merge due to charateristics of production process. Die bond, wire bond and mold were considered as bottlenecks. Due to unbalance throughput during these three stage, there is a split behavior at die bond stage, then to wire bond for reducing flow time by parallel processing; thre is a batch behavior before mold, then batch processing at mold stage due to economic scale. In the latter, jobs that belong to the same order must be processed by the same machine type at each stage under stochastic processing and sequence-dependent setup times. A simulation optimization approach is developed in view of the complex and stochastic nature of the problem. The approach includes a simulation model for performance evaluation, an optimization strategy that applies either a genetic algorithm or particle swarm optimization, and a technique for acceleration via optimal computing budget allocation. Flow time is improved because of optimal assignment in terms of production line and machine type. Scenarios depicting the different levels of demand, product mix, and lot-split size are analyzed to reveal the advantages of the proposed simulation approach. Furthermore, lot split-size (limited 2 options) is included as a decision variable and is coupled with different meta-heuristics to enhance solution quality and practical heuristics. Future research directions are then recommended on the basis of the computational results.

並列關鍵字

semiconductor back-end assembly ； hybrid flow shop scheduling ； lot split and merge ； optimal computing budget allocation ； simulation optimization

參考文獻

Allaoui, H., Artiba, A. (2004) Integrating simulation and optimization to schedule a hybrid flow shop with maintenance constraints, Computers & Industrial Engineering, 47, 431-450.

Almeder, C., Hartl, R. F. (2013) A metaheuristic optimization approach for a real-world stochastic flexible flow shop problem with limited buffer, International Journal of Production Economics,145(1), 88-95.

Ambühl, C., Mastrolilli, M. (2005) On-line scheduling to minimize max flow time: an optimal preemptive algorithm, Operations Research Letters, 33(6), 597-602.

Balin, S. (2011) Parallel machine scheduling with fuzzy processing times using a robust genetic algorithm and simulation, Information Sciences, 181, 3551-3569.

Behera, D. K. (2012) Complexity on parallel machine scheduling: A review, In Emerging Trends in Science, Engineering and Technology, 373-381, Springer India.