臺灣博碩士論文加值系統

摘 要

近年來，啟發式演算法已逐漸成為解決組合最佳化中非多項式時間可解問題(NP-hard)的主流。而在這些組合最佳化問題中，零工式生產排程系統問題在生產管理方面是個相當重視的問題。本文主要針對遺傳演算法探討其於零工式生產排程系統問題的應用，提出改良式遺傳演算法以改善零工式生產排程系統問題的求解效能及效率。首先，針對零工式生產排程系統的作業程序與限制、績效衡量標準和派工法則做一探討。其次，介紹遺傳演算法的基本架構和重要因子，並整理出遺傳演算法的各種編碼方式和交配方式；然後介紹改良式遺傳演算法與傳統遺傳演算法的不同，說明改良式遺傳演算法的理論概念，藉由多個改善策略，來改善傳統遺傳演算法的搜索效率。此外，針對本研究之系統模型架構，對測試問題做一系列的測試，共分兩部分。第一部分探討傳統遺傳演算法的各個控制參數，如交配率、突變率和族群數的變化對於三種不同交配方式的傳統遺傳演算法之影響；第二部分則探討改良式遺傳演算法對於零工式生產排程系統的改善狀況，並與傳統遺傳演算法做比較。
關鍵字：零工式生產排程系統、遺傳演算法、改良式遺傳演算法、交配率、突變率、族群數。

ABSTRACT

In recent years, the heuristic algorithm has gradually been adopted to deal with NP-hard problems in the combinatorial optimization. Among these combinatorial optimal problems, the job-shop scheduling problems are usually encountered in the production managements. In this thesis, the modified genetic algorithms (MGA) are proposed to analyze and further apply to the job-shop scheduling problems for improving the calculation effectiveness and efficiency. First of all, discussions on the operation procedures, restrictions, dispatching and effectiveness evaluating criteria of the job scheduling problems are made. Then, the fundamental framework and some important factors are introduced, and the coding and the cross-over formats of the GA are identified. After introducing several improvement strategies into the searching solvers, an MGA is formulated and used to compare the searching efficiency with the conventional GA. A series of testing examples on the controlling factors, such as cross-over rate, mutation rate and population size, are also conducted to analyze the influences of three different crossover formats on the conventional GA. Moreover, the solving and searching efficiencies of the MGA applied to the job-shop scheduling system are also discussed and compared with the traditional GA.

Keywords: Job-shop scheduling problems, genetic algorithm, modified genetic algorithm, crossover rate, mutation rate, population size.

目錄
中文摘要 Ⅰ
Abstract Ⅱ
圖目錄 Ⅴ
表目錄 Ⅹ

第一章 緒論 1
1.1研究動機 1
1.2研究目的 1
1.3研究方法 2
1.4文獻回顧 3
1.5研究目標 5
1.6論文大綱 5
第二章 零工式生產排程系統問題描述與改良式遺傳演算法 7
2.1排程的定義與分類 7
2.2零工式生產排程系統 9
2.3遺傳演算法 12
2.4遺傳演算法應用於JSP問題上的編碼方式 20
2.5遺傳演算法應用於JSP問題上之交配方式 27
2.6 改良式遺傳演算法 30
第三章 系統模型與測試問題 36
3.1系統模型 36
3.2測試問題 42
第四章 問題分析 .46
4.1以TGA測試問題 47
4.2以NGA測試問題 63
4.3以LGA測試問題 71
4.4結果比較 78
第五章 結論與未來展望 99
5.1結論 99
5.2未來展望 102
參考文獻 104

參 考 文 獻

1. D. C. Mattfeld and R. J. M. Vaessens, “Job Shop Problem Test Instances Set”, <http://www.ms.ic.ac.uk/jeb/pub/jobshop1.txt >, 2003.
2. M. R.Garey, D. S.Johnson and R. Sethi, “The complexity of flowshop and jobshop scheduling” , Mathematics of Operations Research, Vol. 1, No. 2, 1976.
3. J. Holland, “Adaptation in Natural and Artificial Systems” , University of Michigan Press, Michigan, 1975.
4. D. E. Goldberg, “Genetic algorithms: in search, optimization and Machine learning” , Addision-Wesley Publishing Co., 1989.
5. K. F. Man, K. S. Tang and S. Kwong, “Genetic algorithms: concepts and applications” , IEEE Trans. Industrial Electronics, Vol. 43, No. 5, pp. 519-534, 1996.
6. 蘇木春、張孝德，機械學習：類神經網路、模糊系統以及基因演算法則，全華科技圖書股份有限公司，1997。
7. 周鵬程，遺傳演算法原理與應用，全華科技圖書股份有限公司，2001。
8. E. Poirier, M. Ghribi and A. Kaddouri, “Loss minimization control of induction motor drives based on genetic algorithms” , Proceedings of IEEE Conference on Electric Machine and Drives, pp. 475-478, 2001.
9. M. Gen, Y. Tsujimura and E. Kubota, “Solving Job-Shop Scheduling Problems by Genetic Algorithm” , IEEE International Conference on, Vol. 2, pp. 1577-1582, 1994.
10. F. D. Croce, R. Tadei and G. Volta, “A Genetic Algorithm for the Job Shop Problem”, Computer Operations Research, Vol. 22, No. 1, pp. 15-24, 1995.
11. 陳宜欣，“遺傳演算法在 Job Shop 排程問題上的研究”，中央大學資訊管理研究所，碩士論文，1997。
12. 蕭義梅，“遺傳演算法應用在零工式工廠生產排程之應用”，元智大學工業工程研究所，碩士論文，1999。
13. 蘇恆磊，“遺傳演算法於零工式生產排程系統問題之應用”，海洋大學系統工程暨造船學系研究所，碩士論文，2002。
14. T. Yamada and R. Nakano, “A Fusion of Crossover and Local Search”, Proceedings of the IEEE international Conference on Industrial Technology, pp. 426-430, 1996.
15. M. Kirley, “A Coevolutionary Genetic Algorithm for Job Shop Scheduling Problems”, IEEE 1999 Third International Conference on Knowledge-Based Intelligent Information Engineering Systems, pp. 84-87, 1999.
16. L. Yutian, “GA/SA/TS Hybrid Algorithms for Reactive Power Optimization”, IEEE power energy engineering society summer meeting, pp. 245-279, 2000.
17. Y. Tsujimura, Y. Mafune and M. Gen, ”Effect of Symbiotic Evolution in Genetic Algorithms for Job-Shop Scheduling” , Proceedings of the 34th Hawaii International Conference on System Sciences, pp. 1-7, 2001.
18. 蔡崇煒，“多重搜尋基因演算法：一個新的有效解決通訊網路及資料庫中複雜問題之方法”，屏東科技大學資訊管理研究所，碩士論文，2002。
19. 羅友廷，“模糊多目標混合式遺傳演算法在零工式排程系統之應用”，東海大學工業工程研究所，1998。
20. 吳宗益，“應用基因演算法及田口實驗法於模具生產排程系統之研究”，高雄第一科技大學機械與自動化工程所，碩士論文，2002。
21. 鄭价廷，“應用基因遺傳演算法於零工式工場生產排程”，國立高雄第一科技大學機械與自動化工程研究所，碩士論文，2002。
22. 柯惠雯，“結合模擬退火法與禁忌搜尋法在流程式生產排程之應用”， 大葉大學工業工程研究所，碩士論文，2001。
23. 葉靜怡，“以塔布搜尋法求解流程式工廠排程問題”，清華大學工業工程研究所，碩士論文，1994。
24. R. Cheng, M. Gen, Y. Tsujimura, “A tutorial survey of job-shop scheduling problems using genetic algorithms, part Ⅱ: hybrid genetic search strategies”, Computer & Industrial Engineering, Vol. 37, pp. 51-55, 1999.
25. 王培珍，“應用遺傳演算法與模擬在動態排程問題之探討”，中原大學工業工程研究所，碩士論文，1996。
26. R. Cheng, M. Gen and Y. Tsujimura, “A tutorial survey of job-shop scheduling problems using genetic algorithms, part Ⅱ: hybrid genetic search strategies” , Computer & Industrial Engineering, Vol. 36, pp. 343-364, 1999.
27. R. Cheng, M. Gen, Y. Tsujimura, “A tutorial survey of job-shop scheduling problems using genetic algorithms-Ⅰ.Representation”, Computer & Engeng, Vol. 30, No. 4,pp. 983-997, 1996.
28. L. Wang, D. Zheng ,“An effective hybrid optimization strategy for job-shop scheduling problems”, Computers & Operations Research, Vol. 28, pp. 585-596, 2001.