Preview

Информатика

Расширенный поиск

ЭФФЕКТИВНЫЙ BEST-FIT-АЛГОРИТМ ДЛЯ РЕШЕНИЯ ЗАДАЧ ДВУХМЕРНОЙ ОРИЕНТИРОВАННОЙ УПАКОВКИ В КОНТЕЙНЕРЫ

Полный текст:

Аннотация

Рассматривается задача двухмерной упаковки в контейнеры (2D-BPP), которая заключается
в минимизации числа одинаковых больших прямоугольников, используемых для упаковки конечного набора прямоугольников. Предлагается эффективный Best-Fit-алгоритм (IBF), основанный на методе вогнутого угла, для решения 2D-BPP. Вычислительный эксперимент по оценке эффективности алгоритма в сравнении с четырьмя классическими алгоритмами показывает, что IBF получил лучшие результаты почти для всех тестовых примеров за меньшее время.

Об авторе

Да Юн Цао
Белорусский государственный университет
Беларусь


Список литературы

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.


Для цитирования:


Цао Д.Ю. ЭФФЕКТИВНЫЙ BEST-FIT-АЛГОРИТМ ДЛЯ РЕШЕНИЯ ЗАДАЧ ДВУХМЕРНОЙ ОРИЕНТИРОВАННОЙ УПАКОВКИ В КОНТЕЙНЕРЫ. Информатика. 2011;(2(30)):134-138.

For citation:


. . Informatics. 2011;(2(30)):134-138. (In Russ.)

Просмотров: 60


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 1816-0301 (Print)
ISSN 2617-6963 (Online)