液晶顯示模組裝配廠生產排程問題之研究

Abstract

在液晶面板廠中，如何充分利用產能及滿足顧客交期來增加競爭力及獲利，為一重要之研究課題；在液晶面板製造的最終模組裝配製造階段中，印刷電路板焊接作業為生產過程中的瓶頸，其排程結果將影響整個模組裝配廠的生產績效，因此，本論文先針對此瓶頸作業所衍生的平行機台排程問題進行探討。而在經過印刷電路板焊接作業後，工件在出貨前還須經過老化測試作業，這是模組裝配廠中的批次機台，老化測試的排程問題是一個多維度的排程問題，其考量了不同的到臨時間、不同的工件大小、有限的機台產能以及批次相依的加工時間，不當的老化測試排程將影響出貨時程，因此，發展老化測試排程的求解程序在模組裝配廠也是一重要的課題。 本論文首先解決印刷電路板焊接排程問題 (printed circuit board bonding scheduling problem；PCBSP)，其為順序相依設置時間的平行機台排程問題，工件在此問題中分屬不同的產品族，由於模組裝配廠所製造的產品面臨契約與現貨並存的混合市場，因此，工件在PCBSP中依據利潤及客戶重要性等因素被賦予不同的權重，在此問題中，本文於滿足契約數量及不違反交期及機器產能的限制下，以求得最大化總加權產出作為PCBSP的求解目標，這些工件一旦於瓶頸資源上完工，則需要加速出貨，因此，在老化測試排程問題 (aging test scheduling problem；ATSP) 中則以最小化完工時間為目標。 在本論文中，我們針對PCBSP與ATSP兩個排程問題分別建立其混合整數規劃模式，亦將PCBSP的子問題轉換為考量時間窗限制下之車輛路線問題(vehicle routing problem with time window；VRPTW)，並修改既有的網路演算法來發展新的啟發式解法，同時也應用貪婪法則來解決其他的子問題；此外，針對ATSP，我們也設計一個複合啟發式法則來決定批次個數，並將此個數視為一已知的參數帶入混合整數規劃模式中，以降低原先模式求解的複雜度，而針對大型的ATSP，本文也提出三個啟發式解法來求解；經由運算結果及績效比較中得知，本論文針對PCBSP及ATSP所提出的啟發式法則有很好的求解效果。

To be competitive, the thin film transistor liquid crystal display (TFT-LCD) companies need to utilize their capacity and to satisfy customers’ due dates in order to increase their profitability. In the final stage of TFT-LCD, module assembly manufacturing process, the printed circuit board (PCB) bonding usually causes bottleneck in production; its schedule mainly affect the system performance of module assembly factories. Therefore, an essential scheduling problem is tackled for the bottleneck operation first; it is referred to as the printed circuit board bonding scheduling problem (PCBSP). Furthermore, following the PCB bonding operation, there exists an aging test operation, which is the only batch server in the whole process. The aging test scheduling problem (ATSP) is complicated because it is a multi-dimensional problem, which involves the constraints of unequal ready times, non-identical job sizes, limited machine capacity, and batch dependent processing times. Therefore, the development of efficient algorithms is also critical to form appropriate batches and to arrange a suitable schedule for those jobs which have been processed by the PCB bonding operation. For the PCBSP, the jobs are clustered by their product types, which must be processed on identical parallel machines. They are also given various weights based on their profits and customer importance due to hybrid contracted and spot markets being in the module assembly industry. Furthermore, setup times for two consecutive jobs between different product types on the same machines are sequence-dependent. Thus, the objective for the PCBSP is to maximize the total weighted throughput subject to fulfilling contracted quantities without violating the due dates and machine capacity restrictions. Once those jobs are planned and processed in the bottleneck operation, they should be accelerated their speed to complete and delivery. Consequently, the ATSP with a minimal makespan criterion is also considered. In this dissertation, the PCBSP and ATSP are formulated as two mixed integer linear programming models. For the PCBSP, it can be viewed as a multi-level optimization problem, the sub-problem of PCBSP can be transformed into the vehicle routing problem with time window (VRPTW), a well-known network routing problem which has been investigated extensively. We present two new algorithms based on the network algorithms with some modifications to accommodate the PCBSP. Furthermore, the greedy concept is also applied to the other sub-problem of PCBSP. For the ATSP, an effective compound algorithm is proposed to determine the number of batches and to apply this number as one parameter in the MILP model in order to reduce the complexity of the problem. Three efficient heuristic algorithms are also provided for the large-scaled ATSP. Computational results and performance comparisons show that the proposed algorithms, which are used to solve the PCBSP and ATSP, are efficient and near-optimal.