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

•.г> л

г >

О

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

ч

1№€

МАРТЫНОВ Виталий Владимирович

АВТОМАТИЗИРОВАННАЯ СИСТЕМА УПРАВЛЕНИЯ ПРОЦЕССОМ РАСКРОЯ ГЕОМЕТРИЧЕСКИХ ОБЪЕКТОВ СЛОЖНОЙ ФОРМЫ

Специальность 05.13.06 — Автоматизированные системы управления

АВТОРЕФЕРАТ ¡уюх'ртацин на соискание ученой степени доктора техппческих паук

УФА 1999

Работа выполнена в Уфимском государственном авиационном техническом университете

НАУЧНЫЙ КОНСУЛЬТАНТ:

доктор технических наук, профессор Э.А. Мухачева

ОФИЦИАЛЬНЫЕ ОППОНЕНТЫ: доктор технических наук, профессор В Л. Якунин доктор технических наук, профессор В.П. Кулагин доктор технических наук, профессор Г.Г. Куликов

ВЕДУЩАЯ ОРГАНИЗАЦИЯ:

Национальный институт авиационных технологий (НИАТ, г. Москва)

ос часов на

Защита состоится « //ъ Ф^Ре?/?^ 2000 года в ^ заседании диссертационного совета ДР-063.17.34 Уфимского государственного авиационного технического университета по адресу: 450000, Уфа-цеьпр, ул. К. Маркса, 12, УГАТУ.

С диссертацией можно ознакомиться в библиотеке университета

Автореферат разослан « Ученый секретарь диссертационного совета 1Уз. Миронов

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

Актуальность проблемы

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

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

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

тижешм определенных критериев. К этому классу относятся задачи компоновки оборудования или грузов в летательных аппаратах (ЛА), на судах, в производственных цехах, архитектурных сооружениях, моделирование интерьеров и т.д.; задачи размещения элементов на платах и плат в корпусах; задачи проектирования генеральных планов предприятий и карт раскроя промышленных материалов и др. Смежную область занимают проблемы прокладки оптимальных трасс (трассирозки) в областях с запретами.

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

При решении данной проблемы автор в своих исследованиях опирался на труды российских и зарубежных ученых, внесших большой вклад:

- в развитие теории системного анализа и моделирования больших систем (В.И. Николаев, Ф.И. Перегудов, Ф.П. Тарасенко, Л. Заде, И. Дезоер, Б.Г. Ильясов, Г.Г. Куликов, их ученики и последователи и многие другие);

- в создание и исследование автоматизированных систем управления (СЛ. Оптяер, Н.М. Моисеев, А.Г. Мамиконов, В.Н. Бурков, В.М. Глуш-ков, Г.С. Поспелов, И.Ю. Юсупов и др.);

- В ВОПрОСЫ СОЗД&Я2Я СИСТ©М ЗЗТОМйТНЗКрОВЗННОГО ПрОСКТЯрОЗЗПИЯ к технологической подготовки производства (А. Фокс, М. Пратт, Г. Шпур, Ф.Л. Краузе, Ю.С. Завьялов, В.Е. Михайлеико, А.Д. Тузов, В.И. Якунин и др.);

- в разработку и исследование задач рационального раскроя (ЛВ. Канторович, В.А. Залгаллер, Э.А. Мухачева, Л.В. Рвачев, ЮЛ". Стоян, НЛ. Гиль, Л.Б. Белякова, Н. ВускЬо1Г, К.А. Г)о^г81ап<1, V. МИепкоую и многие другие).

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

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

2. В настоящий момент определились три основных направления в развитии теории автоматического раскроя:

- направление, реализующее идеи линейного программирования, включающее в себя работы по размещению геометрических объектов без учетов их геометрической формы (при известных способах раскроя). Родоначальниками этого направления являются Канторович Л.В. и Залгаллер В А.;

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

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

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

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

Цель и задачи исследований

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

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

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

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

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

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

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

6. Разработать алгоритмическое и программное обеспечение основных модулей автоматизированной системы управления раскройно-заготовитель-ным производством: интерактивного и автоматического размещения геометрических объектов.

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

Методы исследования

Для решения поставленных задач применялись методы системного анализа, математического моделирования, теории алгоритмов, оптимизации,

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

Результаты, выносимые на защиту

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

х.. &1СТОДОЛОГКЯ дфОСКТНрОВоШЗЯ раЦИОНаЛЬНОГО роЗМСГЦСНИЯ 1Ц10СКИК

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

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

4. Теоретические основы определения областей допустимого размещения объектов сложных геометрических форм на базе операций Мннковского.

5. Основы построения систем автоматизированного интерактивного и автоматического (регулярного, блочно-рехулярного и нерегулярного) размещения плоских геометрических объектов.

6. Алгоритмическое и программное обеспечение модулей интерактивного, регулярного и нерегулярного размещения геометрических объектов в со-

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

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

Научная новизна результатов

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

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

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

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

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

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

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

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

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

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

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

Результаты, полученные в работе, внедрены:

- на Уфимском унитарном агрегатном производственном объединении «Гидравлика», г. Уфа (методы, алгоритмы и программы интерактивной раскладки плоских деталей сложной формы в произвольных областях, автоматического регулярного размещения плоских деталей сложной формы в полосе и на плоскости, автоматического нерегулярного размещения плоских деталей сложной формы на листе к в рулс-нз);

- в Открытом акционерном обществе «Тамбовский завод «Комсомолец», г.Тамбов (комплекс алгоритмических и программных средств автоматизации представления и хранения информации о раскраиваемых заготовках; модули интерактивного размещения плоских фигурных заготовок на листовом и рулонном материале, автоматического формирования раскройных карт для раскроя полосы под шгамповку на фигурные заго-

ТЛРКК op-Tfv»f<irrTrrr«i*vr\r>rt Лпгттттлиоииа T*is^imnwTjtTV fanr ттггс naovrvia

IVil 11Ы, WlVMUlU LWUUl V . .... I - «uj.. "' ^iHV.iUw..

листа и рулона на фигурные заготовки, что позволило упростить процесс описания заготовок, автоматизировать управление процессом раскроя и повысить коэффициент использования материала в среднем на 3,5%);

- в НИАТ, г. Москва (методика вьщеления, описания и размещения панелей теоретической поверхности летательных аппаратов и технологической оснастки, выходящей на теоистическни контур * позволила автоматизировать процесс проектирования оснастки: снизить трудоемкость и сроки проектирования, повысить точность обработки);

- в Акционерном обществе «Химмаш», г. Екатеринбург (методы и алгоритмы рационального размещения геометрических объектов на плоском материале в составе программного комплекса проектирования раскроя-упаковки «Cut-CAD», что позволило автоматизировать процесс проектирования карт раскроя и увеличить коэффициент использования листового и рулонного материала);

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

тирования, повысить точность обработки оснастки, повысить коэффициент использования материала на 7%);

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

Система интерактивного раскроя зарегистрирована (свидетельство Ро-сАПО об официальной регистрации программ для ЭВМ № 970574 от 11 ноября 1997).

Основания для выполнения работы

Работа явилась обобщением результатов исследований автора в период с 1982 года по настоящее время и выполнена на кафедре «Вычислительная математика и кибернетика» Уфимского государственного авиационного техяи-

им^т/тм-о уиицрпгмтрту! *ноТ1Сэт.ттсэсг г»тчзтттачт тттгяэттгчиотттхй »Лх-ттта лтгчо-ггогто г» */»отт_

дидатской диссертации, выполненной в Московском авиационном институте и защищенной в 1989 году. Работа связана с выполнением хоздоговорных научно-исследовательских работ (НИР) с НИАТ, г. Москва, производственным объединением «Гидравлика» по темам № ИФ-ВК 16-91-0Г и ИФ-ВК 0197- ХГ (1991-1999 г.г.), по теме № ИФ-ВК 01-92 ОГ (1992 -1993 г.г.) с АО «Буммаш» (г. Ижевск), а также НИР, финансируемых по единому заказ-наряду Минобразования РФ № НЧ-ЕЦ-42-96 03 (1996-1999 г.г.). Работа поддержана:

- государственными грантами по фундаментальным исследованиям в области технических наук (направление «Информационные технологии в проектировании изделий и технологических процессов их изготовления», раздел «Проблемы управления и контроля технологических процессов изготовления деталей и изделий авиакосмической техники», конкурсный центр МАТИ) по темам «Разработка концепции информационного обеспечения и прикладной системы поискового конструирования типовых деталей машиностроительных конструкций с применением АРМ на базе рабочих станций типа ЗРАИСб^гоп» №НГ-БЦ-05-94-ГР 1994-1995 г.г. и «Информационные технологии раскроя-упаковки одно-и двумерных объектов» №ИФ-ВК-04-98-ГУ 1998-1999 г.г.;

- федеральной целевой программой «Государственная поддержка интеграции высшего образования и фундаментальной науки на 1997-2000 г.г.» - проект «Развитие научно-производственного комплекса по фундаментальным проблемам математики н теории управления» (УГАТУ, ВЦ УНЦ РАН), контракт № 21-76;

- федеральной целевой программой «Информационные технологии в образовании и науке» № НЧ-БЦ-01-97-ПГ (1997 г.).

Апробация работы я публикации

Основные положения, представленные в диссертации, начиная с 1982 года, регулярно докладывались и обсуждались на научных мероприятиях различного уровня. В том числе на:

- Всесоюзном научно-методическом семинаре «Кибернетика графики», Москва, 1985-1988;

- Международной научно-технической конференции «Проблемы графической технологии», Севастополь,1991;

- Межвузовской научно-методической конференции «Перспективные информационные технологии в высшей школе», Самара, 1993;

- Международном семинаре Нанкинского авиационного института - Уфимского государственного авиационного технического университета «Актуальные проблемы авиадвиготелестроения», Уфа - Нанкин, 1994;

- Всероссийской научно-технической конференции «Управление и контроль технологических процессов изготовления деталей авиакосмической техники», Уфа, 1994;

- The 4th International Conference of Computer Graphic and Visualisation, Niz-hny Novgorod, 1994;

- Международной конференции-выставке «Информационные технологии в непрерывном образовании», Петрозаводск, 1995;

- Всероссийской научно-технической конференции «Перспективные информационные технологии в высшей школе», Тамбов, 1995;

- Международной научно-методической конференции «Новые информационные технологии в университетском образовании», Новосибирск, 1996;

- Second International Conference on Distance Education in Russia "Open and International Learning as a Development Strategy", Moscow, 1996;

- Всероссийской научной конференции «Роль геометрик в искусственном шггешгекге и системах автоматизированного про^ктиповяниУлан-Удэ, 1996 г.;

- International Congress "Mechanical Engineering Technologies'97", Bulgaria, Sofia, 1997;

- ХХШ-ХХУ International Conferences and discussion scientific club "New information technologies in science, education, telecommunications and business", Ukraine, Yalta-Gurzuff, 1996-1998;

- The 16th European Conference on Operational Research, Brussels, Belgium, 1998;

- Международной конференции по тренсфер-технологаям, проведенной в рамках программы EU INCO Copernicus AMETMAS-NOE, Уфа, 1999.

Созданная и зарегистрированная в РосАПО система автоматизированного размещения и отдельные ее модули демонстрировалась и были отмечены в составе экспозиции УГАТУ в приказах по Минобразования РФ на:

- Second International Conference on Distance Education in Russia "Open and International Learning as a Development Strategy", Moscow, 1996;

- Международной выставке-ярмарке «Информатика. Оргтехника. Связь», Уфа, 1994-1997 г.г.

Результаты диссертационной работы непосредственно отражены в 53 публикациях, в том числе в монографии (13,5 пл.), двух учебных пособиях (5,6 п.л. и 4,5 пл.), 22 статьях, 24 трудах конференций (14 докладов и 10 тезисов), 1 свидетельстве на регистрацию программ в РосАПО, 3 депонированных научно-технических отчетах по госбюджетным и хоздоговорным темам, выполненным по теме диссертации при непосредственном участии и руководстве автора.

Структура и объем работы

Диссертация состоит го введения, 6 глав, выводов, списка литеразуры и приложений, включающих акты внедрения результатов работы, примеры раскройных карт промышленных материалов, полученных в результате решения соответствующих задач размещения ГО в полосе, решетчатого размещения, размещения на листе с помощью предложенных в диссертации методов и алгоритмов. Раи era изложена на 272 страницах машинописного текста, кроме того, содержит 76 рисунков и 7 таблиц, размещенных на 48 страницах. Библиографический список включает 235 наименования и занимает 22 страницы.

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

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

Во введении обоснована актуальность работы, определена ее цель и задачи, сформулированы положения, выносимые на защиту, их научная новизна и практическая ценность. Приведены основания для выполнения работы, ее апробация и структура.

ГЛАВА 1. АНАЛИЗ СОСТОЯНИЯ ПРОБЛЕМЫ АВТОМАТИЗАЦИИ РАСКРОЙНО-ЗАГОТОВИТЕЛЬНОГО ПРОИЗВОДСТВА

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

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

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

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

Среди комплекса задач проектирования АСУ РЗП существует класс актуальных задач, связанных с размещением геометрических объектов в различных областях размещения. Данный класс задач известен как проблема раскроя-упаковки (cutting and packing).

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

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

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

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

областях произвольной конфигурации.

ГЛАВА 2. МЕТОДОЛОГИЧЕСКИЕ ОСНОВЫ ПОСТРОЕНИЯ СИСТЕМЫ УПРАВЛЕНИЯ РАЗМЕЩЕНИЕМ ПЛОСКИХ ОБЪЕКТОВ СЛОЖНЫХ ФОРМ В ОБЛАСТЯХ ПРОИЗВОЛЬНОЙ КОНФИГУРАЦИИ

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

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

На основе разработанной методологии определена структура и задачи, которые необходимо решить при проектировании системы, исследованы ее внешние связи и взаимодействие с основными системами интегрированного промышленного комплекса. Определены основные этапы проектирования АСУ РЗП (табл. 1).

тттштш^тттятт

ПОДХОДЫ КОНКРЕТНЫЕ задачи и МЕТОДЫ ПРИНЦИПЫ ФУНКЦИОНИРОВАНИЯ

еиггем-иый 1) определение связей х; внешней средой 2) определение состава системы (на уровне подсистем) Л «разделяй ииластвуй» иерархического упорядочивания

структурный 1) анализ системы 3) струкгур- 2) скитзз сястсмы ная модель 1-формализации

функциональный 1) определение глобаиьой пели системы 2) определяя^ функций подсистем 3) построение функциональной 'МЧлиСЛИСпьЛ £МЬ4 ' . ■ . упрятывания концептуальной общность* полноты

/ГЦ/ ^^*> непротиворечивости : логической независимости

эволюционный - 1) генетически? алгоритмы раскроя

Хйберне-л тичесий ■ 1 )рсализашгобратной связи-2) наличие ЛПР в составе АСУ РЗП : принцип независимости..... Данных

оптимиза ЦИ01ШЫЙ 1) разработка теории и методов -• = оптимизации раскроя ■ принцип [структурирования данных-

информационный ■: 1) разработка информационной ' • -модели ИС РЗП 2) разработка и агсздл ПО подсистем АСУ РЗП ввод в эксплуатацию и ......! сопровождение принцип доступа конечного нольчовятепя ♦--Применяются для всех . задач я.методов. ■ ~ >

Рис. 1

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

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

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

Даны основные понятия и определения, введена терминология, позволившие формализовать реальные производственные явления. Произведена

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

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

таблица 1

ЭТАПЫ РАЗРАБОТКИ АСУ РЗП КОНКРЕТНЫЕ ЗАДАЧИ И МЕТОДЫ

Выработка стратегии 1) определение глобальной цели системы 2) определение связей с внешней средой 3) определение состава системы (на уровне под-

Анализ требований 1) анализ системы 2) синтез системы 3) структурная модель

Проектирование 1) определение функций подсистем 2) построение функциональной модели системы 3) реализация обратной связи 4) наличие ЛПР в составе АСУ РЗП 5) разработка информационной модели АСУ РЗП 6) разработка теории и методов оптимизации раскроя

Кодирование 1) разработка ПО всех подсистем АСУ РЗП

Тестирование и отладка 1) опытная эксплуатация и отладка ПО всех подсистем АСУ РЗП

Эксплуатация и сопровождение 1) ввод АСУ РЗП з промышленную эксплуатацию 2) обучение персонала 3) эксплуатация АСУ РЗП 4) сопровождение АСУ РЗП

ГЛАВА 3. ТЕОРЕТИЧЕСКИЕ ОСНОВЫ МОДЕЛИРОВАНИЯ РАЗМЕЩЕНИЯ ГЕОМЕТРИЧЕСКИХ ОБЪЕКТОВ

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

дробей. Разработаны теоретические и алгоритмические основы создания интерфейсного модуля ввода данных о ГО и областях размещения в АСУ РЗП.

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

На основе анализа операций Минковского над множествами показано, что сумма Минковского С = А Ф (—В) - множества А и множества, центрально симметричного множеству В относительно начала координат, и разность Минковского D — А/В этих множеств имеют большое значение для анализа взаимного расположения множеств: при помощи суммы определяется ОДР одного ГО снаружи другого, а при помощи разности - ОДР одного ГО внутри другого. Сформулированы и доказаны соответствующие утверждения 1 и 2, подтверждающие справедливость сделанных выводов.

Утверждение 1:

Пусть С — А®(—В). Для того, чтобы множества А и В пересекались, необходимо и достаточно перенести множество В на вектор с или множество А на вектор -с, где с е С, а С = А © {-В), т.е.

А~с С\В*ЪштАС\Вс * 0, если се Л® (-Я). (1)

Утверждение 2:

Пусть D-AJß. Дох того, чтобы множество Б располагалось внутри множества А без пересечения границ, необходимо и достаточно перенести множество В на вектор d или множество А на вектор -d. где äsD,aD = AI В:

B<zA~diumBdc:A,ecmdeA/B. (2)

В соответствии с методами реализации основных алгоритмов определения ОДР и необходимостью специального представления информации о ГО и областях размещения в геометрических операциях задач раскроя-упаковки обоснована необходимость разработки интерфейсного модуля, обеспечивающего передачу данных из САПР (CAD/CAM систем) непосредственно в систему раскроя.

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

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

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

Векторные способы представления информации менее чувствительны к точности задания контура. Для контуров, состоящих из отрезков прямых и дуг окружностей1, о зависимости количества аппроксимирующих линейных участков от величины относительного допуска на аппроксимацию можно судить по следующему графику (рис. 2). При использовании различных типов оборудования для раскроя, от точных лазерных резаков до грубой вырезки автогеном интервал допуска колеблется в пределах Д = 0.1...5% от максимального размера контура заготовки. Увеличение допуска на порядок

100 80 6040 -

200

п(д)

4 5

Рис.2

Д,%

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

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

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

Исследование особенностей построения ОДР для многоугольных ГО позволило разработать метод определения ОДР двух ГО сложной формы (рис.3), основанный на топологическом способе построения суммы Минков-ского, инвариантный к способу задания информации об объектах. Выражение для определения ОДР ГО Б7 относительно Б имеет вид:

г \

ПЕ = Д2\П£, п£=«\ и^Т«-^((О7ей*)п8 = 0)1,где

и )

(

п=

(3)

<-> vo/ у ио^ ОУС^О]) V '. > и

К2 - двумерное евклидово пространство. Остальные обозначения в соответствии с рис.3.

Разработаны способы реализации метода определения ОДР на базе обычного аналитического задания ГО и на базе задания при помощи правильных дробей. В частности показано, что при практической реализации данного метода можно выделить три группы:

1) генерация ГО, участвующих в построении ОДР;

2) объединение сгенерированных объектов;

3) корректировка границы ОДР.

Если реализация первой и третьей групп не составляет проблемы, то во второй группе основной операцией является циклическое повторение последовательного попарного объединения двух ГО. Если выполнять данную операцию «в лоб», в результате многократных итераций и приближенных вычислений на ЭВМ в геометрических операциях пересечения прямых происходит накопление погрешности и, как следствие, потеря точности вычислений.

Рис. 3. Геометрическая интерпретация определения ОДР

В работе предложены следующие пути выхода из данной ситуации:

1) для обычного аналитического задания ГО - минимизация итеративных операций пересечения отрезков и выполнение их на заключительном этапе сборки ОДР;

2) задание информации о ГО в виде правильных дробей и оперирование с ними;

3) растровое или дискретное задание ГО.

Для первых двух путей разработана алгоритмическая база и произведена программная реализация. Задание ГО дискретно-логическим способом успешно используется в работах Верхотурова М.А.

В процессе разработки алгоритмической базы для определения ОДР на основе задания информации о ГО в виде правильных дробей был предложен способ задания длинных чисел в виде массива беззнаковых двойных слов, длиною 32 бита. Первое слово в массиве показывает длину числа в двойных словах, затем следует само число в 1п£е1-порздке, то есть слева направо (рис. 4). По отношению к системам счисления данная форма представления чисел является системой по основанию 232=4294967236, то есть каждое двойное слово - это одна отдельная цифра. Такой подход к хранению и представлению чисел существенно упрощает задачу и позволяет на современных 32-битных процессорах достичь максимальной производительности, избавившись от операций конвертации чисел.

length

Dword 0

_L

Dword 1

16 24 31 0 8 16 24 31

Рис.4

I I ттгт ПЛТУТТЛГ'Л ГГ»^гтггттГГ ГТТТЛА!» «ЧЛЧМЛ^/\Т<ЛТТ * IлттГТТАЛТ»Т»ТГ

¿Х^хл. дшшчЛ и ¡.(л^л^шкл. ¿Ич.^.» ^^^¿ии («шхума!и^««^'!!

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

ГЛАВА 4. РАЗРАБОТКА МАТЕМАТИЧЕСКИХ МОДЕЛЕЙ

РЕГУЛЯРНОГО РАЗМЕЩЕНИЯ ГЕОМЕТРИЧЕСКИХ ОБЪЕКТОВ

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

Известно, что существуют регулярные и нерегулярные укладки. К регулярным (периодическим) укладкам в Л "-пространстве относятся укладки, образованные посредством параллельных переносов ГО или группы (блока) ГО на векторы

К, - (4)

где/я = ±1,±2, ...,±оо; j й 1,2,..., п.

При анализе способов образования периодических укладок в задачах регулярного размещения ГО в R2, показано, что существуют однорядные и решетчатые периодические укладки конгруэнтных ГО и блоков ГО в неограниченных и ограниченных областях. Многорядные укладки являются подмножеством решетчатых укладок.

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

Применение аппарата определения ОДР в общем случае позволяет уменьшить размерность задачи определения рациональной однорядной и решетчатой укладок конгруэнтных ГО до одного и двух параметров соответственно.

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

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

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

Рис.5

вине числа их перестановок:

К=п!/2.

То есть, для нахождения варианта рационального размещения в данном случае процедуру перебора и параметров - для случая ориентированных относительно друг друга ГО и 2(п-1) - для неориентированных, характеризующих каждое размещение последовательности, необходимо повторить К раз. Таким образом, размерность N задачи нахождения рационального размещения блока ГО в полосе определится по следующим формулам:

М=К*п =п *п У2 - для ориентированных ГО.

1^=К*2(п-]) = п! *(п-1) -для неориентированных ГО,

где п>1, т.к. вслучае п=1 теряется смысл неориентированности.

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

Исследование решетчатого размещения конгруэнтных ГО (рис. 6) позволило при применении аппарата определения ОДР сузить область определения рационального решения практически до одного параметра (вектор Ы), т.к. второй параметр (вектор Ьз) в данном случае может быть определен точно без использования итеративных методов.

Рис.б. Определение параметров рациональной решетки

Используя подходы, примененные для определения рационального регулярного размещения блока ГО в полосе, в работе исследована задача решетчатого размещения блока ГО и показано, что при небольшом количестве ГО в блоке задача также может быть решена итеративными методами с использованием элементов теории вероятности.

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

ГЛАВА 5. МАТЕМАТИЧЕСКИЕ МОДЕЛИ НЕРЕГУЛЯРНОГО РАЗМЕЩЕНИЯ ГЕОМЕТРИЧЕСКИХ ОБЪЕКТОВ

В главе 5 исследована проблема нерегулярного размещения ГО. Предложены методы автоматизированной интерактивной раскладки, а также автоматического рационального размещения ГО в областях на базе разработанного метода нахождения ОДР.

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

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

Произведена конкретизация общей задачи размещения ГО на класс задач нерегулярного размещения. Исследованы критерии оптимизации при нерегулярном размещении ГО. Показано, что плотность заполнения, являющаяся глобальным критерием, не может являться критерием оптимизации в процессе размещения, т.к. носит дискретный характер. Выделены две группы критериев оптимизации в процессе размещения ГО: линейные и двумерные, доказана их согласованность с глобальным критерием. Из их числа выбраны независимые критерии, на этой базе определена функция цели С* и предложен интегральный локальный критерий оптимизации для определения рационального положения ГО в процессе размещения:

где Хюк. = а\Хп + а2%я +«зЖ54;

а; - весовые коэффициенты, подбираются эмпирически ^«г,- = 1;

м

Хц- минимальная абсцисса размещаемого ГО; Хц - площадь части области размещения, отсекаемой размещенными ГО;

Х5ц - площадь части области размещения, отсекаемой одним

размещаемым ГО; (7 - область ограничений;

2 - 2{хх, уи, х2, у2,вгх„, у„,вп) - вектор параметров, определяющих положение ГО в области размещения.

0<гЛ<>

б)

Рис.7. Определение ОДР для ГО £ и области размещения У

С целью уменьшения общей размерности задачи нерегулярного размещения ГО произведена адаптация разработанного аппарата определения ОДР на данный класс задач. ОДР П ГО 5" в области размещения определится как:

¡=1 м

где обозначения понятны из рис. 7.

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

Процедура распределения >ТО по областям размещения (внешняя или внутренняя)

___* _,

Модуль размещения ГО на| разе ОДР по алгоритму ПУГП|

V '

Модуль постобработки ! раскроез !

I Л

Проверка достижения общего допустимого глобального критерия ¡замещения или предельного времени

Блок ввода Блок вы-

информации вода ин-

в модуль формации

V. Вывод на

печать

1

Вывод на | оборудование!

Рис.8

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

на плоскость. Разработаны теоретические основы решения данной проблемы. Эта проблема представляется интересной также с точки зрения ее вхождения в АСУ РЗП в части определения формы плоских заготовок (панелей) и рационального размещения их на материале.

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

ГЛАВА 6. ИССЛЕДОВАНИЕ ЭФФЕКТИВНОСТИ ФУНКЦИОНИРОВАНИЯ АВТОМАТИЗИРОВАННОЙ СИСТЕМЫ РАСКРОЯ В СОСТАВЕ АСУ РЗП

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

Разработка АСУ РЗП велась в соответствии с разработанной методологией и последовательнсстью разработки (глава 2). Жизненный цикл (ЖЦ) АСУ РЗП образуется в соответствии с принципом нисходящего проектирования и носит итерационный характер. Это заключается в том, что реализованные этапы проектирования системы, начиная с самых ранних, циклически повторяются в соответствии с изменениями требований и внешних условий, введением дополнительных ограничений и т.д.

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

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

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

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

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

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

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

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

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

РЕЗУЛЬТАТЫ И ВЫВОДЫ

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

При решении этой проблемы получены следующие научные и практические результаты и сделаны выводы:

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

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

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

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

4. На основе исследования способов задания и оперирования информацией о ГО в задачах раскроя-упаковки определено представление графической информации в модуле построения ОДР и в соответствии с этим разработана методическая и алгоритмическая база ввода информации в систему размещения ГО. Информация о ГО в систему раскроя может поступать различными способами, в том числе из САПР. Для приближенных мето-

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

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

6. Разработаны теоретические и методологические основы модулей рационального нерегулярного интерактивного и автоматического размещения

оотютгттттлг л^тгллтт» п«лтг>1»лт.млй Ллптт тго пч>»пч(лл'мттпгл >гл.

и ■ "V *,* VI"' ',»' л и1ЛЛ ирип^иилоиии ШЧ'^'и'Ш! ии Ч^МОЪ* ММОриЬО 1У1Л*

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

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

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

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

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

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

- экономию в объемах информации за счет объединения локальных систем РЗП в интегрированную;

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

Эффективность АСУ РЗП и ее отдельных модулей подтверждается внедрением разработанных в диссертации теоретических основ, методов и алгоритмов в промышленность на ряде предприятий (НИАТ, г. Москва; КуАЗ, г.

Самара; АО «Химмаш», г. Екатеринбург; УУАПО «Гидравлика», г. Уфа;

ОАО «Тамбовский завод «Комсомолец», г.Тамбов).

СПИСОК ОСНОВНЫХ ПУБЛИКАЦИЙ

1. Желонкин Е.И., Мартынов В.В. Об анализе и синтезе технических систем в автоматизированном конструировании //Тезисы докладов межзонального научно-методического совещания-семинара заведующих кафедр и ведущих лекторов по начертательной геометрии и инженерной графике. -Йошкар-Ола: МПИ, 1982. - С. 69-70.

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

ния-семинара заведующих кафедр и Бедущих лекторов по начертательной геометрии и инженерной графике. - Йошкар-Ола: МПИ, 1982. - С. 104105.

3. Желонкин Е.И., Мартынов В.В. О некоторых теоремах связи в иерархии системы //Актуальные вопросы инженерной графики: Сборник научно-методических трудов. - Йошкар-Ола: МарГУ,1984. - С.110-112.

4. Мартынов В.В. Методика решения геометро-технологических задач при членении планера по агрегатно-геометрическому признаку (руководство): В техническом отчете №21800 ГРУ-26050, этап 5, приложение 1. - М: МАИ, 1986.-40с.

5. Мартынов В.В. Алгоритм линейной аппроксимации плоского контура (руководство): В техническом отчете №905-02-И, ГТ81001625.- М.: МАИ, 1986.-С.72-75.

6. Мартынов В.В. Метод оптимизации расположения ГО при обработке об-водообразующей оснастки в авиастроении //Геометрическое моделирование в авиационном: проектировании: Сборник научно-методических трудов - К.: КНИГА, 1987. - C.1S-2L

7. Мартынов В.В., Иванов B.C. Отображение в инверсии трех окружностей на окружности с колинейными центрами //Сборник научно-методических статей по начертательной геометрии и инженерной графике. - М: Высшая школа, 1987.-С.111-113.

8. Мартынов В.В. Аппроксимация плоского контура многоугольником при решении задач оптимизации размещения обводообразующей оснастки //Начертательная геометрия и машинная графика в практике решения инженерных задач: Сборник научных трудов. - Омск: ОмПИ, 1987. - С. 7378.

9. Мартынов В.В., Султанова О.Г. Особенности построения годографа ли-нейно-апроксимированных малкованных геометрических объектов. - М., 1 pvKorcKcb дево?ш*х>взкз в ВИНИ1И 22.07.8* ^£"74 В*^— 1 о.

Ю.Мартынов В.В., Султанова О.Г. Способ линейной аппроксимации малко-ванной поверхности деталей обводообразующей оснастки в задачах оптимизации размещения. - М., 1988. Рукопись депонирована в ВИНИТИ 22.07.88 № 5873 В88.- 8 с.

11.Тевлин А.М., Мартынов В.В., Мартынова О.Г. Повышение эффективности изучения начертательной геометрии на примере создания автоматизированной системы размещения //Основные направления повышения качества подготовки инженерных кадров: Тезисы республиканской конференции. -Л.: ЛПИ, 1988. - С. 11-12.

12.Мартынов В.В. О методике решения задач оптимизации размещения малкованных геометрических объектов на плоскости //В сборнике научно-методических статей по начертательной геометрии н инженерной графике. - М.:МПИ,1989. - С.104-106.

13.Тевлин А.М., Мартынов В.В., Мартынова О.Г. Опыт использования автоматизированной системы размещения в курсе НИРС по прикладной геометрии //Комплексная компьютеризация учебного процесса в высшей школе: Тезисы докладов республиканской научно-методической конференции-Л.: ЛКИ, 1989,-С.42.

Н.Мартынов В.В., Тевлин А.М. Функция инцидентности границ в задачах оптимизации размещения геометрических объектов //Геометрическое моделирование инженерных объектов и технологических процессов: Сборник научных трудов. - Омск: ОМПИ, 1989. - С.10-12.

15.Мартынов В.В. Определение геометрических параметров плоского контура //Актуальные вопросы начертательной геометрии и инженерной графики: Тезисы межзональной научно-методической конференции. - Йошкар-Ола: МарПИ, 1990, ч.2. - С. 10-11.

16.Мартынов В.В., Орехов В.Б. Применение графического редактора в про-

TTSCCv Пр5П0ДшЗйсгИЯ xiiDr..SLiSpHOK Граф'НКН Ji НаЧСрТлТсЛьКОи Геометрии

//Интеграция инженерно-графических дисциплин в процессе подготовки инженеров: Тезисы докладов межвузовской научно-методической конференции. -Чебоксары: ЧТУ, 1993. -С.33-34.

17.Маршнов В.В, Меерсон Б.М. Визуализация алгоритмов базовых геометрических пространственных преобразований //Перспективные информационные технологии в высшей школе: Тезисы докладов межвузовской научно-методической конференции. — Самара: СГАУ, 1993. - С,98-99,

18.Martynov V. Software and methodics materials of the course Computer graphics in the US ATU //The 4-th conference of computer graphic and visualisation: Proceeding of conference. - Nizhny Novgorod: NGTU, 1994. - P. 158-160.

19.Мартынов B.B., Верхотуров M.A. Анализ состояния работ в области фигурного раскроя промышленных материалов //Актуальные проблемы авиадвиготелестроения: Труды Международного семинара Нанкинского авиационного института - УГАТУ. - Уфа: УГАТУ, 1994. - С. 108-113.

20.Поликарпов Ю.В., Зелев А.П., Мартьшов В.В. Конструирование технических кривых и поверхностей (Учебное пособие). - Уфа: Издание УГАТУ, 1994.-89 с.

21.Стариков В.Н., Мартынов В.В., Тархов С.В. Сетевые информационные технологии в компьютерной подготовке специалистов в УГАТУ //Информационные технологии в непрерывном образовании: Международная конференция-выставка. - Петрозаводск: Издание ПетрГУ, 1995. -С. 82-83.

22.Мартынов В.В., Стариков В.Н., Ноготков А.О. Системы поискового конструирования на базе SPARCstation /ГУправление и контроль технологических процессов изготовления деталей авиакосмической техники: Тезисы всероссийской научно-технической конференции. - Уфа: УГАТУ, 1995. -С. 22-24.

23.Мартыиов В.В. Перспективы применения НИТ при автоматизации рационального раскроя //Информационные технологии обучения: Межвузовский сборник научных трудов.-Самара: СГАУ, 1995.-С.35-41.

24.Мартыноз В.В. Иллюстративная, деловая и презентационная графика на базе CorelDRAW (учебное пособие). -Уфа: Издание УГАТУ, 1995. - 72с.

25.Мартынов В.В., Чужинов Т.Ю. Пакет геометрического моделирования рационального раскроя //Роль геометрии в искусственном интеллекте и системах автоматизированного проектирования: Сборник докладов Всероссийской научной конференции. - Улан-Удэ: ВСГТУ, 1996. - С. 96-98.

26.Мартынов В.В., Чужинов Т.Ю. Создание САПР раскроя на базе моделирования физических процессов естественного уплотнения //Новые информационные технология в науке, образовании и бизнесе: Труды XXIII Международной конференции. - Украина, Крым, Ялта-Гурзуф, 1996. - С. 53-55.

27.Kusimov S., Martynov V., Mukhtarov A., Khisamutdinov R. Bashkortostan higher education institutions network as the basis for the regional system of distant education //Open and International Learning as a Development Strategy: Proceedings Second International Conference on Distance Education in Russia. - M.: World Trade Center, 1996, v.l. - P.215-217.

28.Мартынов B.B., Мухтаров A.P. Об одном способе размещения плоских фигур в областях произвольной формы применительно к технологии конструирования одежды //Роль геометрии в искусственном интеллекте и системах автоматизированного проектирования: Сборник докладов Всероссийской научной конференции. — Улан-Удэ: ВСГТУ, 1996. — С. 104 -106.

29.Мартынов В.В. Геометрическое моделирование размещения отсеков произвольной формы на технических поверхностях //Роль геометрии в искусственном интеллекте и системах автоматизированного проектирования: Сборник докладов Всероссийской научной конференции. - Улан-Удэ: ВСГТУ, 1996.-С. 77-79. -

30.Мартынов В.В. Об одном алгоритме определения областей допустимых размещений геометрических объектов //Принятие решений в условиях неопределенности: Межвузовский научный сборник. - Уфа: УГАТУ, 1996. -

Г* lit "7

V*. i 1—I / .

31.Martynov V. Lattice packing of flat geometric objects on the basis of a permissible allocation area definition method //Decision making under conditions of uncertainty (cutting-packing problems): The International Scientific Collection. -Ufa: Publ. USATu, 1997.-P. 306-313.

32.Martynov V., Vedenyapin I. Reproduction of complicated engineering surfaces from sheet material //Decision making under conditions of uncertainty (cutting-packing problems): The International Scientific Collection. - Ufa: Publ. USATU, 1997.-P. 314-322.

33.Мартынов В.В. Метод определения областей допустимого размещения как база для создания автоматизированной системы рационального раскроя //Новые информационные технологии в науке образовании и бизнесе: Тезисы докладов Международной конференция и дискуссионного научного клуба. -М.: Издание МАИ - Академии САПР и НИТ, 1997. - С. 43-44.

34.Martynov V., Muhacheva Б., Verhoturov М. On the Problem Solving Methods for Shape Cutting under Single Production Conditions //Mechanical Engineering Technologies'97: Proceedings of International Congress. - Sofia, Bulgaria, v.4, September 17-19,1997.-P. 3-9.

35.Martynov V. Muhacheva E., Verhoturov M. Methods of the Rational Periodic Placement of Bars in Stamping Production //Mechanical Engineering Technologies'97: Proceedings of International Congress. - Sofia, Bulgaria, v.4, September 17-19,1997. - P. 10-17.

36.Свидетельство об официальной регистрации программы для ЭВМ «Система интерактивного раскроя Cuttsn> (Мартынов В.В., Чужиков T.IO.) Xs 970554 от~11. 11.1997. М.:РосАПО, 1997. *

37.Верхотуров М.А., Мартынов В.В., Мухачева Э.А. Интегрированная система раскроя-упаковки и ее базовые методы //Информационные технологии в проектировании и производстве: Научно-технический сборник. - М.: Всероссийский научно-исследовательский институт межотраслевой информации, выпуск 3,1997. - С.69-75.

38.Мартынов В.В. Определение области допустимых размещений двух ограниченных плоских геометрических объектов //Вопросы управления и проектирования в информационных и кибернетических системах: Межвузовский научный сборник.-Уфа: УГАТУ, 1997.-С.131-137.

39.Мухачева Э.А., Верхотуров М.А., Мартынов В.В. Основные модели и методы задач раскроя-упаковки //Принятие решений в условиях неопределенности: Сборник научных статей УГАТУ - Уфа: УГАТУ. 1997. - С.57-69.

40.Martynov V. Packing of flat geometric objects in a strip on the basis of a permissible allocation area definition method //Decision making under conditions of uncertainty (cutting-packing problems): The International Scientific Collection. - Ufa: Publ. USATU,1997. -P. 296-305.

41.Martynov V., Mukhtarov A. About the approaches to development computer-aided cutting system on the basis of plane figures allocation algorithm by means of geometrical transformations //Decision making under conditions of uncertainty (cutting-packing problems): "Ibe International Scientific Collection. -Ufa: Publ. USATU, 1997. - P.323-328.

42.Мартынов ВВ., Валиуллин A. M. Оценка качества программных средств //Проблемы качества образования: Материалы УШ всероссийской научно-методической конференции - Уфа-Москва, 1998. - С. 129-130.

43.Martynov V., Valiullin A. Organization of software test laboratoiy in USATU //New information technologies in science, education, telecommunications and

business: Proceedings of XXV International Conference and discussion scientific club. - №raine~Crimea, Yalta-Gurzuff.May, 15-24,1998. - P.548-552.

44.Martynov V., Vedenyapin I. To problem of reproduction of complicated engineering surfaces from a flat material //New information technologies in science, education, telecommunications and business: Proceedings of XXV International Conference and discussion scientific club. - Ukraine, Crimea, Yalta-Gurzuff, May, 15-24,1998.-P.81-84.

45.Martynov V. Complex Geometrical Object's Packing on the Basis of Methods of Admissible Domain Determination: Proceedings of 16-th European Conference on Operational Research.-Brussels, Belgium, July 12-15,1998.-P.120.

46.Мухачева Э.А., Верхотуров M.A., Мартынов B.B. Модели и методы расчета раскроя-упаковки геометрических объектов (монография). - Уфа: УГАТУ, 1998. - 217с.

47.Мартынов В.В., Веденяпин И.Э., Валиуллин A.M., Мухтаров А.Р., Чужи-нов Т.Ю. Разработка компьютерных технологий панелирования сложных технических поверхностей на базе методов рационального размещения: Отчет по НИР (УГАТУ), ГР № 02990001120. - М.: ВНТИЦ, 1998. - 150с.

48.Martynov V., Valiullin A. About problem of creation of requirements to classes of software //Information technologies in science, education, telecommunications and business: Proceedings of XXVI International Conference and discussion scientific club. - Ukraine, Crimea, Yaita-Gurraff,1999. -P.342-348.

49.Мартынов B.B. Использование операций Минковсксго при анализе взаимного расположения геометрических объектов //Принятие решений в условиях неопределенности: Межвузовский научный сборник. - Уфа: УГАТУ, 1999.-С. 167-174.

50.Мартынов В.В., Шерыхалин О.И. Автоматизированная система управления вузом как часть информационного обеспечения образования /Материалы Всероссийской научно-практической конференции Региональные проблемы информатизации образования. - Пермь: Издание ПИЛИТ, 1999.-С. 50-52.

51.Мартынов В.В., Валиуллин А.М. Реализация алгоритма нахождения области допустимых размещений геометрических объектов на базе суммы Минковского //Принятие решений в условиях неопределенности: Межвузовский научный сборник. -Уфа: УГАТУ, 1999. - С. 183-192.

52.Мартыноз В.В., Веденяпин И.Э. Методы создания поверхностей в современных CAD/CAE/CAM-системах //Принятие решений в условиях неопределенности: Межвузовский научный сборник. - Уфа: УГАТУ, 1999. - С.

53.Ганеев А.А., Готовцева Е.Р., Мартынов В.В. Разработка технологии доступа к информационному ресурсу по жаропрочным материалам //Вычислительная техника и новые информационные технологии: Межвузовский! АТУ, 1999.- С.35-42.

175-182.

и.о. мартынов