ЭФФЕКТИВНЫЙ BEST-FIT-АЛГОРИТМ ДЛЯ РЕШЕНИЯ ЗАДАЧ ДВУХМЕРНОЙ ОРИЕНТИРОВАННОЙ УПАКОВКИ В КОНТЕЙНЕРЫ
Abstract
Рассматривается задача двухмерной упаковки в контейнеры (2D-BPP), которая заключается
в минимизации числа одинаковых больших прямоугольников, используемых для упаковки конечного набора прямоугольников. Предлагается эффективный Best-Fit-алгоритм (IBF), основанный на методе вогнутого угла, для решения 2D-BPP. Вычислительный эксперимент по оценке эффективности алгоритма в сравнении с четырьмя классическими алгоритмами показывает, что IBF получил лучшие результаты почти для всех тестовых примеров за меньшее время.
References
1. Garey, M.R. Computers and intractability / M.R. Garey, D.S. Johnson. – San Francisco,
2. USA, 1979. – 338 p.
3. Harald, D. A typology of cutting and packing problems / D. Harald // European Journal of
4. Operational Research. – 1990. – Vol. 44, № 2. – P. 145–159.
5. Lodi, A. Recent advances on two-dimensional bin packing problems / A. Lodi, S. Martello,
6. D. Vigo // Discrete Applied Mathematics. – 2002. – Vol. 123, № 1–3. – P. 379–396.
7. Heike, H. An improved typology of cutting and packing problems / H. Heike, W. Gerhard,
8. S. Holger // European Journal of Operational Research. – 2007. – Vol. 183, № 3. – P. 1109–1130.
9. Martello, S. Exact solution of the two-dimensional finite bin packing problem / S. Martello,
10. D. Vigo // Management science. – 1998. – Vol. 44, № 3. – P. 388–399.
11. Bengtsson, B.E. Packing rectangular pieces – a heuristic approach / B.E. Bengtsson //
12. The computer journal. – 1982. – Vol. 25, № 3. – P. 353–357.
13. Christofides, N. An algorithm for two-dimensional cutting problems / N. Christofides,
14. C. Whitlock // Operations Research. – 1977. – Vol. 25, № 1. – P. 30–44.
15. Beasley, J.E. Algorithms for unconstrained two-dimensional guillotine cutting / J.E. Beasley // Journal of the Operational Research Society. – 1985. – Vol. 36, № 4. – P. 297–306.
16. Beasley, J.E. An exact two-dimensional non-guillotine cutting tree search procedure /
17. J.E. Beasley // Operations Research. – 1985. – Vol. 33, № 1. – P. 49–64.
18. Berkey, J.O. Two-dimensional finite bin-packing algorithms / J.O. Berkey, P.Y. Wang //
19. The Journal of the Operational Research Society. – 1987. – Vol. 38, № 5. – P. 423–429.
20. Lodi, A. Approximation algorithms for the oriented two dimensional bin packing problem /
21. A. Lodi, S. Martello, D. Vigo // European Journal of Operational Research. – 1999. – Vol. 112, № 1. – P. 158–166.
Review
For citations:
. Informatics. 2011;(2(30)):134-138. (In Russ.)
Views: 702
Email this article 