臺灣博碩士論文加值系統

在本文中，針對製造業目前所面臨的全球性競爭以及非預期性需求波動問題，試圖改善其生產排程的方式。因為多數製造業的生產排程主要是由現場管理者（Shop-Flow）來管控，但因其技術與經驗有限，所規劃的生產排程表並不合適。
另一方面，現場管理者必需同時考量多項的排程績效目標，且所關切的排程績效目標常具有衝突性及損益交換之特性（Trade-Off）。也就是說，欲提升某一目標之績效則會致使另一目標之績效下滑。
在本文中，針對於二個案例公司中的三個實務案例，利用多目標遺傳基因演算法進行生產排程最佳化，並且成功協助現場管理者有效率的求解真實製造環境的生產排程表，提供適時且適合的決策。

Global competitions and problems of the irregular demand pattern are challenging the manufacturing industry nowadays, and utilization of multi-objective genetic algorithm in production scheduling is suggested to improve the efficiency of traditional method in this research.
Most of the manufacturing production scheduling is mainly controlled by shop-flow, and scheduling results are not always proper or fully satisfied due to lack of professional techniques and experiences.
On the other hand, shop-flow is also required to take several scheduling goals of efficiency into considerations, and the goals are often contradictory.
That is to say that improving one of the goals would result in decreasing another goal of efficiency.
In this research, two case companies and three practical examples are represented to demonstrate how applications of multi-objective genetic algorithm in optimizing production scheduling successfully helped shop-flow to find the most efficient scheduling result and meanwhile provide the most proper solutions for decision makers.

目錄
中文摘要 i
英文摘要 ii
致謝 iii
目錄 iv
圖目錄 vi
表目錄 viii
第一章 緒論 1
1.1 研究背景與動機 1
1.2 本文架構 3
第二章 實務生產排程系統最佳化探討 4
2.1 實務生產排程系統介紹 4
（一）、排程類型 5
（二）、排程績效衡量準則 7
（三）、派工法則 10
2.2 等效平行機台問題-以漁具業之抽絲製程為例 11
2.3 等效平行機台問題-以漁具業之編網製程為例 14
2.4 彈性的流線型生產問題-以高爾夫球具業之加工製程為例 16
第三章 智慧型最佳化方法 19
3.1 遺傳基因演算法 19
表示式 20
適應值評估 20
基因操作 21
3.2 非制壓解排序遺傳基因演算法 27
第四章 等效平行機台問題-以漁具業之抽絲製程為例 31
4.1 等效平行機台問題-以漁具業之抽絲製程為例的介紹 31
4.2 數學表示式 33
4.3 遺傳基因演算法於等效平行機台問題-以漁具業之抽絲製程為例 36
4.4 實驗結果 40
4.5 小結 45
第五章 等效平行機台問題-以漁具業編織網製程為例 46
5.1 等效平行機台問題-以漁具業編網製程為例介紹 46
5.2 數學表示式 48
5.3 多目標遺傳基因演算法於等效平行機台問題 50
5.4 實驗結果 55
5.5 小結 60
第六章 彈性的流線型生產問題-以高爾夫球具業之加工製程為例 61
6.1 彈性的流線型生產問題-以高爾夫球具業之加工製程為例的介紹 61
6.2 數學表示式 63
6.3 多目標遺傳基因演算法於彈性的流線型生產問題-以高爾夫球具業之加工製程為例 65
6.4 實驗結果 69
6.5 小結 74
第七章 結論與未來展望 75
參考文獻 76
附錄A等效平行機台抽絲製程實驗數據 79
附錄B等效平行機台編網製程實驗數據 91
附錄C彈性的流線型生產問題高爾夫球具業之加工製程實驗數據 93

圖目錄
圖2.1流線型生產系統示意圖 7
圖2.2漁具業生產流程圖 13
圖2.3等效平行機台生產系統示意圖 13
圖2.4等效平行機台生產系統示意圖 15
圖2.5高爾夫球具業之加工製程示意圖 17
圖2.6彈性的流線型生產示意圖 17
圖2.7高爾夫球具業生產流程圖 18
圖3.1遺傳基因演算法基本流程圖 20
圖3.2單點交配示意圖 21
圖3.3兩點交配示意圖 22
圖3.4多點交配示意圖 22
圖3.5均勻交配示意圖 23
圖3.6字罩交配示意圖 23
圖3.7線性內插法示意圖 24
圖3.8輪盤選擇法之示意圖 26
圖3.9非制壓解排序遺傳基因演算法主要流程圖 27
圖3.10 Fast-Nondominated Sort示意圖 28
圖3.11計算Crowding distance示意圖 30
圖4.1等效平行機台生產系統示意圖 32
圖4.2染色體設計方法示意圖 36
圖4.3無性生殖交配法示意圖 38
圖4.4自身突變之突變方法示意圖 39
圖4.5收斂圖 41
圖5.1等效平行機台生產系統示意圖 47
圖5.2染色體設計方法示意圖 50
圖5.3使用Goldberg’s Ranking最小化二個目標的示意圖 51
圖5.4 Invertion之交配方法示意圖 52
圖5.5 Shift突變之突變方法示意圖 53
圖5.6柏拉圖解 56
圖6.1高爾夫球具業之加工製程示意圖 62
圖6.2染色體設計方法示意圖 65
圖6.3 PMX之交配方法示意圖 67
圖6.4 Inversion突變之突變方法示意圖 68

表目錄
表2.1排程績效衡量準則分類[34] 8
表2.2常見的派工法則[35] 10
表4.1 GA所計算的排程結果 40
表4.2排程結果的詳細排程表 42
表5.1實證資料表 55
表5.2排程結果 55
表5.3排程結果的詳細排程表 57
表6.1實證資料表 69
表6.2迭代至第1代所取得的柏拉圖解 70
表6.3迭代至第100代所取得的柏拉圖解 70
表6.4迭代至第1000代所取得的柏拉圖解 70
表6.5原始人工規劃的排程表與結果之比較 71
表6.6排程結果的詳細排程表 72

[1]C. M. Fonseca and P. J. Fleming, 1993, “Genetic algorithms for multiobjective
optimization: Formulation, discussion and generalization,” in Proceedings
of the Fifth International Conference on Genetic Algorithms, S.
Forrest, Ed. San Mateo, CA: Morgan Kauffman, pp. 416–423.
[2]Zitzler, E.; Thiele, L., Nov 1999, "Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approach," Evolutionary Computation, IEEE Transactions on , vol.3, no.4, pp.257-271
[3]Deb, K.; Pratap, A.; Agarwal, S.; Meyarivan, T., Apr 2002, "A fast and elitist multiobjective genetic algorithm: NSGA-II," Evolutionary Computation, IEEE Transactions on , vol.6, no.2, pp.182-197.
[4]Ta-Yuan Chou; Tung-Kuan Liu; Chung-Nan Lee; Chi-Ruey Jeng, March 2008, "Method of Inequality-Based Multiobjective Genetic Algorithm for Domestic Daily Aircraft Routing," Systems, Man and Cybernetics, Part A: Systems and Humans, IEEE Transactions on , vol.38, no.2, pp.299-308.
[5]N. Srinivas and Kalyanmoy Deb, 1994,“Multiobjective optimization using
nondominated sorting in genetic algorithms”,Journal of Evolutionary
Computation. Volume 2, No.3, pp.221-248.
[6]T. K. Liu and T. Ishihara ,2005, “Multi-objective Genetic Algorithms for the Method of Inequalities”,In Control Systems Design–A New Framework, chapter 8, Ed. V. Zakian. Springer–VerlagLondon, UK,pp
[7]Poon P W , Carter J N,1994, “Genetic algorithm crossover operators for ordering
Applications”, Computers & Operations Research, Volume 22, NO.1,pp. 135-147.
[8]Runwei Cheng, Mitsuo Gen and Yasuhiro Tsujimura, September 1996, “A tutorial survey of job-shop scheduling problems using genetic algorithms—I. representation”,Computers & Industrial Engineering Volume 30, Issue 4, pp.983-997.
[9]Runwei Cheng, Mitsuo Gen and Yasuhiro Tsujimura, April 1999,“A tutorial survey of job-shop scheduling problems using genetic algorithms, part II: hybrid genetic search strategies”, Computers & Industrial Engineering Volume 36, Issue 2, pp. 343-364
[10]Candida Ferreira, 2002, “Combinatorial optimization by gene expression programmin inversion revisited ”,In J. M. Santos and A. Zapico, eds.,Proceedings of the Argentine Symposium on Artificial Intelligence, Santa Fe,Argentina, pp.160-174.
[11]Z.X. Guo , W.K. Wong, S.Y.S. Leung, J.T. Fan and S.F. Chan, July 2006,“Mathematical model and genetic optimization for the job shop scheduling problem in a mixed- and multi-product assembly environment: A case study based on the apparel industry”, Computers & Industrial Engineering Volume 50, Issue 3, pp. 202-219.
[12]Eugeniusz Nowicki and Czeslaw Smutnicki, 24 May 1996,“A fast tabu search algorithm for the permutation flow-shop problem”, European Journal of Operational Research
Volume 91, Issue 1, pp. 160-175
[13]Józef Grabowski, and Mieczyslaw Wodecki, September 2004,“A very fast tabu search algorithm for the permutation flow shop problem with makespan criterion”, Computers & Operations Research,Volume 31, Issue 11, pp. 1891-1909.
[14]Guoyong Shit,1997,“A genetic algorithm applied to a classic job-shop scheduling problem”,International Journal of Systems Science,Volume 28,NO.1,pp.25-32
[15]Imen Essafi, Yazid Mati, Stéphane Dauzère-Pérès, August 2008,“A genetic local search algorithm for minimizing total weighted tardiness in the job-shop scheduling problem”, Computers & Operations Research, Volume 35, Issue 8, Pages 2599-2616.
[16]Gen, M.; Tsujimura, Y.; Kubota, E., 1994, "Solving job-shop scheduling problems by genetic algorithm," Systems, Man, and Cybernetics, 1994. ''Humans, Information and Technology''., 1994 IEEE International Conference on , vol.2, no., vol.2, 2-5 Oct , pp.1577-1582
[17]Ono, I.; Yamamura, M.; Kobayashi, S., 1996, "A genetic algorithm for job-shop scheduling problems using job-based order crossover", Evolutionary Computation, 1996., Proceedings of IEEE International Conference on , vol., no., 20-22 May , pp.547-552
[18]Tsujimura, Y.; Mafune, Y.; Gen, M., 2001, " Effects of symbiotic evolution in genetic algorithms for job-shop scheduling", System Sciences, Proceedings of the 34th Annual Hawaii International Conference on Jan 3-6 Page（s）:6 pp.
[19]Tung-Kuan Liu, Jinn-Tsong Tsai, 2 and Jyh-Horng Chou,Feb. 2006,"Improved genetic algorithm for the job-shop scheduling problem",The International Journal of Advanced Manufacturing Technology, Volume 27, Numbers 9-10, pp.1021-1029.
[20]Mary E. Kurz, Ronald G. Askin, 16 November 2004, "Scheduling flexible flow lines with sequence-dependent setup times", European Journal of Operational Research, Volume 159, Issue 1, pp. 66-82
[21]Monaldo Mastrolilli,Luca Maria Gambardella, 2000, "Effective neighbourhood functions for the flexible job shop problem",Journal of Scheduling, Volume 3,NO. 1,pp. 3-20
[22]
Cheng-Hsieh Lai,2005, “Applications of intelligent taguchi genetic algorithm to
solve scheduling problems”,Master thesis,Department of Mechanical and
Automation Engineering, National Kaohsiung First University of Science and
Technology, Kaohsiung,Taiwan,R.O.C.
[23]Shaw-Cherng Chuo,2006, “Optimization of flexible manufacturing system using
hybrid evolutionary approach”,Master thesis,Graduate Institute of Systems and
Control Engineering,National Kaohsiung First University of Science and
Technology, Kaohsiung,Taiwan,R.O.C.
[24]Yu-Ting Liu,2007, “Applications of multi-objective optimization evolutionary
algorithm to robust airline schedule recovery”,Master thesis, Department of
Mechanical and Automation Engineering,National Kaohsiung First University of
Science and Technology, Kaohsiung,Taiwan,R.O.C.
[25]V. Suresh, Dipak Chaudhuri, 1993, “Dynamic scheduling- A survey of research”, International Journal of Production Economics, Vol. 32, pp.53-63.
[26]林我聰,1994，“現場排程專家系統 應用個體導向技術建立之研究”，第一版，資訊與電腦。
[27]陳志合，2000，“元件化現場排程系統之發展”，東海大學工業工程研究所,碩士論文,台中。
[28]陳永隆,2002,“製鞋業相同平行機台搭配模具生產現場排程之研究”, 東海大學工業工程研究所, 碩士論文,台中。
[29]彭俊昌,2004, “液晶面板組立廠投料與派工模擬分析”,清華大學 工業工程與工程管理學系, 碩士論文,新竹。
[30]郭祐銘,2008, “應用小生境遺傳基因演算法於多自由度機械手臂之最佳化操作”,國立高雄第一科技大學 機械與自動化工程系,碩士論文,高雄
[31]Eugeniusz Nowicki, Czeslaw Smutnicki, “The flow shop with parallel machines: A tabu search approach”, European Journal of Operational Research, Volume 106, Issues 2-3, pp. 226-253, 16 April 1998.
[32]Ceyda Oguz, Yakov Zinder, Van Ha Do, Adam Janiak, Maciej Lichtenstein, “Hybrid flow-shop scheduling problems with multiprocessor task systems”, European Journal of Operational Research, Volume 152, Issue 1, pp.115-131, 1 January 2004.
[33]Bagas Wardono, Yahya Fathi, “A tabu search algorithm for the multi-stage parallel machine problem with limited buffer capacities”, European Journal of Operational Research, Volume 155, Issue 2, Financial Risk in Open Economies, pp. 380-401, 1 June 2004
[34]王培珍,1995,“應用遺傳演算法與模擬在動態排程問題之探討”,中原大學,碩士論文,桃園。
[35]陳永隆,2002, “製鞋業相同平行機台搭配模具生產現場排程之研究”,東海大學,碩士論文,台中。