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

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:洪嘉昕
研究生(外文):Chia-Shin Hung
論文名稱:混合啟發式演算法於成衣業之馬克排版問題
論文名稱(外文):Hybrid Heuristics for Marker Planning Problem in Apparel Industry
指導教授:曹譽鐘曹譽鐘引用關係
指導教授(外文):Yu-Chung Tsao
口試委員:王孔政郭伯勳
口試委員(外文):Kung-Jeng WangPo-Hsun Kuo
口試日期:2019-05-29
學位類別:碩士
校院名稱:國立臺灣科技大學
系所名稱:工業管理系
學門:商業及管理學門
學類:其他商業及管理學類
論文種類:學術論文
論文出版年:2019
畢業學年度:107
語文別:英文
論文頁數:51
中文關鍵詞:馬克排版二維排版問題基因演算法模擬退火法混合基因演算法模擬退火法
外文關鍵詞:marker planningtwo-dimensional packing problemgenetic algorithmsimulated annealinghybrid algorithms
相關次數:
  • 被引用被引用:0
  • 點閱點閱:43
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
在成衣業中,因各服裝的尺寸與眾多服裝類別而有多元的成衣樣板,馬克排版的用意即是將這些成衣樣板在一定長度與寬度的紙上進行移動與排列以形成一張馬克才能執行後續裁剪布料與縫製的程序,所以馬克排版也可以歸類為一種二維排版問題。在進行馬克排版時,需要將樣板排列緊密以減少裁減過後所造成的布料浪費,因此,本研究以馬克的最小長度為目標,以混和啟發式演算法的方式來求出最佳的馬克排版與長度。
首先,本研究考慮多種旋轉角度與鏡像的翻轉來獲取更多樣化的排版結果,而透過這些多元的排版結果,可以得到最佳馬克排版與其最小長度的機會亦會愈高。因此,本研究依上述的考慮條件呈現新的移動方法,用於樣板不重疊的情況下進行排列與移動以獲得初解的馬克排版與長度。為了能改善初解,本研究考量柔性計算,基因演算法與模擬退火法來各結合本研究的移動方法,以尋找具有最佳旋轉角度與翻轉位置的排列順序,從而獲得馬克的最小長度,此外,本研究亦利用基因演算法的全局搜索與模擬退火法的局部搜索之特性,提出混合式基因演算法-模擬退火法來比較此三種演算法的適應值與效率。本研究亦考慮於旋轉角度上的特殊應用情況,以便成衣業於不同狀況下可以決定和式的演算法來執行馬克排版問題。
With diverse sizes and categories of clothes in apparel industry, marker planning aims to arrange and move all these parts of clothes in a long-thin paper before cutting process, which can also be considered as one of a category in two-dimensional packing problems. In order to decrease the wastage of fabric after the cutting process, the marker layout essentially needs to be as compact as possible. Therefore, a minima length in marker layout is required in marker planning problem. In this paper, hybrid heuristics are proposed to conduct and acquire the optimized marker layout and length.
Firstly, a Moving Heuristic is presented as a new packing method to arrange and move the patterns without overlapped situation, where an initial marker will be presented to calculate the length. Specially, this heuristic considers multiple rotated angles and flipping positions of the patterns in order to obtain more diverse arrangements. With more different arrangements, the higher chance of optimized marker layout and length can be obtained. Next, to improve this initial solution, soft computing algorithms are taken into account, including genetic algorithm, simulated annealing, and hybrid genetic algorithm-simulated annealing proposed in this paper to find the best arranging sequence, obtaining the minima length in this marker layout and comparing each of the fitness value and efficiency. In addition, special case with specific scenarios in rotated angles is considered, so that the industry can decide the suitable algorithms to conduct the marker planning problem.
摘要........I
ABSTRACT........II
ACKNOWLEDGMENTS........III
CONTENT........ IV
LIST OF FIGURE........ VI
LIST OF TABLE........ VII

CHAPTER 1 INTRODUCTION........ 1
1.1 Background and motivation........ 1
1.2 Research objective........ 4
1.3 Research organization........ 5

CHAPTER 2 LITERATURE REVIEW........ 7
2.1 General problems in apparel industry........ 7
2.2 Two-dimensional packing problem........ 8
2.3 Soft computing algorithms........ 10

CHAPTER 3 MODEL FORMULATION........ 13
3.1 Problem formulation........ 14
3.2 Packing method........ 15
3.2.1 Representation of apparel patterns........ 16
3.2.2 Moving Heuristic........ 17
3.3 Development for hybrid heuristics........ 22
3.3.1 Genetic algorithm........ 22
3.3.2 Simulated annealing........ 27
3.3.3 Hybrid genetic algorithm-simulated annealing........ 31

CHAPTER 4 NUMERICAL EXPERIMENTS........ 33
4.1 Experiment description........ 33
4.2 Comparison experiment between GA, SA, HGASA........ 34
4.3 Special Case........ 41

CHAPTER 5 CONCLUSIONS AND FUTURE RESEARCH........ 46
5.1 Conclusion........ 46
5.2 Future research........ 47

REFERENCES........ 48
Bennell, J. A., & Oliveira, J. F. (2008). The geometry of nesting problems: A tutorial. European Journal of Operational Research, 184(2), 397-415.

Bortfeldt, A. (2006). A genetic algorithm for the two-dimensional strip packing problem with rectangular pieces. European Journal of Operational Research, 172(3), 814-837.

Burke, E. K., Hellier, R. S., Kendall, G., & Whitwell, G. (2007). Complete and robust no-fit polygon generation for the irregular stock cutting problem. European Journal of Operational Research, 179(1), 27-49.

Chen, P. H., & Shahandashti, S. M. (2009). Hybrid of genetic algorithm and simulated annealing for multiple project scheduling with multiple resource constraints. Automation in Construction, 18(4), 434-443.

Chen, P., Fu, Z., Lim, A., & Rodrigues, B. (2003). Two-dimensional packing for irregular shaped objects. In 36th Annual Hawaii International Conference on System Sciences, 2003. Proceedings of the (pp. 10-pp). IEEE.

Dowsland, K. A., Vaid, S., & Dowsland, W. B. (2002). An algorithm for polygon placement using a bottom-left strategy. European Journal of Operational Research, 141(2), 371-381.

Goldberg, D. E., & Holland, J. H. (1988). Genetic algorithms and machine learning. Machine learning, 3(2), 95-99.

Gomes, A. M., & Oliveira, J. F. (2006). Solving irregular strip packing problems by hybridising simulated annealing and linear programming. European Journal of Operational Research, 171(3), 811-829.

Huang, E., & Korf, R. E. (2013). Optimal rectangle packing: An absolute placement approach. Journal of Artificial Intelligence Research, 46, 47-87.

Jacobs-Blecha, C., Ammons, J. C., Schutte, A., & Smith, T. (2007). Cut order planning for apparel manufacturing. IIE transactions, 30(1), 79-90.

Jain, S., & Gea, H. C. (1998). Two-dimensional packing problems using genetic algorithms. Engineering with Computers, 14(3), 206-213.

Jakobs, S. (1996). On genetic algorithms for the packing of polygons. European journal of operational research, 88(1), 165-181.

Kirkpatrick, S., Gelatt, C. D., & Vecchi, M. P. (1983). Optimization by simulated annealing. science, 220(4598), 671-680.

Leung, T. W., Chan, C. K., & Troutt, M. D. (2003). Application of a mixed simulated annealing-genetic algorithm heuristic for the two-dimensional orthogonal packing problem. European Journal of Operational Research, 145(3), 530-542.

Lin, F. T., Kao, C. Y., & Hsu, C. C. (1993). Applying the genetic approach to simulated annealing in solving some NP-hard problems. IEEE Transactions on systems, man, and cybernetics, 23(6), 1752-1767.

Lin, Y. K., Yeh, C. T., & Huang, P. S. (2013). A hybrid ant-tabu algorithm for solving a multistate flow network reliability maximization problem. Applied Soft Computing, 13(8), 3529-3543.

Lodi, A., Martello, S., & Monaci, M. (2002). Two-dimensional packing problems: A survey. European journal of operational research, 141(2), 241-252.
Mahadevan, A. (1984). Optimization in computer-aided pattern packing (marking, envelopes).

Martins, T. C., & Tsuzuki, M. D. S. G. (2010). Simulated annealing applied to the irregular rotational placement of shapes over containers with fixed dimensions. Expert Systems with Applications, 37(3), 1955-1972.

Metropolis, N., Rosenbluth, A. W., Rosenbluth, M. N., Teller, A. H., & Teller, E. (1953). Equation of state calculations by fast computing machines. The journal of chemical physics, 21(6), 1087-1092.

M'Hallah, R., & Bouziri, A. (2016). Heuristics for the combined cut order planning two‐dimensional layout problem in the apparel industry. International Transactions in Operational Research, 23(1-2), 321-353.

Mundim, L. R., Andretta, M., & de Queiroz, T. A. (2017). A biased random key genetic algorithm for open dimension nesting problems using no-fit raster. Expert Systems with Applications, 81, 358-371.

Pinheiro, P. R., Amaro Júnior, B., & Saraiva, R. D. (2016). A random-key genetic algorithm for solving the nesting problem. International Journal of Computer Integrated Manufacturing, 29(11), 1159-1165.

Sha, O. P., & Kumar, R. (2000). Nesting of two-dimensional irregular parts within an irregular boundary using genetic algorithm. Journal of ship production, 16(4), 222-232.

Shalaby, M. A., & Kashkoush, M. (2013). A particle swarm optimization algorithm for a 2-D irregular strip packing problem. American Journal of Operations Research, 3(02), 268.

Taiwan Textile Federation (2017). 2017年臺灣紡織工業概況-紡拓會. Retrieved April 29, 2019, from https://www.textiles.org.tw/TTF/main/content/wHandMenuFile.ashx?file_id=1

Van Laarhoven, P. J., & Aarts, E. H. (1987). Simulated annealing. In Simulated annealing: Theory and applications (pp. 7-15). Springer, Dordrecht.

Van Laarhoven, P. J., & Aarts, E. H. (1987). Simulated annealing. In Simulated annealing: Theory and applications (pp. 7-15). Springer, Dordrecht.

Wäscher, G., Haußner, H., & Schumann, H. (2007). An improved typology of cutting and packing problems. European journal of operational research, 183(3), 1109-1130.

Whitley, D. (1994). A genetic algorithm tutorial. Statistics and computing, 4(2), 65-85.

Wong, W. K., Guo, Z. X., & Leung, S. Y. S. (2013). Optimizing cut order planning in apparel production using evolutionary strategies. Optimizing Decision Making in the Apparel Supply Chain Using Artificial Intelligence (AI), 81-105.

Wong, W. K., Wang, X. X., & Guo, Z. X. (2013). Optimizing marker planning in apparel production using evolutionary strategies and neural networks. Optimizing decision making in the apparel supply chain using artificial intelligence (AI): form production to retail. Woodhead Publishing Series in Textiles, 106-131.

史俊友, & 冯美贵. (2007). 二维不规则件优化排样的小生境遗传算法. 工程设计学报, 14(2), 170-174.
連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔