Помощь в учёбе, очень быстро...
Работаем вместе до победы

Алгоритмы плотной упаковки прямоугольных объектов на базе аппроксимации линейным раскроем

Диссертация: Алгоритмы плотной упаковки прямоугольных объектов на базе аппроксимации линейным раскроем
ДиссертацияПомощь в написанииУзнать стоимостьмоей работы

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

Содержание

  • Глава 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. Основные результаты главы
  • Глава 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 и ISVCR
    • 2. 3. Эксперимент для одномерного раскроя-упаковки с методом МКК
      • 2. 3. 1. Тестовые задачи
      • 2. 3. 2. Результаты эксперимента с методом МКК

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

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

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

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

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

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

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

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

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

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

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

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

Результаты работы докладывались и обсуждались: на конференции «Математическое программирование и приложения» в 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.332 338.
  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., Wascher 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. Э.А. Рациональный раскрой промышленных материалов: Применение АСУ. -М.Машиностроение, 1984. -176с.
  54. Э.А., Верхотуров М. А., Мартынов В. В. Модели и методы расчета раскроя-упаковки геометрических объектов. Уфа, 1998. -216с.
  55. Э.А., Мухачева A.C. Методы генерации прямоугольной упаковки на базе аппроксимации линейным раскроем. // Информационный бюллетень № 8. Конференция Математическое программирование и приложения (тезисы докладов). Екатеринбург. 1999., 205−206с.
  56. Э.А., Рубинштейн Г. Ш. Математическое программирование. -Новосибирск: Наука. -1987. -274с.110
  57. ГРАФИК ПОВЕДЕНИЯ АЛГОРИТМА SVCR
  58. Элементов т = 80- Нижняя граница N0 = 30- Оптимальное решение Nonm = 30
  59. Итерации 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
  60. Ми 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
  61. Метод: Первый подходящий о перестройкой <�сверху вниз) Нижняя граница = 3 08
  62. Длина = 310 Ширина. = 255 Отн< Ю = Ю1 Вреия (сех/ЮО) = 6Х1. АЛГОРИТМ GEN
  63. Генетический Алгоритм .А 1трио1од.1×11. Файл Настройки Помощь
Заполнить форму текущей работой

Пора сдавать?