臺灣博碩士論文加值系統

摘要
零工式生產排程系統問題在生產管理是個相當重要的問題。這個問題的求解都沒能找到最佳解的多項式時間算法，係為一種非多項式問題，亦稱為NP難問題，在過去數十年間，已經有了許多不同方法的研究，本文主要是針對遺傳演算法，探討其於零工式生產排程系統的應用。
首先，針對零工式生產排程系統的作業程序及限制、績效衡量標準和派工法則做一敘述；其次，介紹遺傳演算法的基本架構和重要因子，並整理出遺傳演算法的各種編碼方式和交配方式；再者，說明本研究之系統模型架構；最後，對測試問題做一系列的測試，探討遺傳演算法的各個控制參數，如交配率、突變率和族群數的變化對於本研究之三種遺傳演算法GAⅠ(部分配對交配與位置互換突變)、GAⅡ(單點交配與位置互換突變)、GAⅢ(以工作為基礎的交配與位置互換突變)之影響。
本研究以Fortran語言撰寫程式，測試問題從D. C. Mattfeld與R. J. M. Vaessens整理文獻裡的選用四個標準檢查程序(Bench-mark)例子。測試結果發現本文三種遺傳演算法對於零工式生產排程問題之完工時間，在特定的突變率與交配率之下可以獲得不錯的搜尋結果。

Abstract
The job-shop scheduling problem is an important problem in the operation production management. During the last few decades, an efficient algorithm hasn’t been found yet for optimizing it in polynomial time. Based on the genetic algorithms is used to solve job-shop scheduling problem in this thesis.
Firstly, to describe operation process, limits, performance, and the rule on dispatch in the job-shop scheduling problem. Secondly, to introduce the basic framework and important parameters such as crossover rate, mutation rate and population in genetic algorithms. According the genetic algorithm with three different crossover mechanisms such as partial-mapped crossover, one-point crossover, job-based order crossover, a program has been complemented in Fortran 90.The program is verified through four bench-mark instances of the job-shop scheduling problem having minizing makespan from paper by D. C. Mattfeld and R. J. M. Vaessens. Finally, the influence of the parameters in three genetic algorithms in this thesis on the makespan for the job-shop scheduling problems are studied and discussed.

目錄
中文摘要.....................................................Ⅰ
Abstract.....................................................Ⅱ
圖目錄.......................................................Ⅴ
表目錄.......................................................Ⅶ
第一章 緒論..................................................1
1.1研究動機與背景............................................1
1.2研究目的..................................................2
1.3研究流程..................................................2
1.4論文架構..................................................4
第二章 遺傳演算法與JSP問題描述...............................5
2.1 排程的定義與分類.........................................5
2.2 零工式生產排程系統.......................................7
2.3遺傳演算法................................................9
2.4 JSP問題上遺傳演算法的編碼方式...........................15
2.5 JSP問題上遺傳演算法的交配方式...........................22
第三章 系統模型與測試問題...................................26
3.1 系統模型................................................26
3.2 測試問題................................................31
第四章 問題分析.............................................35
4.1 6×6問題(ft06)...........................................35
4.2 10×10問題(ft10).........................................42
4.3 20×5問題(ft20)..........................................50
4.4 20×10問題(la26).........................................57
4.5 結果比較................................................65
第五章 結論與未來展望.......................................67
5.1 結論....................................................67
5.2 未來展望................................................67
參考文獻....................................................69

【1】E. K. Burke, A. J. Smith, ”Hybrid Evolutionary Techniques for the Maintenance Scheduling Problem”, IEEE Transactions on power systems, Vol. 15,NO. 1, pp. 122-128,2000.
【2】L. D. Chambers, ”Practical Handbook of Genetic Algorithms”, Boca Raton : CRC Press,1999.
【3】R. Cheng, M. Gen, Y. Tsujimura, ”A tutorial survey of job-shop scheduling problems using genetic algorithms-Ⅰ. Representation”, Computer Ind. Engeng, Vol. 30, No. 4 ,pp. 983-997,1996.
【4】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. 36, pp. 343-364,1999.
【5】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.
【6】E. Falkenauer, S. Bouffouix, ”A Genetic Algorithm for Job Shop”, Proceedings of the 1991 IEEE International Conference on Robotics and Automation , pp. 824-829,1991.
【7】M. Gen, R. Cheng, ”Genetic algorithms and engineering optimization”, New York: Wiley, 2000.
【8】M. Gen, Y. Tsujimura, E. Kubota, ”Solving Job-Shop Scheduling Problems by Genetic Algorithm ” , IEEE International Conference on, Vol. 2, pp. 1577-1582,1994.
【9】D. E. Goldberg, ”Genetic algorithms: in search, optimization and Machine learning”, Addision-Wesley Publishing Co.,1989.
【10】J. Holland, ”Adaptation in Natural and Artificial Systems”, University of Michigan Press, Ann Arbor, Michigan,1975.
【11】A.S. Jain, S. Meeran, ”Deterministic job-shop scheduling: Past, present and future”, European Journal of Research, Vol. 113, pp. 390-434,1999.
【12】D. C. Mattfeld, R. J. M. Vaessens, ”Job Shop Problem Test Instances Set”, <http://www.ms.ic.ac.uk/jeb/pub/jobshop1.txt >.
【13】S. G. Ponnambalam, N. Jawahar, B. S. Kumar, ”Estimation of Optimum Genetic Control Parameters for Job Shop Scheduling”, Int J Adv Manuf Technol, Vol. 19, pp. 224-234,2002.
【14】N. Sannomiya, H. Iima, K. Ashizawa, Y. Kobayashi, ”Application of Genetic Algorithm to a Large-Scale Scheduling Problem for a Metal Mold Assembly Process”, Proceeding of the 38th Conference on Design & Control, pp. 2288-2293,December 1999.
【15】Y. Tsujimura, Y. Mafune, 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.
【16】L. Wang, D. Zheng ,”An effective hybrid optimization strategy for job-shop scheduling problems”, Computers & Operations Research, Vol. 28, pp. 585-596,2001.
【17】王培珍，應用遺傳演算法與模擬在動態排程問題之探討，中原大學工業工程研究所，碩士論文，1996。
【18】林我聰，現場排程專家系統─應用個體導向技術建立之研究，財團法人資訊工業策進會─資訊與電腦出版社，1994。
【19】許丕敏，工單式生產系統排程績效之比較─最小化總延遲時間，成功大學工業管理研究所，1999。
【20】陳宜欣，遺傳演算法在Job Shop排程問題上的研究，中央大學資訊管理研究所，1997。
【21】賴士葆，生產作業管理─理論與實務，華泰書局，1995。
【22】羅友廷，模糊多目標混合式遺傳演算法在零工式排程系統之應用，東海大學工業工程研究所，1999。
【23】蕭義梅，遺傳演算法應用在零工式工廠生產排程之應用，元智大學工業工程研究所，1999。
【24】蘇木春、張孝德，機器學習：類神經網路、模糊系統以及遺傳演算法則，全華科技圖書股份有限公司，2000。