A New Heuristic Approach for the Stock- Cutting Problems
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.
[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.
[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.
@article{"International Journal of Information, Control and Computer Sciences:63132", author = "Stephen C. H. Leung and Defu Zhang", title = "A New Heuristic Approach for the Stock- Cutting Problems", 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.", volume = "3", number = "5", pages = "1455-6", }
