Geodesic
Simulated annealing based algorithm for the rectangular bin packing problem with impurities
Diskretnyj analiz i issledovanie operacij, Tome 17 (2010) no. 4, pp. 43-66.

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

A two dimensional rectangular bin packing problem with impurities is considered. This problem generalizes the classical rectangular bin packing problem. It is NP-hard in strong sense. Encoding schemes for guillotine and non-guillotine cases of packing are proposed. To solve the problem a tailored simulated annealing algorithm based on the proposed encoding schemes has been developed. The initial solution is built by greedy heuristic. It allows the algorithm to start with low temperature. An unload procedure is performed when the temperature is changed. It unloads some bins by packing other bins more compactly. The experimental results show high efficiency of the new encoding schemes and low deviations from the optimum. Ill. 2, tab. 5, bibliogr. 11.
Keywords: bin packing, representation schemes, simulated annealing. 
@article{DA_2010_17_4_a3,
     author = {A. S. Rudnev},
     title = {Simulated annealing based algorithm for the rectangular bin packing problem with impurities},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {43--66},
     publisher = {mathdoc},
     volume = {17},
     number = {4},
     year = {2010},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2010_17_4_a3/}
}
TY  - JOUR
AU  - A. S. Rudnev
TI  - Simulated annealing based algorithm for the rectangular bin packing problem with impurities
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2010
SP  - 43
EP  - 66
VL  - 17
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2010_17_4_a3/
LA  - ru
ID  - DA_2010_17_4_a3
ER  - 
%0 Journal Article
%A A. S. Rudnev
%T Simulated annealing based algorithm for the rectangular bin packing problem with impurities
%J Diskretnyj analiz i issledovanie operacij
%D 2010
%P 43-66
%V 17
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2010_17_4_a3/
%G ru
%F DA_2010_17_4_a3
A. S. Rudnev. Simulated annealing based algorithm for the rectangular bin packing problem with impurities. Diskretnyj analiz i issledovanie operacij, Tome 17 (2010) no. 4, pp. 43-66. http://geodesic.mathdoc.fr/item/DA_2010_17_4_a3/

[1] Beisiegel B., Kallrath J., Kochetov Yu., Rudnev A., “Simulated annealing based algorithm for the 2D bin packing problem with impurities”, Oper. Res. Proc., 2005, Springer-Verl., Heidelberg, 2006, 109–113

[2] Boschetti M. A., Mingozzi A., “The two-dimensional finite bin packing problem. Part I: New lower bounds for the oriented case”, 4OR, 1 (2003), 27–72 | MR

[3] Boschetti M. A., Mingozzi A., “The two-dimensional finite bin packing problem. Part II: New lower and upper bounds”, 4OR, 1 (2003), 135–147 | MR | Zbl

[4] Dell'Amico M., Martello S., Vigo D., “A lower bound for the non-oriented two-dimensional bin packing problem”, Discrete Appl. Math., 118 (2002), 13–24 | DOI | MR

[5] Dongarra J. J., Performance of various computers using standard linear equations software, Technical Report No. CS-89-85, University of Manchester, 2008, 102 pp.

[6] Fekete S. P., Schepers J., On more-dimensional packing. Part II: Bounds, Technical Report No. 97.289, Universität zu Köln, 2000, 20 pp.

[7] Guo P. N., Cheng C. K., Yoshimura T., “An O-tree representation of non-slicing floorplan and its applications”, Proc. DAC, 1999, ACM, New York, 1999, 268–273 http://eda.ee.ucla.edu/EE201A-04Spring/otree.pdf

[8] Lodi A., Martello S., Vigo D., “Heuristic and metaheuristic approaches for a class of two-dimensional bin packing problems”, INFORMS J. Computing, 11 (1999), 345–357 | DOI | MR | Zbl

[9] Osman I. H., Laporte G., “Metaheuristics: a bibliography”, Ann. Oper. Res., 63 (1996), 513–628 | DOI | MR

[10] Wong D. F., Liu C. L., “A new algorithm for floorplan design”, Proc. DAC, 1986, IEEE Press, Piscataway, 1986, 101–107

[11] Zheng Y., Tang L., “Hybrid scatter search and tabu search for the mother plate design problem in the iron and steel industry”, Proc. Comput. Sci. Optimization, 2009, IEEE Computer Society, Washington, 2009, 978–980