ЗАДАЧИ ДВУМЕРНОЙ ПРЯМОУГОЛЬНОЙ УПАКОВКИ И РАСКРОЯ: ОБЗОР
Аннотация
Приводится обзор результатов по решению задач двумерной прямоугольной упаковки и раскроя. Рассматриваются основные формулировки, математические модели и алгоритмы решения задач ортогональной упаковки прямоугольных предметов в контейнер или полубесконечную полосу и двумерного прямоугольного (в том числе гильотинного) раскроя. Основное внимание уделяется эвристическим алгоритмам и метаэвристикам (генетическим алгоритмам, поиску с запретами, метаэвристике муравьиной колонии).
Список литературы
1. Dyckhoff, H. Cutting and Packing in Production and Distributing / H. Dyckhoff, U. Finke. – Heidelberg : Physica Verlag, 1992. – 248 p.
2. Dowsland, K.A. Packing problems / K.A. Dowsland, W.B. Dowsland // European Journal of Operational Research. – 1992. – Vol. 56. – P. 2–14.
3. Dyckhoff, H. Cutting and packing (C&P) / H. Dyckhoff, G. Scheithauer, J. Terno // Annotated Bibliographies in Combinatorial Optimization. – Chichester : Wiley, 1997. – P. 393–413.
4. Стоян, Ю.Г. Методы и алгоритмы размещения плоских геометрических объектов / Ю.Г. Стоян, Н.И. Гиль. – Киев : Наукова думка, 1976. – 247 с.
5. Стоян, Ю.Г. Размещение геометрических объектов / Ю.Г. Стоян. – Киев : Наукова думка, 1975. – 239 с.
6. Стоян, Ю.Г. Периодическое размещение геометрических объектов / Ю.Г. Стоян, А.А. Панасенко. – Киев : Наукова думка, 1978. – 175 с.
7. Мухачева, Э.А. Рациональный раскрой промышленных материалов. Применение АСУ / Э.А. Мухачева. – М. : Машиностроение, 1984. – 176 с.
8. Стоян, Ю.Г. Математические модели и оптимизационные методы геометрического проектирования / Ю.Г. Стоян, С.В. Яковлев. – Киев : Наукова думка, 1986. – 266 с.
9. 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.
10. Dyckhoff, H. A typology of cutting and packing problems / H. Dyckhoff // European Journal of Operational Research. – 1990. – Vol. 44. – P. 145–149.
11. 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.
12. 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.
13. 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.
14. 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.
15. 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.
16. 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.
17. Гэри, М. Вычислительные машины и труднорешаемые задачи / M. Гэри, Д. Джон-сон. – М. : Мир, 1982 .– 416 с.
18. Канторович, Л.В. Рациональный раскрой промышленных материалов / Л.В. Канто¬рович, В.А. Залгаллер. – Новосибирск : Наука, 1971. – 299 с.
19. Автобиография Леонида Витальевича Канторовича // Оптимизация : сб. науч. тр. СО АН СССР. – Новосибирск, 1982. – Bып. 28. – C. 50–57.
20. 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.
21. 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.
22. Beasley, J.E. An exact two-dimensional non-guillotine cutting tree search procedure / J.E. Beasley // Operations Research. – 1985. – Vol. 33. – P. 49–64.
23. 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.
24. 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.
25. Романовский, И.В. Решение задачи гильотинного раскроя методом переработки списка состояний / И.В. Романовский // Кибернетика. – 1969. – № 1. – С. 102–103.
26. 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).
27. 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.
28. Романовский, И.В. Алгоритмы решения экстремальных задач / И.В. Романовский. – М. : Наука, 1977. – 352 с.
29. Martello, S. Knapsack Problems: Algorithms and Computer Implementations / S. Martello, P. Toth. – Chichester : Wiley, 1990. – 296 p.
30. 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.
31. Липовецкий, А.И. К оптимизации свободного размещения прямоугольников / А.И. Липовецкий // Автоматическое проектирование в машиностроении. – Минск : Ин-т техн. кибернетики АН БССР, 1985. – С. 80–87.
32. Бухвалова, В.В. Задачи прямоугольного раскроя: метод зон и другие алгоритмы / В.В. Бухвалова. – СПб. : СПбГУ, 2001. – 96 с.
33. Картак, В.М. Матричный алгоритм поиска оптимального решения для задачи упаковки прямоугольников в полубесконечную полосу / В.М. Картак // Информационные технологии. – 2008. – № 2. – С. 24–30.
34. 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.
35. Martello, S. Exact solution of the two-dimensional finite bin packing problem / S. Martello, D. Vigo // Management Sciences. – 1998. – Vol. 44. – P. 388–399.
36. 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.
37. 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.
38. 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.
39. Тарновский, А.Г. Полиномиальный алгоритм решения задачи монораскроя / А.Г. Тарновский // Системы программного обеспечения решения задач оптимального планирования : тез. Одиннадцатой Всесоюз. школы (г. Кострома, 20–21 мая 1990 г.). – М. : ЦЭМИ, 1990. – С. 128–129
40. 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.
41. Наумович, Н.А. Экспериментальное исследование серий градиентных методов / Н.А. Наумович // Методы, алгоритмы и программы решения экстремальных задач : сб. науч. тр. – Минск : Ин-т техн. кибернетики АН БССР, 1985. – С. 98–111.
42. Ковалев, М.М. Эффективность градиентных алгоритмов раскроя / М.М. Ковалев, А.Г. Тарновский // Комбинаторно-алгебраические методы в дискретной оптимизации : межвуз. тематич. сб. науч. тр. – Нижний Новгород : НГУ, 1991. – С. 22–36.
43. Ковалев, М.М. Анализ эффективности серий градиентных алгоритмов раскроя / М.М. Ковалев, А.Г. Тарновский // Математическое обеспечение рационального раскроя в системах автоматизированного проектирования : тез. Всесоюзн. конф. – Уфа, 1988. – С. 62–65.
44. Тарновский, А.Г. САПР «РАСКРОЙ» – промышленная система раскроя материалов на персональных ЭВМ / А.Г. Тарновский // Методы решения экстремальных задач и смежные вопросы : сб. науч. тр. – Минск : Ин-т техн. кибернетики АН БССР, 1990. – С. 142–158.
45. Филиппова, А.С. Проблемы декодирования прямоугольных упаковок: краткий обзор современных технологий / А.С. Филиппова // Информационные технологии. – 2005. – № 12. – С. 13–19.
46. Методы локального поиска в задачах ортогонального раскроя и упаковки: аналитический обзор и перспективы развития / Э.А. Мухачева [и др.] // Информационные технологии. – 2004. – № 5. – С. 2–17.
47. 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.
48. 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.
49. 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.
50. Мухачева, А.С. Технология блочных структур локального поиска оптимума в задачах прямоугольной упаковки / А.С. Мухачева // Информационные технологии. – 2004. – № 5. Приложение. – С. 18–32.
51. 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.
52. Филиппова, А.С. Задача двумерной упаковки в полубесконечную полосу: численный эксперимент с алгоритмами локального поиска и с декодерами блочной структуры / А.С. Филиппова // Информационные технологии. – 2005. – № 6.– С. 32–45.
53. Мухачева, Э.А. Задача прямоугольной упаковки: методы локального поиска оптимума на базе блочных структур / Э.А. Мухачева, А.С. Мухачева // Автоматика и телемеханика. – 2004. – № 2. – С. 101–112.
54. Goldberg, D. Genetic Algorithms in Search, Optimization and Machine Learning / D. Goldberg. – Boston : Adison-Wesley, 1989. – 372 p.
55. Батищев, Д.И. Генетические алгоритмы решения экстремальных задач / Д.И. Бати¬щев. – Воронеж : ВГТУ, 1995. – 69 с.
56. Aarts, E.H.L. Local search in combinatorial optimization / E.H.L. Aarts, J.K. Lenstra. – Chichester : Wiley, 1997. – 528 p.
57. Норенков, И.П. Эвристики и их комбинации в генетических методах дискретной оптимизации / И.П. Норенков // Информационные технологии. – 1999. – № 1. – С. 2–7.
58. Мухачева, Э.А. Генетический алгоритм блочной структуры в задачах двумерной упаковки / Э.А. Мухачева, А.С. Мухачева, А.В. Чиглинцев // Информационные технологии. – 1999. – № 11. – С. 13–18.
59. 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.
60. Мухачева, А.С. Генетический алгоритм поиска минимума в задачах двумерного гильотинного раскроя / А.С. Мухачева, А.В. Чиглинцев // Информационные технологии. – 2001. – № 3. – С. 27–31.
61. 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.
62. 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.
63. 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.
64. Задачи двумерной упаковки: развитие генетических алгоритмов на базе смешанных процедур локального поиска оптимального решения / А.С. Мухачева [и др.] // Информационные технологии. – 2001. – № 9. Приложение. – С. 1–24.
65. 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.
66. Hertz, A. Tabu Search / A. Hertz, E. Taillard, D. de Werra // Local Search in Combinatorial Optimization. – Chichester : Wiley, 1997. – P. 121–136.
67. Метод поиска минимума с запретами в задачах двумерного гильотинного раскроя / Э.А. Мухачева [и др.] // Информационные технологии. – 2001. – № 6. – С. 25–31.
68. 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.
69. Dorigo, M. Ant algorithms for discrete optimization / M. Dorigo, G. Di Caro, L. Gambardella // Artificial Life. – 1999. – Vol. 5. – P. 137–172.
70. Валеева, А.Ф. Применение метаэвристики муравьиной колонии к задачам двумерной упаковки / А.Ф. Валеева // Информационные технологии. – 2005. – № 10. – С. 36–43.
71. 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.
72. 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.
73. 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.
74. Филиппова, А.С. Задача ортогональной упаковки в полубесконечную полосу: численный эксперимент с безотходными задачами E. Hopper / А.С. Филиппова, Э.А. Мухачева, А.В. Чиглинцев // Информационные технологии. – 2005. – № 7. – С. 45–54.
75. 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.
Рецензия
Для цитирования:
Головистиков А.В. ЗАДАЧИ ДВУМЕРНОЙ ПРЯМОУГОЛЬНОЙ УПАКОВКИ И РАСКРОЯ: ОБЗОР. Информатика. 2008;(4(20)):18-33.
Просмотров: 786
Послать статью по эл. почте 