The Study on the Production Scheduling Problems for Liquid Crystal Display Module Assembly factories
|關鍵字:||平行機台排程;批次;加權產出;順序相依設置時間;模組裝配;parallel machines scheduling;batch;weighted throughput;sequence dependent setup time;module assembly|
本論文首先解決印刷電路板焊接排程問題 (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.
|Appears in Collections:||Thesis|
Files in This Item: