Orthogonal Rectangular Strip Packing Problem

Cutting and packing a given stock material are crucial processes in manufacturing and producing. Paper, plastic, wood, glass, steel and leather are some of the most commonly used stock materials in the industries. Different types of cutting and packing problems arise due to the nature of the stock material, such as different constraints and objectives. Orthogonal Rectangular Strip Packing Problem (SPP) involves in finding the best orthogonal placement of a set of rectangles with given widths and heights in a suitable orientation on a strip of rectangular stock sheet with a fixed width and an infinite height. Orthogonal placement requires the sides of the rectangles to be parallel to the edges of the strip. Based on the recent categorization of the cutting and packing problems provided by Waescher, Haussner and Schumann (2007), SPP is identified as two-dimensional, open dimension problem.

Bidirectional Best-fit Heuristic for Orthogonal Rectangular Strip Packing

Önder Barış Aşık, Ender Özcan

(Under Review)

If the rotation of rectangles by 90-degrees is allowed and guillotine cutting (edge-to-edge) is not required as constraints during the placement process, this type of problems is referred to as RF subtype. In this study, a new heuristic is presented for solving orthogonal rectangular strip packing problem of RF subtype: Bidirectional Best-fit Heuristic (BBF). BBF achieves better results than the existing heuristics and delivers a better or matching performance as compared to the most of the previously proposed meta-heuristics for solving RF-SPPs.

Experimental Data

 Data source Problem(s) Optimal height Pinto and Oliveira (2005) PO1 600 PO2 PO3 PO4 PO5 PO6 PO7 Burke, Kendall and Whitwell (2004) N1 40 N2 50 N3 50 N4 80 N5 100 N6 100 N7 100 N8 80 N9 150 N10 150 N11 150 N12 300 N13 960 Valenzuela and Wang (2001) VN1, VP1 100 VN2, VP2 VN3, VP3 VN4, VP4 VN5, VP5 VN6, VP6 Hopper and Turton (2001a) C1P1 20 C1 C1P2 C1P3 C2 C2-P1, P2, P3 15 C3P1 30 C3 C3P2 C3P3 C4 C4-P1, P2, P3 60 C5P1 90 C5 C5P2 C5P3 C6 C6-P1, P2, P3 120 C7P1 240 C7 C7P2 C7P3 Hopper (2000) H1 200 Explanation: There are 5 problem instances in each problem category H2 H3 H4 H5 H6 H7 Ramesh Babu and Ramesh Babu (1999) RB 375 Jakobs (1996) J1 15 J2

Comparison of BBF to some previous heuristics

The proposed heuristic either improves the solutions or generates a tie for all problem instances obtained from the previous heuristics.

Table A HR: heuristic of Zhang, Kang and Deng (2006), BL: bottom left, BLF: bottom left fill, D-W: decreasing – width, BLD* : Lesh et al. (2005)

Hopper and Turton data set, %-gap

 label no. of shapes BL BL-DW BL-DH BLF BLF-DW BLF-DH BBF HR C1P1 16 45 30 15 30 10 10 0 C1P2 17 40 20 10 35 15 10 5 C1P3 16 35 20 5 25 15 5 5 C1 avr 40.0 23.3 10.0 30.0 13.3 8.3 3.3 8.3 C2P1 25 53 13 13 47 13 13 6.7 C2P2 25 80 27 73 73 20 73 6.7 C2P3 25 67 27 13 47 20 13 0 C2 avr 66.7 22.3 33.0 55.7 17.7 33.0 4.4 4.5 C3P1 28 40 10 10 37 10 10 0 C3P2 29 43 20 10 50 13 6.7 10 C3P3 28 40 17 13 33 13 13 3.3 C3 avr 41.0 15.7 11.0 40.0 12.0 9.9 4.4 6.7 C4P1 49 32 17 12 25 10 10 3.3 C4P2 49 37 22 13 25 5 5 3.3 C4P3 49 30 22 6.7 27 10 5 1.7 C4 avr 33.0 20.33 10.57 25.67 8.33 6.7 2.8 2.2 C5P1 72 27 16 4.4 20 5.6 4.4 1.1 C5P2 73 32 18 10 23 6.7 5.6 2.2 C5P3 72 30 13 7.8 21 5.6 4.4 1.1 C5 avr 29.7 15.7 7.4 21.3 6.0 4.8 1.5 1.9 C6P1 97 33 22 8.3 20 5 5 1.7 C6P2 97 39 25 8.3 18 4.2 2.5 0.8 C6P3 97 34 18 9.2 21 4.2 6.7 1.7 C6 avr 35.3 21.7 8.6 19.7 4.5 4.7 1.4 2.5 C7P1 196 22 16 5 15 4.6 3.8 1.2 C7P2 197 41 19 10 20 3.3 2.9 1.7 C7P3 196 31 17 7.1 17 2.9 3.8 1.7 C7 avr 31.3 17.3 7.4 17.3 3.6 3.5 1.5 1.8

 label no. of shapes Optimum BBF BL PO1 50 7.2 12.3 PO2 100 7.5 13.2 PO3 500 3.0 15.3 PO4 1,000 600 0.0 15.0 PO5 5,000 0.0 14.5 PO6 10,000 0.0 13.5 PO7 15,000 0.0 10.0 2.5 13.4

 no. of BBF BLD* label shapes optimum Mean Best 60 s 3600 s H1 17 8.3 6.0 6.0 4.5 H2 25 8.0 6.5 6.4 4.7 H3 29 7.3 5.0 6.0 4.6 H4 49 200 4.5 2.5 5.1 3.9 H5 73 4.7 3.5 4.6 4.0 H6 97 2.9 2.5 4.0 3.0 H7 197 1.6 1.5 2.3 1.8 avr 3.9 4.9 3.8

Comparison of BBF to BF

BBF outperforms the best fit heuristic. This performance variation is also statistically significant within a confidence interval of 99.99%.

Table B

 label BBF result BF result %-impr. M1 9 13 %-impr. N1 40 45 30.77 N2 52 53 11.11 N3 52 52 1.89 N4 82 83 0.00 N5 104 105 1.20 N6 102 103 0.95 N7 106 107 0.97 N8 82 84 0.93 N9 152 152 2.38 N10 151 152 0.00 N11 151 152 0.66 N12 303 306 0.66 N13 964 964 0.98 C1P1 20 21 0.00 C1P2 21 22 4.76 C1P3 21 24 4.55 C2P1 16 16 12.50 C2P2 16 16 0.00 C2P3 15 16 0.00 C3P1 30 32 6.25 C3P2 33 34 6.25 C3P3 31 33 2.94 C4P1 62 63 6.06 C4P2 62 62 1.59 C4P3 61 62 0.00 C5P1 91 93 1.61 C5P2 92 92 2.15 C5P3 91 93 0.00 C6P1 122 123 2.15 C6P2 121 122 0.81 C6P3 122 124 0.82 C7P1 243 247 1.61 C7P2 244 244 1.62 C7P3 244 245 0.00 VN1 1073 1074 0.41 VN2 1080 1085 0.09 VN3 1069 1070 0.46 VN4 1056 1053 0.09 VN5 1031 1035 - VN6 1036 1037 0.39 VP1 1093 1101 0.10 VP2 1074 1138 0.73 VP3 1080 1073 5.62 VP4 1053 1041 - VP5 1031 1037 - VP6 1026 1028 0.58 RB 400 400 0.19

Comparison of BBF to the meta-heuristics

GA+BL:  Jakobs (1996)

GA+iBL : Liu and Teng (1999)

SA/GA+BLF : Hopper and Turton (2001a)

SA/GA+BLF : Burke et al. (2004)

vGRASP: Beltrán et al. (2004)

SPGAL: Bortfeldt (2006)

rGRASP: Alvarez-Valdes et al. (2006)

BBF: proposed approach

Imahori et al. (2005) employed iterated local search for solving RF-SPPs. According to their results, iterated local search improves SA+BLF by %0.49 based on their evaluation scheme, whereas BBF performs slightly better with a %0.75 improvement over SA+BLF based on average %-gap considering Hopper and Turton problem instances. The results show that BBF performs better than six older meta-heuristics. Burke et al. (2006) experimented with a multistage scheme. BF is executed for a predetermined number of rectangles, and then a meta-heuristic with BLF decoder is invoked. Different meta-heuristics are tested, namely; GA, SA and tabu search (TS). This scheme yielded a better performance as compared to BF. For all data sets in Table 5, excluding M1, BF-GA+BLF, BF-TS+BLF and BF-SA+BLF returns an average gap of 3.61%, 3.29% and 2.86%, respectively. BBF with an average gap of 3.54% performs slightly better than BF-GA+BLF and slightly worse than the others, yet we can say that it has a comparable performance to these approaches.

Table C  Performance comparison based on %-gap.

 label BBF GA+BL GA+iBL J1 6.7 13.3 6.7 J2 6.7 13.3 6.7

 Hopper Burke label BBF GA+BLF SA+BLF vGRASP GA+BLF SA+BLF SPGAL rGRASP C1 3.33 4 4 14.40 1.7 1.7 1.7 0.00 C2 4.44 7 6 17.33 6.7 6.7 0.0 0.00 C3 4.44 5 5 12.93 6.7 6.7 2.2 1.08 C4 2.78 3 3 6.80 5.0 6.1 0.0 1.64 C5 1.48 4 3 4.51 5.6 5.2 0.0 1.10 C6 1.39 4 3 3.55 5.3 5.3 0.3 0.83 C7 1.53 5 4 2.89 5.6 6.0 0.3 1.23 avr 2.77 4.57 4.00 8.92 5.20 5.36 0.64 0.84

 label no. of shapes rGRASP BBF PO1 50 2.83 7.17 PO2 100 2.83 7.50 PO3 500 0.83 3.00 PO4 1,000 0.33 0.00 PO5 5,000 0.00 0.00 PO6 10,000 0.00 0.00 PO7 15,000 0.00 0.00 avr 0.98 2.52

References

Alvarez-Valdes, R., Parreno, F. & Tamarit, J.M. (2008). Reactive GRASP for the strip-packing problem. Computers and Operations Research, 35, 1065–1083.

Beltrán, J. D., Calderón, J. E. , Cabrera, R. J. , Moreno-Pérez, J. A., & Moreno-Vega, J. M. (2004). GRASP-VNS hybrid for the Strip Packing Problem. Proc. of the workshop on Hybrid Metaheuristics (pp. 79–90).

Bortfeld, A. (2006). A genetic algorithm fot the two-dimensional strip packing problem with rectangular pieces. Eur J Oper Res, 172, 814–837.

Burke, E. K., Kendall, G., & Whitwell, G. (2004). A new placement heuristic for the orthogonal stock-cutting problem. Operations Research, 52(4), 655–671.

Burke, E. K., Kendall, G., & Whitwell, G. (2006). Metaheuristic enhancements of the best-fit heuristic for the orthogonal stock cutting problem computer science. Technical Report No NOTTCS-TR-2006-3.

Hopper, E. (2000). Two-dimensional packing utilising evolutionary algorithms and other meta-heuristic methods, PhD thesis, Cardiff University, School of Engineering.

Hopper, E., & Turton, B. C. H. (2001a). An empirical investigation of metaheuristic and heuristic algorithms for a 2D packing problem. Eur J Oper Res, 128, 34–57.

Imahori, S., Yagiura, M., & Ibaraki, T. (2005). Improved local search algorithms for the rectangle packing problem with general spatial costs. Eur J Oper Res, 167, 48–67.

Jakobs, S. (1996). On genetic algorithms for the packing of polygons. Eur J Oper Res,88,165–181.

Liu, D., & Teng, H. (1999). An improved bottom left algorithm for genetic algorithm of the orthogonal packing of rectangle. Eur J Oper Res, 112, 413–419.

Pinto, E., & Oliveira, J. F. (2005). Algorithm based on graphs for the non-guillotinable two-dimensional packing problem, 2nd ESICUP Meeting, Southampton.

Ramesh Babu, A., & Ramesh Babu, N. (1999). Effective nesting of rectangular parts in multiple rectangular sheets using genetic and heuristic algorithms. Int J Production Res, 37(7), 1625–1643.

Valenzuela, C. L., & Wang, P. Y. (2001). Heuristics for large strip packing problems with guillotine patterns: An empirical study. Proceedings of the 4th Metaheuristics Int. Conf., University of Porto, Porto, Portugal (pp. 417–421).

Waescher, G., Haussner, H., & Schumann, H. (2007). An improved typology of cutting and packing problems. Eur J Oper Res, 183, 1109–1130.