A Particle Swarm Optimization Algorithm for a 2-D Irregular Strip Packing Problem

Show more

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