A New Heuristic Approach for the Stock- Cutting Problems

Authors: Stephen C. H. Leung, Defu Zhang

Abstract:

This paper addresses a stock-cutting problem with rotation of items and without the guillotine cutting constraint. In order to solve the large-scale problem effectively and efficiently, we propose a simple but fast heuristic algorithm. It is shown that this heuristic outperforms the latest published algorithms for large-scale problem instances.

Keywords: Combinatorial optimization, heuristic, large-scale, stock-cutting.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1082401

References:

[1] A. Lodi, S. Martello, and D. Vigo, "Recent advances on two dimensional bin packing problems," Discrete Applied Mathematics, vol. 123, pp. 379-396, 2002.
[2] Z. Li, and V. Milenkovic, "Compaction and separation algorithms for non-convex polygons and their applications," European Journal of Operational Research, vol. 84, pp. 539-561, 1995.
[3] K. A. Dowsland, and W. B. Dowsland, "Packing problems," European Journal of Operational Research, vol. 56, pp. 2-14, 1992.
[4] José Fernando Oliveira, and Gerhard W├ñscher, "Cutting and Packing," European Journal of Operational Research, vol. 183, pp. 1106-1108, 2007.
[5] Defu Zhang, Yan Kang, and Ansheng Deng, "A new heuristic recursive algorithm for the strip rectangular packing problem," Computers and Operations Research, vol. 33, pp. 2209-2217, 2006.
[6] A. Bortfeldt, "A genetic algorithm for the two-dimensional strip packing problem with rectangular pieces," European Journal of Operational Research, vol. 172, pp. 814-837, 2006.
[7] Gerhard W├ñscher, Heike Haußner, and Holger Schumann, "An improved typology of cutting and packing problems," European Journal of Operational Research, vol. 183, pp. 1109-1130, 2007.
[8] Defu Zhang, Shui-hua Han, and Wei-guo Ye, "A bricklaying heuristic algorithm for the orthogonal rectangular packing problem," Chinese Journal of Computers, vol. 23, pp. 509-515, 2008.
[9] E. Hopper, and B. C. H. Turton, "An empirical investigation of metaheuristic and heuristic algorithms for a 2D packing problem," European Journal of Operational Research, vol. 128, pp. 34-57, 2001.
[10] E. K. Burke, G. Kendall, and G. Whitwell, "A new placement heuristic for the orthogonal stock-cutting problem," Operations Research, vol. 52, pp. 655-671, 2004.
[11] E. Pinto, and J. F. Oliveira, "Algorithm based on graphs for the nonguillotinable two-dimensional packing problem," Second ESICUP Meeting, Southampton, 2005.
[12] Wenqi Huang, Duanbing Chen, and Ruchu Xu, "A new heuristic algorithm for rectangle packing," Computers and Operations Research, vol. 34, pp. 3270-3280, 2007.
[13] E. K. Burke, G. Kendall, and G. Whitwell, "Metaheuristic enhancements of the best-fit heuristic for the orthogonal stock cutting problem," Computer science technical report no. NOTTCS-TR-SUB-0605091028- 4370, University of Nottingham, 2006.