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

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:李勝隆
研究生(外文):Sheng-Lung Li
論文名稱:基因演算法於印刷電路板鑽孔排程之應用
論文名稱(外文):Application of genetic algorithm to the production scheduling of drilling operation in a PCB factory
指導教授:張百棧張百棧引用關係
指導教授(外文):Pei-Chann Chang
學位類別:碩士
校院名稱:元智大學
系所名稱:工業工程與管理學系
學門:工程學門
學類:工業工程學類
論文種類:學術論文
論文出版年:2003
畢業學年度:91
語文別:中文
論文頁數:81
中文關鍵詞:基因演算法非等效平行機台排程塔布搜尋法印刷電路板
外文關鍵詞:Genetic AlgorithmUnrelated Parallel Machines SchedulingTabu SearchPrinted Circuit Board
相關次數:
  • 被引用被引用:31
  • 點閱點閱:370
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:89
  • 收藏至我的研究室書目清單書目收藏:0
本研究主要探討隨機選取交配與突變運算元之基因演算法(Genetic Algorithm),在印刷電路板產業的應用,並以鑽孔排程為例。鑽孔排程在印刷電路板產業中為一典型的非等效平行機台(Unrelated Parallel Machine)排程問題,此生產型態隨著訂單派工法則的不同,對客戶交期有一定的影響,本研究採取訂單不可分割原則,並考慮機器產能將訂單排入機台,並以總延遲時間最小化為評估準則。
在以往的文獻中,以基因演算法求解非等效平行機台之問題,皆採取固定選取交配與突變運算元,但是,經過許多世代的演算,會造成母體相似度太高,而無法突破區域最佳解,因此如何使基因演算法之求解品質提高乃是一重點所在,本研究則導入交配與突變運算元12種組合進行隨機選取,不論問題組合多寡與其他啟發式法則比較皆能夠得到近似最佳解,其最小改善率也達到45.8%,因此,本研究所提出之演算法具有實際應用價值,可協助管理者在排程作業之決策。
This research applies the genetic algorithm with random chosen crossover and mutation operations to printed circuit board industry and takes drilling operation process as an example. Scheduling of in printed circuit board industry belongs to unrelated parallel machine scheduling problem. Due-date is affected by different dispatching rules. This research assumes that orders are undivided and are assigned to machines according machines’ capacities is to distribute it onto the unrelated parallel machines for meeting the due-date. The objective is the minimization of the sum of the tardiness.
The past literatures about application of genetic algorithm to the unrelated parallel scheduling machine problems apply fixed crossover and mutation operations. But, it will make homogeneity of population too high after many generations and is unable to skip the local optimal solution. Therefore how to raise the solution quality of genetic algorithm is the key issue in this research. In this research, we propose the genetic algorithm with random chosen crossover and mutation operations to reduce the sum of the tardiness. The results of genetic algorithm with random chosen operation are superior to those of other approaches and the lowest percentage of improvement is around 45.8%. It shows this algorithm is worth considered for application on real world case.
目 錄
中文摘要 i
英文摘要 ii
誌謝 iii
目錄 iv
圖目錄 vii
表目錄 viii
符號說明 x
第一章 緒論 1
1.1 研究背景與動機 1
1.2 研究範圍與目的 2
1.3 研究方法 2
1.4 論文架構與流程 3
第二章 文獻探討 6
2.1 基因演算法 6
2.1.1基因演算法簡介 6
2.1.2基因演算法於排程之應用 9
2.1.3基因演算法與傳統演算法之差異 12
2.1.4小結 13
2.2 平行機台 14
2.2.1平行機台系統定義及分類 14
2.2.2非等效平行機台問題相關文獻 16
2.2.3小結 17
第三章 問題描述與模式建構 19
3.1印刷電路板鑽孔作業現況 19
3.2問題描述 20
3.3問題限制與假設 22
3.4問題架構模式 22
第四章 研究方法 26
4.1基因演算法 26
4.1.1編碼 28
4.1.2基因參數設定 30
4.1.3產生起始解 31
4.1.4計算目標值 33
4.1.5定義適合度函數 33
4.1.6執行基因運算元並產生子代 36
4.1.6.1複製/選擇 36
4.1.6.2交配 40
4.1.6.3突變 48
4.1.7產生新群體 50
4.1.8演化世代停止條件 51
4.2排程限制與派工準則 51
4.3鄰域解搜尋(Neighborhood Search) 53
第五章 實驗設計 55
5.1 基因演算法隨機選取交配與突變運算元最佳參數組合 56
5.1.1實驗方式 56
5.1.2 母群體數與演算世代變異數分析 61
5.2 參數結果驗證 64
5.2.1確認參數實驗結果….…………………………………64
5.2.2 各項因子實驗結果討論 66
第六章 實驗結果 69
6.1 隨機與固定選取交配與突變運算元之基因演算法比較 69
6.2 隨機選取運算元之基因演算法與塔步搜尋法比較 71
第七章 結論及未來展望 77
7.1隨機選取交配與突變運算元之特性 77
7.2結論 77
7.3未來展望 78
參考文獻 79
圖 目 錄
圖1.1 研究架構流程圖 5
圖2.1基因演算法流程 9
圖2.2平行機台生產系統 14
圖4.1混合式基因演算法 27
圖4.2輪盤法各染色體累積機率 38
圖4.3(A) 依據機台可開始時間前後的排程結果 53
圖4.3(B) 依據交期內產能大小的排程結果 53
圖4.4鄰域搜尋圖 54
圖5.1隨機選取交配與突變收斂過程 57
圖5.2固定機率之回應圖 60
圖5.3起始解產生方式驗證 66
圖5.4複製方式驗證 68
圖6.1運算元組合之平均折線圖 71
圖6.2多訂單於5台非等效平行機台之目標值比較 73
圖6.3多訂單於10台非等效平行機台之目標值比較 73
圖6.4多訂單於5台非等效平行機台改善率之比較 75
圖6.5多訂單於10台非等效平行機台改善率之比較 76
表 目 錄
表2.1 基因演算法的優缺點 18
表4.1 常見啟發式解法 32
表4.2 輪盤法染色體適合度值 38
表4.3 輪盤法選擇機率與累加機率 38
表4.4 輪盤法之選擇染色體 38
表4.5 期望值模式染色體適合度值 39
表4.6 期望值模式之期望複製個數 40
表4.7 期望值模式之實際複製個數 40
表4.8 機台產能及閒置時間表 52
表5.3 固定機率因子與水準設定 58
表5.4 L16直交表之因子與水準配置 58
表5.5 固定機率實驗結果與S/N比 59
表5.6 固定機率之回應表 60
表5.7 固定交配、突變機率的最佳參數 60
表5.8 母群體與演算世代組合之設定與實驗數據 61
表5.9 組間效應項之檢定 62
表5.10母群體與演算世代組合成對比較 62
表5.10母群體與演算世代組合成對比較(續) 63
表5.11隨機選取交配與突變運算元之基因演算法最佳參數組合 64
表5.12最佳參數組合確認實驗數據 64
表5.13參數結果驗證統計報表 64
表5.14平均收斂世代實驗數據 65
表5.15平均收斂世代統計報表 65
表5.16隨機選取交配與突變運算元之基因演算法(N-GA) 68
表6.1 基因演算法運算元組合實驗數據 69
表6.2 變異數分析摘要表 70
表6.3 描述統計量表 70
表6.4非等效平行機台5台之總延遲時間最小化之目標值 72
表6.5非等效平行機台10台之總延遲時間最小化之目標值 72
表6.6非等效平行機台5台之總延遲時間最小化之改善率 74
表6.7非等效平行機台10台之總延遲時間最小化之改善率 75
表6.4非等效平行機台5台之總延遲時間最小化之目標值 72
表6.4非等效平行機台5台之總延遲時間最小化之目標值 72
參考文獻
1. Allahverdi, A. and J., Mittenthal, “Scheduling on M parallel machines subject to random breakdowns to minimize expected mean flow time,” Naval Research Logistics, 41, pp.677-682, 1994.
2. Chang, P. C. and J. C. Hsieh, “A comprehensive review of genetic algorithms applied to the production scheduling problems,”submitted to Applied Soft Computing, 2002.
3. Chang, P. C., J. C. Hsieh and S. G. Lin,“The development of gradual-priority weighting approach for the multi-objective flowshop scheduling problem,” International Journal of Production Economics, 79, pp.171-183, 2002.
4. Cheng, R. and M. Gen,“Parallel machine scheduling problems using memetic algorithms” Computers & Industrial Engineering, 33, 3, pp.761-764, 1997.
5. Croce, D., R. T. Federico, and V. Giuseppe,“A genetic algorithm for the job shop problem,”Computer & Operations Research, 122, 1, pp.15-24, 1995.
6. Davis, L., Handbook of Genetic Algorithms, Morgan Kaufmann, San Mateo, CA, 1987.
7. De Jong, K. A. An Analysis of the Behavior of a Class of Genetic Adaptive Systems, Ann Arbor: University of Michigan Press, 1975.
8. Falkenaurer, E. and S. Bouffouix,“A genetic algorithm for job shop scheduling,”Proceedings of IEEE International Conference on Robitcs and Automaion Sacramento, pp.824-829, 1991.
9. Funda, S. S. and G. Ulusoy, “Parallel machine scheduling with earliness and tardiness penalties,” Computers & Operations Research 26, pp.773-787, 1999.
10. Gillies, A. M., Machine Learning Procedures for Generating Image Domain Feature Detectors, Ph.D. Dissertation, University of Michigan, 1985.
11. Glass C., C. Potts, and P. Shade,“Unrelated parallel machine scheduling using local search,”Mathl. Comput. Modelling, 20, 2, pp.41-52, 1994.
12. Goldberg, D. and R. Lingle,“Loci and the traveling salesman problem,” Proceedings of International conference on Genetic Algorithms and Their Applications, pp.154-159, 1985.
13. Goldberg, D., Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesly, MA, 1989.
14. Grefenstette, J. J.,“Optimization of control parameters for genetic algorithms,”IEEE Transactions on systems, man & cybernetics, pp.122-128, 1986.
15. Grefenstette, J. J., J. E. Baker,“How genetic algorithms work: a critical look at implicit parallelism,” Proceedings of the Third International conference on Genetic Algorithms, pp.20-27, 1989.
16. Hariri, A. M. A. and C. N. Potts, “Heuristics for scheduling unrelated parallel machines,”Computers in Operations Research, 18, 3, pp.323-331, 1991.
17. Hemant Kumar, N. S. and G. Srinivasan,“A genetic algorithm for job shop scheduling - A case study,”Computers in Industry, 31, 2, pp.155-160, 1996.
18. Holland, J. H., Adaptation in Natural and Artificial Systems, Ann Arbor: University of Michigan Press, 1975.
19. Karp, R. M.,“Reducibility Among Combinatorial Problems,”In Complexity of Computer Computations, New York: Plenum, pp.85-103, 1972.
20. Kim D. W., K. H. Kim, W. Jang and F. F. Chen,“Unrelated parallel machine scheduling with setup times using simulated annealing,” Robotics and Computer Integrated Manufacturing, 18, pp.223-231, 2002.
21. Lawler, E.L. and J. Labetoulle“On preemptive scheduling of unrelated parallel processors by linear programming,”Journal of the Association for Computing Machinery, 25, pp.612-619, 1978.
22. Michalewicz, Z., Genetic Algorithm + Data Structures = Evolution Programs, 2nd ed., Springer-Verlag, New York, 1994.
23. Mingail, H., “Genetic algorithm gaining faster results,”Computing Canada, 21, 11, pp.18-25, 1995.
24. Murata, T., H. Ishibuchi and H. Tanaka,“Genetic algorithms for flowshop scheduling problems,”International Journal of Computers and Industrial Engineering, 30, 4, pp.1061-1071, 1996a.
25. Murata, T., H. Ishibuchi and H. Tanaka,“Multi-objective genetic algorithm and its applications to flowshop scheduling,”International Journal of Computers and Industrial Engineering, 30, 4, pp.957-968, 1996b.
26. Piersma, N. and W. van Dijk,“A local search heuristic for unrelated parallel machine scheduling with efficient neighborhood search,” Mathl. Comput. Modelling, 24, 9, pp.11-19, 1996.
27. Reeves, C. R.“A genetic algorithm for flowshop sequencing,”Computers & Operations Research, 122, 1, pp.5-13, 1995.
28. Schaffer, J. D., R. A. Caruana, L. J. Eshelman, and R. Das,“A study of control parameters affecting online performance of genetic algorithms for function optimization,”Proceedings of the Third International Conference on Genetic Algorithms, pp51-60, 1989.
29. Srivastava, B.,“An effective heuristic for minimizing makespan on unrelated parallel machines,”Journal of the Operational Research Society, 49, pp.886-894, 1998.
30. Suresh, V. and D. Chaudhuri,“Minimizing maximum tardiness for unrelated parallel machines,”International Journal of Production Economics, 34, pp.223-229, 1994.
31. Varela, R., C. R. Vela, J. Puente and A. Gomez,“A knowledge-based evolutionary strategy for scheduling problems with bottlenecks,”European Journal of Operational Research, 145, pp.57-71, 2003.
32. Wang, C. S. and R. Uzsoy,“A genetic algorithm to minimize maximum lateness on a batch processing machine,”Computers & Operations Research, 29, pp.1621-1640, 2002.
33. 王彥文,「印刷電路板鑽孔作業生產排程之研究」,碩士論文,元智大學,2002。
34. 阮永漢,「系統模擬與基因演算法於完全相同機台排程之應用」,碩士論文,元智大學,2002。
35. 徐烈昭,「應用塔步搜尋法於非等效平行機台之研究─以PCB鑽孔作業為例」,碩士論文,元智大學,2001。
36. 陳正雄,「塔布搜尋法在塑化業排程之應用-以BOPP FILM為例”」,碩士論文,元智大學,2000。
37. 游擱鴻,「以啟發式方法求解不相關平行機器排程問題」,碩士論文,朝陽大學,1997。
38. 趙文涼,「基因演算法於單機交期絕對偏差及整備成本總和最小化排程問題之應用」,碩士論文,元智大學,2001。
39. 劉志宏,「不確定加工時間之平行機台排程」,碩士論文,清華大學,2000。
40. 蕭陳鴻,「基因演算法於非等效平行機台排程之應用」,碩士論文,元智大學,2001。
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關期刊
 
系統版面圖檔 系統版面圖檔