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

Я

Ч Г

УРАЛЬСКИЙ ОРДЕНА' ТРУДОВОГО КРАСНОГО ЗНАМЕНИ ПОЛИТЕХНИЧЕСКИЙ ИНСТИТУТ им.С'.Л.КИРОВА

На правах рукописи

Корницкая Маргарита Нияолаевна

АВТОМАТИЗАЦИЯ ПРОЕКТИРОВАНИЯ КАРТ ФИГУРНОГО НЕРЕГУЛЯРНОГО РАСКРОЯ В УСЛОВИЯХ ЕДИНИЧНОГО ПРОИЗВОДСТВА НА ОСНОВЕ АППРОКСИМАНИОННОГО ПОДХОДА

Специальность 05.13.12 - Системы автоматизации

проектирования

Автореферат

диссертации на соискание ученой степени . кандидата технически* наук.

Свердловск 1920

"...у /-">,->

-7 ; /^¿-Л

Работа выполнена в Уральском ордена Трудового «Красного Знамени политехническом институте имени С.М.Кирова

Научный руководитель - доктор технических наук, профессор , ВайсСурд P.A.

Официальные оппоненты: доктор технических наук, профессор

Мухачева З.А., • кандидат технических наук Старостин Н.Д.

■Ведущее предприятие — -Центральный научно-исследовательский

. ИНСТИТУТ Металлург«;;; üä-iepEBJäOB,

т.Свсрдловск -

Защита состоится 21 декабря 1990 г., ауд.Р-237 на заседании специализированного совета К.063.13 по Л присувденив ученой степени кандидата технических наук в Уральском ордена Трудового Красного Знамени политехническом институте им.С.fi.Кирова

С диссертацией'«окно ознакомиться в библиотеке института. Отзывы.на автореферат водном экземпляре с подписью, заверенной гербовой печатьо, просим присылать по адресу: 620002,*г.Свердловск,К-2, УДИ им.С.Н.Кирова, ученому секретари института.

Автореферат разослан "" 13" НРЯбЬЯ 1990 г.

Ученый секретарь • '

специализированного совета K.063.I4.I3 ' '■ ,

кандидат технических наук (¿iSP*" £ухих

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность работы. ?кономия материальных ресурсов представ-ют для народного хозяйства важную проблему. Наибольшие резервы • шкения материалоемкости продукции скрыты в изменении технологии юектирования процесса раскроя в заготовительном производстве, >евде всего, это переход к централизации раскройных операций, ко-рый немыслим без эффективного решения проблемы оптимального рас->оя, включающей различные по математической постановке задачи. К именее исследованным и трудноформализуемым относятся задачи Мирного нерегулярного раскроя, возникающие в единичном производстве, обую актуальность оти задачи приобрели в связи с широким исполь-ванием в технологических процессах раскроя металла оборудования я термической резки, позволяющего выкраивать заготовки разнооб-зных конфигураций.

Б настоящее время, как показывает опыт, на многих машиностро-зльных предприятиях с единичным характером производства преобла-;т ручной раскрой, что, помимо увеличения отходов металла и сни-■шя качества раскроев, сказывается на сроках проектирования тех-югической подготовки заготовительного производства. В связи с го, актуальной является задача автоматизации процесса раскроя с юльзованием оптимизационных методов получения раскройных карт, ¡ожаленип, "¿"настоящее время не известны" методы точного" "решения 'за! фигурного раскроя. В то же время для фигур простых форм (прежде ;го, прямоугольников) имеются методы нахождения приближенных и ■имальных решений. ■ Поэтому актуальным становится аппроксимационный [ход к решении задачи фигурного нерегулярного раскроя, рассматри-мый в диссертационной работе и -подразумевавший формирование из одного- набора деталей блоков, заданных типов простоя конфигурации оследуювдм-решением задачи раскроя блоков.

Цель и задачи работы. Основной целью диссертационной работы яэ-гся разработка эффективных вычислительных алгоритмов решения за-1. фигурного нерегулярного раскроя,- 'использупцах аппроксимацию де-:й многоугольниками специального вида, и создание на их основе 'раммного обеспечения для генерирования рациональных раокройных ■ в единичном производстве. Достижение цели' потребовало решения 1уювд1Х задач:

1) исследования свойств укладок некоторого класса фигур, называемых гофрами;

2) построения схемы перебора укладок гофров, введения сценок

частичных укладок гофров с целью выявления бесперспективн: уоадок;

3) разработки "жадных" алгоритмов решения задачи построения ; циональных укладок гофров; - •.

4) разработки алгоритмов построения типовых совмещений конгр; энтных деталей и аппроксимации их гофрами; .

5) создания гибкого быстродействующего программного обеспечен]

■ реализующего аппроксимационный подход, на основе эффективных алгоритмов раскроя гофр-блоков и" прямоугольных блоков

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

- формализован подход к решению задач фигурного раскроя, осн( ванный на аппроксимации раскраиваемого набора блоками определенных типов, для которых известны методы получения опт мального решения;

- выделен класс изотетичных многоугольников-гофров, исследов, ни свойства укладок гофров, позволившие применить известны матод зон для прямоугольного раскроя к построению укладок . ■грог;

- предложена схема перебора укладок гофров, приведена оценка количества элементарных операций, необходимых для построен:

плотных укладок гофров;

- разработаны быстродействующие "жадные" алгоритмы нахождени рациональных уоадок гофров;

- разработан алгоритм построения типовых совмещений невыпукл конгруэнтных деталей в гофр-блок;

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

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

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

.-.^.осдачЯ работы . Основные результаты диссертационной работы доллзд.;: чдись на Зсесоазных научно-технических конференциях: "Вне, 1-н;;е новых технологии и методов в разработка и функционирование

'" (Свердловск, 1937), "Системы автоматизированного про«кти»»о«ё-в кузнечно-штамповочном производстве" (Свердлове!;, чно-технических конференциях; "Применение САПР в машиностроении" ердловск, I9S9), "Проблемы и опыт применения САПР в масинострог -" (Свердловск, I9E6). Публикации. По результатам диссертации опубликовано б рьсст. Структура и объем работы. Диссертация состоит из введения, ех глав, заключения, списка использованной литературы и прпло.е-. Объем основного текста 130 страниц. Имеется 26 рисунков и едка лица. Библиография включает IIS наименований.

СОДЕРЖАНИЕ РАБОТЫ В первой главе проведен обзор фундаментальных и прикладных ис-цовакий в области раскроя; рассмотрена классификация задач рас-ч; кратко охарактеризованы методы решения задач прямоугольного згулярного фигурного раскроя; приведена постановка задачи нерегу-зого фигурного раскроя и описаны подходи к ее решение, один из эрых - исследуемый в работе аппроксимационный подход; сформулиро-i задачи исследования.

Исследования проблемы раскроя показали, что решение задачи рас-i в общем случае включает два основных взаимосвязанных аспекта:

- генерирование всевозможных раскройных карт с допустимыми размещениями деталей, при которых заготовки не пересекаются меэду собой и не выходят за пределы области размещения;

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

Первый аспект подразумевает рсасние в»числительно-геомс-тричг-с-задач, связанных с размещением фигур в заданных областях. Бто-аспект опирается на адекватную постановку, восходящую к работам Канторовича И 3.А.Залгаллера, которые свели задачу построения мального раскройного плана в условиях массового производства к че линейного программирования (ЛП) и целочисленного лине/ного раммирования (Ш:П) в условиях единичного производства. Поскольку известны методы решения задач ЛП и Ш:П, особое эни-е в литературе по раскрою уделяется генерированию карт рзскро-.. олее исследованными классами задач размещения являются зал йного и прямоугольного гильотинного раскроя в условиях массово-единичного производства. Значительная роль я области разрзоот-атематического обеспечения линейного и прямоугольного гильотин-раскроя принадлежит коллективу Уфимского авиационного институ-од руководством Ь.А.МухачевоЯ.

- 5

В институте машиноведения УрО АН СССР А.И.Липовецким проведе! исследование задачи негильотинного прямоугольного раскроя в общей постановке и для ее решения предложен метод зон, позволивший свесо задачу оптимизации прямоугольного негильотинного раскроя к комбинг торной, т.е. выбору оптимальной укладки из конечного дискретного множества укладок специального вида. На основе метода зон были ра: работаны аффективные по быстродействии алгоритмы негильотинного п] моугольного раскроя.

Наименее исследованными и трудноформализуемыми является зада1 нерегулярного фигурного раскроя, характерные для единичного производства. Рассматривается следующая постановка: необходимо разместить/2- фигурных (в общем случае'различных) заготовок в полуполосе ширины Н так, чтобы-длина занятой части была минимальной.

Зто задача математического программирования, характеризующаяся высокой размерностью, нелинейностью и недифференцируемостью фуь кции цели и пр., В связи с этим применение известных точных методо* к решению задачи невозможно. Поэтому развивается подходы, использ) ющие эвристические приемы и позволяющие получать приближенные ресе ния исходной задачи. Наиболее распространен подход последовательно одиночного размещения (ПОР),, заключающийся в построении укладки пу тем присоединения детали к уложенным, ранее неподвижным в соответст вии с некоторой последовательностью номеров и поиске такой последовательности, которая соответствует рациональной укладке деталей, ¿ля построения укладок предлагаются различные вкчнелктельно-геомет рические процедуры: годограф функции плотного размещения (Ю.Г.Стоя H.H.Гиль), метод слоения .(Белякова 1.Б., Рябина Н.О.). Поиск оптимальной последовательности ведется методом сугсающихся окрестностей (Соколовский В.З., Стоян Ю.Г.), методом локальной оптимизации в плавающей квазиметрике (Петунии A.A.) и другими.

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

ученного набора блоков. Развитие такого подхода долило вестись ледуоцих взаимосвязанных направлениях: •

- поиск классов фигур, аппроксимирующих совмещения небольшого количества деталей с минимальной площадью потери от аппроксимации;

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

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

Во второй главе рассмотрена задача раскроя полуполосы заданной ¡ны на многоугольники специального вида (гофры), являющиеся предателями класса о£-фигур при Я-^г. исследованы свойства и предло-I схема перебора укладок гофров на основе метода зон А.И.Липонец-

приведена оценка- количества элементарных вычислительных проце-(ЭВП), необходимых для построения множества укладок гофров, ;лояена характеристики качества укладок и правила отсечения бес-пективных укладок.

Метод зон, используемый для репения задачи раскроя, основан на уюцих понятиях. С каждой точкой М(ха1/„)плоскосг'Л и углом СХ связаны сти , называемые зоной и антизоной точки (рис.1):

г(М)*[(х.у)\{/<у0 3 {{/-рсоъа>(х-х.)<мя а },

Сегменты непрерывных кривых, любые две точки Л? и N которых заданного угла с( удовлетворяет свойству .

2.(М) л г(ы)~0,

ваются (X-монотонными кривыми. Зона (антизона) ¿(-монотонной ой представляет собой объединение зон (антизон) точек кривой рис.1,а).

Объединение <х -монотонной кривой^ с некоторым множеством / , здлеаащим антизоне кривой, называется «-фигурой (рис.1,6).

Рис. I. К определении Л -монотонных кривых и ЛЧ-игур:

а) оС -монотонная кривая , ее зона?$)и антизона2(^ с) Л4и1ура Р , ее. зона и актинона г ( Р)

Г

ГО7»

% т»

^ В»

-Ш(й) !

Л

-Г-1--

г

I

V

I

,! ^

Щ_I

Уь

Фй

Хь,

Сис. Луимер гофра & и его зоны

Зона с*-фигуры совпадает с зоной Л-монотонной кривой (см.рис. ,б). Рассматривается конечное множество попарно непересекающихся (-фигур, называемое укладкой. Укладки Л-фигур на плоскости удов-етворяют свойству топологической сортируемости: для лвбой укладки

(-фигур мокно указать такой порядок. ^ , Рг....., согласно кото-

ому каждая последующая Л-фигура не пересекается-с объединением зон редыдущих. Порядок топологической сортировки не единственен, ¿ля введения единственной последовательности укладки вводится условие: реди всех «-фигур, претендующих занять ^-ю позицию последователь-эсти, выбирается самая верхняя. Последовательность топологической эртировки сХ-фкгур, удовлетворяющая условию единственности, назы-ются ?-последовательностью. ..

Таким образом, клндой укладкеоС-фигу.р (в том числе и оптималь-зй) соответствует ¿-последовательность. Зная вычислительные про-здуры, позволяющие генерировать укладку по заданной последователь-;сти, можно строить схемы перебора'¿Г-последовательностей с целью феделения оптимальной. '

К сожалению, для ос-фигур общего вида не удалось построить схему". :ребора, поэтому в работе, рассматривается подмножество (X-фигур т А** , а именно : класс изотетичгшх, монотонных по двум направляй многоугольников, называемых гофрами.

Гофром & называется многоугольник, ребра которого моето раз-:ть на две ветви (низгнвю и верхнюю), составленные из ступенчатых каных, координаты вершин которых монотонно возрастают по оси абс-сс и монотонно убывают по оси ординат (рис.£). Зона гофра совпа-ет с зоной его верхней ветви.

Рассматривается .следующая задача : треоуется определить такую ладку набора гофров б полуполосе, допуская преобразования, ост и— вщие фигуру гофром, которой соответствует минимальная длина заикой ста полуполосы.

Поскольку гофры являются частным случаем Л-зигур, то их углчд-удовлетворяет свойству топологической сортируемости." Ниделин к-;: фр &кв укладке. Показано, что граница" объединения зон ги-рвих алойных К-1 гофров представляет ссбой ступенчатую ломанус, и суиест-гт единственное преобразование гофра в пределах ася^ исходного вожения, называемое ¿Г-сдеигом гофра, которое включает горизонтальный и вертикальный сдвиги до касания с границей объединен;:« зон здыдуцих з ^-последовательности гофров. Укладка, в которой вг' Еры Е-сдвинуты, называется ¿-сдЕинутой. Множество £-сдвинутых

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

Среди множества ¿5-сдвинутых укладок выделяется подмножестве плотных, т.е. таких, в которых каждый гофр касается снизу и слева границ полуполосы или предшествующих ему в Е -последовательности гофров, так что дальнейший ¿-сдвиг невозможен без нарушения условия непересечения. Плотные укладки строятся из исходных £ -сдвинутых с помощью разработанной процедуры уплотнения, не ухудшающей качества укладки. Таким образом, исходная задача сводится к эквивалентной:

требуется определить такую укладку на множестве плотных 2 ~ сдвинутых укладок Р- гофров в полуполосе' иирины Н, допуская преоб разования, оставляющие фигуру гофром* которой соответствует минимальная длина занятой части полуполосы.

Это комбинаторная задача дискретной оптимизации, принадлежащая классу МР-трудных, ¿ля ее решения необходимо:

1) определить ЭВП построения множества плотных -сдвинутых' укладок гофров;

2) оценить количество ЭВП, необходимых для построения множества укладок гофров;

3) исследовать тэеличины, характеризующие качество укладки;

А) разработать правила отсечения бесперспективных укладок.

В работе.описан способ построения множества плотных £-сдвинутых укладок, включаюций следующие олеыентарные операции (30):

I)- 2?-сдваг гофра; .2) уплотнение гофра;

3) проверка выхода за пределы полуполосы;

А) построение границы объединения уложенных гофров.

Совокупность ЭО, последовательно примененных к одному гофру, называется Э5П..В результате очередной размещаемый гофр £ -последовательности' займет одно.из конечного числа положений на границе объединения зон уложенных гофров, называемое местом укладки (МУ). Обозначим -. I -й гофр в ¿-последовательности, к которому применено к-е преобразование, ~ количество МУ гофра &£ . если уложено i~i гофров'и предыдущий.в Е -последовательности гофр ' &1Р_1 находится в т -м МУ' в положении р . -количество ЭВП, необходимых для построения укладки I гофров.

Тогда верхняя оценка количества ЗВП, требуемого для построения плотных 2 -сдвинутых укладок гофроЕ

%-г (&„.,) 4 4 р

Тпч (&*) С (X г1)

" 7 т*1. р* г .*-- /

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

1) длина занятой части полуполосы; ■

Ь = ГПОс£ Х1 ■ *

где - абсцисса правой нихней вершины гофра ;

2) плогадь укладки

где К - количество уложенных гофров, ГЪК- количество ступеней-границы объединения зон !( улокенных гофров,

координата вэршн границы .объединения зон гофров;

3) площадь потери укладки

где. К - количество гофров, - площадь укладки, плоцадь I- -го гофра.'

' Показано, что .отсечения по площади потери и по длине занято!', части листа равносильны. Помимо отсечений по рекорду рассматриваются отсечения по плотности, т.е. отсекаются все укладки, ссде~м-те частичную с неплотно расположенными гофрами.

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

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

Во второй главе показано, что задача определения оптимальной укладки на множестве ~Z— сдвинутых плотных откосится к задачам дискретной оптимизации. Один из известных методов решения задач дискретной оптимизации ("жадный" алгоритм) заключается в том, что на каждом cars из множества вариантов реиения выбирается вариант с наилучпей частичной оценкой качества. Эффективность "жадных" алгоритмов зависит от выбора величины, характеризующей качество варианта и правил включения исследуемого элемента в решение. Анализ свойств укладок гофров показывает, что:

1) поскольку количество всевозможных последовательностей топологической сортировки укладок гофров велико («л.'),

то-необходимо выделять последовательности, соответствующие рациональным укладкам; .

2) поскольку количество укладок, соответствующих одной £ -■последовательности, зависит экспоненциально от числа гофров к количества ступеней в.гофрах, то необходимо найти эффективный способ построения одной рациональной укладки по заданной Z -последовательности.

"Еадный" прием, используемый -при рещении первой проблемы, заключается в применении эвристического правила размерной последовательности, т.е. в задании таких последовательностей, в которых фигура определенным -образом упорядочены (например, по убыванию площадей). /

Множественность укладок, соответствующих одной if -последовательности, объясняется множеством возможных положений гофра в укладке, ¿ля выделения единственной рациональной укладки, соответствующей заданной 2 -последовательности,.необходимо, исходя из свойств укладок, ввести оценочные характеристики каждого положения и выбирать .вариант с наилучшей частичной оценкой. Б качестве таких оценок .предлагаются следусвдае характеристики укладки гофров:

1) длина занятой части пол;полосы (барьер укладки);

2) площадь внутренней потери от укладки гофра;

3) площадь превышения барьера;

4) площадь кромки. .

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

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

1. Вычислить первоначальную длину укладки в предположении равенства нулю площади потери укладки.

2. Пока не уложены все гофры 2 -последовательности, выполнять: ¿.I. Пока не исчерпаны разрешенные преобразования гофра,

выполнять.

2.1.1. Двигать очередной гофр вдоль лестницы с выполнением в каждом МУ следующих процедур.

2.1.1.1. Уплотнить гофр.

2.1.1.2. Определить внутреннюю область потери и заполнить ее мелкими гофрами из конца последовательности.

2.1.1.3. Определить площадй кромки и превышения барьера. 2Л.1.4. Вычислить полную площадь потери.

2.1.1.5. Если площадь потери на предыдущем МУ не.меньше площади потери а очередной-месте, то запомнить .новую площадь потери- . 2.Г.2. При достижении верхней.ступени лестница, скорректиро-

- вать барьер с учетом полной-площади потери. 2.1.3. Построить новую лестницу объединения зон уложенных •гофров.

2.1.<+. Если площадь потери гофра, подвергнутого очередному преобразованию, не больше, чем на предыдущем шаге, ■ то запомнить лучший вариант размещения. 2.2. Перейти к. следующему гофру' в последовательности.

3. Размещены все гофры последовательности.

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

Показано, что сложность алгоритмов (с учетом составляющих их вычислительных процедур) зависит от количества укладываемых гофров и количества ступеней в гофрах и оценивается сверху величиной Т~ ОСпк + к*) ~0(/1>т3), .

где К - количество элементов в группе перебора, /72. - максимальное количество ступеней'в гофрах, • Л- - количество гофров.

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

Предложенные алгоритмы программно реализованы на языке ФОРТРАН в ОС машины МОйЪ-ЮО СХ . Бремя построения укладки П гофров ( Я ^100) не превышает 2 мин , построение гофр-блоков занимает 3-5 с • . Программная реализация предназначена для винчения в САПР раскроя..

В четвертой главе даны рекомендации по применению аппроксима-ционного подхода к построении подсистемы генерирования рациональных карт фигурного нерегулярного раскроя, получаемых термической резкой; описана САП? раскроя и ее место в технологической подготовке раскройно-заготовительного производства; приведены задачи, требующие решения при аппроксимационном подходе, и.' в соответствии с этим структура и состав подсистемы генерирования карт раскроя, использующей аппроксимационный подход.

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

1А

раскроя. Эта задача особенно актуальна в связи с тем, что применение "постоянных" карт раскроя в единичном производстве невозможно из-за часто обновляющейся номенклатуры деталей.

Основное назначение системы автоматизированного проектирования (САПР) раскроя - исходя из задания на раскрой, включающего описания деталей и раскраиваемого материала, сгенерировать раскройные карты, удовлетворяющие технологическим требованиям и эффективно использующие материал, и создать управляющую программу для оборудования с ЧПУ.

В соответствии с этим, основными структурными компонентами САПР раскроя являются следующие подсистемы:

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

2. Подсистема построения рациональных раскройных карт, содержащая программные средства, реализующие алгоритмы оптимального и рационального раскроев, программные средства интерактивного раскроя.

3. Подсистема разработки технологии раскроя. Предназначена для определения маршрута режущего инструмента по полученной карте раскроя.

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

1) компоновка набора'деталей в блоки упрощенных конфигураций;

2) выбор оптимального набора блоков минимальной площади, содержащего детали в заданном ассортименте;

3) раскрой металла на блоки заданных типов.

Применение этого подхода обоснованно, так как, во-первых, иие-атся эффективные по быстродействию алгоритмы компоновки'деталей типа кольцевых секторов, круговых сегментов, косынок в прямоугольные блоки, уголкоз, невыпуклых П-образных деталей в гофр-блоки, Ео-вторых, разработаны ¡эффективные алгоритмы построения рациональных и оптимальных укладок прямоугольников и гофр-блоков. Предложенные алгоритмы охватывают около 80 % номенклатуры деталей, используемых в машиностроении.

Б диссертационной работе описана система раскроя, эксплуатируемая в ПО "Уралхиммаш". Для нее предложена подсистема построения карт раскроя, основанная на аппроксимационном подходе и включающая следующие программные блоки:

1) прикладные программы анализа типа деталей (уголок, косынка, сектор, сегмент), (Построения типовых совмещений и аппроксимации совмещений прямоугольниками и гофрами;

2) прикладные программы построения рациональных укладок прямоугольников;

3) прикладные программы построения рациональных укладок гофров;

4) системные программы интерактивной доработки карт раскроя.

Списанные программы оформлены в виде пакета прикладных программ. Модульная структура пакета позволяет расширять и модифицировать подсистему путем:

- подключения диалога с пользователем на этапе построения типовых совмещений и компоновки в блоки;

- расширения классов аппроксимирующих фигур;

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

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

Разработанное БО могет использоваться автономно.

ОБЩЕ ЕЫВОДЫ

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

2. Исследованы свойства укладок гофров ( В -сдвиг, уплотнение, топологическая сортируемость). С использованием метода зон А.И.Ли-повецкого и свойств укладок гофров, задача определения оптимальной укладки в полуполосе строго сведена к задаче дискретной оптимизации на конечном множестве плотных 2 -сдвинутых укладок. Предложены элементарные вычислительные процедуры построения плотных

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

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

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

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

6. Описана подсистема генерирования рациональных карт фигурного раскроя в условиях единичного производства, основанная на аппроксимационном подходе. Разработанные алгоритмы оформлены . в виде ППП, который входит в подсистему САПР раскроя. Подсистема проходит опытную.эксплуатацию в ПО "Уралхиммап". Спроектированные карты раскроя отвечают технологическим' требованиям, при этом время проектирования, по сравнении с ручным вариантом,- сокращается на порядок. Ожидаемый экономический- эффект от внедрения- САП? составляет 75' тысяч рублей.

ОСНОВНОЕ СОДЕРШИЕ ДИССЕРТАЦИИ ОПУБЛИКОВАНО В СЛЕДУЮЩИХ- РАБОТАХ:. '

I. Гусев А.К., Корницкак М.Н. Разработка алгоритма расчета параметров раскроя листа для ГПМ-УЕШ // Внедрение новых технологий и методов в разработки и функционирование АСУ: йнф. сб. М: ЦНИИТЗИ приборостроения, 1987.Вып.3. С. 33-35.

2. fyceB А.И., Корницкая M.H., Плещев В.П. Постановка задачи раскроя листа // Проблемы и опыт применения САПР в машиностроении: Тез.докл.НТК.; Свердловск, 1986. - С.25-26.

3. Липовецкий А.И.,■Корницкая М.Н. Элементы адаптации при построении плотных совмещений сложных фигур // Системы

•автоматизированного проектирования в кузнечно-штамповоч-' ' ном производстве: Тез.докл.НТК. Свердловск, 1933. -С.122-' 124.

Липовецкий А.И., Корницкая М.Н. Алгоритм раскроя листа на детали типа гофров // Применение САПР в машиностроении: Тез.докл.НТК. Свердловск, 1989. -С, 38-39.

5. Липовецкий А.И., Верещагина О.И., Корницкая М.Н. Алгоритмы проектирования и оптимизации раскроя для фигур одного класса // Автоматизация технологической подготовки производства : Межвузовский сборник. Свердловск: УПЛ, 1989. ,

С.50-57.

6. Липовецкий А.И., Корницкая М.Н. Алгоритм совмещения невы. пуклых конгруэнтных деталей // Принятие решений в условиях

неопределенности: Межвузовский сборник. Уфа: УАИ, 1990.

Подписано в печать I3.II.S0 • _ 'Формат 60x84 1/16 Бумага Плоская печать . Усл.п.я. 1,16

Уч.-нзд.д; 1,00 Тирая 100 'Заказ 961 • Бзсплатно

Редакционно-издательский отдал УПЫ им.С.М.Кирова 620002, Свердловск, УЛИ, 8-й учебный корпус' Ротапринт УШ1. 620002, Свердловск, УШ1, 8-й учебный корпус