液晶顯示器陣列製程之彈性零工式生產排程

Flexible Job Shop Scheduling for the Array Process of LCD Manufacturing

張皇文(Chang Huang-Wen)

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

摘要

陣列製程為液晶顯示器製程的一部份，每一個產品有各自的加工途程，排程安排上如同零工式生產。此外，陣列製程的工作站都包含了多部機台，而每一部機台的效能不盡相同，因此產品進入每一個工作站的機台皆必須挑選合適的加工機台。加上在陣列製程中黃光製版需要五到七道的光罩再回流生產，更增加了排程上的困難度。因此陣列製程可被視為彈性零工式生產(flexible job shop)，有再回流現象的排程問題。為解決此複雜的排程問題，本論文運用Brandimarte【1993】所提出的「傳統式雙向搜尋法」以及本論文提出「改進式雙向搜尋法」兩種搜尋法求解並比較其求解效果優劣。
雙向的涵義在於將彈性零工式生產問題分為機台選派與零工式生產兩個面向，求解過程中當其中一個面向求出目前最合適解時，就進入另一個面向作求解，兩個面向不斷循環求解，直到達停止條件。Brandimarte【1993】所提出的傳統式雙向搜尋法，零工式生產求解利用隨機塔布搜尋法，而機台選派則以選取最佳要徑的方式求解。本論文的改進式雙向搜尋法在零工式生產求解利用Nowicki and Smutnicki【1996】所提出的快速塔布搜尋法，而機台選派則利用模擬退火法。
實驗結果顯示，兩演算法在求解小型問題時並無顯著差異，在處理中型以及大型問題時改進式雙向搜尋法的求解效率較高，也能持續針對問題作改善，最後所獲得的結果也較傳統式雙向搜尋法佳。

關鍵字

薄膜電晶體陣列製程 ； 彈性零工式生產 ； 再回流 ； 快速塔布搜尋法 ； 模擬退火法

並列摘要

The TFT-array process is a portion of the TFT-LCD manufacturing. The scheduling problem of the TFT-array process can be treated as flexible job shop with recirculation. A flexible job shop is a generalization of the job shop. Each workstation consists of multiple parallel machines and the machines have similar functions. The machines in a workstation may have different efficiency. A job has to choose a qualified machine when entering a workstation. In addition, a job may visit some workstations more than once. To solve this difficult problem, this thesis uses two methods. One is called “traditional two-way heuristic”, which is proposed by Brandimarte【1993】. The other one is called “modified two-way heuristic”, which is proposed by this study.
The meaning of “two-way” is that we separate the problem into two dimensions. One is machine allocation and the other one is job shop scheduling. During the solution process, the solution of the procedure of one dimension problem will become the initial solution of the other one. The procedures for these two dimension problems keep alternative in loops until satisfying the over all stopping criteria. We refer the method which is proposed by Brandimarte【1993】 as the traditional two-way heuristic. It uses the stochastic tabu search to solve the job shop dimension. In the machine allocation dimension, it chooses one operation on the critical path and this operation is assigned to one of the alternative machines. It chooses one operation at one time and records the new solution. When all operations on the critical path are assigned, the best insertion solution is chose. In modified two-way heuristic, we use the fast tabu search proposed by Nowicki and Smutnicki【1996】 to solve the job shop dimension and use the simulated annealing to solve the machine allocation dimension.
The experiment results show that modified two-way heuristic outperforms traditional two-way heuristic when solving medium and big problem.

並列關鍵字

TFT-array process ； flexible job shop ； recirculation ； fast tabu ； simulated annealing

參考文獻

Adams, J., Balas, E. and Zawack, D. (1988), “The Shifting Bottleneck Procedure for Job Shop Problem”, Management Science, Vol. 34, pp. 391-401.

Baykasolu, A. (2002), “Linguistic based meta-heuristic optimization model for flexible job shop scheduling”, International Journal of Production Research, Vol. 40, pp. 4523–4543.

Brandimarte, P. (1993), “Routing and scheduling in a flexible job shop by tabu search”, Annals of Operations Research, Vol. 22, pp. 158-183.

Carlier, J. and Pinson, E. (1989), “An Algorithm for Solving the Job-Shop Problem.”, Management Science, Vol. 35, pp. 164-176

Chao, X. and Pinedo, M. (1999), Operation Scheduling with Applications in Manufacturing and services, Irwin, McGraw-Hill, U.S.A.