A Particle Swarm Optimization Algorithm for a 2-D Irregular Strip Packing Problem
Affiliation(s)
Mechanical Design and Production Department, Faculty of Engineering, Cairo University, Giza, Egypt.
Mechanical Design and Production Department, Faculty of Engineering, Cairo University, Giza, Egypt.
ABSTRACT
Two-Dimensional
Irregular Strip Packing Problem is a classical cutting/packing problem. The
problem is to assign, a set of 2-D irregular-shaped items to a rectangular
sheet. The width of the sheet is fixed, while its length is extendable and has
to be minimized. A sequence-based approach is developed and tested. The
approach involves two phases; optimization phase and placement phase. The
optimization phase searches for the packing sequence that would lead to an
optimal (or best) solution when translated to an actual pattern through the
placement phase. A Particle Swarm Optimization algorithm is applied in this
optimization phase. Regarding the placement phase, a combined algorithm based
on traditional placement methods is developed. Competitive results are
obtained, where the best solutions are found to be better than, or at least
equal to, the best known solutions for 10 out of 31 benchmark data sets. A
Statistical Design of Experiments and a random generator of test problems are
also used to characterize the performance of the entire algorithm.
Cite this paper
M. Shalaby and M. Kashkoush, "A Particle Swarm Optimization Algorithm for a 2-D Irregular Strip Packing Problem," American Journal of Operations Research, Vol. 3 No. 2, 2013, pp. 268-278. doi: 10.4236/ajor.2013.32024.
M. Shalaby and M. Kashkoush, "A Particle Swarm Optimization Algorithm for a 2-D Irregular Strip Packing Problem," American Journal of Operations Research, Vol. 3 No. 2, 2013, pp. 268-278. doi: 10.4236/ajor.2013.32024.
References
[1] H. Dyckhoff, “A Typology of Cutting and Packing Problems,” European Journal of Operational Research, Vol. 44, No. 2, 1990, pp. 145-159. doi:10.1016/0377-2217(90)90350-K [2] G. W?scher, H. Hau?ner, and H. Schumann, “An Improved Typology of Cutting and Packing Problems,” European Journal of Operational Research, Vol. 183, No. 3, 2007, pp. 1109-1130. doi:10.1016/j.ejor.2005.12.047 [3] R. J. Fowler, M. S. Paterson and S. L. Tanimoto, “Optimal Packing and Covering in the Plane Are NP-Complete,” Information Processing Letters, Vol. 12, No. 3, 1981, pp. 133-137. doi:10.1016/0020-0190(81)90111-3 [4] A. R. Babu and N. R. Babu, “A Generic Approach for Nesting of 2-D Parts in 2-D Sheets Using Genetic and Heuristic Algorithms,” Computer-Aided Design, Vol. 33, No. 12, 2001, pp. 879-891. doi:10.1016/S0010-4485(00)00112-3 [5] A. D. Fischer and C. H. Dagli, “Employing Subgroup Evolution for Irregular-Shape Nesting,” Journal of Intelligent Manufacturing, Vol. 15, No. 2, 2004, pp. 187-199. doi:10.1023/B:JIMS.0000018032.38317.f3 [6] S. Takahara, Y. Kusumoto and S. Miyamoto, “Solution for Textile Nesting Problems Using Adaptive Meta-Heuristics and Grouping,” Soft Computing, Vol. 7, No. 3, 2003, pp. 154-159. doi:10.1007/s00500-002-0203-9 [7] E. Burke, R. Hellier, G. Kendall and G. Whitwell, “A New Bottom-Left-Fill Heuristic Algorithm for the Two Dimensional Irregular Packing Problem,” Operations Research, Vol. 54, No. 3, 2006, pp. 587-601. doi:10.1287/opre.1060.0293 [8] J. A. Bennell and K. A. Dowsland, “Hybridising Tabu Search with Optimisation Techniques for Irregular Stock Cutting,” Management Science, Vol. 47, No. 8, 2001, pp. 1160-1172. doi:10.1287/mnsc.47.8.1160.10230 [9] A. M. Gomes and J. F. Oliveira, “Solving Irregular Strip Packing Problems by Hybridising Simulated Annealing and Linear Programming,” European Journal of Operational Research, Vol. 171, No. 3, 2006, pp. 811-829. doi:10.1016/j.ejor.2004.09.008 [10] T. Imamichi, M. Yagiura and H. Nagamochi, “An Iterated Local Search Algorithm Based on Nonlinear Programming for the Irregular Strip Packing Problem,” Discrete Optimization, Vol. 6, No. 4, 2009, pp. 345-361. doi:10.1016/j.disopt.2009.04.002 [11] S. Umetani, M. Yagiura, S. Imahori, T. Imamichi, K. Nonobe and T. Ibaraki, “Solving the Irregular Strip Packing Problem Via Guided Local Search for Overlap Minimization,” International Transactions in Operations Research, Vol. 16, No. 6, 2009, pp. 661-683. doi:10.1111/j.1475-3995.2009.00707.x [12] R. B. Grinde and K. Daniels, “Solving an Apparel Trim Placement Problem Using a Maximum Cover Problem Approach,” IIE Transactions, Vol. 31, No. 8, 1999, pp. 763-769. doi:10.1080/07408179908969875 [13] M. Fischetti and I. Luzzi, “Mixed-Integer Programming Models for the Nesting Problem,” Journal of Heuristic, Vol. 15, No. 3, 2009, pp. 201-226. doi:10.1007/s10732-008-9088-9 [14] M. A. Carravilla, C. Ribeiro and J. F. Oliveira, “Solving Nesting Problems with Non-Convex Polygons by Constraint Logic Programming,” International Transactions in Operational Research, Vol. 10, No. 6, 2003, pp. 651- 663. doi:10.1111/1475-3995.00434 [15] J. F. Oliveira, A. M. Gomes and J. S. Ferreira, “TOPOS— A New Constructive Algorithm for Nesting Problems,” OR-Spektrum, Vol. 22, No. 2, 2000, pp. 263-284. doi:10.1007/s002910050105 [16] J. A. Bennell and X. Song, “A Beam Search Implementation for the Irregular Shape Packing Problem,” Journal of Heuristic, Vol. 16, No. 2, 2010, pp. 167-188. doi:10.1007/s10732-008-9095-x [17] S. Jain and H. C. Gea, “Two-Dimensional Packing Problems Using Genetic Algorithms,” Engineering with Computers, Vol. 14, No. 3, 1998, pp. 206-213. doi:10.1007/BF01215974 [18] M. Hifi and R. M’Hallah, “A Hybrid Algorithm for the Two-Dimensional Layout Problem: The Cases of Regular and Irregular Shapes,” International Transactions in Operational Research, Vol. 10, No. 3, 2003, pp. 195-216. doi:10.1111/1475-3995.00404 [19] S. Jakobs, “On Genetic Algorithms for the Packing of Polygons,” European Journal of Operational Research, Vol. 88, No. 1, 1996, pp. 165-181. doi:10.1016/0377-2217(94)00166-9 [20] H.-Y. Liu and Y.-J. He, “Algorithm for 2D IrregularShaped Nesting Problem Based on the NFP Algorithm and Lowest-Gravity-Center Principle,” Journal of Zhejiang University, Science A, Vol. 7, No. 4, 2006, pp. 570- 576. doi:10.1631/jzus.2006.A0570 [21] J. F. Oliveira and J. S. Ferreira, “Algorithms for Nesting Problems,” R. V. V. Vidal, Ed., Applied Simulated Annealing, Lecture Notes in Economics and Mathematical Systems, Vol. 396, Springer-Verlag, Berlin, 1993, pp. 255-274. [22] G. C. Han and S. J. Na, “Two-Stage Approach for Nesting in Two-Dimensional Cutting Problems Using Neural Network and Simulated Annealing,” Proceedings of the Institute of Mechanical Engineers, Part B, Journal of Engineering Manufacture, Vol. 210, No. B6, 1996, pp. 509- 519. [23] R. Heckmann and T. Lengauer, “Computing Closely Matching Upper and Lower Bounds on Textile Nesting Problems,” European Journal of Operational Research, Vol. 108, No. 3, 1998, pp. 473-489. doi:10.1016/S0377-2217(97)00049-0 [24] J. Blazewicz, P. Hawryluk and R. Walkowiak, “Using a Tabu Search Approach for Solving the Two-Dimensional Irregular Cutting Problem,” Annals of Operations Research, Vol. 41, No. 4, 1993, pp. 313-325. doi:10.1007/BF02022998 [25] J. Kennedy and R. C. Eberhart, “Particle Swarm Optimization,” Proceedings of IEEE International Conference on Neural Networks, Piscataway, 27 November-1 December 1995, pp. 1942-1948. doi:10.1109/ICNN.1995.488968 [26] J. A. Bennell and J. F. Oliveira, “The Geometry of Nesting Problems: A Tutorial,” European Journal of Operational Research, Vol. 184, No. 2, 2008, pp. 397-415. doi:10.1016/j.ejor.2006.11.038 [27] M. Konopasek, “Mathematical Treatments of Some Apparel Marking and Cutting Problems,” U.S. Department of Commerce, Washington DC, 1981. [28] E. Hopper, “Two-Dimensional Packing Utilising Evolutionary Algorithms and Other Meta Heuristic Methods,” Ph.D. Thesis, Cardiff University, Cardiff, 2000. [29] C. Blum and D. Merkle, “Swarm Intelligence: Introduction and Applications,” Springer-Verlag, Berlin, 2008. doi:10.1007/978-3-540-74089-6 [30] M. F. Tasgetiren, Y. C. Liang, M. Sevkli and G. Gencyilmaz, “Particle Swarm Optimization Algorithm for Makespan and Maximum Lateness Minimization in Permutation Flowshop Sequencing Problem,” Proceedings of the Fourth International Symposium on Intelligent Manufacturing Systems, Sakarya, 6-8 September 2004, pp. 431- 441. [31] J. Egeblad, B. K. Nielsen and A. Odgaard, “Fast Neighborhood Search for Two and Three-Dimensional Nesting Problems,” European Journal of Operational Research, Vol. 183, No. 3, 2007, pp. 1249-1266. doi:10.1016/j.ejor.2005.11.063
[1] H. Dyckhoff, “A Typology of Cutting and Packing Problems,” European Journal of Operational Research, Vol. 44, No. 2, 1990, pp. 145-159. doi:10.1016/0377-2217(90)90350-K [2] G. W?scher, H. Hau?ner, and H. Schumann, “An Improved Typology of Cutting and Packing Problems,” European Journal of Operational Research, Vol. 183, No. 3, 2007, pp. 1109-1130. doi:10.1016/j.ejor.2005.12.047 [3] R. J. Fowler, M. S. Paterson and S. L. Tanimoto, “Optimal Packing and Covering in the Plane Are NP-Complete,” Information Processing Letters, Vol. 12, No. 3, 1981, pp. 133-137. doi:10.1016/0020-0190(81)90111-3 [4] A. R. Babu and N. R. Babu, “A Generic Approach for Nesting of 2-D Parts in 2-D Sheets Using Genetic and Heuristic Algorithms,” Computer-Aided Design, Vol. 33, No. 12, 2001, pp. 879-891. doi:10.1016/S0010-4485(00)00112-3 [5] A. D. Fischer and C. H. Dagli, “Employing Subgroup Evolution for Irregular-Shape Nesting,” Journal of Intelligent Manufacturing, Vol. 15, No. 2, 2004, pp. 187-199. doi:10.1023/B:JIMS.0000018032.38317.f3 [6] S. Takahara, Y. Kusumoto and S. Miyamoto, “Solution for Textile Nesting Problems Using Adaptive Meta-Heuristics and Grouping,” Soft Computing, Vol. 7, No. 3, 2003, pp. 154-159. doi:10.1007/s00500-002-0203-9 [7] E. Burke, R. Hellier, G. Kendall and G. Whitwell, “A New Bottom-Left-Fill Heuristic Algorithm for the Two Dimensional Irregular Packing Problem,” Operations Research, Vol. 54, No. 3, 2006, pp. 587-601. doi:10.1287/opre.1060.0293 [8] J. A. Bennell and K. A. Dowsland, “Hybridising Tabu Search with Optimisation Techniques for Irregular Stock Cutting,” Management Science, Vol. 47, No. 8, 2001, pp. 1160-1172. doi:10.1287/mnsc.47.8.1160.10230 [9] A. M. Gomes and J. F. Oliveira, “Solving Irregular Strip Packing Problems by Hybridising Simulated Annealing and Linear Programming,” European Journal of Operational Research, Vol. 171, No. 3, 2006, pp. 811-829. doi:10.1016/j.ejor.2004.09.008 [10] T. Imamichi, M. Yagiura and H. Nagamochi, “An Iterated Local Search Algorithm Based on Nonlinear Programming for the Irregular Strip Packing Problem,” Discrete Optimization, Vol. 6, No. 4, 2009, pp. 345-361. doi:10.1016/j.disopt.2009.04.002 [11] S. Umetani, M. Yagiura, S. Imahori, T. Imamichi, K. Nonobe and T. Ibaraki, “Solving the Irregular Strip Packing Problem Via Guided Local Search for Overlap Minimization,” International Transactions in Operations Research, Vol. 16, No. 6, 2009, pp. 661-683. doi:10.1111/j.1475-3995.2009.00707.x [12] R. B. Grinde and K. Daniels, “Solving an Apparel Trim Placement Problem Using a Maximum Cover Problem Approach,” IIE Transactions, Vol. 31, No. 8, 1999, pp. 763-769. doi:10.1080/07408179908969875 [13] M. Fischetti and I. Luzzi, “Mixed-Integer Programming Models for the Nesting Problem,” Journal of Heuristic, Vol. 15, No. 3, 2009, pp. 201-226. doi:10.1007/s10732-008-9088-9 [14] M. A. Carravilla, C. Ribeiro and J. F. Oliveira, “Solving Nesting Problems with Non-Convex Polygons by Constraint Logic Programming,” International Transactions in Operational Research, Vol. 10, No. 6, 2003, pp. 651- 663. doi:10.1111/1475-3995.00434 [15] J. F. Oliveira, A. M. Gomes and J. S. Ferreira, “TOPOS— A New Constructive Algorithm for Nesting Problems,” OR-Spektrum, Vol. 22, No. 2, 2000, pp. 263-284. doi:10.1007/s002910050105 [16] J. A. Bennell and X. Song, “A Beam Search Implementation for the Irregular Shape Packing Problem,” Journal of Heuristic, Vol. 16, No. 2, 2010, pp. 167-188. doi:10.1007/s10732-008-9095-x [17] S. Jain and H. C. Gea, “Two-Dimensional Packing Problems Using Genetic Algorithms,” Engineering with Computers, Vol. 14, No. 3, 1998, pp. 206-213. doi:10.1007/BF01215974 [18] M. Hifi and R. M’Hallah, “A Hybrid Algorithm for the Two-Dimensional Layout Problem: The Cases of Regular and Irregular Shapes,” International Transactions in Operational Research, Vol. 10, No. 3, 2003, pp. 195-216. doi:10.1111/1475-3995.00404 [19] S. Jakobs, “On Genetic Algorithms for the Packing of Polygons,” European Journal of Operational Research, Vol. 88, No. 1, 1996, pp. 165-181. doi:10.1016/0377-2217(94)00166-9 [20] H.-Y. Liu and Y.-J. He, “Algorithm for 2D IrregularShaped Nesting Problem Based on the NFP Algorithm and Lowest-Gravity-Center Principle,” Journal of Zhejiang University, Science A, Vol. 7, No. 4, 2006, pp. 570- 576. doi:10.1631/jzus.2006.A0570 [21] J. F. Oliveira and J. S. Ferreira, “Algorithms for Nesting Problems,” R. V. V. Vidal, Ed., Applied Simulated Annealing, Lecture Notes in Economics and Mathematical Systems, Vol. 396, Springer-Verlag, Berlin, 1993, pp. 255-274. [22] G. C. Han and S. J. Na, “Two-Stage Approach for Nesting in Two-Dimensional Cutting Problems Using Neural Network and Simulated Annealing,” Proceedings of the Institute of Mechanical Engineers, Part B, Journal of Engineering Manufacture, Vol. 210, No. B6, 1996, pp. 509- 519. [23] R. Heckmann and T. Lengauer, “Computing Closely Matching Upper and Lower Bounds on Textile Nesting Problems,” European Journal of Operational Research, Vol. 108, No. 3, 1998, pp. 473-489. doi:10.1016/S0377-2217(97)00049-0 [24] J. Blazewicz, P. Hawryluk and R. Walkowiak, “Using a Tabu Search Approach for Solving the Two-Dimensional Irregular Cutting Problem,” Annals of Operations Research, Vol. 41, No. 4, 1993, pp. 313-325. doi:10.1007/BF02022998 [25] J. Kennedy and R. C. Eberhart, “Particle Swarm Optimization,” Proceedings of IEEE International Conference on Neural Networks, Piscataway, 27 November-1 December 1995, pp. 1942-1948. doi:10.1109/ICNN.1995.488968 [26] J. A. Bennell and J. F. Oliveira, “The Geometry of Nesting Problems: A Tutorial,” European Journal of Operational Research, Vol. 184, No. 2, 2008, pp. 397-415. doi:10.1016/j.ejor.2006.11.038 [27] M. Konopasek, “Mathematical Treatments of Some Apparel Marking and Cutting Problems,” U.S. Department of Commerce, Washington DC, 1981. [28] E. Hopper, “Two-Dimensional Packing Utilising Evolutionary Algorithms and Other Meta Heuristic Methods,” Ph.D. Thesis, Cardiff University, Cardiff, 2000. [29] C. Blum and D. Merkle, “Swarm Intelligence: Introduction and Applications,” Springer-Verlag, Berlin, 2008. doi:10.1007/978-3-540-74089-6 [30] M. F. Tasgetiren, Y. C. Liang, M. Sevkli and G. Gencyilmaz, “Particle Swarm Optimization Algorithm for Makespan and Maximum Lateness Minimization in Permutation Flowshop Sequencing Problem,” Proceedings of the Fourth International Symposium on Intelligent Manufacturing Systems, Sakarya, 6-8 September 2004, pp. 431- 441. [31] J. Egeblad, B. K. Nielsen and A. Odgaard, “Fast Neighborhood Search for Two and Three-Dimensional Nesting Problems,” European Journal of Operational Research, Vol. 183, No. 3, 2007, pp. 1249-1266. doi:10.1016/j.ejor.2005.11.063