修正式NEH基因演算法(MNGA)之應用-以流程 型生產排程總完工時間極小化問題為例

The Application of Modify NEH Genetic Algorithm for Minimizing Makespan for the Flowshop Scheduling Problem

吳冠億(Kuan-I Wu)

指導教授 ： 胡伯潛

國立虎尾科技大學/管理學院/工業工程與管理研究所/碩士(2009年)

摘要

生產排程是製造業管理活動中重要的一部分，因此數十年來有許多的研究人員投入此領域的探討中。生產排程問題非常複雜，是屬於完全非多項式時間的問題(NP-complete)。由於即使針對小型的生產排程問題都必須花費大量時間才能求得真正的最佳解，因此，有關排程的研究都傾向於利用啟發式方法在短時間內求取最佳解或近似最佳解的解，以有效率的解決各式複雜之生產排程問題。
在本研究中，我們提出一種修正式NEH(Nawaz,Enscore and Ham)結合基因演算法(Modify NEH Genetic Algorithm, MNGA)，並以流程型生產排程總完工時間(makespan)極小化的問題為求解對象。為了證明此演算法的表現，本研究亦將基因演算法(Genetic Algorithms, GA)及NEH結合基因演算法(NEH Genetic Algorithms, NGA)應用於同樣的問題，並將三種演算法求解所得到的結果，做一分析以比較其優劣性。
經分析比較後，顯示本研究所提出之MNGA演算法在求解流程型生產排程總完工時間極小化問題時，能夠尋找到較好的最佳近似解，因此可證明本研究所提出的MNGA演算法具有良好之改善效能。

關鍵字

排程 ； 流程型生產排程 ； NEH ； 修正式NEH基因演算法(MNGA) ； 總完工時間

並列摘要

Scheduling is one of the vital manufacturing practices, thus numerous researchers has involved in this area for the past several decades. Scheduling problems are very complicated, and belong to NP-complete family. Since tremendous effort and time are needed to get the optimal solutions even for a small scale of the problem, studies in this area tends to apply heuristics to efficiently solve for the optimal or near optimal solutions of different kinds of complicated scheduling problems.
In this study, a modified NEH (Nawaz, Enscore, and Ham) genetic algorithm (MNGA) has been developed for minimizing the makespan for the flowshop scheduling problems. In order to display the performance of the MNGA, results obtained from the simple genetic algorithm and hybrid NEH genetic algorithm for the same sets of these flow shop scheduling problems are compared to the results solved by the MNGA.
Form the comparison, it is clear that the MNGA developed in this study can effectively and efficiently solve for the optimal or near optimal solutions for minimizing the makespan for the flowshop scheduling problems and it is also superior than the simple genetic algorithm and hybrid NEH genetic algorithm.

並列關鍵字

Scheduling ； FlowShop ； NEH ； MNGA ； Makespan

參考文獻

1. 王立志(1994)，現場排程簡介，東海大學工業工程系。

2. 王培珍(1996)，應用遺傳演算法與模擬在動態排程問題之探討，中原大學工業工程研究所，碩士論文。

3. 吳承宗(2002)，應用模擬方法於印刷電路板生產排程影響因素之研究，元智大學工業工程與管理研究所，碩士論文。

4. 李正羿(2007)，於流程式生產排程以基因演算法將總完工時間最小化之研究，虎尾科技大學工業工程與管理研究所，碩士論文。

5. 李佳瑜(2008)，流程式生產系統下混線生產重排程，屏東科技大學，工業工程與管理研究所，碩士論文。