Volume 17, No 4, 2010, P. 43-66

UDC 519.8
A. S. Rudnev
Simulated annealing based algorithm for the rectangular bin packing problem with impurities

Abstract:
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. 7, tab. 5, bibliogr. 18.

Keywords: bin packing, representation schemes, simulated annealing.

Rudnev Anton Sergeevich ^1,2
1. S. L. Sobolev Institute of Mathematics, SB RAS,
4 Acad. Koptyug Ave., 630090 Novosibirsk, Russia
2. Novosibirsk State University,
2 Pirogov St., 630090 Novosibirsk, Russia
e-mail: anton.rudnev@gmail.com