臺灣博碩士論文加值系統

裁切、堆疊與排版的問題對於業界是很重要的課題，而擁有一套優良的全自動排版系統，不但可以提升效率、精簡人力，更對於鈑金、皮革、造紙業等許多原物料成本佔很大比重的行業有著決定性的競爭力。
本研究討論之二維排版最佳化的目的，是將固定數目的不同或相同零件（piece）排列於基板（sheet）上，以基板的可排面積使用率最高或是浪費最少空間為目標。決定排版結果的優劣，一般而言可分為排列演算（Placement Algorithm）與排列次序（Permutation）兩個重要因素。排列演算的意思為零件排入基板的位置，而排列次序則是零件排入基板的順序。如果排列演算的方法符合需求，而排列次序也是正確的，則最後就有可能得到最佳解。
本研究提供新的「排列演算」法則－面積分割法，搭配零件旋轉機制與基因演算法則。將排版結果與文獻及商用軟體進行測試比較。最後結果顯示本研究的確可針對不同情況的需求，得到良好的排版結果。

The problem about cutting, packing and nesting is a very important subject to the industry. A better full-automatic nesting system, not only can raise the efficiency and simplify manpower, but also increase competitiveness. Because the raw material takes the huge cost for such kind of companies.
The objective of two-dimensional optimal nesting problem is to place the same or different pieces of the fixed quantity on the sheet in this paper. What we want to do is increase the rate of utility and decrease the waste of panel. Generally, determine the quality of the nesting results; it can briefly be divided into two factors: placement algorithm and permutation. Placement algorithm means the how to decide the positions where the pieces place into the sheet. And permutation is the placing sequence order of pieces. If the sequence of permutation is available and the placement rule also meets the demand of packing, then the exact or optimal solutions could be found.
This research provides a new placement algorithm rule ”Area-Decomposition” method. This combines the rotation function for each piece and genetic algorithm. A comparison of nesting with literature and commercial software shows the results. This research can really receive good results of nesting according to the demand of different situations.

封面內頁
簽名頁
授權書……………………………………………………...... iii
中文摘要………………………………………………...…… iv
英文摘要…………………………………………………...... v
誌謝…………………………………………………............... vi
目錄………………………………………………………...... vii
圖目錄……………………………………………………...... x
表目錄……………………………………………………...... xvi

第一章 緒論…………………………………………………. 1
1.1 研究動機……………………………………….. 2
1.2 研究目的……………………………………….. 2
1.3 研究範圍……………………………………….. 2
1.4 文獻回顧……………………………………….. 3
1.5 研究方法及論文架構………………………… 5
第二章 排版分類及影響因素.... ……………………………. 7
2.1 定義與分類…………………………………….. 7
2.2 排版之影響因素……………………………….. 14
2.3 零件之旋轉機制……………………………….. 17
第三章 創新排列演算法…………………………………… 18
3.1 傳統排列演算法介紹…………………………… 18
3.2 面積分割法…………………………………… 23
3.2.1 幾何干涉分類………………………… 23
3.2.2 範例說明……………………………… 26
第四章 基因演算法…………………………………………. 45
4.1 基因演算法之基本架構………...………….… 45
4.1.1 基本架構………………………..……….. 46
4.1.2 參數編碼與解碼類型……………….….. 47
4.1.3 染色體………………………………..… 48
4.1.4 初始族群…………………………………. 48
4.1.5 適應性函數………………………………. 49
4.1.6 運算因子…………………………………. 49
4.1.7 停止條件…………………………………. 54
4.2 基因演算法應用於排版問題之方法架構……. 55
4.2.1 排版流程…………………………………. 55
4.2.2 設定參數…………………………………. 57
4.2.3 初始族群…………………………………. 57
4.2.4 編碼方式…………………………………. 57
4.2.5 目標函數…………………………………. 58
4.2.6 複製、交配、突變……………………… 60
第五章 排版系統測試與分析……………………………….. 67
5.1 與文獻相比................................................ 67
5.1.1 條型堆積問題..................................... 67
5.1.2 裝填問題........................................... 77
5.2 族群數對排版之影響.................................. 81
5.2.1 零件不旋轉之情況…………………...... 81
5.2.2 零件可旋轉之情況…………………...... 85
5.3 與商用軟體相比較…………………………….. 88
5.3.1 零件不旋轉……………………................ 89
5.3.2 零件可旋轉……………………................ 97
第六章 結論與展望………………………………………… 105
6.1 結論…………………………………………… 105
6.2 未來展望……………………………………… 106

[1] Blaewicz, J., and Walkowiak, R.（1995）A local search approach for two-dimensional irregular cutting. OR Spektrum, 7, 93-98.
[2] Baker, B., Coffman, E., and Rivest, R.（1980）Orthogonal packing in two dimensions. SIAM Journal of Computing, 9, 846-855.
[3] Coffman, E.G., and Shor, P.W.（1990）Average-case analysis of cutting and packing in two dimensions. European Journal of Operational Research, 44, 134-144.
[4] Christofides, N., and Whitlock, C.（1977）An algorithm for two-dimensional cutting problems. Operations Research, 25, 30-44.
[5] Gu,W., Nemhauser, G.L., and Savelsbergh, M.W.P.（1995）Lifted cover inequalities for 01 integer programs I: computation, Tech. Report COC-95-02, Industrial and Systems Engineering, Georgia Institute of Technology, GA, Atlanta.
[6] Fasano, G.（1999）Cargo analytical integration in space engineering: a three dimensional packing model, in Ciriani, Gliozzi and Johnson (Eds.), Operational Research in Industry, MacMillan.
[7] 邵揮洲、陳建聲（民91）。結合啟發式與基因演算法解決不規則形船體內構件排版問題之研究。中國造船暨輪機工程學刊，1，59-69
[8] Cheng, S.K., and Rao, K.P.（2000）Large-scale nesting of irregular patterns using compact neighborhood algorithm. Department of Manufacturing Engineering Management,City University of Hong Kong, Journal of Material Processing Technology, 103, 135-140.
[9] Jacobs, S.（1996）On Genetic Algorithm for the Packing of Polygons. European Journal of Operational Research, 84, 645-661.
[10] Hooper, E., and Turton, B.（1999）A genetic algorithm for a 2D industrial packing problem. Indust.Engrg, 97, 375-378.
[11] Lui, D., and Teng, H.（1999）An improved BL-algorithm for genetic algorithms of the orthogonal packing of rectangles. European Journal of Operational Research, 112, 413-419
[12] Bruke, E.K., Kendall, G., and Whitewell, G.（2004）A new placement for the Orthogonal Stock-Cutting Problem. European Journal of Operational Research, 52(4), 655-671.
[13] Dorigo, M.（1992）Optimization, Learning and Natural Algorithms. PhD thesis, Politecnico di Milano, Italy.
[14] Kröger, B.（1995）Guillotinable bin packing: A genetic approach. European Journal of Operational Research, 84, 645-661.
[15] Melanie, M., and Davis, L.V.（1998）Handbook of Genetic algorithm. Engineering Applications of Artificial Intelligence, 100, 325-330.
[16] Tay, E.H., Chong, T.Y., and Lee F.C. (2002)Pattern nesting on irregular-shaped stock using genetic algorithms. Engineering Applications of Artificial Intelligence, 15, 551-558.
[17] 吳泰熙、吳奕樺、張欽智（民95）。以基因演算法求解單原片方形物件排列問題。科學與工程技術期刊，3，75-83。
[18] Syswerda, G. (1989)Uniform crossover in genetic algorithms, Proceedings of the third international conference on genetic algorithms and their applications, San Mateo, CA: Morgan Kaufmann, 2-9.
[19] Bortfeldt, A., Gehring, H., and Mack, D.（2003）A parallel tabu search algorithm for solving the container loading problem. Parallel Computing, 29, 641–662.
[20] Alvarez-Valdes, R., Parreno, F. , and Tamarit, J.M.（2007）A tabu search algorithm for a two-dimensional non-guillotine cutting problem. European Journal of Operational Research, 183, 1167–1182.
[21] Alvarez-Valdes, R., Parreno, F., and Tamarit, J.M.（2002）A tabu search algorithm for large-scale guillotine (un)constrained two-dimensional cutting problems .Computers & Operations Research, 29, 925-947.
[22] Alvarez-Valdes, R., Parreno, F., and Tamarit, J.M.（2005）A tabu search algorithm for the pallet loading problem. Department of Statistics and Operations Research, 27, 43-61.
[23] Zhang, D.F., and Deng, A.S.（2005）An effective hybrid algorithm for the problem of packing circles into a larger containing circle. Computers & Operations Research, 32, 1941–1951.
[24] Lodi, A., Martello S., and Vigo D.（1999）Approximation algorithms for the oriented two-dimensional bin packing problem. European Journal of Operational Research, 112, 158-166.
[25] Burke E., and Kendall, G.（1999）Comparison of Meta-Heuristic Algorithms for Clustering Rectangles. computers and industrial engineering, 37,383-386.
[26] Lodi, A., Martello, S., and Vigo, D.（2002）Heuristic algorithms for the three-dimensional bin packing problem. European Journal of Operational Research, 141, 410–420.
[27] Marques, V. M. M., Bispo, C. F.G., and Swntiero, J. J. S.（1991）A system for compaction of two-dimensional irregular shapes based on simulated annealing,IECON-91 (IEEE), 1911-1916.
[28] Faina, L.（1999）An application of simulated annealing to the cutting stock problem, European Journal of Operational Research 114 542-556.
[29] Leung, T.W., Chan, C.K., and 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, 530-542.
[30] Leung, T.W., Yung, C.H., and Troutt, M.D.(2001)Applications of genetic search and simulated annealing to the two-dimensional non-guillotine cutting stock problem. Computers and industrial engineering, 40, 201-214.
[31] Dagli, C.H., and Hajakbari, A.（1990）Simulated annealing approach for solving stock cutting problem, Proceedings of IEEE International Conference on Systems, Man and Cybernetics, 221-223.
[32] Theodoracatos, V.E. and Grimsley, J. L.（1995）The optimal packing of arbitrarily-shaped polygons using simulated annealing an polynomial-time cooling schedules. Methods in Applied Mechanics and Engineering, 125, 53-70.
[33] 黃玟錫（民90）。不規則物件排列問題解法之研究。,大葉大學工業工程學系碩士論文，未出版，彰化縣。
[34] Hopper, E., and Turton, B.C.H. (2001)An Empirical Investigation of Meta-heuristic and Heuristic Algorithms for a 2D Packing Problem. European Journal of Operational Research, 128(1), 34-57.
[35] Ramesh, B. A., and Ramesh, B. N. (2001) A generic approach for nesting of 2-D parts in 2-D sheets using genetic and heuristic algorithms. Computer-Aided Design, 33, 879-891.
[36] Wu, T.H., Chen, J.F., Low, C., and Tang, P.T.（2003）Nesting of two-dimensional parts in multiple plates using hybrid algorithm. International Journal of Production Research, 41(16), 3883-3990.
[37] Gomes, A. M., and Oliveira, J. F.（2006）Solving Irregular Strip Packing problems by hybridising simulated annealing and linear programming. European Journal of Operational Research, 171, 811–829.
[38] Soke, A., and Bingul, Z.（2006）Hybrid genetic algorithm and simulated annealing for two-dimensional non-guillotine rectangular packing problems. Engineering Applications of Artificial Intelligence, 19, 557–567.
[39] Zhang, D., Kang, Y., and Deng, A.(2006) A new heuristic recursive algorithm for the strip rectangular packing problem. Computers and Operations Research, 33, 2209-2217.
[40] Huang, W., Chen, D., and Xu, R.（2007）A new heuristic algorithm for rectangle packing. Computers and Operations Research, 34, 3270–3280.
[41] Cui, Y.（2007）Exact algorithm for generating two-segment cutting patterns of punched strips. Applied Mathematical Modeling, 31, 1865–1873.
[42] Alves, C., Vale’rio, J.M., Carvalho, D.（2007）Accelerating column generation for variable sized bin-packing problems. European Journal of Operational Research, 183, 1333–1352
[43] Gomes, A. M., and Oliveira, J. F.（2002）A 2-exchange heuristic for nesting problems. European Journal of Operational Research, 141, 359–370.
[44] Wu, Y.L., Huang, W., Lau, S., Wong, C.K., and Young, G.H.（2002）An Effective Quasi-Human Based Heuristic for Solving Rectangle Packing Problem. European Journal of Operational Research, 141, 341–358.
[45] Ma, H., Cannon, D.J., and Kumara, S.R.T.（1995）A scheme integrating neural networks for real-time robotic collision detection, Proceedings of IEEE International Conference on Robotics and Automation. Nagoya, Japan.
[46] 李志宏（民93）。平面規劃最佳化問題研究。中原大學電子工程學系博士論文，未出版，中壢市。
[47] 王誌謙（民94）。AutoCAD系統於二維排版問題最佳化之研究。國立台灣海洋大學系統工程暨造船學系研究所碩士論文，未出版，基隆市。
[48] 李文成（民93）。直線逼近與快速定位法之不規則圖形自動排版系統。中華大學科技管理研究所碩士論文未出版，新竹市。
[49] 辛宜芳（民91）。以CAD為平台之自動排版系統使用基因演算法。中華大學科技管理研究所碩士論文，未出版，新竹市。
[50] Dyckhoff, H.（1990）A typology of cutting and packing problems. European Journal of Operational Research, 44, 145-159.
[51] WÄascher, G., Hauβner, H., and Schumann, H.（2004）An improved typology of cutting and packing problems. European Journal of Operational Research, 183, 1109-1130.
[52] de la Vega, W.F., and Zissimopoulos, V.（1998）An approximation scheme for strip packing of rectangles with bounded dimensions. Discrete Applied Mathematics,82, 93-101.
[53] Yeung, L.H.W., and Tang, W.K.S.（2004）Strip-packing using hybrid genetic approach. Engineering Applications of Artificial Intelligence, 17, 169–177.
[54] Bortfeldt, A.（2006）A genetic algorithm for the two-dimensional strip packing problem with rectangular pieces. European Journal of Operational Research, 172, 814–837.
[55] Zhang, D.F., Chen, S.D., and Liu, Y.J.（2007）An Improved Heuristic Recursive Strategy Based on Genetic Algorithm for the Strip Rectangular Packing Problem. ACTA AUTOMATICA SINICA ,33, 911-916.
[56] Cintra, G.F., Miyazawa, F.K., Wakabayashi, Y., and Xavier, E.C.（2008）Algorithms for two-dimensional cutting stock and strip packing problems using dynamic programming and column generation. European Journal of Operational Research, 191, 61–85.
[57] Milenkovic, V.J.（2000）Densest Translational Lattice Packing of Non-Convex Polygons (extended abstract). In Symposium on Computational Geometry, 280–289.
[58] Lee, C.H., Fu, W.Y., and Chang, C.C.（2002）An efficient hierarchical approach for general floorplan area minimization. in Proc. IEEE Asia-Pacific conference on Circuits and Systems, 2, 347-352.
[59] Grinde, R.B., and Cavalier, T.M.（1995）A new algorithm for the minimal-area convex enclosure problem. European Journal of Operational Research, 84, 522-538.
[60] Vassiliadis, V.S.（2005）Two-dimensional stock cutting and rectangle packing: binary tree model representation for local search optimization methods. Journal of Food Engineering, 70 ,257–268.
[61] Arenales, M., and Morabito, R.（1995）An AND/OR-graph approach to the solution of two-dimensional non-guillotine cutting problems. European Journal of Operational Research , 84, 599-617.
[62] Christofides, N., and Hadjiconstantinou, E.（1995）An exact algorithm for orthogonal 2-D cutting problems using guillotine cuts. European Journal of Operational Research ,83 ,21-38.
[63] Baldacci, R., and Boschetti, M.A.（2007）A cutting-plane approach for the two-dimensional orthogonal non-guillotine cutting problem. European Journal of Operational Research, 183, 1136–1149.
[64] Cui, Y., Yang, Y., Cheng, X., and Song, P.（2008）A recursive branch-and-bound algorithm for the rectangular guillotine strip packing problem. Computers & Operations Research, 35, 1281–1291.
[65] Beasley, J.E.（1985）Algorithms for unconstrained two-dimensional guillotine cutting. Journal of Operational Research Society, 36, 297-306.
[66] Xavier, E.C., and Miyazawa, F.K.（2008）A one-dimensional bin packing problem with shelf divisions. Discrete Applied Mathematics, 156, 1083–1096.
[67] Hayeka, J.E.I., Moukrima, A., and Negreb, S.（2008）New resolution algorithm and pretreatments for the two-dimensional bin-packing problem. Computers & Operations Research, 35, 3184 – 3201.
[68] Loh, K.H., and EdwardWasil, B.G.（2008）Solving the one-dimensional bin packing problem with a weight annealing heuristic. Computers & Operations Research, 35 ,2283 – 2291.
[69] Bansal, N., and Sviridenko, M.（2007）.Two-dimensional bin packing with one-dimensional resource augmentation. Discrete Optimization, 4, 143–153.
[70] 許冠文（民94）。遺傳演算法和啟發式裝箱演算法為基之單一容器裝填最佳化方法。國立台灣大學工業工程研究所碩士論文，未出版，台北市。
[71] Lodi, A., Martello, S., and Vigo, D.（1999）Heuristic and meta-heuristic approaches for a class of two-dimensional bin packing problems. INFORMS J. on Computer, 11, 345.
[72] Coffman, E.G., Garey, M.R., and Johnson, D.S. (1984)An approximation algorithms for bin packing: an update survey, in G. Ausiello et al. Approximation Algorithms for Computer System Design, Wien, 49-106.
[73] Konga, M., Tiana, P., and Kao, Y.（2008）A new ant colony optimization algorithm for the multidimensional Knapsack problem. Computers & Operations Research, 35, 2672 – 2683.
[74] Egeblad, J., and Pisinger, D.（2007）Heuristic approaches for the two and three-dimensional knapsack packing problem. Computers & Operations Research
[75] Caprara, A., and Monaci, M.（2004）On the two-dimensional Knapsack Problem. Operations Research Letters, 32,5–14.
[76] Lin, F.T.（2008）. Solving the knapsack problem with imprecise weight coefficients using genetic algorithms. European Journal of Operational Research, 185, 133–145.
[77] Absi, N., and Kedad-Sidhoum, S.（2008）The multi-item capacitated lot-sizing problem with setup times and shortage costs. European Journal of Operational Research, 185, 1351–1374.
[78] Hadjiconstantinou ,E., and Christofides, N.（1995）An exact algorithm for general, orthogonal, two-dimensional knapsack problems. European Journal of Operational Research, 83, 39-56.
[79] Fekete, S.P. and Schepers, J.（1997）A New Exact Algorithm for General Orthogonal D-Dimensional Knapsack Problems. Springer Lecture Notes in Computer Science, 1284, 144-156.
[80] Cui, Y.（2005）A cutting stock problem and its solution in the manufacturing industry of large electric generators. Computers & Operations Research, 32, 1709–1721.
[81] Karelahti, J.（2002）Solving the cutting stock problem in the steel industry. Department of Engineering Physics and Mathematics, Helsinki University of Technology, Espoo, 25.11.
[82] Gilmore, P.C., and Gomory, R.E.（1965）Multistage cutting stock problems of two and more dimensions, Operational Research, I3, 94-120.
[83] Vanderbeck, F.（2001）A nested decomposition approach to a three-stage, two-dimensional cutting-stock problem. Management Science, 47, 864-869.
[84] Cung, V.D., Hifi, M., and Cun, B.（2000）Constrained two-dimensional cutting stock problems a best-first branch-and-bound algorithm. International Transactions in Operational Research, 7, 185-210.
[85] Beasley, J.E., and Mingozzi, A. （1996）A new formulation for the two-dimensional orthogonal cutting stock problem, Tech. report, University of Bologna, Italy.
[86] Dagli, C.H., and Tatoglu, M.Y.（1987）An approach to two dimensional cutting stock problems. International Journal of Production Research, 25, 175-190.
[87] Daniels, J.J. and Ghandforoush, P.（1990）An improved algorithm for the non-guillotine constrained cutting stock problem. Journal of the Operational Research Society, 41, 141-149.
[88] Beasley, J.E., and Mingozzi, A.（1996）A new formulation for the two-dimensional orthogonal cutting stock problem, Tech. report, University of Bologna, Italy.
[89] Martins, G.H.A., and Dell, R.F.（1996）Solving the pallet loading problem. European Journal of Operational Research , 184, 429–440.
[90] Pureza, V. and Morabito, R.（2006）Some experiments with a simple tabu search algorithm for the manufacturer’s pallet loading problem. Computers & Operations Research, 33 804–819.
[91] Martins, G.H.A., and Dell, R.F.（2007）The minimum size instance of a Pallet Loading Problem equivalence class. European Journal of Operational Research, 179, 17–26.
[92] Morabito, R., and Morales, S.（1998）A simple and effective recursive procedure for the manufacturer's pallet loading problem. European Journal of Operational Research, 49, 819-828.
[93] Bortfeldt, A., and Gehring, H.（2001）A hybrid genetic algorithm for the container loading problem. European Journal of Operational Research, 131, 143-161.
[94] Chen, C.S., Lee, S.M., and Shen, Q.S.（1995）An analytical model for the container loading problem. European Journal of Operational Research, 80（1）,68-76.
[95] Dowsland, K.A.（1987）An exact algorithm for the pallet loading. European Journal of Operational Research, 31, 78-84.