References

inform

Информатика

Informatics

1816-03012617-6963

UIIP NASB

inform-592

Research Article

МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ

MATHEMATICAL MODELING

ЗАДАЧИ ДВУМЕРНОЙ ПРЯМОУГОЛЬНОЙ УПАКОВКИ И РАСКРОЯ: ОБЗОР

Головистиков

А. В.

Объединенный институт проблем информатики НАН БеларусиBelarus

2008

09112018

04(20)1833

2018

Головистиков А.В.

Данная работа распространяется под лицензией Creative Commons Attribution 4.0.

This work is licensed under a Creative Commons Attribution 4.0 License.

https://inf.grid.by/jour/article/view/592

Приводится обзор результатов по решению задач двумерной прямоугольной упаковки и раскроя. Рассматриваются основные формулировки, математические модели и алгоритмы решения задач ортогональной упаковки прямоугольных предметов в контейнер или полубесконечную полосу и двумерного прямоугольного (в том числе гильотинного) раскроя. Основное внимание уделяется эвристическим алгоритмам и метаэвристикам (генетическим алгоритмам, поиску с запретами, метаэвристике муравьиной колонии).

References1

Dyckhoff, H. Cutting and Packing in Production and Distributing / H. Dyckhoff, U. Finke. – Heidelberg : Physica Verlag, 1992. – 248 p.

Dowsland, K.A. Packing problems / K.A. Dowsland, W.B. Dowsland // European Journal of Operational Research. – 1992. – Vol. 56. – P. 2–14.

Dyckhoff, H. Cutting and packing (C&P) / H. Dyckhoff, G. Scheithauer, J. Terno // Annotated Bibliographies in Combinatorial Optimization. – Chichester : Wiley, 1997. – P. 393–413.

Стоян, Ю.Г. Методы и алгоритмы размещения плоских геометрических объектов / Ю.Г. Стоян, Н.И. Гиль. – Киев : Наукова думка, 1976. – 247 с.

Стоян, Ю.Г. Размещение геометрических объектов / Ю.Г. Стоян. – Киев : Наукова думка, 1975. – 239 с.

Стоян, Ю.Г. Периодическое размещение геометрических объектов / Ю.Г. Стоян, А.А. Панасенко. – Киев : Наукова думка, 1978. – 175 с.

Мухачева, Э.А. Рациональный раскрой промышленных материалов. Применение АСУ / Э.А. Мухачева. – М. : Машиностроение, 1984. – 176 с.

Стоян, Ю.Г. Математические модели и оптимизационные методы геометрического проектирования / Ю.Г. Стоян, С.В. Яковлев. – Киев : Наукова думка, 1986. – 266 с.

Gilmore, P.C. Multistage cutting problems of two or more dimensions / P.C. Gilmore, R.E. Gomory // Operations Research. – 1965. – Vol. 13. – P. 94–119.

Dyckhoff, H. A typology of cutting and packing problems / H. Dyckhoff // European Journal of Operational Research. – 1990. – Vol. 44. – P. 145–149.

Wascher, G. An improved typology of cutting and packing problems / G. Wascher, H. Haussner, H. Schumann // European Journal of Operational Research. – 2007. – Vol. 183. – P. 1109–1130.

Lody, A. Heuristic and metaheuristic approaches for a class of two-dimensional bin packing problems / A. Lody, S. Martello, D. Vigo // INFORMS Journal on Computing. – 1999. – Vol. 11. – P. 345–357.

Lody, A. Recent advances on two-dimensional bin packing problems / A. Lody, S. Martello, D. Vigo // Discrete Applied Mathematics. – 2002. – Vol. 123/124. – P. 373–380.

Lody, A. Two-dimensional packing problems: a survey / A. Lody, S. Martello, M. Monaci // European Journal of Operational Research. – 2002. – Vol. 141. – P. 241–252.

Tarnowski, A.G. Advanced polynomial time algorithm for guillotine generalized pallet loading problem / A.G. Tarnowski // Decision Making under Conditions of Uncertainty (Cutting-Packing Problems); ed. E.A. Mukhacheva. – Ufa, 1997. – P. 93–124.

Tarnowski, A. A polynomial time algorithm for the guillotine pallet loading problem / A. Tarnowski, J. Tern, G. Scheithauer // INFOR. – 1994. – Vol. 32. – P. 275–286.

Гэри, М. Вычислительные машины и труднорешаемые задачи / M. Гэри, Д. Джон-сон. – М. : Мир, 1982 .– 416 с.

Канторович, Л.В. Рациональный раскрой промышленных материалов / Л.В. Канто¬рович, В.А. Залгаллер. – Новосибирск : Наука, 1971. – 299 с.

Автобиография Леонида Витальевича Канторовича // Оптимизация : сб. науч. тр. СО АН СССР. – Новосибирск, 1982. – Bып. 28. – C. 50–57.

Gilmore, P.C. A linear programming approach to the cutting stock problem / P.C. Gilmore, R.E. Gomory // Operations Research. – 1961. – Vol. 9. – P. 849–859.

Gilmore, P.C. A linear programming approach to the cutting stock problem. Part II / P.C. Gilmore, R.E. Gomory // Operations Research. – 1963. – Vol. 11. – P. 863–888.

Beasley, J.E. An exact two-dimensional non-guillotine cutting tree search procedure / J.E. Beasley // Operations Research. – 1985. – Vol. 33. – P. 49–64.

Hadjiconstantnou, E. An exact algorithm for the orthogonal, 2-D cutting problems using guillotine cuts / E. Hadjiconstantnou, N. Christofides // European Journal of Operational Research. – 1995. – Vol. 83. – P. 21–38.

Lodi, A. Models and bounds for two-dimensional level packing problems / A. Lody, S. Martello, D. Vigo // Journal of Combinatorial Optimization. – 2004. – Vol. 8. – P. 363–379.

Романовский, И.В. Решение задачи гильотинного раскроя методом переработки списка состояний / И.В. Романовский // Кибернетика. – 1969. – № 1. – С. 102–103.

Fekete, S.P. On more-dimensional packing I: Modelling / S.P. Fekete, J. Schepers. – Köln, 1997. – 15 p. – (Technical paper ZPR97-288 / Matematisches Institut, Universität zu Köln).

Fekete, S.P. A combinatorial characterization of higher dimensional orthogonal packing / S.P. Fekete, J. Schepers // Mathematics of Operations Research. – 2004. – Vol. 29. – P. 353–368.

Романовский, И.В. Алгоритмы решения экстремальных задач / И.В. Романовский. – М. : Наука, 1977. – 352 с.

Martello, S. Knapsack Problems: Algorithms and Computer Implementations / S. Martello, P. Toth. – Chichester : Wiley, 1990. – 296 p.

Belov, G. A cutting plane algorithm for the one-dimensional cutting stock problem with multiple stock lengths / G. Belov, G. Scheithauer // European Journal of Operational Research. – 2002. – Vol. 141. – P. 274–294.

Липовецкий, А.И. К оптимизации свободного размещения прямоугольников / А.И. Липовецкий // Автоматическое проектирование в машиностроении. – Минск : Ин-т техн. кибернетики АН БССР, 1985. – С. 80–87.

Бухвалова, В.В. Задачи прямоугольного раскроя: метод зон и другие алгоритмы / В.В. Бухвалова. – СПб. : СПбГУ, 2001. – 96 с.

Картак, В.М. Матричный алгоритм поиска оптимального решения для задачи упаковки прямоугольников в полубесконечную полосу / В.М. Картак // Информационные технологии. – 2008. – № 2. – С. 24–30.

Clautiaux, F. A new exact method for the two-dimensional orthogonal packing problem / F. Clautiaux, J. Carlier, A. Moukrim // European Journal of Operational Research. – 2007. – Vol. 183. – P. 1196–1211.

Martello, S. Exact solution of the two-dimensional finite bin packing problem / S. Martello, D. Vigo // Management Sciences. – 1998. – Vol. 44. – P. 388–399.

Boschetti, M. New upper bounds for the two-dimensional orthogonal non guillotine cutting stock problem / M. Boschetti, E. Hadjiconstantinou, A. Mingozzi // IMA Journal of Management Mathematics. – 2002. – Vol. 13. – P. 95–119.

Martello, S. An exact approach to the strip-packing problem / S. Martello, M. Monaci, D. Vigo // INFORMS Journal on Computing. – 2003. – Vol. 15. – P. 310–319.

Fekete, S.P. A general framework for bounds for higher- dimensional orthogonal packing problems / S.P. Fekete, J. Schepers // Mathematical methods of Operations Research. – 2004. – Vol. 60. – P. 311–329.

Тарновский, А.Г. Полиномиальный алгоритм решения задачи монораскроя / А.Г. Тарновский // Системы программного обеспечения решения задач оптимального планирования : тез. Одиннадцатой Всесоюз. школы (г. Кострома, 20–21 мая 1990 г.). – М. : ЦЭМИ, 1990. – С. 128–129

Girlich, E. On polynomial solvability of two multiprocessor scheduling problems / E. Girlich, A.G. Tarnowski // Mathematical Methods of Operations Research. – 1999. – Vol. 50. – P. 27–51.

Наумович, Н.А. Экспериментальное исследование серий градиентных методов / Н.А. Наумович // Методы, алгоритмы и программы решения экстремальных задач : сб. науч. тр. – Минск : Ин-т техн. кибернетики АН БССР, 1985. – С. 98–111.

Ковалев, М.М. Эффективность градиентных алгоритмов раскроя / М.М. Ковалев, А.Г. Тарновский // Комбинаторно-алгебраические методы в дискретной оптимизации : межвуз. тематич. сб. науч. тр. – Нижний Новгород : НГУ, 1991. – С. 22–36.

Ковалев, М.М. Анализ эффективности серий градиентных алгоритмов раскроя / М.М. Ковалев, А.Г. Тарновский // Математическое обеспечение рационального раскроя в системах автоматизированного проектирования : тез. Всесоюзн. конф. – Уфа, 1988. – С. 62–65.

Тарновский, А.Г. САПР «РАСКРОЙ» – промышленная система раскроя материалов на персональных ЭВМ / А.Г. Тарновский // Методы решения экстремальных задач и смежные вопросы : сб. науч. тр. – Минск : Ин-т техн. кибернетики АН БССР, 1990. – С. 142–158.

Филиппова, А.С. Проблемы декодирования прямоугольных упаковок: краткий обзор современных технологий / А.С. Филиппова // Информационные технологии. – 2005. – № 12. – С. 13–19.

Методы локального поиска в задачах ортогонального раскроя и упаковки: аналитический обзор и перспективы развития / Э.А. Мухачева [и др.] // Информационные технологии. – 2004. – № 5. – С. 2–17.

Liu, D. An improved BL-algorithm for genetic algorithm of the orthogonal packing of rectangles / D. Liu, H. Teng // European Journal of Operational Research. – 1999. – Vol. 112, № 2. – P. 413–420.

Performance bounds for level-oriented two-dimensional packing algorithms / E.G. Coffman Jr. [et al.] // SIAM Journal on Computing. – 1980. – Vol. 9. – P. 801–826.

Baker, B.S. Orthogonal packing in two dimensions / B.S. Baker, E.G. Coffman Jr., R.L. Riverst // SIAM Journal on Computing. – 1980. – Vol. 9. – P. 846–855.

Мухачева, А.С. Технология блочных структур локального поиска оптимума в задачах прямоугольной упаковки / А.С. Мухачева // Информационные технологии. – 2004. – № 5. Приложение. – С. 18–32.

Rectangle-packing-based module placement / H. Murata [et al.] // Proc. IEEE/ACM Int. Conf. on Computer-Aided Design. – San Jose, California, 1995. – P. 472–479.

Филиппова, А.С. Задача двумерной упаковки в полубесконечную полосу: численный эксперимент с алгоритмами локального поиска и с декодерами блочной структуры / А.С. Филиппова // Информационные технологии. – 2005. – № 6.– С. 32–45.

Мухачева, Э.А. Задача прямоугольной упаковки: методы локального поиска оптимума на базе блочных структур / Э.А. Мухачева, А.С. Мухачева // Автоматика и телемеханика. – 2004. – № 2. – С. 101–112.

Goldberg, D. Genetic Algorithms in Search, Optimization and Machine Learning / D. Goldberg. – Boston : Adison-Wesley, 1989. – 372 p.

Батищев, Д.И. Генетические алгоритмы решения экстремальных задач / Д.И. Бати¬щев. – Воронеж : ВГТУ, 1995. – 69 с.

Aarts, E.H.L. Local search in combinatorial optimization / E.H.L. Aarts, J.K. Lenstra. – Chichester : Wiley, 1997. – 528 p.

Норенков, И.П. Эвристики и их комбинации в генетических методах дискретной оптимизации / И.П. Норенков // Информационные технологии. – 1999. – № 1. – С. 2–7.

Мухачева, Э.А. Генетический алгоритм блочной структуры в задачах двумерной упаковки / Э.А. Мухачева, А.С. Мухачева, А.В. Чиглинцев // Информационные технологии. – 1999. – № 11. – С. 13–18.

Linear one-dimensional cutting-packing problems: numerical experiments with sequencial value correction method (SVC) and a modified branch-and-bound method (MBB) / E.A. Mukhacheva [et al.] // Pescuisa Operational. – 2000. – Vol. 20. – P. 153–168.

Мухачева, А.С. Генетический алгоритм поиска минимума в задачах двумерного гильотинного раскроя / А.С. Мухачева, А.В. Чиглинцев // Информационные технологии. – 2001. – № 3. – С. 27–31.

Gehring, H. Genetic algorithm for solving the container loading problem / H. Gehring, A. Bortfeldt // International Transactions in Operational Research. – 1997. – Vol. 4. – P. 401–418.

Hadjiconstantnou, E. A hybrid genetic algorithm for the two-dimensional single large object placement problem / E. Hadjiconstantnou, M. Iori // European Journal of Operational Research. – 2007. – Vol. 183. – P. 1150–1166.

Scholl, A. BISON: A fast hybrid procedure for exactly solving the one-dimensional Bin-Packing Problem / A. Scholl, R. Klein, C. Yuergens // Computers & Operations Research. – 1997. – Vol. 24. – P. 627–645.

Задачи двумерной упаковки: развитие генетических алгоритмов на базе смешанных процедур локального поиска оптимального решения / А.С. Мухачева [и др.] // Информационные технологии. – 2001. – № 9. Приложение. – С. 1–24.

Glover, F. Tabu search and adaptive memory programming – advances, applications and challenges / F. Glover // Interfaces in Computer Science and Operations Research. – Kluwer Academic Publishers, 1996. – P. 1–75.

Hertz, A. Tabu Search / A. Hertz, E. Taillard, D. de Werra // Local Search in Combinatorial Optimization. – Chichester : Wiley, 1997. – P. 121–136.

Метод поиска минимума с запретами в задачах двумерного гильотинного раскроя / Э.А. Мухачева [и др.] // Информационные технологии. – 2001. – № 6. – С. 25–31.

Alvarez-Valdes, R. A tabu search algorithm for two-dimensional non-guillotine cutting problem / R. Alvarez-Valdes, F. Parreno, J.M. Tamarit // European Journal of Operational Research. – 2007. – Vol. 183. – P. 1270–1277.

Dorigo, M. Ant algorithms for discrete optimization / M. Dorigo, G. Di Caro, L. Gambardella // Artificial Life. – 1999. – Vol. 5. – P. 137–172.

Валеева, А.Ф. Применение метаэвристики муравьиной колонии к задачам двумерной упаковки / А.Ф. Валеева // Информационные технологии. – 2005. – № 10. – С. 36–43.

Schwerin, P. A new lower bound for the bin-packing problem and its integration to MTP / P. Schwerin, G. Wascher // Pescuisa Operational. – 1999. – Vol. 9. – P. 111–131.

Schwerin, P. The bin-packing problem: a problem generator and some numerical experiments with FFD packing and MTP / P. Schwerin, G. Wascher // International Transactions in Operational Research. – 1997. – Vol. 4. – P. 337–389.

The Management School, Imperial College, UK [Electronic resource]. – Mode of access: http://people.brunel.ac.uk/~mastjjb/jeb/info.html. – Date of access: 16.06.2008.

Филиппова, А.С. Задача ортогональной упаковки в полубесконечную полосу: численный эксперимент с безотходными задачами E. Hopper / А.С. Филиппова, Э.А. Мухачева, А.В. Чиглинцев // Информационные технологии. – 2005. – № 7. – С. 45–54.

Hopper, E. An empirical investigation of metf-heuristic and heuristic algorithms for a 2D packing problem / E. Hopper, B. Turton // European Journal of Operational Research. – 2001. – Vol. 128. – P. 34–57.

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