ЗАДАЧИ ДВУМЕРНОЙ ПРЯМОУГОЛЬНОЙ УПАКОВКИ И РАСКРОЯ: ОБЗОР
Аннотация
Приводится обзор результатов по решению задач двумерной прямоугольной упаковки и раскроя. Рассматриваются основные формулировки, математические модели и алгоритмы решения задач ортогональной упаковки прямоугольных предметов в контейнер или полубесконечную полосу и двумерного прямоугольного (в том числе гильотинного) раскроя. Основное внимание уделяется эвристическим алгоритмам и метаэвристикам (генетическим алгоритмам, поиску с запретами, метаэвристике муравьиной колонии).
Список литературы
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.
Просмотров: 898
ISSN 1816-0301 (Print)
ISSN 2617-6963 (Online)
ISSN 2617-6963 (Online)
Послать статью по эл. почте 