автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.16, диссертация на тему:Алгоритмы плотной упаковки прямоугольных объектов на базе аппроксимации линейным раскроем

Введение.

Глава 1. Задачи одно и двухмерного раскроя-упаковки и методы их решения.

1.1. Классификация задач раскроя-упаковки.

1.2. Задача одномерной целочисленной упаковки.

1.2.1. Математические модели одномерного раскроя-упаковки.

1.2.2. Методы решения задач линейного раскроя-упаковки, основанные на использовании линейного программирования.

1.2.3. Эвристические методы расчета одномерного раскроя-упаковки.

1.2.4. Точные методы расчета одномерного раскроя-упаковки.

1.3. Задача прямоугольной упаковки.

1.3.1. Постановка задачи прямоугольной упаковки.

1.3.2. Эвристические методы решения задачи прямоугольной негильотинной упаковки.

1.3.3. Точные методы решения задачи негильотинного прямоугольного раскроя.

1.4. Постановка задачи исследования.

1.5. Основные результаты главы 1.

Глава 2. Задачи одномерного целочисленного раскроя-упаковки: вычислительный эксперимент.

2.1.Краткая характеристика исследуемых методов решения одномерного раскроя-упаковки.

2.1.1. Метод первый подходящий с упорядочиванием (FFD).

2.1.2. Метод последовательного уточнения оценок (SVC).

2.1.3. Модифицированный метод ветвей и границ (МКК).

2.2. Эксперименты для одномерного раскроя-упаковки с методами SVC и SVCR.

2.2.1. Тестовые задачи.

2.2.2. Результаты эксперимента с методами SVC и ÍSVCR.

2.3. Эксперимент для одномерного раскроя-упаковки с методом МКК.

2.3.1. Тестовые задачи.

2.3.2. Результаты эксперимента с методом МКК.

Проблема оптимального раскроя-упаковки объединяет различные по математической и прикладной ^остановке задачи. В литературе они встречаются под разными названиями: задачи раскроя, упаковки, размещения, загрузки, распределения ресурсов и т.д. Общим для них является наличие двух групп объектов. К первой группе относятся большие объекты, ко второй -малые. Требуется установить соответствие и порядок назначения между ними так, чтобы некоторая целевая функция достигала минимум при выполнении определенных ограничений.

Диссертационная работа посвящена разработке алгоритмов для решения задач плотной упаковки прямоугольных объектов в прямоугольной области на основе ее линейной аппроксимации. Эта задача является ИР-трудной и отыскание даже псевдополиномиального точного алгоритма для ее решения невозможно. Поэтому наряду с громоздкими точными алгоритмами получили широкое распространение различные эвристики. От эвристических алгоритмов требуется хорошее приближение к точному решению и быстрота исполнения. Этим качеством удовлетворяют алгоритмы, основанные на линейной аппроксимации. Однако, задача линейного раскроя, аппроксимирующая прямоугольную упаковку, так же является ЫР-трудной. В связи с этим выбор подходящего алгоритма для ее решения так же представляет определенные трудности. Этим обстоятельством и объясняется научная актуальность проблемы в целом. Что касается актуальности работы на практике, то ее трудно переоценить. Создание быстрых и достаточно точных алгоритмов позволит решать массу практических задач, связанных, так или иначе, с использованием материальных ресурсов. Что является особенно актуальным на фоне современной тенденции сохранения и сбережения природных ресурсов.

Диссертация посвящена разработке и исследованию эффективности приближенных эвристических алгоритмов для решения задачи прямоугольной упаковки: аппроксимации линейным раскроем с целью получения начального решения; созданию детерминированного и стохастического алгоритмов продолжения и оценки улучшенного решения; проведению и анализу вычислительных экспериментов.

Научная новизна диссертационной работы заключается в следующем:

• разработаны методы и условия аппроксимации прямоугольной упаковки линейным раскроем;

• предложены нижние границы для оценки полученных решений;

• разработан быстрый детерминированный алгоритм улучшения начального решения с использованием топологических свойств упаковок;

• разработан генетический алгоритм улучшения начального решения;

• исследована эффективность алгоритмов линейного раскроя и прямоугольной упаковки.

Предложенные в диссертации алгоритмы ориентированы на широкий класс прикладных задач. Их адаптация к конкретным производственным условиям не представляет особого труда. Это и составляет практическую значимость работы.

Работа выполнялась по заданию ФЦП "Интеграция", проект 76, а также на завершающем этапе при поддержке Российского Фонда Фундаментальных Исследований, проект 99-01-00937.

Результаты работы докладывались и обсуждались: на конференции "Математическое программирование и приложения" в 1997 и 1999 годах; институте математики и механики УрО АН РФ, г. Екатеринбург; на международной конференции "Проблемы оптимизации и экономические приложения", в 1997 г. институте математики СО РАН РФ, г. Омск; на международной научной конференции «Оптимизация численных методов» в 1998 г. институте математики ИМВЦ УНЦ РАН; на международной сибирской конференции по исследованию операций, ИМ СО АН РФ, 1998 г.; на XVIII международной конференции "Исследование операций", г. Брюссель; на научных семинарах ИМ БФ АН РФ; математического факультета БГУ и кафедры вычислительной математики и кибернетики УГАТУ, кафедры «исследования операций» С. Петербургского государственного университета.

Диссертация состоит из введения, четырех глав, списка цитируемой литературы и приложения.

4.3. Основные результаты и выво л главы 4

1. В рамках проведенных экспериментов была ; одтверждена следующая гипотеза: «эффективность алгоритма определяется параметрами задачи по ширине и мало зависит от параметров задачи по ине».

2. Показано, что эффективность разработанных ал горитмов плотной упаковки на базе аппроксимации линейным раскроем, а к jhho детерминированного «перестройка» (REC) и стохастического «генетического» (GEN), значительно выше известных эвр, ических алгоритмов «последовательного уточнения оценок» (SVC) i. < динамического перебора» (DS).

3. Замечено, что эффективность разработанного алгоритма REC возрастает с увеличением заготовок по ширине.

4. Была исследована эффективность различных схем реализации генетического алгоритма, касающаяся процедуры скрещивание . И выявлено, что лучшие результаты дает алгоритм с более простой процеду рой скрещивания.

5. Для эвристических алгоритмов (SVC, DS, R 1 J, GEN) решения задач прямоугольной упаковки выявлены классы al-оч /■ > трудные, al- трудные и al-легкие.

ЗАКЛЮЧЕНИЕ

1. На базе линейной аппроксимации разработаны два эвристических алгоритма для решения задачи прямоугольной упаковки: REC (перестройка) и GEN (генетический). С этой целью:

1.1. введено понятие прямоугольно ориентированного линейного раскроя (ROLC), сформулированы и доказаны необходимые и достаточные условия для ROLC;

1.2. введены понятия ослабленного (d.ROLC) и сильно ослабленного (e.d.ROLC) прямоугольно ориентированного линейных раскроев, разработаны алгоритмы их построения;

1.3. рассмотрены топологические свойства прямоугольных упаковок, сформулированы и доказаны необходимые и достаточные условия эквивалентности d.ROLC и ROLC;

1.4. предложены новые нижние границы RP, позволившие более точно оценивать эффективность алгоритмов и находить хорошее начальное приближение;

1.5. произведено структурирование d.ROLC и определение генетических элементов: гена, аллели, локуса, хромосомы, особи;

1.6. введены генетические процедуры скрещивания, мутации, селекции.

2. Произведены вычислительные эксперименты с ВРР и RP задачами. Анализ результатов экспериментов позволил сделать следующие выводы:

2.1. алгоритм SVCR для решения задачи линейного раскроя вполне ориентирован на решение задачи d.ROLC: с его помощью определяется приближенная нижняя граница RP и начальное решение, которое принимается в качестве верхней границы;

2.2. алгоритмы REC и GEN полиномиальной сложности превосходят по своей эффективности (трудоемкость и близость к оптимуму) ранее разработанные алгоритмы FFD, SVC и DS;

2.3. генетический алгоритм значительно превосходит по эффективности и трудоемкости все рассмотренные алгоритмы.

1. Arenales M.N., Morabito R.N. An AND/OR graph approach to the solution of two-dimensional non-guillotine cutting problems. European Journal of Operational Research. 1995, vol.84, pp.559-617.

2. Arenales M.N., Morabito R.N. An AND/OR-graph approach to cutting and packing problems. Decision Making under Conditions of Uncertainty (Cutting -Packing Problems). The International Scientific Collection. Ufa. 1997. p. 207-225.

3. Beasley J.E. An exact two-dimensional non-guillotine cutting tree search procedure. Operational Research. 1985, vol.33, pp.49-64.

4. Belov G. A modified sequential values correction method for the one-dimensional cutting stock problem. // Decision Making under Conditions of Uncertainty (Cutting-Packing Problems). The International Scientific Collection. Ufa. 1997. p. 41-47.

5. Dudzinski K., Walukiewicz S. Exact methods for the knapsack problem and its generalizations. European Journal of Operational Research. 1987. vol.28, pp.3-21.

6. Dyckhoff H. A Typology of Cutting and Packing Problems. //European Journal of Operational Research. 1990.v.44.p.l45-159.

7. Falkenauer E. The Grouping Genetic Algorithms Widening the Scope of the Gas. JORBEL - Belgian Journal of Operations Research, Statistics and Computer Science, 1993, vol. 33 (1,2), pp. 79-102.

8. Falkenauer E. The Grouping Genetic Algorithms for Bin Packing. JORBEL -Belgian Journal of Operations Research, Statistics and Computer Science, 1995, vol. 35, pp. 64-88.

9. Galambus G., Van Vliet A. Louwer bounds for 1-, 2- and 3-dimensional on-line bin packing algorithms. Computing vol. 52, pp. 281-297.

10. Garey M.R., Jonson D.S. Computersand Intractability: A Guide to the Theory of NP-Completeness. // Freeman. San Francisco. CA. 1979.

11. Gau T., Wascher G. CUTGEN1: A problem generator for the standard one-dimensional cutting stock problem. European J. Oper. Res. 1995, 84, p.572-579.

12. Gehring H., Bortfeldt A. A Genetic Algorithm for Solving the Container Loading Problem. // International transactions in operational research. 1997, vol.4, № 5/6, p. 401-418.

13. Khan L.R. An exchange heuristic for the bin packing problem. For presentation at the Triennial conference of IFORS. Vancouver, British Columbia, Canada, Juli 812, 1996.

14. Marcotte O. The cutting stock problem and integer rounding. Mathematical Programming, 33(1): 82-92,1985

15. Martello S., Toth P. Lower Bounds and Reduction Procedures for the Bin Packing Problem. Discrete Applied Mathematics. 1990, vol. 22. North-Holland, Elsevier Science Publishers B.V., pp.59-70.

16. Martello S., Toth P. Knapsack problems: Algorithms and Computer Implementations. John Wiley, Chichester. Ong H.L., Magazine M.J. and Wee T.S. (1984) Probabilistic analysis of bin packing heuristics. // Operations Research. 1990. v. 32. p. 983-998.

17. Martello S., Vigo D., Exact solution of two-dimensional finite bin packing problem. Management Science. 1997, vol. 35, pp. 68-74.

18. Mukhacheva E.A. One-dimensional bin packing problems. Models and methods. Decision Making under Conditions of Uncertainty (Cutting Packing Problems). The International Scientific Collection. Ufa. 1997. p. 7-14.

19. Mukhacheva E.A., Zalgaller V.A. Linear Programming Cutting Problems. // International Journal of Software Engineering and Knowledge Engineering. 1993. v. 3. №4. p. 463-476.

20. Richter K. Solving sequential interval cutting problems via dynamic programming. European Journal of Operational Research. 1992, vol.57, pp.332338.

21. Scheithauer G. The solution of packing problems with piece of variable length and additional allocation constraints. Optimization. Vol 34, pp. 81-96.

22. Scheithauer G., Terno J. The modified integer round-up property of the one-dimensional cutting stock problem. European J. Oper. Res., 84: 562-571,1995.

23. Scheithauer G., Terno J. Theoretical investigation on the modified integer roundup property of the one-dimensional cutting stock problem. Technical report, MATH-NM-23-1995, TU Dresden, 1995.

24. Scheithauer G, Terno J. A heuristic approach for solving the multi-pallet packing problem. Decision Making under Conditions of Uncertainty (Cutting Packing Problems). The International Scientific Collection. Ufa.1997. p. 140-155.

25. Schwerin P., Wäscher G. The Bin-Packing Problem: A problem Generator and

26. Some Numerical Experiments with FFD Packing and MTP. // International Transactions in Operational Research. 1997.v. 4. № 5/6. p.337-389.

27. Serker B.R., An optimum solution for one-dimensional slitting problems: a dynamic programming approach. European Journal of Operational Research. 1988, vol.39, pp.749-755.

28. Simchi-Levi D. New worst-case results for the bin packing problem. Naval Res. Log.Quart. 1994. vol.41, pp. 579-585.

29. Sinuany-Stern Z., Weiner I. The one-dimensional cutting stock problem using two objectives. Journal of Operational Research. 1994, vol.45, pp.231-236.

30. Stadtler H. A comparison of two optimization procedures for 1- and 1,5-dimensional cutting stock problems. Oper. Res. Spekt. 1988,10, p.97-111.

31. Terno J., Lindeman R., Scheithauer G. Zuschnitprobleme und ihre prakti-sche Losung. -Leiprig, 1987, p.207.

32. Van Driessche R., Piessens R. Load Balancing With Genetic Algorithms. Proceedings of the second Conference on Parallel Problem Solving from Nature (PPSN2), Brussels, Belgium, September 28-30, 1992.

33. Vasko F.J., Cregger M.L., Newhhart D.D., Stott K.L. A real-time one-dimensional cutting stock algorithm for balanced cutting patterns. Oper. Res. Lett. 1993, 14, p.275-282.

34. Von Laszewski G. Intelligent Structural Operators for the k-way Graph Partitioning Problem. Proceedings of the Fourth International Conference on Genetic Algorithms. San Diego, July 13-16, 1991.

35. Wascher G., Gau T. Heuristics for the one-dimensional cutting stock problem: a computational study. Oper. Res. Spekt. 1996,18, p.131-144.

36. Аккуратов Г.В., Березнев B.A., Брежнева O.A. О методе решения уравнения с булевыми переменными. Принятие решений в условиях неопределенности: межвуз. научный сб. Уфа, 1990. с. 145-146.

37. Батищев Д.И. Генетические алгоритмы решения экстремальных задач. /Под ред. Академика АЕН Я.Е.Львовича: Учеб. Пособие. Воронеж. Гос. Техн. Унт; Нижегородский гос. Ун-т. Воронеж, 1995. 69 с.

38. Бронштейн Е.М., Валеева А.Ф., Мухачева Э.А. Линейный способ построения прямоугольной упаковки. Оптимизация, Новосибирск, ИМ СЩ РАН, 1993, вып.51(69). с.34-42.

39. Бухвалова В.В. Реализация метода зон Липовецкого для прямоугольного раскроя. Математическое обеспечение рационального раскроя в системахавтоматизированного проектирования. Тезисы докл. всесоюзной конференции. Уфа, 1987, с. 16-17.

40. Вайнштейн А.Д. Задачи об упаковки прямоугольников в полосу (обзор) // Управляющие системы, ИМ СОАН СССР, 1984, вып.25.

41. Валеева А.Ф. Негильотинный прямоугольный раскрой на базе применения методов математического программирования в автоматизированных системах управления. Диссертация на соискание ученой степени кандидата технических наук. Уфа, 1993 г.

42. Валеева А.Ф. Алгоритм прямоугольной упаковки и применение его к задаче фигурного раскроя. // Труды международной конференции по прикладной и индустриальной математике. Новосибирск, ИМ СО РАН, 1997, с.46-56.

43. Гери М.П., Джонсон Д.С. Вычислительные машины и трудноразрешимые задачи. -М.; Мир, 1987. -272с.

44. Канторович JI.B., Залгаллер В.А. Рациональный раскрой промышленных материанов. -Новосибирск: Наука СО, 1971. -320с.

45. Картак В.М. Модели и методы оптимизации упаковки N-мерных параллелепипедов. Диссертация на соискание ученой степени кандидата физико-математических наук. Уфа, 1999г.

46. Кацев C.B. Об одном классе дискретных минимаксных задач. Кибернетика,3, Киев, 1979,113-118.

47. Кофман А. Введение в прикладную комбинаторику. -М. Наука, Гл. ред. физ.-мат. лит., 1975. -447 с.

48. Липовецкий А.И. Свойства прямоугольных укладок и алгоритмы оптимального раскроя. Свердловск: Уро АН СССР, 1988. -50 с.

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

50. Липовецкий А.И. Алгоритмы негильотинного прямоугольного раскроя. Математическое обеспечение рационального раскроя в САПР: Материалы всесоюзной конференции: Уфа, 1988, с. 72-79.

51. Мухаметзянов Р.З. Структурные преобразования прямоугольных упаковок. . //Рук. Деп. в ВИНИТИ. №53-В99. от 18.01.1999. -15 с.

52. Мухачева A.C. Алгоритмы плотной упаковки прямоугольных объектов на базе аппроксимации линейным раскроем. // Рук. Деп. в ВИНИТИ. №53-В99. от 14.01.1999. -18 с.

53. Мухачева A.C. Житников В.П. Метод оценок для решения задач линейной и прямоугольной упаковки. Международная научная конференция. Оптимизация численных методов. Уфа, 1998. с.40.

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

55. Мухачева Э.А., Верхотуров М.А., Мартынов В.В. Модели и методы расчета раскроя-упаковки геометрических объектов. Уфа, 1998. -216с.

56. Мухачева Э.А., Мухачева A.C. Методы генерации прямоугольной упаковки на базе аппроксимации линейным раскроем. // Информационный бюллетень №8. Конференция Математическое программирование и приложения (тезисы докладов). Екатеринбург. 1999., 205-206с.

57. Мухачева Э.А., Рубинштейн Г.Ш. Математическое программирование. -Новосибирск: Наука. -1987. -274с.110

58. ГРАФИК ПОВЕДЕНИЯ АЛГОРИТМА SVCR

59. Элементов т = 80; Нижняя граница N0 = 30; Оптимальное решение Nonm = 30

60. Итерации N опт = 30, N о = 301. Ширина полосы W=255;1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

61. Ми 38 39 39 39 40 41 41 42 43 45 45 45 45 46 46 47 48 48 50 51и 123 58 112 124 70 40 96 100 111 117 114 67 69 82 89 104 39 38 47 1001. АЛГОРИТМ ИКСхо хз 9 15 Х6 б 18 1г 14 XX 8 4 5 12 Х9 1. X 2 20 7 3

62. Метод : Первый подходящий о перестройкой <сверху вниз) Нижняя граница = 3 08

63. Длина = 310 Ширина. = 255 Отн< Ю = Ю1 Вреия( сех/ЮО) = 6Х1. АЛГОРИТМ GEN

64. Генетический Алгоритм .А 1трио1од.1х11. Файл Настройки Помощь