臺灣博碩士論文加值系統

快速的排程是工廠急欲解決的問題，遺傳演算法是目前常用解決NP-hard 排程問題的方法。在傳統上，使用遺傳演算法是需要長時間的演進，而時間正是排程問題的最大敵人。
本研究的目的在於如何利用遺傳演算法的良好特性：跳脫區域最佳解，並排除需要長時間演進的問題，使得可在短時間內獲得好的答案。
研究的結果中發現，在特定的交配法及突變率下，確實可讓問題快速的收斂，且也達到不錯的答案。

In factory, it is an important problem for scheduling rapidly, and genetic algorithm is a popular method to solve the NP-hard scheduling problem. In tradition, using genetic algorithm to solve the problem needs a long time, but ''time'' is the most important problem in scheduling.
This research intends to how to use the character of genetic algorithm to escape the trap in local solution, and exclude the long time of evolution from the genetic algorithm, then get the better solution in short time.
In this research, we develop a combination of using crossover, and mutation rate, to derive the solution fast and better.

目錄
目錄………………………………………………………………… Ⅰ
表目錄……………………………………………………………… Ⅱ
圖目錄……………………………………………………………… Ⅲ
一、 緒論………………………………………………………………… 01
1.1 研究動機與背景…………………………………………………… 01
1.2 研究目的…………………………………………………………… 02
1.3 研究流程…………………………………………………………… 02
二、 文獻探討…………………………………………………………… 04
2.1 零工式工廠之概況………………………………………………… 04
2.2 零工式工廠常用模式之探討……………………………………… 04
2.3 遺傳演算法之應用與法則………………………………………… 12
三、 遺傳演算法在JSP上之發展……………………………………… 19
3.1 在排序問題上的交配法…………………………………………… 19
3.2 在排序問題上的突變法…………………………………………… 21
3.3 在排序問題上的編碼方式………………………………………… 23
四、 實驗數據分析……………………………………………………… 26
4.1 實驗目的與設計…………………………………………………… 26
4.2 數據分析…………………………………………………………… 34
4.3 實驗結果…………………………………………………………… 61
五、 結論與未來研究方向……………………………………………… 63
5.1 結論………………………………………………………………… 63
5.2 未來研究方向……………………………………………………… 64
參考文獻……………………………………………………………………… 65
附錄一………………………………………………………………………… 67
附錄二………………………………………………………………………… 69

【1】 Autin, S. "An introduction to genetic algorithms," AI Expert , pp.49-53.1990.
【2】 Ballakur, A., and H. J.Steudel, "Integration of Job Shop Control System : a State-of-the-Art Review," Journal of Manufacturing Systems, Vol. 3,No.1,pp.71-79. 1984.
【3】 Chao-Hsien Yeh, "A Literature Review on the Componnts Improvement of Gentic Algorithms, " Journal of Taiwan Water Conserbancy, Vol. 44, No. 1, March 1996.
【4】 Croce, F.D., Tadei, R. and Volta, G. "A genetic algorithm for the job shop problem," Computer Operation Research 22(1),pp.15-24.1995
【5】 Davis, L, 1985, "Job Shop Scheduling with genetic algorithm",in:Proc. Of 1st Int.Conf. on Genetic Algorithm and Their applictation,pp.136-140.
【6】 Dorndorf, U. and Pesch, E., "Evolution based learning in a job shop scheduling enviroment," Computer Operation Research 22(1), pp.25-40.1995.
【7】 Falkenaurer, E. and Bouffouix, S., "A Genetic Algorithm for Job Shop Scheduling," Proceedings of the 1991 IEEE International Conference on Robitcs and Automation Sacramento, April, pp824-829.1991.
【8】 Gen, Mitsuo, Yasuhiro Tsujimura and Erika Kubota, "Solving Job Shop Scheduling Problem Using Genetic Algorithm ,"Proc. of 16th Int. Con. on Computers&Ind. Eng., Mar.7-9,pp.576-579.1994.
【9】 Gerard Fleury and Michel Gourgand, "Genetic Algorithm Applied to Wordshop Problems，"INT. J. Computer Integrated Manufacturing, Vol. 2, pp. 183-192, 1998
【10】 Jone E. Bisgel and James J. Davern, "Genetic Algorithms and Job Shop Scheduling, " Computer Ind. Engng. Vol. 19, Nos 1-4, pp. 81-91, 1990
【11】 K. C. Chan and H. Tansri, "A Study of Genetic Crossover Operation on the Facilities Layout Problem," Computers Ind Engng. Vol. 3, pp. 537-550, 1994
【12】 Nakano, R, and Yamada, T., "Conventional Genetic Algorithm for job shop problem," in:Proc 4th Int. Conf. On Genetic Algorithm and Their Application..1991.
【13】 P. W. Poon and J. N. Garter, "Genetic Algorithm Crossover Operators for Ordering Application, "Computers Ops. Res, Vol.22, No. 1, pp. 135-147, 1995
【14】 方曉嵐，「排程方法研究」， 技術與訓練 21 卷 1 期，1996年二月， 149-155 頁。
【15】 王培珍，「應用遺傳演算法在動態排程問題之探討」，中原大學工業工程研究所，碩士論文，1995。
【16】 張俊仁，「結合多目屬標與遺傳基因演算法於彈性製造系統排程之應用」，大葉工學院工業工程研究所碩士論文，1997。
【17】 陳宜欣，「遺傳演算法在Job Shop排程問題上的研究」，中央大學資訊管理研究所，碩士論文，1995。
【18】 楊宗銘，「遺傳演算法在多途程排程問題之探討」，中原大學工業工程研究所，碩士論文，1994。
【19】 "Evolutionary Algorithms：Principles, Methods and Algorithms" http://www.systemtechnik.tu-ilmenar.de/~pohlheim/GA_Toolbox/algintro.html
【20】 "Genetic Algorithm" http://www.dai.ed.ac.uk/groups/ev…994_95/andrewt/outline/
【21】 "Genetic Algorithms" http://http1.brunel.ac.uk/depts/AI/alife/ga.htm
【22】 "Intro To Genetic Algorithms "http://lancet.mit.edu/~mbwall/presentation/IntroToGAs/