Помощь в написании студенческих работ
Антистрессовый сервис

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

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

Высокие требования современного производства диктуют создание новых технологий проектирования и изготовления изделий, что должно вести к комплексной экономии всех видов ресурсов. Определяющими факторами успеха в промышленном производстве сегодня и в обозримом будущем являются: уменьшение времени выхода продукции на рынок, снижение стоимости и повышение качества. Значительное сокращение цикла… Читать ещё >

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

Содержание

  • Глава 1. Постановка задачи и обзор существующих методов решения задачи упаковки прямоугольных объектов
    • 1. 1. Автоматизация проектирования и технологической подготовки раскройно-заготовительного производства
    • 1. 2. Классификация задач раскроя-упаковки. Основные этапы развития
    • 1. 3. Приближенные методы решения задачи негильотинного прямоугольного раскроя
    • 1. 4. Точные методы решения задачи негильотинного прямоугольного раскроя
    • 1. 5. Математическая постановка задачи прямоугольной упаковки листов

Высокие требования современного производства диктуют создание новых технологий проектирования и изготовления изделий, что должно вести к комплексной экономии всех видов ресурсов. Определяющими факторами успеха в промышленном производстве сегодня и в обозримом будущем являются: уменьшение времени выхода продукции на рынок, снижение стоимости и повышение качества. Значительное сокращение цикла проектирования и подготовки производства, подразумевающее внедрение систем автоматизации проектирования (САПР) и автоматизированных систем технологической подготовки производства (АСТПП), может способствовать созданию конкурентоспособной продукции и своевременному выходу ее на рынок.

Среди множества задач, возникающих в проектировании, особое место занимают задачи, связанные с компоновкой и размещением объектов — задачи раскроя и упаковки. Среди многообразия постановок задач раскроя самостоятельный интерес представляют задачи прямоугольного раскроя. Это объясняется высокой долей прямоугольных заготовок в общей массе выкраиваемых деталей, применением прямоугольного раскроя при получении фигурных деталей. К таким задачам относятся, например, оптимизация складирования грузов, планирование помещений, проектирование систем, конструктивно выполненных в виде набора блоков, компоновка деталей. От качества решения этих задач зависит стоимость строительства, эффективность использования площадей, транспорта, складских помещений, технологичность, сокращение сроков и стоимости проектирования.

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

Условия мелкосерийного (единичного) производства требуют рассмотрения задач планирования раскроя как задачи целочисленного математического программирования (ЦМП). Точные методы решения задач данного класса не пригодны в условиях реального производства. Это объясняется сложностью задач и трудоемкостью их решения. Поэтому становится актуальной проблема разработки и использования эффективных эвристических оптимизационных методов решения задачи прямоугольного раскроя.

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

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

— разработаны математические модели задачи прямоугольной упаковки и определено их место в комплексной САПР раскроя-упаковки;

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

— модифицированы алгоритмы «первый подходящий с упорядочиванием», «последовательного уточнения оценок» и динамического перебора" для решения задач планирования прямоугольной упаковки листов;

— разработано программное обеспечение, реализующее предложенные методы и алгоритмы;

— проведен вычислительный эксперимент.

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

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

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

— модифицированы алгоритмы «первый подходящий с упорядочиванием», «последовательного уточнения оценок» и «динамического перебора» для решения задач планирования прямоугольной упаковки листов с учетом особенностей САПР единичного и мелкосерийного производства.

Практическая ценность. Разработанные в диссертации методы и алгоритмы служат оптимизационным ядром в САПР раскройно-заготовительного производства, а также применимы для решения большого круга других прикладных задач. Разработанное программное обеспечение может использоваться для решения задачи прямоугольного раскроя, нерегулярной упаковки в условиях единичного и мелко серийного производства, содержит развитый интерфейс и может использоваться как автономно, так и в составе САПР раскроя-упаковки.

На защиту выносятся:

1. Математические модели задачи прямоугольной упаковки в составе САПР раскроя-упаковки.

2. Модификация алгоритмов «первый подходящий с упорядочиванием», «последовательного уточнения оценок» и «динамического перебора» для решения задач планирования прямоугольной упаковки листов.

3. Методы и алгоритмы, реализующие преобразование структуры прямоугольной упаковки на основе ее топологических свойств.

4. Программное обеспечение, реализующее разработанные алгоритмы размещения прямоугольников.

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

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

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

2. Изучены топологические свойства прямоугольной упаковки и разработаны алгоритмы, реализующие преобразование структуры прямоугольной упаковки.

3. На основе разработанных алгоритмов, создано программное обеспечение, которое имеет развитый интерфейс и может использоваться автономно или в составе САПР и АСТП раскройно-заготовительного производства в различных отраслях промышленности, что гарантирует сокращение сроков проектирования карт раскроя в несколько раз при расчете научно-обоснованных норм расхода материала.

4. Предложена методика создания подсистемы рационального двухмерного раскроя-упаковки и включения ее в САПР раскрояупаковки.

ЗАКЛЮЧЕНИЕ

.

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

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

Показать весь текст

Список литературы

  1. Автоматизированная система технологической подготовки производства в машиностроении, /под ред. Г. К. Горанского. -М.: Машиностроение, 1976. -240с.
  2. Автоматизация проектно-конструкторских работ и технологической подготовки производства в машиностроении, Т1, Т2 /под ред. О. И. Семенкова. -Минск: Вышэйшая школа, 1977. -312с.
  3. Автоматизация технологической подготовки заготовительного производства / под общей ред. Г. П. Гырдымова. -Ленинград: Машиностроение, 1990. -350с.
  4. Г. В., Березнв В. А., Брежнева O.A. О методе решения уравнения с булевыми переменными //Принятие решений в условиях неопределенности: межвуз. научный сб. -Уфа, 1990. -С. 145−146.
  5. В.В. и др. информационное обеспечение ИПК. -М.: Машиностроение, 1986. -283с.
  6. О.Г. Комплексное применение методов дискретной оптимизации. -М.: Наука, 1987. -247с.
  7. Т.М. Автоматизация информационных процессов в интегрированных АСУ промышленным производством. -М.: Машиностроение, 1981.-315с.
  8. И.Б. Интегрированная АСУ в машиностроении. -М.: Машиностроение, 1988. -290с.
  9. Е.И. Проблемы разработки систем автоматизированного проектирования //Приборы и системы управления, 1981. -№ 2.
  10. Ю.Ахо А. и др. Построение и анализ вычислительных алгоритмов. -М.: Мир, 1979. -536с.
  11. Ф.В. Оптимальный раскрой материалов с помощью ЭВМ. -М.: Машиностроение, 1982. -168с.
  12. Р., Дрейфус С. Прикладные задачи динамического программирования. -У.: Наука, 1965. -458с.
  13. Л.Б. О развитии математического обеспечения оптимального раскроя фигурных заготовок // Математическое обеспечение рационального раскроя в системах автоматизированного проецирования: Тез.докл. всесоюзной конференции. -Уфа, 1988. -С. 103−109.
  14. Л.Б., Рябина Н. О. Проектирование на ЭВМ оптимального раскроя заготовок при листовой штамповке сложных форм //Кузнечно-штамповочное производство, 1977. -№ 11. -С.25−28.
  15. Т.К., Верхотуров М. А. Некоторые аспекты проблемы построения рационального плана нерегулярного раскроя на заготовки сложных форм //Принятие решений в условиях неопределенности: межвуз. научный сб. -Уфа, 1990. -С.117−120.
  16. Ю.А., Пазюк В. А., Хейло C.B. Диалоговая система рационального раскроя металла //Применение ЭВМ в решении научно-технических задач.: Тез. докл. I Республиканской конференции молодых ученых. Уфа, 1985. -52с.
  17. В. В. Реализация метода зон Липовецкого для прямоугольного раскроя //Математическое обеспечение рационального раскроя в системах автоматизированного проектирования: Тез.докл. всесоюзной конференции. -Уфа, 1987. -С. 16−17.
  18. А.Д. Задачи об упаковки прямоугольников в полосу (обзор) //Управляющие системы, ИМ СОАН СССР, 1984., вып.25.
  19. А.Д. Приближенные алгоритмы упаковки прямоугольников с априорными оценками погрешности //Математическое обеспечение рационального раскроя в системах автоматизированного проектирования: Тез.докл. всесоюзной конференции. -Уфа, 1987. -С.26−27.
  20. А.Ф., Мухаметзянов Р. З., Тихомиров С. К., Юлдыбаева Ж. Л. Алгоритмы решения задачи плотной упаковки геометрических объектов./ Принятие решений в условиях неопределенности: Межвуз. науч. сб. Уфа, 1996. — с. 30−34.
  21. P.A. Вопросы развития работ по созданию систем автоматизированного проектирования процессов кузнечно-штамповочного производства //Кузнечно-штамповочное производство, 1985. -№ 8.
  22. Г. Основы исследования операций. -М.: Мир, 1973. -т. 1,2,3.
  23. Ю.Х. Основы автоматизации проектирования. -М.: Радио и связь, 1988.-279с.
  24. А.П., Ефремов А. И. Автоматизация технологической подготовки машиностроительного производства. -Киев: Техника, 1982. -215с.
  25. В.Я., Липовецкий AM., Петунин A.A. Автоматизация проектирования раскройных карт в условиях индивидуального производства // Кузнечно-штамповочное производство, 1982. -№ 3. -С.26−27.
  26. Гривачевский А. П Автоматизация проектирования технологической подготовки холодно штамповочного производство //Кузнечно-штамповочное производство, 1985. -№ 8. -С.28−30.
  27. Г. К., Бендарева 9.И. Технологическое проектирование в комплексных автоматизированных системах подготовки производства. -М.: Машиностроение, 1981. -455с.
  28. М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. -М.: Мир, 1982. -416с.
  29. В.А. Применение теории графов, а программировании. -М.: Наука, 1985.
  30. O.A. К комбинаторным задачам размещения прямоугольников //Математическое обеспечение рационального раскроя в системах автоматизированного проектирования: Тез.докл. всесоюзной конференции.-Уфа, 1987.-С.63.
  31. В.В., Фридман Д. С., Розенфельд В. Х. Оптимизация раскроя проката. -М.: Металлургия, 1984. -159с.
  32. Жак C.B. О методах решения задач, сочетающих эвристику и случайный выбор // Кибернетика, 1972. -№ 1. -С. 119−121 ю35.3алгаллер В. А. Раскрой линейных материалов. -:Егоровец, 1949. -220с.
  33. М.В. Рациональный раскрой заготовок//Машиностроитель, 1982. -№ 5.
  34. Л.В. Математические методы в организации и планирования производства. -П.: ЛГУ, 1939. -60с.
  35. Л.В. Методы рационального раскроя металла //Произ-водственно-техн. бюллетень НК боеприпасов. -М., 1942. -35с.4!Канторович Л. В., Горстко A.B. Математическое оптимальное программирование. -М.: Экономика, 1968. -96с.
  36. Л.В. Экономический расчет наилучшего использования ресурсов. -М.: Изд-во АН СССР, 1959. -348с.
  37. Л.В., Залгаллер В. А. Расчет рационального раскроя промышленных материалов. -Л.: Лениздат, 1951, -199с.
  38. Л.В., Залгаллер В. А. Рациональный раскрой промышленных материалов. -Новосибирск: Наука, 1971, -299с.
  39. А. В в ведение в прикладную комбинаторику. -М.:Наука, 1975. -447с.
  40. Лекции по теории графов /Емеличев В.А., Мельников О. И. и др. -М.: Наука, 1990. -384с.
  41. А.И. Свойства прямоугольных укладок и алгоритмы оптимального раскроя: Препринт. -Свердловск: Уро АН СССР, 1988. -50с.
  42. А.И. Сокращение перебора при автоматизированном проектировании прямоугольного раскроя //Автоматизация технологической подготовки производства: Межвузовский сборник. Свердловск: изд. УПИ им. Кирова, 1986. -С.77−86.
  43. А.И. К оптимизации свободного размещения прямоугольников //Автоматизация проектирования в машиностроении. -Минск: ИТК АН БССР, 1985. -С.80−87.
  44. А.И. Алгоритмы негильотинного прямоугольного раскроя // Математическое обеспечение рационального раскроя в САПР: материалы всесоюзной конференции: -Уфа, 1988, -с.72−79.
  45. Математическое обеспечение расчетов линейного и прямоугольного раскроя: Материалы всесоюзного семинара. -Уфа: УАИ, 1981. -179с.
  46. Математическое обеспечение рационального раскроя в системах автоматизированного проектирования: Материалы всесоюзной конференции. -Уфа: УАИ, 1988. -159с.
  47. Методология разработки и внедрения автоматизированной системы проектирования технологической подготовки производства: Тез. докл. научно-техн. конференции. -Минск, Бел. НИИ НТИ, 1979. -63с.
  48. Э.А. Рациональный раскрой промышленных материалов. Применение в АСУ. -М.: Машиностроение, 1984. -176с.
  49. Э.А. Многовариантная схема генерирования раскроев в пакете «Рациональный раскрой 2» И Математическое обеспечение расчетов линейного и прямоугольного раскроя: Материалы всесоюзного семинара. -Уфа, 1981. -С6−24.
  50. Э.А., Рубинштейн Г. С. Математическое программирование. -Новосибирск: Наука, 1977.-319с.
  51. Э.А., Валеева А. Ф. К разработке САПР рационального раскроя //Применение ЭВМ в решении научно-технических и народно-хозяйственных задач: Тез.докл.респ. конф. -Уфа, БФАН СССР, 1985. С.95−96.
  52. Э.А., Мухаметзянов Р. З., Шехтман Л. И. Декомпозиционные алгоритмы в задачах распределения двух- и трехмерного ресурса //Проблемы оптимизации и экономические приложения: Междунар. науч.-техн. конф. -Омск, 1997.-е. 113.
  53. Э.А., Николаева М. А., Ибатуллина С. М., Валеева А. Ф. Информационная система технологического проектирования «Раскрой» //Диалог-Человек-ЭВМ: тез.докл.конф. -Свердловск, АН СССР, 1989. -50с.
  54. Р.З. Структурные преобразования прямоугольныхупаковок. Рукопись деп. в ВИНИТИ, № 98-В99 от 18.01.99.
  55. М.В. Решение задачи поиска глобального экстремума линейной функции цели на структуре линейных неравенств. -Харьков, 1988. -48с. (Препринт / АН УССР, Инс-т пробл. машиностроения)
  56. X., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. -М.: Мир, 1985. -512с.
  57. Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. -М.: Мир, 1980. -466с.
  58. Л.Ф., Тарасова Т. Д. Использование метода последовательного уточнения оценок при решении задачи прямоугольного раскроя //Применение САПР в машиностроении: Тез.докл. конференции. -Свердловск, 1989. -С.51−53
  59. И.В. Алгоритмы решения экстремальных задач. -М.: Наука, 1977. -351с.
  60. М., Тхуласироман К. Графы, сети, алгоритмы. -М.: Мир, 1984. -454с.
  61. Свид-во о гос.per. программы на ЭВМ № 940 517. Программа решения задачи рационального использования ресурсов для выполнения различных работ / Валеева А. Ф., Мухаметзянов Р.З./ -М.- РосАПО, 16.12.94.
  62. Свид-во о гос.per. программы на ЭВМ № 960 295. Трехмерная упаковка предметов / Мухаметзянов Р. З., Тоцков И. Е. / -М.- РосАПО, 08.07.96.
  63. В.А. Оптимизация раскроя материалов в легкой промышленности. -М.: Легпробытиздат, 1989. -144с.
  64. Ю.Г., Гиль Н. И. Методы и алгоритмы размещения плоских геометрических объектов. -Киев: Наукова думка, 1976. -247с.
  65. У1.Стоян Ю. Г., Новожилова М. В. Метод поиска локального экстремума в задаче размещения многоугольников в полосе. -Харьков, 1987. -24с. (Препринт / АН УССР, Инс-т пробл. машиностроения)
  66. Ю.Г., Новожилова М. В., Карташов М.В.
  67. Ю.Г., Яковлев С. В. Математические модели и оптимизационные методы геометрического проектирования. -Киев: Наукова думка, 1980. -268с.
  68. Т.Д. О некоторых постановках задач линейного раскроя // Математическое обеспечение рационального раскроя в системах автоматизированного проектирования: Материалы всесоюзной конференции. -Уфа, 1988. -С.39−44.
  69. С., Гудман С. Введение в разработку и анализ алгоритмов. -М.: Мир, 1981. -361с.
  70. В.В., Саенко Ю. И. О решении задач оптимального раскроя. -Журн. вестник машиностроения, 1965. -С.27.
  71. Г., Краузе Ф.-Л. Автоматизированное проектирование в машиностроении. -М.: Машиностроение, 1988.-648с.
  72. Hofri Micha Two-dimensional packing: expected performance of simple level algorithms. -Inform, and Contr., Vol.45, N1, 1980.
  73. Kartack V.M., Mukhametzyanov R.Z. Method of rectangular packing calculation // Decision marking under conditions of uncertainly: The International Scientific Collection, SATU of Ufa, 1997, -p.178−188.
  74. Morabito, R., Arenales, M. An AND/OR-Graph Approach to the Container Loading Problem.//lnternational Transactions in Operational Research, Vol.1, N1,1994, p.59−73.
  75. Schwerm P., Wascher G. The Bin-Packing Problem: A problem Generator and Some Numerical Experiments with FFD Packing and MTP. //International Transactions in Operational Research, 1997, N4, p.337−389.
Заполнить форму текущей работой

Сессия? Спокойно!