(3.235.25.169) 您好!臺灣時間:2021/04/18 03:45
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:詹晏昇
研究生(外文):ZHAN, YAN-SHENG
論文名稱:多重交叉突變複合遺傳演算法於彈性零工式批次移轉生產排程
論文名稱(外文):Hybrid Genetic Algorithm Designed for Batched Flexible Job-Shop Scheduling
指導教授:賴玟杏
指導教授(外文):LAI, WEN-HSING
口試委員:劉東官賴育誠
口試委員(外文):LIU, TUNG-KUANLAI, YU-CHENG
口試日期:2019-04-16
學位類別:碩士
校院名稱:國立高雄科技大學
系所名稱:電腦與通訊工程系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2019
畢業學年度:107
語文別:中文
論文頁數:81
中文關鍵詞:彈性零工式生產排程遺傳演算法多目標最佳化多目標標度化
外文關鍵詞:Flexible Job-shop SchedulingGenetic AlgorithmMulti-objective OptimizationMulti-objective Scaling
相關次數:
  • 被引用被引用:1
  • 點閱點閱:78
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:1
在傳統的鑄造生產業中,作業的調度常常是由老練的生管職員或師傅所累積的經驗來決定,但是這種決策效益往往是有限的,沒有考量未來的決策將無法顧及整體全貌,同時人工排程需耗費龐大的精力且難以應對突發狀況,致使生產線容易阻塞與等待,使作業不斷堆壘無法消化,效益不復存在,因此必須設計一排程演算模型來對現況工作進行未來預測,在當前的運作效率下來尋求未來的達交程度與各種目標,且藉由綜觀排程結果,使生管單位擁有商談籌碼,更容易的評斷接單與奠定交期,有效地調配工廠作業來達到更高的效率與利益。
本研究將鑄造工法的射蠟、組樹、浸將、鑄造、清砂製程提出,進行排程規劃設計,並說明如何針對完工日、逾期單數、總逾期天數、機台群負載標準差四個目標進行最佳化,運用彈性零工式與基因演算法的概念,制定基因初始化策略與實數染色體編碼方式,採用多種交配突變機制,並在沒有工件標準工時下,轉以每日平均產能進行以天為批次單位的排程推演,最後仿照射蠟報工資料,使用過去近半年之工單進行排程效益比較,實驗結果表示排程模型將有效地降低各項指標。

In the traditional foundry industry, the scheduling of operations is often determined by the veteran management staff or operators, but the effectiveness of such decisions is often narrow and limited. The decisions based on the past can not take into account the overall picture, artificial scheduling will consume a lot of human resource and difficult to deal with unexpected situations, which will make the production line blocked, so that the load can not be digested and the benefits will no longer exist. Therefore, it is necessary to design a scheduling model which is fast to predict the future state and seeking the various goals with current work efficiency. Then according to the scheduling results, the management staff will have the bargaining chip, make it easier to judge the order and set the delivery time, and effectively deploy the factory operations to achieve higher efficiency and benefits.
This study pick up five operation of foundry method which is wax injection, assembly, shell making, casting, and cut-off for designing the scheduling model. Four goals including makespan, amount of delay orders, number of delay days, and standard deviation of machine load were optimized. A hybrid multiple crossover and mutation genetic algorithm is proposed, which combines the global search and random procedure to produce initial population. Besides, in the absence of standard work hours of the workpiece, the daily average output is used to be a batch unit to perform the schedule day-to-day. Finally, using the history data in recently half year for comparing the proposed method with manual dispatching, the results show that the scheduling model will effectively reduce the indicators.

摘要 I
ABSTRACT II
誌謝 III
目錄 IV
圖目錄 VII
表目錄 IX
第一章 緒論 1
1.1 前言 1
1.2 研究動機與目的 2
1.3 論文架構 3
第二章 文獻探討與問題塑模 4
2.1 生產排程問題分類 4
2.2 派工法則 8
2.3 排程指標 9
2.4 問題塑模 11
2.4.1 問題描述 11
2.4.2 引入實際問題 12
第三章 啟發式演算法與多目標 13
3.1 啟發式演算法 13
3.2 傳統遺傳演算法 15
3.2.1 初始化(Initialization) 17
3.2.2 選擇(Selection) 18
3.2.3 交配(Crossover) 20
3.2.4 突變(Mutation) 22
3.2.5 淘汰(Elimination) 24
3.2.6 終止(Termination) 24
3.3 遺傳算法變形 25
3.3.1 混合遺傳演算法(Hybrid Genetic Algorithm) 25
3.3.2 混合田口遺傳演算法(Hybrid Taguchi-method Genetic Algorithm) 25
3.4 多目標最佳化(Multi-objective Optimization) 28
第四章 提案方法設計 31
4.1 提案方法與流程概述 31
4.1.1 製程對應演算設計 31
4.1.2 排程資料結構 33
4.2 染色體編解碼表示法 34
4.2.1 製程序列(Operation Sequence) 34
4.2.2 機台選擇(Machine Selection) 35
4.3 初始族群建構策略 37
4.3.1 製程序列規則(OS Rules) 37
4.3.2 機台挑選規則(MS Rules) 37
4.4 基因運算子 38
4.4.1 製程序列 38
4.4.2 機台挑選 39
4.5 多目標 40
4.5.1 求解目標函數 40
4.5.2 求解多目標 41
4.6 演算流程與批次算法實現 43
4.7 平行演算設計 48
第五章 實驗結果與討論 49
5.1 實驗數據與環境 49
5.1.1 設置虛擬機台 49
5.1.2 整體系統架構 49
5.2 多目標適應值標度化評估實驗 51
5.3 初始化策略比較 52
5.4 演算法效能實驗 54
5.5 實際排程結果 56
5.6 仿歷史報工排程實驗 57
5.6.1 選擇標準工時 58
5.6.2 調整排程限制 61
第六章 結論與未來展望 63
6.1 章節回顧 63
6.2 結論與未來展望 64
參考文獻 65
[1] 楊瑞雯,2016,”臺灣鑄造產業發展現況與展望”
[2] 陳建良,1995,”排程概述”,機械工業雜誌,頁122-137
[3] 江賀,2011,”超啟發式演算法:跨領域的問題求解模式”,中國計算機學會通訊,第7卷第3期
[4] H. Chen, J. Ihlow, C. Lehmann, 1999, “A genetic algorithm for flexible job-shop scheduling”, IEEE International Conference on Robotics and Automation, Vol. 2, pp. 1120–1125
[5] H.Van Dyke Parunak, 1991, “Characterizing the manufacturing scheduling problem”, Journal of Manufacturing Systems, Vol. 10, pp. 241-259
[6] R.L. Graham, E.L. Lawler, J.K. Lenstra, A.H.G.Rinnooy Kan, 1979, “Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey”, Annals of Discrete Mathematics, Vol. 5, pp. 287-326
[7] Gregory Dobson, CANDACE ARAI YANO, 2002, “Product offering, pricing, and make-to-stock/make-to-order decisions with shared capacity”, Production and Operations Management, Vol. 11, pp. 293-312
[8] Pei-Chann Chang, Shih-Hsin Chen, Kun-Lin Lin, 2005, “Two‐phase sub population genetic algorithm for parallel machine-scheduling problem”, Expert Systems with Applications, Vol. 29, pp. 705-712
[9] Dirk Reichelt, Lars Mönch, 2006 “Multiobjective Scheduling of Jobs with Incompatible Families on Parallel Batch Machines”, Evolutionary Computation in Combinatorial Optimization
[10] Pei-Chann Chang, Jih-Chang Hsieh, Shui-Geng Lin, 2002, “The development of gradual-priority weighting approach for the multi-objective flow shop scheduling problem”, International Journal of Production Economics, Vol.3, pp. 171-183
[11] Tsung-Che Chiang, Li-Chen Fu, 2006, “Multiobjective Job Shop Scheduling using Genetic Algorithm with Cyclic Fitness Assignment”, 2006 IEEE International Conference on Evolutionary Computation
[12] P. Brucker, R. Schlie, 1990, “Job-shop scheduling with multi-purpose machines”, Computing, Vol. 45, pp. 369-375
[13] Haipeng Zhang, Mitsuo Gen, 2005, “Multistage-based genetic algorithm for flexible job-shop scheduling problem”, J. Complexity Internat
[14] M. R. Garey, D. S. Johnson, Ravi Sethi, 1976, “The Complexity of Flowshop and Jobshop Scheduling”, Mathematics of Operations Research, Vol. 1, pp. 117-129
[15] Yazid Mati, Xiaolan Xie, 2004, “The complexity of two-job shop problems with multi-purpose unrelated machines”, European Journal of Operational Research, pp. 159-169
[16] Joc Cing Tay, Nhu BinhHo, 2008, “Evolving dispatching rules using genetic programming for solving multi-objective flexible job-shop problems”, Computers & Industrial Engineering, Vol. 54, pp. 453-473
[17] Gere, W. S., 1966, “Heuristics in Job Shop Scheduling”, Management Science, Vol. 13, pp. 167-190
[18] J.H. Blackstone, D.T. Phillips, G.L. Hogg, 1982, “A state-of-the-art survey of dispatching rules for manufacturing job shop operations”, International Journal of Production Research, Vol. 20, pp. 27-45
[19] Kenneth R. Baker, 1974, “Introduction to sequencing and scheduling”
[20] Michael L. Pinedo, 1995, “Scheduling: Theory, Algorithms, and Systems”
[21] Wei-Ting Lin, Ding-Tsair Chang, 2011, “The scheduling problem of LED packaging and testing factory - a case study”
[22] R. Haupt, 1989 “A survey of priority rule-based scheduling”, Operations Research-Spektrum, Vol. 11, pp. 3-16
[23] I. Kacem, S. Hammadi, and P. Borne, 2002, “Approach by localization and multiobjective evolutionary optimization for flexible job-shop scheduling problems”, IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), Vol. 32, pp. 1-13
[24] Vincent Kenny, Matthew Nathal, and Spencer Saldana, 2014, “Heuristic algorithms”
[25] Natallia Kokash, 2014, “An introduction to heuristic algorithms”
[26] Kenneth Sörensen, 2013, “Metaheuristics - the metaphor exposed”, International Transactions in Operational Research, Vol. 22, pp. 3-18
[27] Russell C. Eberhart, Yuhui Shi, James Kennedy, 2001, “Swarm Intelligence”
[28] K. Y. Lee, 2008, “Modern Heuristic Optimization Techniques : Theory and Applications to Power Systems”
[29 Adel Mellit, Soteris A. Kalogiroub, 2008, “Artificial intelligence techniques for photovoltaic applications: A review”, Progress in Energy and Combustion Science, Vol. 34, pp. 574-632
[30] A. M. Turing, 1950, “Computing machinery and intelligence”. Mind, Vol. LIX , pp. 433–460
[31] Barricelli, Nils Aall, 1954, “Esempi numerici di processi di evoluzione” Methodos, pp. 45–68.
[32] Barricelli, Nils Aall, 1957, “Symbiogenetic evolution processes realized by artificial methods”. Methodos, pp. 143–182.
[33] A. S. Fraser, 1957, “Simulation of genetic systems by automatic digital computers. I. Introduction", Australian Journal of Biological Sciences 10(4), pp. 484–491.
[34] Jack L Crosby, 1973, “Computer Simulation in Genetics”
[35] Rechenberg, Ingo, 1973, “Evolutionsstrategie. Stuttgart: Holzmann-Froboog”
[36] Schwefel, Hans-Paul, 1977, “Numerische Optimierung von Computer-Modellen mittels der Evolutionsstrategie”
[37] Sachin Desale, Akhtar Rasool, Sushil Andhale, Priti Rane, 2015, “Heuristic and Meta-Heuristic Algorithms and Their Relevance to the Real World: A Survey”, International Journal of Computer Engineering in Research Trends, Vol. 2, pp. 296-304
[38] S. Arora, 1998, “Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems”, Journal of the ACM, Vol. 45, pp. 753-782
[39] 劉東官,2007,”智慧型多目標動態生產排程系統教材”,工業技術研究院,台灣。
[40] Randy L. Haupt, Sue Ellen Haupt, 2004, “Practical genetic algorithms”
[41] Kenneth Alan De Jong, 1975, “Analysis of the behavior of a class of genetic adaptive systems”, University of Michigan
[42] Hao-Chin Chang, Yeh-Peng Chen, Tung-Kuan Liu, Jyh-Horng Chou, 2015, “Solving the Flexible Job Shop Scheduling Problem With Makespan Optimization by Using a Hybrid Taguchi-Genetic Algorithm”, IEEE Access, Vol. 3, pp. 1740-1754
[43] Jinn-Tsong Tsai, Tung-Kuan Liu, Jyh-Horng Chou, 2004, “Hybrid Taguchi-Genetic Algorithm for Global Numerical Optimization”, IEEE Transactions on Evolutionary Computation, Vol. 8, No. 4, pp. 365-377
[44] David E. Goldberg, 1989, “Genetic Algorithms in Search, Optimization and Machine Learning”, Addison-Wesley, Boston
[45] Y. Sawaragi, H. Nakayama, T. Tanino, 1985, “Theory of Multiobjective Optimization”, Academic Press, London
[46] R.E. Steuer, 1986, “Multiple Criteria: Theory, Computation and Application”
[47] Graham Kalton, Ismael Flores-Cervantes, 2003, “Weighting Methods”, Journal of Official Statistics, Vol. 19, No. 2, pp. 81-97
[48] A. H. Lachlans, 1967, “The Priority Method I”
[49] Waiel F. Abd El-Wahed, Sang M. Lee, 2006, “Interactive fuzzy goal programming for multi-objective transportation problems”, Omega, Vol. 34, pp. 158-166
[50] Carlos M. Fonseca, 1995, “Multiobjective Genetic Algorithms with Application to Control Engineering Problems”
[51] Tung Kuan Liu, T. Ishihara, H. Inooka, 1995 “Multiobjective control systems design by genetic algorithms”, SICE '95. Proceedings of the 34th SICE Annual Conference. International Session Papers, pp. 1521-1526
[52] T. Murata, H. Ishibuchi, 1995, “MOGA: Multi-objective genetic algorithms”, Proceedings of 1995 IEEE International Conference on Evolutionary Computation, pp. 284-294
[53] C.A. Coello Coello, M.S. Lechuga, 2002 “MOPSO: a proposal for multiple objective particle swarm optimization”, Proceedings of the 2002 Congress on Evolutionary Computation, pp. 1051-1056
[54] S. Kukkonen, J. Lampinen, 2004, “An Extension of Generalized Differential Evolution for Multi-objective Optimization with Constraints”, Computer Science, Vol. 3242, pp. 752-761
[55] Guohui Zhang, Liang Gao, Yang Shi, 2011, “An effective genetic algorithm for the flexible job-shop scheduling problem”, Expert Systems with Applications, Vol. 38, pp. 3563-3573
[56] K.M. Lee, T. Yamakawa, 1998, “A Genetic Algorithm for General Machine Scheduling Problem”, Proceedings of International Conference on Knowledge based Intelligent Electronics Systems, Vol. 2, pp. 60-66.
電子全文 電子全文(網際網路公開日期:20231231)
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔