informИнформатикаInformatics1816-03012617-6963UIIP NASBinform-374Research ArticleИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИINFORMATION TECHNOLOGYЭФФЕКТИВНЫЙ BEST-FIT-АЛГОРИТМ ДЛЯ РЕШЕНИЯ ЗАДАЧ ДВУХМЕРНОЙ ОРИЕНТИРОВАННОЙ УПАКОВКИ В КОНТЕЙНЕРЫЦаоДа ЮнБелорусский государственный университетBelarus20112004201802(30)134138Copyright © Цао Д.Ю., 20182018Цао Д.Ю.Цао Д.Ю.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://inf.grid.by/jour/article/view/374

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

ReferencesGarey, M.R. Computers and intractability / M.R. Garey, D.S. Johnson. – San Francisco,Garey, M.R. Computers and intractability / M.R. Garey, D.S. Johnson. – San Francisco,USA, 1979. – 338 p.USA, 1979. – 338 p.Harald, D. A typology of cutting and packing problems / D. Harald // European Journal ofHarald, D. A typology of cutting and packing problems / D. Harald // European Journal ofOperational Research. – 1990. – Vol. 44, № 2. – P. 145–159.Operational Research. – 1990. – Vol. 44, № 2. – P. 145–159.Lodi, A. Recent advances on two-dimensional bin packing problems / A. Lodi, S. Martello,Lodi, A. Recent advances on two-dimensional bin packing problems / A. Lodi, S. Martello,D. Vigo // Discrete Applied Mathematics. – 2002. – Vol. 123, № 1–3. – P. 379–396.D. Vigo // Discrete Applied Mathematics. – 2002. – Vol. 123, № 1–3. – P. 379–396.Heike, H. An improved typology of cutting and packing problems / H. Heike, W. Gerhard,Heike, H. An improved typology of cutting and packing problems / H. Heike, W. Gerhard,S. Holger // European Journal of Operational Research. – 2007. – Vol. 183, № 3. – P. 1109–1130.S. Holger // European Journal of Operational Research. – 2007. – Vol. 183, № 3. – P. 1109–1130.Martello, S. Exact solution of the two-dimensional finite bin packing problem / S. Martello,Martello, S. Exact solution of the two-dimensional finite bin packing problem / S. Martello,D. Vigo // Management science. – 1998. – Vol. 44, № 3. – P. 388–399.D. Vigo // Management science. – 1998. – Vol. 44, № 3. – P. 388–399.Bengtsson, B.E. Packing rectangular pieces – a heuristic approach / B.E. Bengtsson //Bengtsson, B.E. Packing rectangular pieces – a heuristic approach / B.E. Bengtsson //The computer journal. – 1982. – Vol. 25, № 3. – P. 353–357.The computer journal. – 1982. – Vol. 25, № 3. – P. 353–357.Christofides, N. An algorithm for two-dimensional cutting problems / N. Christofides,Christofides, N. An algorithm for two-dimensional cutting problems / N. Christofides,C. Whitlock // Operations Research. – 1977. – Vol. 25, № 1. – P. 30–44.C. Whitlock // Operations Research. – 1977. – Vol. 25, № 1. – P. 30–44.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.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.Beasley, J.E. An exact two-dimensional non-guillotine cutting tree search procedure /Beasley, J.E. An exact two-dimensional non-guillotine cutting tree search procedure /J.E. Beasley // Operations Research. – 1985. – Vol. 33, № 1. – P. 49–64.J.E. Beasley // Operations Research. – 1985. – Vol. 33, № 1. – P. 49–64.Berkey, J.O. Two-dimensional finite bin-packing algorithms / J.O. Berkey, P.Y. Wang //Berkey, J.O. Two-dimensional finite bin-packing algorithms / J.O. Berkey, P.Y. Wang //The Journal of the Operational Research Society. – 1987. – Vol. 38, № 5. – P. 423–429.The Journal of the Operational Research Society. – 1987. – Vol. 38, № 5. – P. 423–429.Lodi, A. Approximation algorithms for the oriented two dimensional bin packing problem /Lodi, A. Approximation algorithms for the oriented two dimensional bin packing problem /A. Lodi, S. Martello, D. Vigo // European Journal of Operational Research. – 1999. – Vol. 112, № 1. – P. 158–166.A. Lodi, S. Martello, D. Vigo // European Journal of Operational Research. – 1999. – Vol. 112, № 1. – P. 158–166.

The authors declare that there are no conflicts of interest present.