(3.236.214.19) 您好!臺灣時間:2021/05/09 22:43
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:謝承志
研究生(外文):CHEN CHIH,HSIEH
論文名稱:應用差分演算法解決平面切割問題
論文名稱(外文):Solving Two-Dimensional Cutting Stock Problem Using Differential Evolution
指導教授:邱志洲邱志洲引用關係
口試委員:蔡榮發黃馨瑩高凌菁邱志洲
學位類別:碩士
校院名稱:國立臺北科技大學
系所名稱:經營管理系碩士班
學門:商業及管理學門
學類:企業管理學類
論文種類:學術論文
畢業學年度:104
中文關鍵詞:差分演算法最佳化二維原物料切割
外文關鍵詞:Differential evolutionOptimization2D Stock Cutting
相關次數:
  • 被引用被引用:1
  • 點閱點閱:56
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
本研究主要在解決平面切割問題。過去文獻中,隨著切割模式上越趨複雜,為尋求快速取得切割模式,許多學者採用啟發式演算法求解。本研究採用差分演算法來解決平面切割問題。該演算法擁有基因演算法類似的突變、交配及天擇機制外,且具有與粒子群演算法相同的隨機搜尋能力,以期能大幅節省時間,並且得到良好的求解品質。
本研究分為兩部分:(1)透過數學規劃模型,使用差分演算法進行求解。(2)透過BL擺放法則結合差分演算法求解。在研究上,首先透過部分文獻中之範例進行參數測試,產生較佳參數配置。使用較佳參數設定,對全部範例進行實驗,將數學規劃模型、BL擺放法則以及基因演算法,三者結果進行比較。以證明差分演算法在平面切割問題的可行性及有效性。
This study mainly use Differential Evolution algorithm (DE) for solving the two-dimensional rectangular strip cutting problem. Because cutting mode become more complicated than past, many studies adopt heuristic algorithm to solve the problem. Compared to genetic algorithm (GA), DE has same mechanisms: Mutation, Crossover, and Selection; in addition, search ability of DE is as good as Particle Swarm Optimization (PSO). In this study, we look forward to solve cutting problem with more efficient and good performance in computation time.
There are two parts in this study: (i) using formulated model for DE algorithm
(ii) using BL-algorithm for DE algorithm. Compare the presented results in two parts by computing examples from the literature and compare with GA further. To prove that differential evolution is an effective approach to solve 2D cutting problem.
目錄 iii
表目錄 iv
圖目錄 v
第一章 緒論 1
1.1 研究背景與動機 1
1.2 研究目的 3
1.3 研究架構 4
第二章 文獻探討 5
2.1 單維原物料切割問題 5
2.2 平面原物料切割問題 6
2.2.1 確定性方法 7
2.2.2 啟發式演算法 7
2.3 差分演算法 8
第三章 研究方法 10
3.1 平面矩形切割最佳化數學模式 10
3.1.1 模型說明 10
3.1.2 模型解向量說明 13
3.2 BL擺放法則以及編碼方式 13
3.2.1 BL擺放法則(Bottom-Left Algorithm) 13
3.2.2 編碼方式 14
3.3 差分演算法流程說明 15
3.3.1 平面矩形切割最佳化數學模式之差分演算法流程 19
3.3.2 BL擺放法則之差分演算法流程 19
第四章 演算結果及分析 20
4.1 範例說明 20
4.2 平面矩形切割最佳化數學模式結果及分析 21
4.2.1 結果及分析 21
4.3 BL擺放法則結果及分析 24
4.3.1 參數設定 24
4.3.2 結果及分析 29
第五章 結論與建議 38
5.1 研究結論 38
5.2 研究建議 39
參考文獻 40
[1]王韋傑,多尺寸平面切割問題之決策支援系統,碩士論文,國立臺北科技大學商業自動化與管理研究所,臺北,2011。
[2]吳泰熙、吳奕樺、張欽智,「以基因演算法求解單原片方形物件排列問題」,科學與工程技術期刊,2006,第75-83頁。
[3]吳盈志,雙演化演算法之研究,碩士論文,中原大學資訊管理研究所,桃園,2009。
[4]李國銘,微分進化演算法於工程最佳化之應用,博士論文,國立高雄第一科技大學工程科技研究所,高雄,2011。
[5]李維平、江長育、蔡宛庭,「搭配擾動策略之差分演化演算法」,資訊科技國際期刊,第五卷,第一期,2011,第24-39頁。
[6]陳雅祺,利用差分演算法解決投資組合最佳化問題,碩士論文,大同大學資訊經營研究所,臺北,2012。
[7]楊士杰、李坤洲,「利用差分演算法將非均勻天線最佳化」,工程科技與教育學刊,第八卷,第二期,2011,第309-319頁。
[8]M. Ali, C. W. Ahn , and M. Pant , " Trim loss optimization by an improved differential evolution," Mathematical Problems in Engineering, vol. 2013,2013
[9]J. E. Beasley,"An algorithm for the two-dimensional assortment problem," European Journal of Operational Research, vol. 19, no. 2, 1985, pp. 253-261.
[10]J. E. Beasley," A population heuristic for constrained two-dimensional non-guillotine cutting," European Journal of Operational Research, vol. 156, no. 3 , 2004, pp. 601-627.
[11]C. S. Chen, S. Sarin, and B. Ram," A mixed-integer programming model for a class of assortment problems," European journal of operational research, vol.65, no. 3, 1993, pp. 362-367.
[12]G. F. Cintra, F. K. Miyazawa, Y. Wakabayashi, and E. C. Xavier, " A note on the approximability of cutting stock problems," European journal of operational research, vol. 183, no. 3, 2007, pp. 1328-1332.
[13]E. L. T. Conceicao, and M. Maechler, Package ‘DEoptimR’, 2014.
[14]J. V. de Carvalho,"LP models for bin packing and cutting stock problems," European Journal of Operational Research, vol. 141, no. 2 , 2002, pp. 253-273.
[15]K. A. Dowsland, S. Vaid, and W.B. Dowsland ," An algorithm for polygon placement using a bottom-left strategy," European Journal of Operational Research, vol. 141, no. 2, 2002, pp. 371-381.
[16]H. Dyckhoff," A typology of cutting and packing problems," European Journal of Operational Research, vol. 44, no. 2, 1990, pp. 145-159.
[17]H. Dyckhoff, H. J. Kruse, D. Abel, and T. Gal," Trim loss and related problems," Omega, vol. 13, no. 1, 1985, pp. 59-72.
[18]M. Gradisar, and P. Trkman ," A combined approach to the solution to the general one-dimensional cutting stock problem," Computers & Operations Research, vol. 32, no. 7, 2005, pp. 1793-1807.
[19]O. Holthaus," Decomposition approaches for solving the integer one-dimensional cutting stock problem with different types of standard lengths," European Journal of Operational Research, vol. 141, no. 2, 2002, pp. 295-312.
[20]E. B. C. H. Hopper, and B. C. H. Turton," An empirical investigation of meta-heuristic and heuristic algorithms for a 2D packing problem," European Journal of Operational Research, vol. 128, no. 1, 2001, pp. 34-57.
[21]S. Jakobs," On genetic algorithms for the packing of polygons," European Journal of Operational Research, vol. 88, no. 1, 1996, pp. 165-181.
[22]K. K. Lai, and J. W. Chan," Developing a simulated annealing algorithm for the cutting stock problem," Computers & industrial engineering, vol. 32, no. 1, 1997, pp. 115-127.
[23]J. Lampinen, and I. Zelinka," Mixed integer-discrete-continuous optimization by differential evolution," In Proceedings of the 5th International Conference on Soft Computing, 1999, June, pp. 71-76.
[24]T. W. Leung, C. K. Chan, and M. D. Troutt," Application of a mixed simulated annealing-genetic algorithm heuristic for the two-dimensional orthogonal packing problem," European Journal of Operational Research, vol. 145, no. 3, 2003, pp. 530-542.
[25]H. L. Li, and C. T. Chang," An approximately global optimization method for assortment problems," European Journal of Operational Research, vol. 105, no. 3, 1998, pp. 604-612.
[26]H. L. Li, and C. T. Chang, and J. F. Tsai," Approximately global optimization for assortment problems using piecewise linearization techniques," European Journal of Operational Research, vol.140, no. 3, 2002, pp. 584-589.
[27]D. Liu, and H. Teng," An improved BL-algorithm for genetic algorithm of the orthogonal packing of rectangles," European Journal of Operational Research, vol. 112, no. 2, 1999, pp. 413-420.
[28]D. Maringer, and P. Parpas," Global optimization of higher order moments in portfolio selection," Journal of Global Optimization, vol. 43, no. 2-3, 2009, pp. 219-230.
[29]M. Rode, and O. Rosenberg," An analysis of heuristic trim-loss algorithms," Engineering Costs and Production Economics, vol. 12, no. 1, 1987, pp. 71-78.
[30]J. G. Sauer, L. dos Santos Coelho, V. C. Mariani, L. de Macedo Mourelle, and N. Nedjah," A discrete differential evolution approach with local search for traveling salesman problems. In Innovative Computing Methods and Their Applications to Engineering Problems, Springer Berlin Heidelberg, 2011, pp.1-12.
[31]G. Schilling, and M. C. Georgiadis," An algorithm for the determination of optimal cutting patterns," Computers & Operations Research, vol. 29, no. 8, 2002, pp. 1041-1058.
[32]L. Scrucca, Package ‘GA’, 2014.
[33]G. S. Jong, H. K. Oh, and C. Ryu ,"Heuristic and metaheuristic spatial planning of assembly blocks with process schedules in an assembly shop using differential evolution," Production Planning and Control, vol. 19, no. 6, 2008, pp. 605-615.
[34]R. Storn, and K. Price," Differential evolution–a simple and efficient heuristic for global optimization over continuous spaces," Journal of global optimization, vol. 11, no. 4, 1997, pp. 341-359.
[35]S. M. Suliman," Pattern generating procedure for the cutting stock problem," International Journal of Production Economics, vol. 74, no. 1, 2001, pp. 293-301.
[36]P. E. Sweeney, and E. R. Paternoster," Cutting and packing problems: a categorized, application-orientated research bibliography," Journal of the Operational Research Society, 1992, pp. 691-706.
[37]S. Umetani, M. Yagiura, and T. Ibaraki," One-dimensional cutting stock problem to minimize the number of different patterns," European Journal of Operational Research, vol. 146, no. 2, 2003, pp. 388-402.
[38]T. H. Wu, J. F. Chen, C. Low, and P. T. Tang ," Nesting of two-dimensional parts in multiple plates using hybrid algorithm," International Journal of Production Research, vol. 41, no. 16, 2003, pp. 3883-3900.
[39]Y. L.Wu, W. Huang, S. C. Lau, C. K. Wong, and G. H. Young," An effective quasi-human based heuristic for solving the rectangle packing problem," European Journal of Operational Research, vol. 141, no. 2, 2002, pp. 341-358.
[40]G. Young-Gun, and M. K. Kang," A fast algorithm for two-dimensional pallet loading problems of large size," European Journal of Operational Research, vol. 134, no. 1, 2001, pp. 193-202.
[41]H. Zhang, and G. P. Rangaiah," An efficient constraint handling method with integrated differential evolution for numerical and engineering optimization," Computers & Chemical Engineering, vol. 37, 2012, pp. 74-88.
連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔