臺灣博碩士論文加值系統

生產排程為製造加工業中管理活動中重要的一環，但隨著排程問題的日益繁雜，想求取出真正最佳解之可行性也變得極低。而且，近年來排程研究已漸漸傾向於使用啟發式方法在短時間內求取近似最佳解，來有效率的解決各式複雜之排程問題。許多相關文獻中也早已證實基因演算法與其它啟發式方法在解決排程問題上有著不錯的結果。在本研究中以流程型工廠T公司為案例，搭配演算法來求解出符合具T公司生產目標最大完工時間最小化的生產排程。
針對T公司之生產目標，本研究採以基因演算法來求解，並分為二個部份來分別討論基因演算法中參數設定問題。經由抽取出的T公司訂單資料測試結果發現，本研究基因演算法中不同的交配率及突變率搭配設定，對於演算結果並無太大影響。但初始族群設定與演算世代的設定問題，卻會影響到最終Makespan值與工件排程結果。最後，本研究提出適合於T公司之基因演算法參數設定，及生產目標之生產排程。

In this research a genetic algorithm is presented to solve the T-Company production scheduling problem, subjecting to minimizing the Makespan. In order to obtain the optimal solution, the determination of the parameter sets of the genetic algorithm is discussed, and then the selected parameters are applied to .the T-Company scheduling problem. With the different mutation rate and crossover rate settings, the results show that the outcomes are not much improved. However, the initial setups and ethnic calculus generation of set-up problems affect the final Makespan values obviously and come out the better acceptable scheduling results.

摘要i
英文摘要ii
誌謝iii
表目錄v
圖目錄vi
第一章 緒論1
1.1 研究背景與動機1
1.2 研究目的與限制2
1.3 研究流程2
1.4 研究架構4
第二章 文獻探討5
2.1 排程簡介5
2.2 排程問題的解決方法7
2.3 基因演算法簡介 9
2.3.1 基因演算法的演變10
2.3.2 基因演算法的運算流程11
2.3.3 近年來基因演算法之相關文獻14
第三章 建構基因演算法17
3.1 問題描述17
3.2 建構基因演算法18
第四章 研究結果29
4.1 案例公司簡介29
4.2 基因演算法之各項參數設定33
4.2.1 族群及演算世代設定33
4.2.2 交配率及突變率之設定40
4.3 研究結果彙整47
第五章 結論與建議48
5.1 結論48
5.2 未來研究方向49
參考文獻50

1.王培珍，應用遺傳演算法與模擬在動態排程問題之探討，中原大學工業工程研究所，碩士論文，1996。
2.李宜達，動態模擬與繪圖:使用MATLAB/SIMULINK，全華科技，1998。
3.李顯宏，MATLAB 7.X程式設計與應用技巧，文魁資訊出版，2004。
4.何仁祥，以案例式推理為基礎的基因演算法解決生產排程問題，元智大學工業工程研究所，碩士論文，2003。
5.周鵬程，遺傳演算法原理與應用－活用Matlab（修訂版），全華科技圖書股份有限公司，2002。
6.柯惠雯，結合模擬退火法與禁忌搜尋法在流程式生產排程之應用，大葉大學工業工程研究所，碩士論文，2001。
7.陳志合，元件化現場排程系統之發展，東海大學工業工程研究所碩士論文，2000。
8.陳宜欣，遺傳演算法應用在Job Shop 排程問題上的研究，中央大學資訊管理研究所，碩士論文，1997。
9.陳青岑，一個新的智慧型演算法解決流程型工廠排程問題，屏東科技大學
資訊管理研究所，碩士論文，2003。
10.莊鎮嘉、鄭錦聰，MATLAB程式設計.進階篇，全華科技，2004。
11.張育仁、李慶恩、王立志，「自我調適的動態排程系統-限制排程、模糊理論和遺傳演算法的應用」，工業工程學刊，第15 卷，第六期，1998。
12.張智星，MATLAB程式設計與應用，清蔚科技股份有限公司出版事業部，2000。
13.葉倍宏，MATLAB 7程式設計，全華科技，2006。
14.鄭价廷，應用基因遺傳演算法於零工式工場生產排程，國立高雄第一科技大學機械與自動化工程所，碩士論文，2001。
15.韓駿逸，基因演算法解算交貨時區限制零工型排程問題之效果分析，元智大學工業工程研究所，碩士論文，2001。
16.賴郁玲，以基因演算法求解最少延遲工作數下總延遲時間最小化之單機排程 問題，南台科技大學工業管理研究所，碩士論文，2005。
17.蘇木春，機器學習:類神經網路、模糊系統以及基因演算法則，全華科技，1999。
18.Chang, P. C., Hsieh, J. C. and Hsiao, C. H. “Application of Genetic Algorithm to the Unrelated Parallel Machine Problem Scheduling,” Journal of the Chinese Institute of Industrial Engineering, 19(2), pp.79-95, 2002.
19.Cheng, T.C.E., and Jiang, J., “Job Shop Scheduling for Missed Due-date Performance, ” Computers and Operations Research, 34, No. 2, 297-307,1998.
20.Cheng, T.C.E. and Wang, G. “Single Machine Scheduling with Learning Effect Considerations,” Annals of Operation Research, 98, 273-290, 2000.
21.Davis, L., “Applying Adaptive Algorithms to Epistatic Domains,” In Proc. of the Inter. Joint Conf. on Artificial Intelligence, pp. 162-164, 1985.
22.Gen, M. and Cheng, R., “Genetic Algorithms and Engineering Design,” John Wiley & Sons, New York, 1997.
23.Gen, M., Tsujimura ,Y. and Kobota , E. “Solving Job- Shop Scheduling Problem Using Genetic Algorithms” Proceedings of the 16th International Conference on Computers and Industrial Engineering, Japan, Arshikaga, pp. 576-579,1994.
24.Goldberg, D. and Lingle, R. A., “Loci and the Traveling Salesman Problem,” In Grefenstette, J. J., editor, Proc. of 1st ICGA, pp.154-159,1985.
25.Haupt, R.L., “An Introduction to Genetic Algorithms for Electromagnetics,” IEEE Antennas and Propagation Magazine, 37(2), pp. 7 -15, 1995.
26.Holland, J., “Adaptation in Natural and Artificial Systems,” Ann Arbor University of Michigan Press, 1975
27.Johnson, S.M., “Optimal Two- and Three-stage Production Schedules with Set up Times,” Research Logistics Quarterly, vol. 1, pp. 61-68, 1954.
28.Lawton, G., “Genetic Algorithms for Schedule Optimization,” AI Expert, Vol. 17, No. 5, pp. 23-27, 1992.
29.Lawton, G., “Genetic Algorithms for Schedule Optimization,” AI Expert, Vol. 17, No. 5, pp. 23-27, 1992.
30.Liaw, C.F., “A Hybrid Genetic Algorithm for the Open Shop Scheduling Problem,” European Journal of Operational Research, vol. 124, pp.28-42, 2000.
31.Martin, C. H,” A Hybrid Genetic Algorithm/Mathematical Programming Approach to the Multi-family Flowshop Scheduling Problem with Lot Streaming,” Omega, Volume 37, Issue 1, Pages 126-137,2008.
32.Murata, T., Ishibuchi, H. and Tanaka, H., “Genetic Algorithm for Flowshop Scheduling Problem,” International Journal of Computers and Industrial Engineering, 30, pp.1061-1071, 1996.
33.Oliver, I., Smith, D., and Holland, J., “A Study of Permutation Crossover Operators on the Traveling Salesman Problem,” In Grefenstette, J. J., editor, Proc. of 2nd ICA, pp. 224-230, 1997.
34.Kan, R. A. H. G., “Machine Scheduling Problems: Classification, Complexity and Computations,” Martinus Nijhoff, The Hague, 1976.
35.Syswerda, G. “Uniform Crossover in Genetic Algorithms,” Proceedings of the 3rd International Conference on Genetic Algorithms, Morgan Kaufmann Publishers, San Mateo, CA, pp.2~9,1987.
36.Ting, C. K., Li, S. T. and Lee, C. N., “TGA: A New Integrated Approach to Evolutionary Algorithms,” Congress on Evolutionary Computation (CEC2001), pp.917-924, 2001.
37. Vilcota, G. and Billaut, J. C.,” A Tabu Search and a Genetic Algorithm for Solving a Bi-criteria General Job Shop Scheduling Problem,” European Journal of Operational Research, Volume 190, Issue 2, 16Pages 398-411 , 2008