Geodesic
A heuristic algorithm for the non-oriented 2D rectangular strip packing problem
Buletinul Academiei de Ştiinţe a Republicii Moldova. Matematica, no. 2 (2011), pp. 81-88.

Voir la notice de l'article provenant de la source Math-Net.Ru

In this paper, we construct best fit based on concave corner strategy ($BF_{BCC}$) for the two-dimensional rectangular strip packing problem (2D-RSPP), and compare it with some heuristic and metaheuristic algorithms from the literature. The experimental results show that $BF_{BCC}$ could produce satisfied packing layouts, especially for the large problem of 50 pieces or more, $BF_{BCC}$ could get better results in shorter time. 
@article{BASM_2011_2_a6,
     author = {V. M. Kotov and Dayong Cao},
     title = {A heuristic algorithm for the non-oriented {2D} rectangular strip packing problem},
     journal = {Buletinul Academiei de \c{S}tiin\c{t}e a Republicii Moldova. Matematica},
     pages = {81--88},
     publisher = {mathdoc},
     number = {2},
     year = {2011},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/BASM_2011_2_a6/}
}
TY  - JOUR
AU  - V. M. Kotov
AU  - Dayong Cao
TI  - A heuristic algorithm for the non-oriented 2D rectangular strip packing problem
JO  - Buletinul Academiei de Ştiinţe a Republicii Moldova. Matematica
PY  - 2011
SP  - 81
EP  - 88
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/BASM_2011_2_a6/
LA  - en
ID  - BASM_2011_2_a6
ER  - 
%0 Journal Article
%A V. M. Kotov
%A Dayong Cao
%T A heuristic algorithm for the non-oriented 2D rectangular strip packing problem
%J Buletinul Academiei de Ştiinţe a Republicii Moldova. Matematica
%D 2011
%P 81-88
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/BASM_2011_2_a6/
%G en
%F BASM_2011_2_a6
V. M. Kotov; Dayong Cao. A heuristic algorithm for the non-oriented 2D rectangular strip packing problem. Buletinul Academiei de Ştiinţe a Republicii Moldova. Matematica, no. 2 (2011), pp. 81-88. http://geodesic.mathdoc.fr/item/BASM_2011_2_a6/

[1] Garey M. R., Johnson D. S. and others, Computers and Intractability: A Guide to the Theory of $NP$-completeness, Freeman, San Francisco, 1979 | MR | Zbl

[2] Burke E. K., Kendall G., Whitwell G., “A new placement heuristic for the orthogonal stock-cutting problem”, Operations Research, 52:4 (2004), 655–671 | DOI | Zbl

[3] Lodi A., Martello S., Monaci M., “Two-dimensional packing problems: A survey”, European Journal of Operational Research, 141:2 (2002), 241–252 | DOI | MR | Zbl

[4] Hopper E., Turton B., “An empirical investigation of meta-heuristic and heuristic algorithms for a $2D$ packing problem”, European Journal of Operational Research, 128:1 (2001), 34–57 | DOI | Zbl

[5] Gilmore P. C., Gomory R. E., “A linear programming approach to the cutting stock problem, II”, Operations Research, 11:6 (1963), 863–888 | DOI | Zbl

[6] Christofides N. Whitlock C., “An algorithm for two-dimensional cutting problems”, Operations Research, 25 (1977), 30–44 | DOI | Zbl

[7] Christofides N., Hadjiconstantinou E., “An exact algorithm for orthogonal $2-D$ cutting problems using guillotine cuts”, European Journal of Operational Research, 83:1 (1995), 21–38 | DOI | Zbl

[8] Sweeney P. E., Paternoster E. R., “Cutting and packing problems: a categorized, application-orientated research bibliography”, The Journal of the Operational Research Society, 43:7 (1992), 691–706 | DOI | Zbl

[9] Baker B. S., Coffman E. G. (jr.), Rivest R. L., “Orthogonal packings in two dimensions”, SIAM Journal on Computing, 9 (1980), 846–855 | DOI | MR | Zbl

[10] Chazelle B., “The bottom-left bin-packing heuristic: An efficient implementation”, IEEE Transactions on Computers, 32:8 (1983), 697–707 | DOI | Zbl

[11] Liu D., Teng H., “An improved $BL$-algorithm for genetic algorithm of the orthogonal packing of rectangles”, European Journal of Operational Research, 112:2 (1999), 413–420 | DOI | Zbl

[12] Hopper E., Turton B., “A genetic algorithm for a $2D$ industrial packing problem”, Computers and Industrial Engineering, 37:1–2 (1999), 375–378 | DOI

[13] Leung T. W., Chan C. K., Troutt M. D., “Application of a mixed simulated annealing-genetic algorithm heuristic for the two-dimensional orthogonal packing problem”, European Journal of Operational Research, 145:3 (2003), 530–542 | DOI | MR | Zbl

[14] Leung T. W., Yung C. H., Troutt M. D., “Applications of genetic search and simulated annealing to the two-dimensional non-guillotine cutting stock problem”, Computers and industrial engineering, 40:3 (2001), 201–214 | DOI

[15] Lodi A., Martello S., Monaci M., “Heuristic and metaheuristic approaches for a class of two-dimensional bin packing problem”, Informs Journal on Computing, 11:4 (1999), 345–357 | DOI | MR | Zbl