臺灣博碩士論文加值系統

不規則物件的切割與排列問題在工業界是很常見的的一個問題，諸如製鞋業、皮革業、鋼鐵業、成衣業等，雖各個工業的材料成本不相同，不過其物料成本均在總成本中佔有相當大的比例。而找到一個有效的排列方法以降低生產成本獲得較高利潤是各企業極力追求的目標之一。
本研究主要目的在於建立一模擬退火演算模式來求解不規則物件的排列問題，配合三個有效的移步法則，並依據各物件的不同特性與物料原片是否為一均質規則原片等相關問題，提出傳統型不規則物件排列與非均質及不規則外型原片的排列兩種不同的解題模式，在合適的起始溫度、馬可夫鍊、冷卻率與目標函數值的設定下，以求在最短的時間內找到在最理想的排列結果，希望本研究所建構之模擬退火演算模式，可提供工業界處理此類問題的參考，達到節省營運成本之企業目標。

Packing and cutting irregular objects are tasks frequently encountered by the industries, such as shoes making, textile, steel, clothing, etc. The greater saving in the wastage of materials of the above-mentioned industries, the lower the total production cost. Lots of research in the literature has been devoted to developing algorithms to find the optimal / near optimal way of cutting and packing.
In this study, we propose a simulated annealing (SA) approach for packing patterns with irregular shapes in a rectangular sheet. In addition, the sheet accommodating irregular shapes is allowed to have non-rectangular shape and non-uniform quality inside. Several parameters controlling the mechanism of SA are also tested through some experiments to accelerate the convergence of the SA algorithm.

封面內頁
簽名頁
授權書1 iii
授權書2 iv
中文摘要 v
英文摘要 vi
誌謝 vii
目錄 viii
圖目錄 xi
表目錄 xii
第一章 緒論 1
1.1 研究背景與動機 1
1.2 研究目的 2
1.3 研究假設 3
1.4 研究方法與架構 3
第二章 文獻探討 7
2.1 物件分類與排列 7
2.2 規則方形物件的排列問題 9
2.3 不規則形狀物件之排列問題 10
2.3.1 圓形物件之排列問題 10
2.3.2 不規則物件排列問題 10
第三章 不規則物件排列問題之求解法 13
3.1 問題定義 13
3.1.1 傳統型不規則物件排列問題 13
3.1.2 非均質及不規則外型原片之不規則物件排列問題 13
3.2 傳統型不規則物件之SA演算法 14
3.2.1 預處理 16
3.2.2 起始解 22
3.2.3 使用率 24
3.2.4 目標函數 24
3.2.5 移步之種類與選取方式 25
3.2.6 退火程序 31
3.2.7 終止條件 33
3.3 非均質及不規則外型原片排列問題之SA演算法 34
3.3.1 預處理 34
3.3.2 起始解 35
3.3.3 使用率 37
3.3.4 目標函數 37
3.3.5 移步之種類與選取方式 39
3.3.6 退火程序 39
3.3.7 終止條件 39
第四章 演算結果與分析 40
4.1 實驗參數說明 40
4.1.1 起始溫度、冷卻率與馬可夫鍊 40
4.1.2 馬可夫鍊改善水準 45
4.1.3 目標函數權重值 46
4.2 實例說明與驗證 49
4.3 傳統型不規則物件排列問題之SA演算結果 51
4.4 非均質及不規則原片排列問題之SA演算結果 55
第五章 結論與建議 61
5.1 結論 61
5.2 建議 61
參考文獻 63
附錄一 70
附錄二 71

[1] 吳泰熙、駱景堯、林東養,「多尺寸方形排列問題啟發式解法之研究」,工業工程學刊,第17卷, 75-85, (2000)
[2] 林東養,「不規則物件排列問題解法之研究」,大葉大學工業工程研究所碩士論文, (1998)
[3] 徐德興,「利用模擬退火演算法求解不規則物件排列及切割問題」,大葉大學工業工程研究所碩士論文,(2000)
[4] Albano, A. and G. Sapuppo, “Optimal allocation of two- dimensional irregular shapes using heuristic search methods”, IEEE Transactions on System, Man, and Cybernetics, 10, 242- 248, (1980)
[5] Beasley, J. E., “Algorithms for unconstrained two-dimensional guillotine cutting”, Journal of the Operational Research Society, 36, 297-306, (1985)
[6] Biro M., and E. Borors, “Network flows and non-guillotine cutting patterns”, European Journal of Operational Research, 16, 215-221, (1984)
[7] Bruce W. L., J. A. George, Jennifer M. George, “Packing different-sized circles into a rectangular container”, European Journal of Operational Research, 84, 693-712, (1995)
[8] Christofides, N. and C. Whitlock, “An algorithms for two dimensional cutting problems”, Operations Research, 25, 30-44, (1977)
[9] Christoph N. and G. Scheithauer, “Tighter relaxations for the cutting stock problem”, European Journal of Operational Research,654-663,(1999)
[10] Dagli, C. H., “Neural network in manufacturing: Possible impacts on cutting stock problems”, IEEE Transactions on Systems, Man, and Cybernetics, 531-537, (1990)
[11] Dagli, C. H. and A. Hajakbari, “Simulated annealing approach for solving stock cutting problem”, IEEE Transactions on Systems, Man, and Cybernetics, 221-223, (1990)
[12] Dagli, C. H. and M. Y. Tatoglu, “An approach to two- dimensional cutting stock problem”, International Journal Production Research, 25, 175-190, (1987)
[13] Dowsland, K. A. and W. Dowsland, “Packing problem”, European Journal of Operational Research, 56, 2-14, (1992)
[14] Fuh-Hwa F. L. and C-J. Hsiao, “A three-dimensional pallet loading method for single-size boxes” Journal of the Operational Research Society, 48, 726-735, (1997)
[15] G-C H., MSc and S-J Na, Dr Ing, “Two-stage approach for nesting in two-dimensional cutting problems using neural network and simulated annealing”, Proceeding of Institution of Mechanical Engineers, Journal of Engineering Manufacture, 210, 509-519, (1996)
[16] Gilmore, P. C. and R. E. Gomory, “A linear programming approach to the cutting stock problem (Part 1)”, Operations Research, 9, 849-855, (1961)
[17] Gilmore, P. C. and R. E. Gomory, “A linear programming approach to the cutting stock problem (Part 2)”, Operations Research, 11, 863-888, (1963)
[18] Gilmore, P. C. and R. E. Gomory, “Multistage cutting problems of two and more dimensions”, Operations Research, 13, 94-120, (1965)
[19] Gilmore, P. C. and R. E. Gomory, “The theory and computation of knapsack functions”, Operations Research, 14, 1045-1074, (1966)
[20] Grinde, R. B. and T. M. Cavalier, “A new algorithm for the minimal-area convex enclosure problem”, European Journal of Operational Research, 84, 522-538, (1995)
[21] Grinde, R. B. and T. M. Cavalier, “Containment of a single polygon using mathematical programming”, European Journal of Operational Research, 92, 386-286, (1996)
[22] Goulimis C., “Optimal solution for the cutting stock problem”, European Journal of Operational Research, 44, 197-208, (1990)
[23] Henry L. and W. N. Waggenspack, Jr., “Practic & experience nesting of two-dimensional irregular parts using a shape reasoning heuristic” Computer-Aided Design, 29, 221-238, (1997)
[24] Hifi, M., "The DH/KD, “Algorithm: a hybrid approach for unconstrained two -dimensional cutting problems”, European Journal of Operational Research, 97, 41-52, (1997)
[25] Hyun-Chan Lee, “Determining in linear time the minimum area convex hull of two polygons”, IIE Transactions, 20, 338-345, (1988)
[26] Ismail, H. S. and J. L. Sanders, “Two-dimensional cutting stock problem research: A review and a new rectangular layout algorithm “, Journal of Manufacturing Systems, 1, 169-182, (1982)
[27] Ismail, H. S. and K. K. B. Hon, “The nesting of 2-dimensional shapes using genetic algorithm”, Proceedings of the Institution of Mechanical Engineers Part B-Journal of Engineering Manufacture, 209, 115-124, (1995)
[28] J. Blazewicz, P. Hawryluk and R. Walkowiak, “Using a tabu search approach for solving the two-dimensional irregular cutting problem”, Annals of Operations Research, 41, 313-325, (1993)
[29] Jacobs, S., “On genetic algorithm for the packing of polygons”, European Journal of Operational Research, 88,165-181, (1996)
[30] Jimmy W.M., K. K. Lai, Chan, “Developing a simulated annealing algorithm for the cutting stock problem”, Computers Industrial Engineer, 32, 115-127, (1997)
[31] Kirkpatrick, S., C.D. Gelatt. Tr., and M.P. Vecchi, “Optimization by simulated annealing”, Sci., 22, 671-680(1983)
[32] Kroger, B., “Guillotineable bin packing: A genetic approach”, European Journal of Operational Research, 84, 645-661, (1996)
[33] Lai, K. K. and J. Xue, “Container packing in a multi-customer delivering operation”, Computers Industrial Engineer, 35, 323- 326, (1998)
[34] Lamousin H. J., W. N. Waggenspack, Jr. and G. T. Dobson, “Nesting of complex 2-D parts within irregular boundaries”, Journal of Manufacturing Science and Engineering, 118, 615- 622, (1996)
[35] Lutfiyta, H. and B. Mcmillin, “Composite stock cutting through simulated annealing”, Mathematical Computing and Modeling, 16, 57-74, (1992)
[36] Morabito, R. N. and M. N. Arenales, “An and-or-graph approach for two-dimensional cutting stock problems”, European Journal of Operational Research, 58, 263-271, (1992)
[37] Richard V., “Random search in the one-dimensional cutting stock problem”, European Journal of Operational Research, 95, 191-200, (1996)
[38] Sarker, B. R., “An optimal solution for one-dimensional slitting problems: A dynamic programming approach”, Journal of the Operational Research Society, 39, 749-755, (1988)
[39] Silvano M. and D. Vigo, “Exact solution of the two-dimensional finite bin packing problem”, Management Science, 44, 388-399, (1998)
[40] S. K. Cheng and K. P. Rao, “Large-scale nesting of irregular patterns using compact neighborhood algorithm”, Materials Processing Technology, 103, 135-140, (2000)
[41] Theodoracatos, V. E. and J. L. Grimsley, “The optimal packing of arbitrarily-shaped polygons using simulated annealing and polynomial-time cooling schedules”, Journal of the Operational Research Society, 125, 53-70, (1995)
[42] Vassilios E. T. and J. L. Grimsley, “The optimal packing of arbitrarily-shaped polygons using simulated annealing and polynomial-time cooling schedules”, Computer Methods in Applied Mechanics and Engineering, 125, 53-70, (1995)
[43] Victor P., M. Sepulveda, M. Solar and A. Gomes, “Solution for the constrained guillotine cutting problem by simulated annealing”, Computers Operations Research, 25, 37-47, (1998)
[44] Wascher, G., “An LP based approach to cutting stock problem with multiple objectives”, European Journal of Operational Research, 84, 522-538, (1995)
[45] Yu G.S., M.V. Novozhilova and A.V. Kartashov, “Mathematical model and method of searching for a local extreme for the non-convex oriented polygons allocation problem”, European Journal of Operational Research, 92, 193-210, (1996)
[46] Yu G.S. and V.N. Patsuk, “A method of optimal lattice packing of congruent oriented polygons in the plane”, European Journal of Operational Research, 124, 204-216, (2000)
[47] Y.K.D.V. Prasad, S. Somasundaram and K.P. Rao, “A sliding algorithm for optimal nesting of arbitrarily shaped sheet metal blanks”, International Journal of Production Research, 33, 1505-1520, (1995)