搜尋法應用於彩色濾光片之生產排程

Application of Search Algorithms in Color Filter Production Scheduling

詹宗憲(Tsung-Hsien Chan)

指導教授 ： 洪一峯

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

摘要

彩色濾光片的三原色(RGB)製程中，利用相同的平行機台經過裝設後可以生產多種不同規格的產品，而每種產品皆須在平行機台上回流三次以上才能完成此製程。本論文針對三原色製程的生產排程問題作研究，因為排程的目的為及時滿足後端製程的需求，所以將目標函數定為使所有批次產品的總延遲時間(total tardiness)最小。在求解問題時考慮了產品需求率隨著時間而變動、不同的作業間具有順序相關的裝設時間、產品以批量方式進行製造等生產特性。
求解這個生產排程問題時，本論文使用賴【2005】提出的二階段式解法，並對其解法做了部分修正，以考量隨著時期而變動的產品需求率。第一個階段，利用經濟訂購批量模型(EOQ Model)求出合適的批量大小，決定在規劃時間內所有待加工的批量，一個批量即為平行機台排程問題的一個工件。第二個階段，先利用ATCS(Apparent Tardiness Cost with Setups)派工法則排出工件在平行機台上的加工順序，再以此作為起始解，用搜尋演算法尋找較佳解。本論文對三種搜尋演算法進行比較，分別是模擬退火法(Simulated Annealing)、塔布搜尋法(Tabu Search)及模因演算法(Memetic Algorithm)。模擬退火法的鄰近解採取隨機方式產生，塔布搜尋法的鄰近解則設計了一個半隨機的方式產生，模因演算法的鄰近解依照基因演算法，採取交配(crossover)和突變(mutation)的方式產生。
最後，本論文的計算實驗中列出了數個因子，討論其對總延遲時間的影響。發現規劃時間、搜尋法、機台數目、產品種數這四個因子皆對最終的總延遲時間有顯著的影響。在排程環境的設定方面，較短的規劃時間、較多的機台數、較少的產品種數皆有助於降低總延遲時間。至於所使用的搜尋法，本實驗顯示半隨機式鄰近解的塔布搜尋法明顯優於其他兩種搜尋法。

關鍵詞：三原色製程、生產排程、再回流、經濟批量、搜尋演算法。

關鍵字

三原色製程 ； 生產排程 ； 再回流 ； 經濟批量 ； 搜尋演算法

並列摘要

In the RGB process of color filter production, different products can be
processed on the same parallel machines, and each product has at least three visits to the parallel machines. This thesis focuses on the production scheduling of the RGB process, and the objective is to fulfill the demand of later production stage in time. After observing the RGB process, this study considers the following three factors:
(1) the demand rates of products are time-varying; (2) different operations have sequence dependent setup time; (3) products are manufactured by lots.
This thesis uses a two-stage approach to solve the production scheduling problem. In the first stage, the EOQ model is used to determine the proper lot size. A production lot can be treated as a job in the parallel machines scheduling problem. In the second stage, the apparent tardiness cost with setups (ATCS) dispatching rule is applied to obtain the initial schedule, and then a search algorithm is used to improve the initial schedule calculated by ATCS dispatching rule. We compare three search algorithms in this thesis. They are Simulated Annealing, Tabu Search and Memetic Algorithm.
In the computation experiment, several factors are used to investigate
their influences on the total tardiness. Four factors affect the result significantly. In the scheduling environment, shorter planning horizon, more parallel machines and less product types can reduce the total tardiness. In the search algorithms, the Tabu Search outperforms the others.

Keywords: RGB process, production scheduling, reentry, economic lot size, search algorithms.

並列關鍵字

RGB process ； production scheduling ； reentry ； economic lot size ； search algorithms

參考文獻

Bilge, U., Kirac, F., Kurtulan, M., Pekgun, P. (2004), “A tabu search algorithm for parallel machine total tardiness problem”, Computers & Operations Research, 31, 397-414.

Cheng, R., Gen, M. and Tsujimura, Y. (1996), “A tutorial survey of job-shop scheduling problems using genetic algorithms, part I: Representation”, Computers & Industrial Engineering, Vol 30, No. 4, 983-997.

Cheng, R., Gen, M. and Tsujimura Y. (1999), “A tutorial survey of job-shop scheduling problems using genetic algorithms, part II: hybrid genetic search strategies”, Computers & Industrial Engineering, 36,343-364.

Drexl, A.. and Kimms, A. (1997), “Lot sizing and scheduling-Survey and extensions”, European Journal of Operational Research, No. 99, pp. 221-235.

Franca, P. M.., Gupta, J. N. D., Mendes, A. S., Moscato, P., Veltink, K.J. (2005), “Evolutionary algorithms for scheduling a flowshop manufacturing cell with sequence dependent family setups”, Computer & Industrial Engineering, 48, 491-506.