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

1 О 3 9'1-

А и ГОСУДА

УДАРСТВЕННЫЙ КОМИТЕТ СССР ПО НАРОДНОМУ ОБРАЗОВАНИЮ

ЛЮСКОВСКИЙ ЛЕСОТЕХНИЧЕСКИЙ ИНСТИТУТ

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

САМОЛДИН Александр Николаевич

УДК 676.028.42:621.373.826

АЛГОРИТМИЧЕСКОЕ ОБЕСПЕЧЕНИЕ СИСТЕМЫ

АВТОМАТИЗИРОВАННОГО УПРАВЛЕНИЯ ЕШЛОГИЧЕШШ ПРОЦЕССОМ ЛАЗЕРНОГО

РАСКРОЯ В ЦЕЛЛЮЛОЗНО-БУМАЖНОЙ ДЕРЕВООБРАБАТЫВАЮЩЕЙ ПРОМЫШЛЕННОСТИ

!пециалыюсть 05.13.07 — Автоматизация технологи-¡еских процессов и производств (промышленность)

АВТОРЕФЕРАТ

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

Москва — 1991

V */ /'> • ^ Л

- 1 /'.'' С-' ,

Работа выполнена в Московском лесотехничесг институте.

Научный руководитель — кандидат технических нау

.' , ■ : доцент Павлов 10.

Научный консультант — доктор технических науь

профессор Духон Ю

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

профессор Петровский В.

г.- . кандидат технических на

доцент Степанов И.

Ведущая организация — Центральный научно-иссле

вательскин институт мехаш ции и энергетики лесной п . . мышленностн

Защита состоится , 20 " tiQ^TCj_ 1991 п

в часов на заседании специализировашн

сонета К.053.31.02 по присуждению ученых степеней i Московском лесотехническом институте по адресу: 141001, Мытшци-1, Московской области, МЛТИ.

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

С диссертацией можно ознакомиться в библиотеке МЛТИ. Автореферат разослан „ ^ " 1991 го

Ученый секретарь специализированного сов* кандидат технических наук, доцент Федорчук Р.

5.01 1991 г. Объем 1 п. л. Тираж. 100 Заказ

Типография Московского лесотехнического института

Л I ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТУ ^

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

Актуальность теш, Автоматизация производства, наряду с разработкой ресурсосберегающих те:.но логий, является одним из вазшейшк направлений научно-технического прогресса. Б связи с этшл представляется актуальной разработка систем автоматизированного управления технологическими процессами, применение кон -:с методов и технологий разделения материалов. Создание и широкое внедрение автоматизированных систем раскроя, представляодих собой принципиально новпе, ресурсосбе-регагацие технологии, обеспечивает значительное снижение расхода материала, трудоемкости производства, сокращение непроизводительного трупа, позволяет полностью автоматизировать процесс раскроя. Наиболее прогрессивном направлением совершенствования технологии и повгшенвд эффективности производства в отраслях лесного комплекса является использование . лазерн-х усгановоьущтегрировакшос с 7ЧПУ или непосредственно с микроЗШ, для раскроя целлшозно-бумаютых материалов (ЦШ) и некоторых материалов деревообработки. Применение технологических лазерных установок...(ТЛУ) создает принципиально нопуа, гибкую технологию раенроя, позволяющую с мини- . малыгоми затратами времени переходить на. изготовление новых видов изделий слоеной-конфигурации. Применение лазерной технологам, например, в деревообработке, в целом ряде случаев позволяет почти что здвое сократить число операций по сравнению с традиционной технологией обработки древесных материалов. Однако, при внедрении лазерного раскроя возникает рад проблем* требущих глубокой прорабо/ки: формирование оптиыальннх планов, раскроя и оперативный поиск траектс ри|"

. 4

\ * '

: ' ' ' ■ •

двиаеюш лазерного резака , о<5есяечивркх;ях шксшальную производительность лазерного комплекса, преобразование полученной траектории в коды УЧПУ, выбор и. оптимизация технологически параметров резшпш и т.д. С точки зрения разработки алгоритм ноского и программного обеспечения систега; автоматизированного управления технологическим процессом лазерного раскроя клетевыми полностью определяющий эффективность применения ТЛУ являются проблеш размещения геометрических объектов слс::згой конфигурации и попек эф1)ектнвго.!х: траекторий резания. Несмотря на большой интерес исследователей к проблеме размещения геометрических объектов, она на сегодняшний день но утратила своей актуальности. При этом практика постоянно выдвигает все нате задачи, требущие своего рсиения. Задача поиска оптимальной траектории движения' ревущего инструмента кс-нее исследована, а' имеющиеся в настоящее врегдя се рогения носят частный характер. Такигл образом, актуальность проблем оптимального размещения геометрических объектов слоеной конфигурации и синтезг. оптилальню: траекторий движения рекущего инструмента, .а такке необходимость эффективного решения практичесюЕ задач размещения и трассн-розки с пс:.:одью ЭВМ об, словили внбор тем,! диссертационной работы.

Цель и задачи исследования. Цальа настоящей работа явл стоя разработка алгоритмического п программного обеспечения элементов систем-! автоматизированного управления технологическим процессом лазерного раскроя н использование его для репения практически задач, возникшдих при изготовлении де талей.сложной конфигурации. В соответствии с данной целью осковшжи задачами работы являются: анализ особенностей раз меценка геометрических объектов и движения рехуцего инструмента при использовании ТЛУ з целлшозно-бум&'хной и дере-вообрабатываэдей промышленности; анализ состояшш вопроса размещения геометрических объектов и поиска оптимальных тра екторшУ резания; моделирование размещения геометрических об ектов сложной конфигурации а прямоугольной области, синтез математической модели и алгоритмов реализации; разработ; . методов и алгоритмов определения эффективных траекторий дви

На защиту вукос.чтся: метод генеравдк размещений одно-связзмс геометрических объектов слояной конфэтурацж: в прямо. угсльноГ: области; алгоритмическое л npoi рам.мое обеспечений размещения геометрических. объектов произвольной формы; алгоритмическое я програташое обеспечение размещения прямоугольник геометрических объектов; алгоритм н программное обеспечение . задачи определения оптаильнкс траекторий движения лазерного резака. ' ' •

■ Практическая ценность табот;?. Исследования по теме диссертационной работ;-! выполнялись в рамках научной тематики кафедры технической кибернетикл (ШТИ) по програют 00.11.03 ШГГ СМ СССР в рагах, хоздоговоркк-с работ (гос.регистрация JS - 0I8S0C04259). Разработанное математическое и ярогра-алное обеспечение решаемых ко.-ллексоз задач я его элег.:ектк впедренч на ряде предприятий' страну : Залзол.™ском картонио-ф"бровом пропз-водствешгоп объединении,- 1Г.73 "Россия", ПШ "Ыоскза", XCK-I6Q .МО СССР, йкне-Таггаьском мебельном комбинате, Тпраспольскш ДОКе, з НИШШе.; Еодтзергдсшшй документально экономический ■ эффект, от-внедрения результатов дпссертациошой работа сеста-311Л 242, 12 тес.руб. . . ^

Аппобгли'л паботчГ Основное '.содераакно дпссертацпошюЯ работы. докладывалось - и; обсундалось на Всесоюзно:! научно-технической конференции "Ь'атсьатическос обеспечение рациоиадьно-го раскроя .в системах автоматизированного проектировшпш" (г.Уфа, 1987 г.), на Всесоюзной научно-техтонеском семинаре "Котенсь^якация производственных процессов в отраслях' лесного комплекса с использованием комплексной мехаяизащп! и средств вычислительной техникл" (г.Ленинград, 1933 г.), на научно-технической конференции с мездународнкм. участком "Яерспектив-нне материала и технологии в производстве. мебели и столяряо-стрсительшх изделий" (г.Стара-Загора, 1988 г.), на Всесоюзной научно-технической конференции "Научно-технический прогресс лесной и деревообрабатывающей промышленности" (г.Киев, IS89 14 ), на научно-технической конференции "Автоматизация технологического проектирования" (г.Пенза, IS89 г.), на Всесоюзном научно-техническом семинаре "Совершенствование системы автоттизарованного проектирования при технологической под-

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

Оснонипе метода исследований. Для решения поставленш?х задач бкли использованы метод» математического анализа, математического про г рах.миро ваши, теории графов, методн аналитической и вычислительной геометрии, исследования операций. При разработке программного обеспечения применена принципы модульного и структурного программирования и использован стандартней набор технических и прогр&'лгшых средств микроЭЕЛ 1Ш РС.

Научная новизна полученных в диссертационной работе результатов состоит в следупцем: разработана и исследована математическая модель задачи размещения геометрических объектов слоеной конфигурации в прямоугольной. области при лазерном раскрое; для математических моделей размещения объектов сложной конфигурации разработшг метод получения эффективнкх укладок с использованием элементов математического программирования; разработано алгоритмическое а программное обеспечение для ремения задачи размещения геометрически объектов сложной конфигурашш в условиях лазерной технологии для целлюлоз но-¿углааной и деревообрабаткващей" промышленности; для математической модели размещения прямоугольных объектов синтезирован алгоритм генерации частично сыешашшх размещений на основе двухуровневой оптимизации и метода последовательного улучшение разработаны и нсследозанч '.атематические модели задачи поиска едтнмальнь'х траекторий двияенпя лазерного резака с учетом технологических особенностей лазерного раскроя древесных и ЦБ.*; сиитезироБачь: алгоритмы и разработано программное обеспечение, позволяпдее получать оптимальные траектория движения лазерного резака при реализации раскройиос карт лсбой'сложности; про-уеденг эксперименталх нке «еследЬ'ааяия разработанного математического и программного обеспечение на комплексе реалыгде сроиз-аодствешшх задач, которке показали его высокую эффективность ;! практическую ценность.

готовке производства машаюстроительной продукции" (г. Москва, 1Э09 г.), на Всесоюзном научно-техническом семинаре-"Совре-меннке проблема автоматизация и внедрения вычислительной техники в целяшозно-буначноИ и деревообрабатнващей промшплен- ■ ности" (г.'.'юсква, 2990 г.), на научно-технических конференциях 1.ИТИ (г.'.Ь'таци, 1987-1590 гг.)

Публикации. По катериалал диссертации опубликовано тринадцать печатая работ.

Структура диссертационной тботя. Диссертация состоит из . введения, пяти глаз, заключения, списка использованной лигера-гурн и прялоаений. Основной материал исследований излояен на 132 страницах машинописного текста. Имеется 8 рисунков и 3 таблица. Сцссок использованной литературы содераит 116 наименований. г ' ■

СОДЕРЖАНИЕ РАБОМ

Во введении обоснована актуальность теш диссертационной работы, цель, задачи к метода исследований, приведена струкгу-/ за работы. • ,

Глава I. Анализ технологических особенностей лазерной:' эбработкк материалов в отраслях лесного комплекса.

В данной главе рассмотрены основы и особенности нового метода разделения материалов для отраслей лесного комплекса • лазерной резки, дается обзор работ по исследуемой проблеме, ¡формулированы требования,предъявляемые к раскройным картам й . траекториям двякения лазерного резака. Анализ технологическо-•о процесса лазерного раскроя и проведенные эксперименты по >аскрою древесных материалов на целлюлозной основе показали, ¡то даншй метод имеет существендае преимущества перед тр&-дационнкми, особенно яри раскрое листовых материалов на зато- ' :0вки кразолинеГаюй форш. К достоинствам лазерного раскроя "ЛЗДО отнести: отсутствие механического воздействия на обра-1ат»ваекнй материал; внеокая производительность процесса в со-[даднии с вксокш качеством поверхностей резов; возмоайость • 'дробить" лазерный луч и направлять его . на те шш иные техно- ,, »русские позиции; легкое в сравнительно простое управление ¡рзддссом раскроя; значитеяь'й&е «йфащеяие числа гехнологичес-¡^'оверадаД, ..яеяйсадзг.?-». ¿#5 деталей сложное-'

s —

конфигурации, возможность быстрой сменл номенклатуры изделий значительная эконоюш раскраиваемого материала и т.д. Реализация достоинств лазерного раскроя, обеспечение экономической эффективности от применения дорогостоящие ТЛУ возможна лишь при 1лтоматизации на высоком уровне не только собственно процесса раскроя, но. и его подготовки. .При этом основнн-N01, практически полностью определяющим экономическую эффективность использования ТЛУ, являются проблемн фэрмирования размещений заготовок слоеной конфигурации и определения опт» ыальных траекторий двизения лазерного резака. Решение указанных проблем предполагает в свою очередь разработку мощного алгоритмического и программного обеспечения.

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

Глава 2. Математические подели и алгоритма размещения криволинейна геометрических объектов в односвязной прямоугольной области.

В этой главе веделен класс объектов исследования: рассмотрен« способы задания их численнтс моделей, необходимых для работы на ЭВМ, осуществлена формализация задачи оптиыаль ного размещения геометрических объектов сложной конфигурации и приведена математическая постановка решаемой задачи, с:тн-тезирован алгоритм генерации размещений геометрических ос.„-ектов слокной конфигурации и его модификации, а также приведет доказательства основных положений разработанного алго-

ритма. ■'.'"•

Приведем матеглатическуо постановку.задачи размецения геометоиче : .«к объектов слохной конфигурации с учетом особен-:остей технологического процесса лазерного раскроя целлвлоз-нп-бугэгянх и древес пых «атерпалов. Задана прямоугольная од-носвяэная область размещения - раскройный лист с размерами: длиной D' ■ и пяриной Е . Задано ¡.конество {RL} из М злдов односачзнпх. разг.:едае;.гяе гео;,:етр;гческ;:х объектов, каздкЗ из котор;о: алпрокс;гяровач ляогоугольшусом с заданной: точностью, к известии координаты верпия глюгоугольнпков п {yi.}M • Tarcse задано количество {BrJ геометрических объектов каждого в;да, и заданы технологические особенности лазерного раскроя древесну;: и ЦК,!. Сзяхем с Si пеподв;шгую декартозу систему координат, а с CR'i} — подвигнке декарто-вч системы координат. Располононле какого геометрического объекта в исходной области разведения характеризуется параметрами размещения { ЗС^ , Q^} . Задача размещения сводится к совокупности следующих соотношений:

Р (Q) = [ D\-Я'*>+8 ] '*[ Е2 е£+$], ; . "

.. Iх* [0,2*] , - .

Um( Rm, 0 Rma) =: { S } f 0 , / , ■ ; ; .

Ч=z: яД р с^) - г sci; )• Kl (min, \

где P(i2) - плодадь области размещено*;

- ширина резе

(лазерного луча), -£3 ,"6Е - припуск на обрезку кромок

области размещения, соответственно но ее длине л ширине; i^ijw " геометрические объекта, контурн которк:: экви-

дистантны исходам на половину пиршн лазерного луча,

т.е. 5 ; © - множество граничите точек ■ геометрически: объектов; ^ - интенсивность применения £ -го способа размещения; Б ( К ¿) - площадь геометрического объекта I -го вида; К^Ь;) - количество геометрических объектов I -го вида размещеншх % -и способом; Н - множество раз-,

личних способов размещения геометрических объектов.

Из вышеизложенного, следует, что задача размещения геометрических объектов сложной конфигурации сводится к минимизации функции цели на множестве технологических ограничений, накладываемы на параметры- размещения геометрических объектов сяоаной ,' конфигурации в заданной области и ыоает быть классифицирована как задача нелинейного программирования. Применение для решения поставленной задачи методов нелшюй- • ного программирования,невозмояно вследствие неявного задания функции цели ^ . Для решения исходной задачи применен метод декомпозиции, ядром' которого являются две задачи - генерация размещений геометрических' объектов с лоаиой' конфигурации и учет исходной кошлектности размещаемых объектов. Задача генерации размещений геометрических объектов слохной конфигурации решается на основе предложенного автором метода определяющей прямой. Метод состоит в том, что на каздом иаге ■ вычислительного -процесса размещение очередного геометрического объекта ; ведется относительно одной ^сторон уае размещенных геометрических объектов . V ^ ,/-1 " Причем, тамил образом, чтобы опискваздий й] и У прямоугольник бня минимальной площади. Применение данного подхода и доказанных в диссертации утверждений позволило исходную условно - экстремальную задачу свести к многошаговому -итерационному процессу решения формализованной, задачи мате.матичес-кого программирования малой размерности. На основе приведенное в работе положений синтезирована'вычислительная схема генерация эффективных размещений геометрических объектов елоз-ной конфигурации. Задача учета исходной' кошлектности решается методом последовательного улучшения. Разработана серия модификаций алгоритма генерации размещений геометрических объектов слояной конфигурации, которые учитывают вычислительные возможности имеющейся ЭЕУ, требуемую точность получаемых

размещений и оперативность получения решения.

Глава 3. Алгоритмизация размещения прямоугольных геометрических объектов в технологических условиях деревообработки.

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

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

Задача размещения прлкоугольннх геометрических объектов с учетом вектора практических ограничешШ монет быть сформулирована в следующем ввде. Задано множество односвязнга прямоугольных, областей размещения N типов £2 {сО^.} н - раскраиваема-листов с размерами: длиной {и шириной { ЕоД [Ч • Задано тшеяе множество из Н . видов (тицоразмероз) { , ' односвязннх прямоугольных геометрических объектов - внкраиваомнх заготовок с pa3Mepai.ni: длиной {^г^м и вириной. { Е г ¡.} м ' а таняе количества объектов размещения каздого вида ^ {Я^Ом* Пусть заданы технологические и организационные особенности раскроя. Тогда требуется определить способы размещения

Ь { на множестве областей размещения заданных

прямоугольных геометрических объектов 2Ш1 , а таюсе интен-

* Т Г н

сквносгл применения ка,сцого способа размещения ^ | ^ , удовлетворяющие услрвшш:

2 обеспечит* клю^и фунади цож

■У, ¿ с^)сг'о-9«>]»- '

где - интенсивность п ^ -го способа размещения в

п . -Г. облает;; размещения", ^ - £ -й способ размйцешм в " п -2.^ластг размецеш^; - - количество геомет-

рических объектов. I -го вэда получаем:-« по } -му способу р^^еюм'из Ч/я '-В '^-об»йста:разкеиения; - признак пру^'ене^п^я / ^ -ой облает:: размещения:

' : 13г'тС ыу=о,

; (ущ: Эг'т^'сО,) <¿¿>1;

Э ( ) - площадь . £ -ой области раз'меценгя: ; ,

= (Эо^-кЦ-8)х(ЕЦ-Кеи. +5)'; "

, К ео- - кромки по длинен ширине -ой облает;: размещения; 8 - ширина реза; Б (2п) - площадь т -го геометрического объекта : о = * Ег«

{ Е ¿} м - кнокество заготовок с учетом ппрнш ' реза 6: '/ ■ -

Х^З^-Я , Ег^Е^ + Я.

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

полезного вихода. Поэтому .'для. генерации частично смешанных размещений синтезирована двухуровневая спталиалконкся схем Применение. дааюго .'.способа, генерации .допустшнх. рйзмецегай позволяет на первом уровне оптигяйашгарешая:вспомогательную задачу, получит!. шозёс71й. йо^с с наг-лучиим размещением в них лрп:.юугрльша * геометрических объел: тоа-исходного множества ' ZL {Z¿} м > а на зтором уровн полученные полосы разместить^на теходдом'Кйогссствб областей размещения','-£2 {позволяет получить рациональное ро^егше исходной задачи а результате огра ничейного' целенаправленногоперебора/йопусташх-размещений. Это достигается использованием:.приоритетного списка, когорк: формируется на основе объектизнообуслозлен;шх оценок Л.В. Каитороштча. На основа вше идей сшггезпрован эф фективннй алгоритм реыенгл - задачи размещения прямоугольных геометричс. шве объекте за условиях, лазерной технологии. Раз работаш; шдификащш'основной/ вычислительной схемк. Введен эффект::п;гкс процедур:? докроя остатков справа.и .снизу исходной области размещения да .основе гибкого 'непрерывного разде. нпя исходного множества геометричеемк объектов на два пере секающахся подашокесгва.Предусштрена. возыояяоеть 'декомпозш исходной задачи на подзадачи ii" ¿ts. ..ийтёраэдюняой ушзки. Ста* тезнрозшшые в: данной- главе алгоритмы; могут бить' использопа нк-!как автоноьзю,.' " .так лг'з: "составе обцего алгоритма размещения-геометрических объектов. еловой: конфигурации.

Глава: 4.' Синтез. оптимальных траекторий.движения ла?ерн< 'го'резака. . '' "-V'^'••*.' •"■;'■.■'''' '.-'':•- '

3 отой главе анделен, класог'-задач'. определения -эффектна::-траекторий -, двкяения- лазерного .'резака,. ш^хс место в царе обрабатывающей - л ЦБП, осуществлена математическая постанов ; задач,' синтезирована' сёрик'алгоритмов, .позволящих осуществлять поиск наилучшей ; траектории-.. резания в- ргичмещешшх любо] илогносги. т-,л -

; Ксходшлп1дшшг^.2:>для-рейешй задачи поиска эффективна траекторий резашм' с^зат ,синтезг1рован1?лс способч^ размещен» При этом способ размещения трактуется-кал: кеориёнтировшпп'й геометрический граф .J • 6 { V г ¿ t ^ - Как следу!

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

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

■ Задача I.Имеется раскладка Л , которая продстазлс-на в виде неориентированного графа ( £', О*) ,

где каедой вершине графа " поставлена в соответствие верппша размещенного геометрического объекта, а ребру

: (й У-)V (V/ 8с \'1) - сторона соответствующего многоугольника. При этом известны координаты кацдой вершины

V] ( , 11^) в базовой декартовой системе коордшат» ааданн степеш! вершин графа == Б-1 и технологические требования к трассе. Причем, степень вершин обязательно четная 8} - 2, [£¿/23 = О - Задана точка.старта лазерного резака V/ (0,0) • . Таким образом, в неориентированном графе б0. ( V*, £' ,Ф') требуется выделять эйлеров цикл . , т.е. определить последовательность обхода вершин графа . , обеспечив при этом выполнение технологических требована!; , предъявляемых к траектории резания. ■' Задача 2. Задан неориентированный геометрический граф б й ( У',£',сЬ') , в обцем случае состояний из К неевдзшгс подграфов. Причем, граф ' вК дополняет выделенный эйлеров граф 60 до исходного 6 . Граф 6Р состоит из |£'| = П1 простых кривта - резов, соеданящих . 2ш вершин нечетной степени. Таким образом, задача состоит в откскании на плоскости такого маршрута, соединяющего мезду собой щ кривых, в котором сушарная длина переходов от одной кривой к другой минимальна. Поскольку кривые из множества £' является элемента.'М расклдцки и значит прорезаются, то, другими словами, задача состоит в нахождении един-

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

Для заданной матрици К ( ^1].} , 1= 1,2 т ,

^ = 1,2 т + 1 , удовлетворяющей. усло-

виям у

на шояестве допустимых циклических подстановок найти подстановку СГо в , для которой и¡.п ~Р(<э,) ,

принадяекат в о» . Здесь - длины ребер £ £х из множества

холосткх ходов лазера, ' £м - множество розов, р{<о,) -длина оптимального гашльтонсша цикла.

Задача 3.' Задало '/сходное размещение -Я. , представленное в вцде неориентированного графа € ( V , £ > ф) Причем в данном графе тлеется 2 т вершин нечеткой степени. Необходимо дополнить исходной граф б множеством ребер £х до эйлерова вЦ ( V , £ и £*, с+Э' ) путем по-

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

На плоскости задано 2 т точек V} и извести1-; их координате < ос^ , ^ ). Необходимо объединить ^ в ^арн, соединив отрезками £у : ( ) V С ^ & тчкал

образом, чтобн суща для; отрезков бь'ла бы минимальной:

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

job нмделешш эйлероЕа „цикла к определения минимальной ' дли-' m холостого г,ода лазерного регшка. Предлагаемые методн-состоят в.-слсдаойв«:;."-'.V-:;-}'•••■!"' - " '

1. Ill графа |avi.(;-'У Vойжл.тдд .т юрвом этапе решения исходной задачи выделяет - эйлеров цикл LG , которой Нщно реализовать без использования дазер-юй заслонки.. Оставпаяся, цевкрезанпой часть раскладки итерпретпруется как'геоиетрический граф 6R ( У.с'.Ф'} „

I обуем случае несаязний. Таг~:м образом, дальнейшая задача остокт в . реализации графаSR нзшаальной дленой олоетого хода лазерно;;э резака. Очевддно, что при данном одходе осуществляется, peneirse: задач X и-2.

2. Альтернативсшй подход к рещешю ксуодной задачи баз;:~ уется ка переходе от произвольного графа 6 ( V, £ .О)

эйлерову ' :'6Q, ( V *,-£*, ,Ф*) ., с последующ!« выделением йдерова.цикла;';. ••' t.S . ■■•',,;го-есть, в-данном случае решаюг-а задачи I и 3. '• •; '.' . _ '. '.■

Для реализации пр'едяохеннше-методик.определения ,;птл-. альнш: траекторий резашш скатезироватг эффективные а^го-ятш выделения эйлерова цикла с учетом технологических трс-эааний, предъявляешь к траектории и поиска холостого хода -i'j-ni-.'.ajbhoit длину в раскладке любой слоядастп. Для решения' адачя поиска мшшшльной длит-:' холостого зеода лазерного ре-mjs, т.е..для ревеюш задач,I и 2, модифицирован метод зет-эй и границ. Прл этом "сшяезироваш' процедуру условного ; гтвленш и прину.д1?геяьного стягшшшя»- разработана ¡.:од:;фикя-m алгоритмам матрицей .. расстояний специального вида и кз-люнпой процедурой стягивания. '"Применение;процедур условного зтвленил и принудительного стягивания позволяет обеспечить ?Ш1адлеаность полученному циклу розов; которие прянаддекат гсгладке. Проведение принудительного стягивания по ребрам

ззов позволяет уменьшить размерность задачи, решаемой мсто->м В( твей и границ по классической схеме. Использование ко 1Трицп расстояний специального вида позволяет учесть аль-зрнатшшость в направлении реча, но при этом ее рапг&риость >зрастает в два раза. 3 целой увеличение размерности матри-1 расстояний не оказывает суцествешюго елг.ч'гля на вь-члелл-

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

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

Глава 5. Экспериментальное исследование синтезирование алгоритмов.

В этой главе приведено описание программного обеспечеш разработанного на базе сштезировагашх в диссертационной работе алгоритмов к результата, полученные при решении комплекса практиче ких задач с его помощью. Программное обеспеченно разработано гто модульному принципу, оформлено в виде универсальной систем! и осуцстспяяет ввод исходных дапшос, получение приемлемых для технолога-проектировщика размещений геометрических объектов как сложной, так и прямоугольно!! сюрг.г? с учетом технологических я организационных ограничений. , сга-• тез для сформирозаннгас размещений - наилучезгх траекторий резания в вывод на печать итоговое результатов. Для обеспечена возможности визуального контроля вычислительного процесса ра-работала подсистема графического отображения информации. Про; раммное обеспечение ориентировано на пользователя не профессионала в области применения вычислительной техники, поэтому для удобства проектировщика при управлении вычислительннм процессом используются элементы диалога: на бг о разветвлекпо; сети меню. Разработанное программное обесш. ¿ение монет экс л л; атироваться как в составе автоматизированной с истунравл« ния технологическим'процессом лазерного раскроя, тьч и автономно. Программное обеспечение р<' лизовано на алгоритмических языках Паскаль а Фортран и функционирует на микроЭЗЛ 1Ш РС.

Для проверки эффективности синтезирозаншас. алгоритмов Си ли проведенч экспериментальные исследования на комплексе пра; тических задач. Оценка эффективности алгоритмов размещения

проводилась по;;коэ®1ЭД!енту'1:спользова!111я 'материала, таге как этот коэффициент' является иордаг^вяьм ¿ля рассматриваема* отраслей йромнпдешгЬсти. Разработанное программное ойсс печение было использовано для проектирования размещений деталей механики шанино и раздачи»: деталей. слоеной конфигурации из фпбри. 'Баш . ейпезированы промыалегс-ке раскройное карти с учетом слещ^ш^кошфетюлс производств. Применение в данном случае разработанного программного обеспечения позволило повыесть коэф|Ш1ент пепользоэагшг материала в средне» на' 10-11$. Для -оцеиш эффективности алгоритмов размещения прямоугольник геометрических,^ нроведено большое количество расчетов реальшзх зздач.: Проведенное эксперимент« показали, что синтезированные алгоритма гагу? бить эффективно кспсяьзоваш ке тольков услоы:ях лазерной технологи, ко при традиционных методах'раск|юя.' Практически во всех расчетах был получен коэффициент раскроя ке нинс нормативного со отрасли,- что.подтверждает внеоку» эффективность синтезпрозая-тзе алгоритмов. С цельр оценки качества скктез прозак-шх алгоритмов поиска эффектившх траекторий дв;кек:и лазерного резака проведен сравнительнкй эксперимент с.алгоритмом полного перебора возмогтзе лопарнкх соедикеггай .верзил нечетной степени. Специально для дачного эксперимента'с штользованием рекурсивна функций синтезировано программное обеспечение, позволяющее получить -оптимальную траекторию холостого хода лазерного резака в результате хгрямого1 ; полного "перебора. Про-зедеиипе эксперименты показали, что при числе зернин нечета ной степени больпе восьми алгоритм полного перебора. становится практически неприемлемом для решения исходной задачи, из-за больпих вре.мешпгх затрат. В тоне время разработанной ал-горстм.с использованием-1.5одафицированного метода зетЕей и границ позволяет • получить „-■' приемле:,кй результат при нез-качптельних затратах времени. При этом на малой размерности 'задач, как показали проведеннке эксперименты, в пяти Из семи случаев полученный с помодьа синтезированного в работе алгоритма результат является оптимальным.

Таким образом, прозедешше экспериментальные исследования подтвердили правильность сделанных в работе теоретических вкводов, вксокуп эффективность и работоспособность спнтезиро-

ипшх алгоритмов, а внедрение в народное хозяЕстло-прахси->скуэ це:шость получешгкх результатов.Для оценю: эффектка-¡сти внедрен::* лазерной технологии Ери раскрое з целом »ведено сравнение технологических процессов изготовления ¡талей механики пианино. трацпциоихи:: е по с обо:.: и с нсполъзо-1зп:ем лазерного раскроя. Переход пр:: изготовлении деталей .ханжи пианино на лазерную технологи» позволяет достигнуть кштадогоП окояокнк раскраЕзаеиого материала па 294£,уцает-: число операций, ясобходавчх на. езготоздсйио деталей кех&'п:-

п::а;:гло, умень-пггъ более чем на полов:пг/, увеличить про-водителыюсть технологического потока, представляется воз-к-мстъ полностью автоматизировать, процесс изготовления ^ета-й механик:: пианино и т.д. Таким образом ,. сопоставление з ином случае трздлщюшюго тсхполопгсеского процесса и :го-го демонстрирует преимущество последнего. Эффективность впе-слия в дашом случае полностью определяется полученной эко-кией раскраиваемого материала, т.е. качеством раскройшх анов, синтезмрозанн'гх с помогла разработанного программного еспечешш. 3 заклнченип .рассмотрены'некоторое практ;пеские гсектн внедрения разработанного алгоритмического обеспечен:'.1: :оставе автоматизированной систем: управления технодогичее-I процессом лазерного раскроя. Призеденн результат:» экспонентов по раскрои фибра и граба.

' В заключении изложен« осшвше,результат;-: , получешг-й цгссертацяонной работе. ,,

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

:-• ОСНОШЫБ РЕЗУЛЬТАТ РАБОТЫ -

Основные таучнке результата. диссертационнойЙ работе сос-:т в следующем: •'■''■■' .- '

1. В результате анализа особенностей технологического цесса лазерного раскроя древесных и целяшозяс-бумаг'. :сс ериалов выявлен комплекс основкг-х факторов, опредеяяктас уктуру ограничений в рекаеыкх задачах, а сформулиропачк терки оценка получаемьс репеккй. ' :• . " ,.

2. Синтезирована а исследована модель размещения одно-

£ . .

вязн'У. геометрических объектов сломсной ко5хТ)игурацки в одно-ал зной прямоугольной области размещения с учетом сфоршро-зк чого вектора технологических и оргашзационшх ограничений условиях лазерного раскроя.

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

4. Разработана математическая модель и синтезирован ал-орнтгл генерация частично смешшнгх комбинировали! х размеще-:яй на основе.двухуровневой оимойзациошюй схем:' и метода .ослсдовательного улучшения.

5. Синтезировали и исследованы,модели задачи поиска .ффективиг-т: траекторий движения лазерного резака в условиях [сревообрабативаыцой и ЦЕП. 11а основе интегрированного ис~ юяьзования сицтезированшвс алгоритмов поиска ишикад юй 'расктории холостого хода лазерного резака и алгоритгла ю'.де-:отт эйлерова цикла разработана серия алгоритмов форшрола-ига наклучаей траектории' резания различной•внчислитсльпсй :яохносгя с учетом технологических ограничений.

6. Для определения минимальной длин;: холостого хода яа-5ср1ьлч> резака мо.дифицирован метод ветвей и границ. В резуль-сато чего сштезировони' аяторитш поясгл минимальной траскто-Х1и холостого хода с ввсде;шем процедур условного ветепешш

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

7. На базе синтезировашпгх адгор.ггмов созвано гибкое, цегко адаптируемое к различном производственном условиям программное обеспечение для реаешш :<адач размещения геометрических объектов и формирования эффективных траекторий ролл ния. йрименение разработанного программного обеспечения позволяет обеспечить значительную экономны раскраиваемого материала, сокращает время резания, позволяй: более э£>фек?иь.':о

j^'19 _ •.

использовать техдо^гтегскиа лазерные установки п увеличить срок IX слугбн, .

8. Проведенше- эк5пс,рдапгалышй исследования- подтвердили правильность сдслшвют; в работе' теоретических выводов, згеокун п?ф:ктш?!гост-у сшгс з крогллннх алгоритмов, а промышленное внедрение их прагетпсс^суя цепкость. Разработанное программное обеспечение- а- есс^ зл®ленты используются на ряде предприятий страян. эсо.ксаднескгй эффект от его внед рения составляет 242,12. даируЗ-л

Излокенике в днх сертацта. положения ивквод:: отрасеш.- в следущпх опубликованных, работах, автора:.-

1. Павлов В.Г. .Самоддин А..1Ц и др., Автоматизированной ксгяг-лекс рационального раскроя, па базе мжроЗЙ^Г/атемагнчгсяое обеспечение рационального'раскроя в системах-автоматизирссвзп-ного проектирования: Натериалн Всесоюзной. научно-тсхштческой конференции. Уфа, IS88.-C.I3I-I34.

2. Павлов ? Г. ,Самоядшт А.Н., идр. Система-. автоматизцровашго-го управления технологическим процессом лазерного раскроя материалов деревообработка/Интенсификация. производственных процессов'в отраслях лесного комплекса с'использованием комплексной механизации и средств-вычислительной. техники: Тез. докл. Всесоюзного научно-технического. секивара» Ленинград, 1588.-С.28-31. - .

3.- Павлов Ю.Г., Самодкин А.Н.и др.. Автоматизированное проектирование технологии лазерной.резки в мебельном производстве //Перспективнее материалы и технологии в производстве мебели и стопярно-строигельнюс изделий:- Материала научно-техшгае -ico конференции с мекцународнны участием. СтарагЗагора,1588.-С.2й

4. Павлов Ю.Г., Самоддип А.Н. Автоматизация; подготовки техно логического процесса лазерной обработки мате^'-алов,{/Научно-технический прогресс в лесной н деревообра,. т'ва-щс-й нро?.шш-ленности:Матерпатр-- Всесоюз ной научно-технической, копфеосзщпи. Киев, 1989 . - С.43. ;':■'.

5. Павлов Ю.Г. .Самоядш А.Н. Оно 'деление оптимально?: траекто рии резания при лазерном раскрое материалоз//Научно-техничес кие разработки проблей лесного комплекса: Меявузовский сб. научннх тр. Л.: ЛТА, IS89. - 0.70-74.

6. Павлов Ю.Г., Сададцки А.Н. Гибкая управляемая CAl'íP прямо-

угольного раскрой//, Автоматизация технологического проекти-ро. кшкя:¡-¿атегиаяи научно-технической конференции. Пенза,1989. - сла-19. •

7. Павлов В.Г., Cai40Ír7ftiH А.Н. и др. Автоматизации проектиро-ванш траектория, лазерной резки штериалов//Автоматизация технологического проектирования: -Материала научно-техничес-кок конференции. Пенза, 1989. -C.IQ-II. Б. Павлов Ю.Г., Самолдеш А.Н. Диалоговая управляемая САПР прямоугольного раскроя. "Деревообрабагнващая прамкляенность, 1939, » п, с. 13-14.;. ...-. д■■■■;.

9. Павлов Ю.Г., Саыодглн А.Н. Авто;,'атизация проектирования технологии лазерной резки вмашиностроении. - Экспресс- ин-грор; ¡ащш//1есоэксп:^атащ1Я и лесосплав, 1990, шп.20, С.20-

29. ". '■■; ,.-' . , ,

10. Самодцш А.Н. Диалоговый комплекс авгоматизировшшой иод-готовки технологического процесса лазерного раскроя. - Экс-нресс-щ1формация//1ес6эксцлуатация и лесосплав, I9S0, вкл.20» С.30-31. ■ '

11. Самодцш А.Н. и др/Графический редактор для вычислительного комплекса на базе микроЭШ "Электроника-60". - В сб.: Депонированные'научнкв 'работы. - ГЛ.ШЙШЭИдеспром, XS82,

й ¿413-лб 89, 10 С.

12. Самолдин А.Н. Автоматизация процесса лазерной резки лис-товнх целяюлозко-бушгных к древесных материалов на базе микроЗШ// Современные проб пеш автоматизации и внедрения выделительной техники в целлюлозно-бумажной и деревообрабатк-ващзй. промышленности: Тез.докл. Всесоюзного научно-технического семинара. Москва, 1990. - 0.55 57.

13. Самолдин А.Н. Метод и алгоритм раскроя листовых материалов'на криволинейные заготовки для АСУ ТЦ//Автоматизация и компьютеризация информационной техники и технологии: Сб. научн. тр. ШТИ. В¡.-п. 232. М.: МЕТИ, 1990. - С. 157-164.