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

РГВ 08

~ Я янв МС1

На Iгринах рукописи

ВЕРХОТУРОВ Михаил Александрович

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

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

управления

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

УФА 2000

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

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

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

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

дании диссертационного совета ДР-063.17.34 Уфимского государственног авиационного технического университета по адресу: 450000, Уфа-центр, у: К. Маркса, 12, УГАТУ.

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

ВЕДУЩАЯ ОРГАНИЗАЦИЯ: ОАО «Уралхиммаш», г. Екатеринбург

Защита состоится «» 2000 года в "/У.&О

в

часов на засс

Автореферат разослан «_££_»

.2000 вода

Ученый секретарь диссертационного совета

.В. Миронов

^640--5-05,0 -V ъ.Ыг.ъ.О

oc:CÎ:7IC:ia:.'

/п ',i:rv" г 1

rir-л ¡:ot""A

Y6 £О 2 ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность проблемы

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

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

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

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

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

Сложность решения этих задач заключается в том, что они относятся

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

1 полиномиальное время.

Текущий этап развития экономики России определяется переходом\/ ромышленных предприятий к функционированию в условиях рыночной «эномшга и характеризуется серьезными финансовыми проблемами и жест-эй конкуренцией, как со стороны отечественных, так и зарубежных товаро-роизводителей. Имея ограниченные ресурсы, предприятия должны действо-1ть быстро и эффективно, проникать на мировые рынки, использовать но-ые технологии, совершенствовать организационную структуру, товарные, инансовые и информационные потоки, внутренний и внешний документо-борот. Ключ к разрешению этих проблем лежит в сквозной автоматизации, источающейся в разработке и использовании интегрированных систем правления, базирующихся на современных методологиях^планирования и V правления различного вида ресурсами (MRP, MRPII, CRP, FRP, ERP, CSRP т.д.), отражающих необходимость дальнейшей автоматизации управления I азличными процессами, происходящими как внутри сферы производства, îk и при его взаимодействии с потребителем.

Обе эти задачи: раскроя-упаковки и автоматизации тесно переплетайся в проблеме разработки автоматизированных систем размещения \СР) объектов разного вида в заданных областях на базе адекватных мате-атических моделей и эффективных современных методов их решения. Эта

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

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

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

- исследованием и разработкой методов решения задач двумерно. нерегулярного размещения занимаются несколько коллективов и о дельных авторов, это: Харьковская школа Р-У академика Стоя! Ю.Г.; Институт алгоритмов и научных вычислений Германии (Jlei гауэр Т.); Миленковик В., Даниэльс К. (США); Доусланд К., Доу ланд В.(Великобритания); и ряд ученых в различных странах мира;

- исследование и разработка методов решения задач трехмерного н регулярного размещения является новым научным направлением классе задач раскроя - упаковки, которым занимается несколько а: торских коллективов: Иконен И., Билес В. и др., Баллинг Р., Ландс М. и др., Зукман С., Каган И., Coca М. (С1ПА); Дикинсон и Кноп (Канада); Такаюки Осогами (-Япония). Активно работы в этом к: правлении развернулись во второй половине 90-х годов в связи развитием одного из практических приложений этих задач - быстр( го прототипирования.

Несмотря на заметное продвижение в области решения задач раскроя упаковки:

- до сих пор в большинстве случаев на производстве карты Р-У прс СгСТИруЮТСл Еру 4liyiG xülli IfplI&lilTrlB 11ЫМХ1 ШГГСриКТИБНЫМЦ прс граммными средствами. Это нарушает непрерывность процесса ai томатизации и приводит к нерациональному использованию дороге стоящих материалов и высокопроизводительного оборудования дл Р-У. Причиной такого состояния является отсутствие эффективног математического обеспечения для автоматизации решения задач ш регулярного размещения ГО для двух- и для трехмерного npoerpat ства.

- профессиональные укладчики при ручном размещении при решени задач нерегулярного размещения часто получают результаты луч шие, чем сгенерированные на ЭВМ;

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

составе АСР, в связи с тем, что эта задача является некорректно поставленной;

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

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

1ну ОПО,Г7Г.ГГ1ЩЛЛУГ?У йТТГОрТГТМОВ £ 5оЛЫ1П1НСТ5С СДУ^ЗСЗ О^УС1йВЛ1'Вь1СТ С Л С 7К-

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

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

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

Цель работы: разработка методологических основ и инвариантного математического обеспечения автоматизированных систем нерегулярного эазмещения двух- и трехмерных геометрических объектов, функционирую--! цих в составе интегрированных систем управления современным предпри- ! '' 1тием и направленных на рациональное использование материальных ресур- I ■ ;ов. {

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

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

2. Разработать теоретические основы оптимизации нерегулярного ра: мещения двух- и трехмерных геометрических объектов на базе ди< кретных методов локального поиска, направленные на создани гибкого математического обеспечения АСР ГО.

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

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

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

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

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

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

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

1. Методология создания автоматизированных систем нерегулярной размещения двух- и трехмерных геометрических объектов, позво лающая разрабатывать автоматизированные системы, взаимодейст вующие с различными подсистемами (САПР, АСУ, АС ТПП и т.д.) работающими в составе интегрированных систем управления со временным предприятием и базирующиеся на структуре, содержа щей блоки оптимизащи и обработки данных о геометрии, а таюк< интерфейс раскроя-упакоеки, регламентирующий ззаимодействи! АСР ГО с различными подсистемами ПСУ.

2. Теоретические основы оптимизации нерегулярного размещения двух- и трехмерных геометрических объектов, базирующиеся на адаптации и интеграции методов дискретной оптимизации: "Поиска с запретами" (TS), "Моделирования отжига" (SA), "Генетических алгоритмов" (GA), "Муравьиной колонии" (АС), "Объективно - обусловленных оценок Л.В.Канторовича" (SVC) и на построении годографа функции плотного размещения, позволяющие разрабатывать инвариантное различньш подсистемам в составе ИСУ математическое обеспечение оптимизационного ядра АСР ГО.

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

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

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

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

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

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

следующих метаэвристинеских методов локального поиска: "Пои ка с запретами" (75), "Моделирования отжига" (SA), "Генетт ских алгоритмов" (GA), "Муравьиной колонии" {АС). Это позволж получать допустимые и близкие к оптимальным решения задач н регулярного размещения ГО.

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

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

Практическая значимость работы.

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

VCVn, САПР н АСТПП, a также для создания на этой основе автономного юмплекса программных средств. На базе проведенных исследований разработан работающий в среде Microsoft Windows 95/98 комплекс программных редств для решения задач Р-У - "Cut-CAD", который на практике показал (ысокую эффективность за счет быстрой адаптации к условиям работы про-оводств различного вида в разнообразных отраслях промышленности, хо-юшей совместимости с различными подсистемами, функционирующими в оставе ИСУ, уменьшения времени проектирования карт Р-У (в 5-10 раз) и 1КОНОМИИ материала (до 5%).

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

Работы в данном направлении проводились автором в Уфимском авиа-щонном институте в 1989-1992 годах в рамках поисковых НИР по заказам Уральского филиала НИИД ("Рациональный раскрой материала с учетом ориентации волокон") а НПО БУММА1Д ("Система автоматизированного юрмирования и расхода материала с обеспечением его рационального рас-;роя"). В дальнейшем работы были продолжены в рамках выполнения хоздо--оворных научно-исследовательских работ с Уфимским производственным )бъединением "Гидравлика" по темам №ИФ-ВК 01-92-ОГ (1992-1993 г.г.), М1Ф-ВК-07-95-ОГ (1995-1996 г.г.) и М>ИФ-ВК-09-97-ХГ (1997-1999 г.г.); с ЗАО "Уралхиммаш" и ОАО "Белебеевский опытный механический завод".

В 1998-1999 г.г. работа была поддержана государсивениым грантом по фундаментальным исследованиям в области технических наук (направление 'Информационные технологии в проектировании изделий и технологических троцессов их изготовления", раздел "Проблемы управления и контроля тех-шлогических процессов изготовления деталей и изделий авиакосмической техники", конкурсный центр МАТИ) по теме "Информационные технологии )аскроя-упаковки одно и двухмерных объектов" №ИФ-ВК-04-98-ГУ.

Внедрение результатов:

- на НПО БУММАШ г.Ижевск (алгоритмы и программы дискретно-логической аппроксимации исходных плоских контуров; методы, алгоритмы и программы формализации плотного движения объектов на базе дискретно-логического представления информации; методы, алгоритмы и программы решения задачи оптимизации размещения дискретно - аппроксимированных деталей на листовом изотропном материале);

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

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

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

- в Акционерном обществе "Белебеевский опытный механический за вод", г.Белебей (подсистема препроцессорной подготовки информа ции, включающая алгоритмы и программы аппроксимации исходны; данных об объектах раскроя - упаковки; алгоритм моделирована процесса плотного движения объектов в области размещения на ос иове их дискретно-логического представления и цепного кодирова ния; методы и алгоритмы автоматизированного нерегулярного раз мещения деталей сложных геометрических форм; интегрирования; оболочка САПР раскроя - упаковки "Cut-CADfor Windows")',

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

Апробация работы.

Основные результаты работы докладывались и обсуждались на еле дующих конференциях:

- Республиканская научно-техническая конференция "Применен;!; САПР в машиностроении", Свердловск, 1989 г.;

- 8-ая поволжская межзональная конференция "Актуальные вопрось начертательной геометрии и инженерной графики", Йошкар-Ола 1990 г.;

- Республиканская научно-техническая конференция "Автоматизации проектирования в энергетике и электротехнике", Иваново, 1990 г.;

- Всесоюзная научно-техническая конференция "Теория и методы создания интеллектуальных САПР в машиностроении и приборостроении", Минск, 1992 г.;

- Региональная научно-техническая конференция "Математическое программирование и приложения", Екатеринбург, 1993, 1995, 1997, 1999 гг.;

- Межрегиональная научно-методическая конференция "Актуальные вопросы современной инженерной графики", Уфа, 1994 г.;

- Сибирский конгресс "Прикладная и индустриальная математика", Новосибирск, 1994,1996,'1998 гг.;

- Российско-китайский семинар "Актуальные проблемы авиадвигате-лестроения", Уфа, 1994 г.;

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

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

- Международная конференция "Комплексный анализ, дифференциальные уравнения и смежные вопросы", Уфа, 1996 г.;

- 14 международная конференция "Исследование операций", Ванкувер, Канада, 1996 г.;

- Всероссийская конференция по математическому программированию "Проблемы оптимизации и экономические приложения", Омск, 1997 г.;

- Международная конференция "Технология машиностроения", София, Болгария, 1997 г.;

- Международный конгресс по исследованию операций. Е1ЖО-ХУ1, Брюссель, Бельгия, 1998 г.;

- Международная научная конференция "Моделирование, вычисления, проектирование в условиях неопределенности, Уфа, 2000 г.

Публикации.

По теме диссертации опубликованы 53 работы, в том числе 1 монография (в соавторстве), 26 статей, 24 тезисов докладов, а также 2 научно-•ехнических отчета.

Структура работы.

Диссертация состоит из введения, шести глав, выводов, списка литера-•уры и приложения. Объем основной части диссертации составляет 324 стра-шцы, кроме того, работа содержит 69 рисунков и 12 таблиц, расположенных ¡а 44 страницах. Библиографический список включает 300 наименований.

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

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

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

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

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

Прогноз

^^ Ассортимент продукции

Качество продукции

СБШЕЕ РУКОВОДСТВО

Финансовая политика

Маркетинговая, политика

Направление исследований и разработок

Трзбззгии: исследовачивй"7"" и рдэддботсам ♦

МАРКЕТИНГ И СБЫТ

ИССЛЕДОВАНИЕ И РАЗРАБОТКА

Техническая информация

Конструкторские требования

Ведомость материалов

КО мг ТДУУТОРСКр. ЗРАБОТ

Техническая политика

Состояние производства

Состояние вывоза

УПРАВЛЕНИЕ ПРОИЗВОДСТВОМ ^КАЧЕСТВО. СТОИМОСТЬ, ДОСТАВКА)

Заказ на потребление

Коиструггсрсш-технологичАская информация

Материалы

СНАБЖЕНИЕ

Обеспечение

ресурсам* .ГУТТРАЭЛЕН^Е Ресурсы

РЕСУРСАМИ

^Производственные ТЗагаз ► распоряжения вывоз

Информация о^ГРадУЦ™ ' ■'" (продукции! ' "

ОСНОВНОб ПРОИЗВОДСТВО.

еывоз

ПРОДУКЦИИ

Запрос на обслуживание

ОРГАНИЗАЦИЯ ОБСЛУЖИ ВАНИ

УТИЛИЗАЦИЯ ОТХОДОВ

Обслуживание |

I .....I I .. . Состояние производства ■■■

Рис.1

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

рыночным условиям автоматизированных систем управления необходимым является переход на внедрение интегрированных систем управления (ИСУ).

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

Современные интегрированные системы управления базируются на методологиях планирования и управления разнообразными видами ресурсов, таких как: MRP II - планирование и управление производственными ресурсами, ERP - планирование и управление ресурсами предприятия, CSRP - планирование и управление ресурсами, ориентированное на потребителя и т.д. Основой же любой из современных концепций планирования и управления являются две составляющие - планирование и управление потребностями в материалах (MRP) и производственных мощностях (CRP).

Рис. 2

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

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

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

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

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

ГЛАВА 2. МЕТОДОЛОГИЯ СОЗДАНИЯ АВТОМАТИЗИРОВАНИИ? СИСТЕМ НЕРЕГУЛЯРНОГО РАЗМЕЩЕНИЯ ГО, ФУНКЦИОНИРУЮЩИХ В СОСТАВЕ ИСУ

Эта глава посвящекй разраооткс методологии создания автоматизиро ванных систем нерегулярного размещения ГО, работающих в составе интег рированных систем управления современным промышленным предприятием

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

Рассматривается следующая постановка задачи нерегулярного разме щения двух- и трехмерных ГО (на примере ЗВ размещения):

Имеется множество трехмерных ГО Р1,1 = 1,2,...,п, которые требуете:

разместить в области Л пространства Я3 так, чтобы минимизировать функ цию ¡'('¿) при выполнении следующих условий <р(2 )>0, где:

2 = 2(х1,у1,г1,а1,рьу1,вь...,хп,уп,гп,ап,рг1,уп,вп) - вектор, определяющш размещение (упаковку) ГО в области П, причем положение ГО Р1 определя ется величинами: х^у^- координат его центра, а,,/?,-,/,- - углов наклона пря

;ой, вокруг которой производится поворот объекта на угол 0h при этом •os2 a + cos2 /З + cos2 у ~ 1>

Ч> = \rPhrP2.....<Pkl к = - ограничения на параметры размещения

включающие условия взаимного непересечения ГО между собой и усло-1ия размещения ГО в области размещения Q.

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

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

С учетом взаимодействия с различными подсистемами в составе ИСУ, 1 также вышерассмотренных особенностей задач нерегулярного Р-У проектирование автоматизированных систем размещения ГО необходимо осуще-;твлять таким образом, чтобы они:

- не зависели от вида различных автоматизированных систем, с которыми будут взаимодействовать (внешние факторы),

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

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

Внешние факторы, воздействующие на АС, определяются спецификой информации, входящей в систему и выходящей из нее. Для регламентирования взаимодействий между АСР и другими подсистемами ЙСУ разработан интерфейс раскроя - упаковки ('cutting-packing interface - СРГ).

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

- блока оптимизации;

- блока обработки данных о геометрии.

Структура АСР изображена на Рис. 3.

Методы

Методы вычислительной геометрии и машинной графики

Рис. 3 Структура и интерфейсы АСР ГО

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

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

Связь между блоком оптимизации и блоком обработки данных о гес метрии осуществляется согласно интерфейсу математического программирс вания (mathematical programming interface - MPI), который делает независи мым использование различных методов математического программирован!! от специфики описания и обработки геометрических данных.

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

Для реализации двух частей, составляющих интерфейс раскроя - упа ковки (CPI): входной (CPI-Input) и выходной (CPI-Output), более подроби

рассмотрено взаимодействие АСР с различными подсистемами, входящими в состав ИСУ:

- системами автоматизации проектирования (САПР);

- автоматизированными системами управления производством (АСУП);

- автоматизированными системами технологической подготовки производства.

ГЛАВА 3. ТЕОРЕТИЧЕСКИЕ ОСНОВЫ ПРИМЕНЕНИЯ МЕТОДОВ ДИСКРЕТНОЙ ОПТИМИЗАЦИИ ДЛЯ РЕШЕНИЯ ЗАДАЧ НЕРЕГУЛЯРНОГО РАЗМЕЩЕНИЯ ДВУХ -И ТРЕХМЕРНЫХ ГО

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

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

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

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

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

Особое внимание уделено методам МГП, основанным на обеспечении условий взаимного непересечения (УВН) размещаемых ГО между собой и с границей области размещения.

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

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

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

Функция выбора точки размещения ГО

ПС- приоритетный список

Параметры метаэвристж (TS, GA, SA, АС)

Рис.4

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

В уфимской школе профессора Э.А. Мухачевой для решения некоторых Л'Р- трудных задач гильотинного и негильотинного прямоугольного Р-У широкое применение нашел метод последовательного уточнения оценок (5ТС), который является тем эффективным аппаратом, на основе которого разработаны эвристические алгоритмы полиномиальной сложности. В качестве оценок у, принимаются нормы расхода материала, которые рассчитываются на основе некоторого допустимого плана Р-У для каждого ГО (Рис. 5).

- незэполненн ые области

т я

у- = 5ГР, ^ )Ч >, Л/ > = Е)

1=1 <=/

Роль оценок аналогична роли двойственных переменных в задачах JUL Для реализации метода 5КС использовался их физический, смысл. Метод представляет собой итерационный процесс, на каждом шаге которого оценки пересчитываются и отвечают новому плану Р-У. Оценки позволяют сформировать приоритетный список, в котором ГО ранжированы по убыванию удельных оценок ^y'j/SfPjj. Согласно этому приоритетному списку производятся размещение ГО в области Р-У.

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

- метод подсчета оценок для несвязной непокрытой геометрическим] объектами области Р-У, основанный на понятии отсекаемых облас тей (Рис. 5);

- метод подсчета оценок для многосвязной непокрытой геометриче скими объектами области Р-У, основанный на понятии оболочек.

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

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

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

ГЛАВА 4. МЕТОДЫ И АЛГОРИТМЫ ПОСТРОЕНИЯ ГОДОГРАФА ФУНКЦИИ ПЛОТНОГО РАЗМЕЩЕНИЯ ГО НА БАЗЕ ДИСКРЕТНО - ЛОГИЧЕСКОГО ПРЕДСТАВЛЕНИЯ ИНФОРМАЦИИ И ЦЕПНОГО КОДИРОВАНИЯ

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

Под годографом 01](в1,9]) объекта Р1 относительно объекта Р^ пони

мается такое множество положений центра с,, объекта Рп развернутого н угол в,, при котором объекты /¡- и пересекаются граничными точками, п не пересекаются своими внутренними точками, причем объект разверну на угол в1, т.е. выполняются условия:

¡тР1(О1)Г\1п1Р/д]) = 0,

сЩ(91)[)с1Р^)*0.

При помощи операций Минковского годограф 01](01,01) может быт определен следующим образом:

=Р](9})®-(т);с1),

где

А ® В - сумма Минковского двух множеств А и В;

А/В - разность Минковского;

А=В.2\А - дополнение множества А до Я2;

-А = {-а\аеА) - отображение множества А относительно начала координат.

Аналогично, для объекта Р1 (развернутого на угол в,) годограф относительно области П:

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

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

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

- связность границ ГО (четырех или восьми связные - для 20 пространства к шести, восемнадцати или двадцати ш^сти снизньте - для ЗВ пространства) (Рис. 6);

- касание границ ГО и области Р-У (плотное и неплотное) (Рис. 7);

- выбор направления движения ГО (используемые для этого методы: анализа точек касания и "грубой силы" по правилу "правой руки") (Рис. 8).

Предложена структура элемента графической информации, позволяющая реализовать способ построения годографа на основе ДЛПИ и ЦК для 2В и ЗО пространства. Разработаны следующие алгоритмы:

- первоначального занесения ГО в область размещения;

- построения годографа для различных случаев реализации ДЛПИ и ЦК;

- изменения области Р-У при занесении ГО в данную область и удалении ГО из неё;

построения частей несвязного годографа (для двухмерного пространства).

1 (ц-1) 3 0-и-1) ...... \ 2 0^-1) —&—. 1 0*1*1)

2 0-1^ 1 - (Г \ 0 г 0+1Л 4 0-1 ¿Т к I / к?" 0 "0+1 и)

\з (Ц+1) 5 X 0-1^1) *6 0^1) \ 7 0+1и+1)

ь V.. 1

1 \

% —

п У <4—

1

I I

а > четырехсвязнзя

б) восьмисвязная

Рис. 6 Связность ¡ранни (на примере 2В пространства)

Точка касания

Точкакасания

а) плотное б)неплотное

Рис. 7 Касание границ (на примере 2В пространства)

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

5 в

* —вектор предыдущего направления сдвига; ** —лектор последующего направления сдвига, а) метод анализа точек касания

М

б) метод "правой руки" Рис. 8 Выбор направления движения (на примере 2В пространства)

ГЛАВА 5. МЕТОДЫ И AJД ОРИТМЫ АППРОКСИМАЦИИ ЦЕПНЫМИ КОДАМИ ОБЪЕКТОВ С ЛИНЕЙНО-ЗАДАННЫМИ ГРАНИЦАМИ

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

Анализ различных способов представления информации об исходных ГО и областях размещения позволил выделить два основных класса: аналитические и дискретные способы.

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

Недостатками известных дискретных способов задания являются: неэффективное использование памяти ЭВМ; необходимость реализации большого количества операций; невозможность (или трудоемкость) моделирования всей области размещения, удовлетворяющей УВН.

Разработана структура решения задачи аппроксимации ГО цепным)! кодами. Способ аппроксимации ГО цепными кодами зависит от метода, согласно которому производится выбор направления движения ГО в процессе построения годографа.

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

- линейная аппроксимация контуров исходных ГО;

- аппроксимация линейно-заданных ГО многоугольниками с целочисленными вершинами;

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

Метод "грубой силы" по правилу "правой руки" использует описание ГО в виде цепных кодов, задающих растеризированные границы произвольных ГО. Решение задачи включает два этапа:

- растеризация границ исходных плоских ГО;

- цепное кодирование полученных на предыдущем шаге точек растра принадлежащих границам ГО.

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

проксимации ГО цепными кодами состоит из двух этапов:

- трехмерная растеризация исходной поверхности;

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

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

Основными преимуществами применения дискретно-логического представления информации и цепного кодирования являются:

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

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

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

ГЛАВА б. РАЗРАБОТКА И ВНЕДРЕНИЕ ПРОГРАММНОГО

ОБЕСПЕЧЕНИЯ АВТОМАТИЗИРОВАННОЙ СИСТЕМЫ НЕРЕГУЛЯРНОГО РАЗМЕЩЕНИЯ ГО

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

С этой целью был создан автономный комплекс программных средств (КПС) "Cut-CAD", предназначенный для решения задач Р-У различного вида: линейного, прямоугольного, 2£)-геометрических объектов сложных форм, параллелепипедного и 31>-геометрических объектов сложных форм.

Согласно разработанной вышеописанной методологии, были созданы:

- структура КПС "Cut-CAD" (Рис. 9);

- структура интерфейса с пользователем КПС "Cut-CAD".

На базе разработанного математического обеспечения было создано программное обеспечение - КПС "Cut-CAD". Этот комплекс предназначен для автономной работы в различных подразделениях современных промышленных предприятий, связанных по роду своей деятельности с необходимостью решения задач нерегулярного размещения двух- и трехмерных геометрических объектов. Также его можно использовать для проведения научно -

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

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

В связи с тем, что в данной работе рассмотрены подходы на основе принципа пообъектного размещения, разработана реализация MPI для методов дискретной оптимизации - интерфейс дискретной оптимизации (discrete optimization interface - DOÎ).

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

- разработанными в данной работе;

- адаптацией метода TS Блазевича П.;

- реализацией годографа Hdg Хекманна Р.

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

Эксперимент показал высокую эффективность созданных алгоритмов. Так, алгоритмы SVC, разработанные в данной работе характеризуются тем, что за примерно одинаковое время1 практически всегда генерируют близкие к нижней границе решения, лучшие, чем адаптация метода TSБлазевича П., и не хуже, чем Hdg Хекманна Р. Соответствующие результаты показаны в Таблица 1 (КРА - коэффициент Р-У (в %), Т - время (з сек.)).

Таблица 1

Примеры TS (Блазевич П.) Hdg (Хекманн Р.) SVC Оценки

КРА Т КРА Т КРА Т

TEST! 80.0 14 80.0 0 80.0 0

TEST2 70.7 29 70.7 0 70.7 1

TEST3 62.1 18 77.5 1 77.5 2

TEST4 87 О 57 87.9 п R7.9 2

TEST5 72.9 39 81.7 116 81.7 36

TEST6 43.0 33 46.5 575 47.5 2

TEST7 61.6 70 77.0 582 77.0 18

TESTS 66.7 67 78.5 423 78.5 42

трстл ¿0 с. vy.w 1Q7 76.8 78 76 8 36

TEST10 69.1 150 76.4 504 76.4 120

TEST 11 73.3 29 78.4 18 78.4 7

TEST 15 93.8 62 93.8 38 93.8 12

среднее 70.8 56 77.1 195 77.3 24

TEST24 100 20 100 0 100 1

TEST25 100 62 100 6 100 2

TEST26 100 75 100 16 100 8

TEST30 100 13 100 1 100 13

TEST31 100 28 100 12 100 19

TEST35 96 56 96 6 96 5

TEST36 96 29 96 3 96 9

среднее (1-36) 81.1 50 85.1 125 85.2 18.6

1 Вычисления производились на разных видах и поколениях вычислительной техники: Биазекич П. - IBM PC XT, Хекманн P. - SPARC-ULTRA, автор - Pentium 166.

Отличие результатов, полученных методами SVC и Häg, находится в пределах погрешности, образованной за счет использования различных способов аппроксимации исходных геометрических объектов.

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

Приведена задача, решаемая в рамках автоматизированной системы управления машиностроительным производством и заключающаяся в расчете подетальных норм расхода материала изготавливаемых на предприятии изделий (Рис. 10). На вход системы подаются: файл обмена данными, содержащий информацию о деталях, их входимости в различные изделия, имене файлов чертежей в формате DXF системы AutoCAD-, соответствующие DXF-файлы Необходимо подсчитать нормы расхода материала на каждую детал! изделия, с учетом выбранного для этого листового материала, к величина полученных норм расхода занести в файл обмена данными. Для этого на основе созданного математического обеспечения разработан дополнительны! набор алгоритмов, включенный в КПС "Cut-CAD" и позволяющий рассчиты вать планы Р-У листовых материалов на ГО сложных форм. Время генерации одной карты раскроя листа 6000x2000, содержащей от 80 до 100 деталей со ставляет около 8 мин mPeniium-166. Коэффициент раскроя равен 0.79.

Информация о деталях и их вложенности в изделие

Чертежи_

деталей

Наименование изделия

1

Размеры листового материала

1

КПС

"Cut-CAD"

АО

т Инженер

Рис. 10

Информация о деталях с заполненными -> подетальными нормами расхода материала

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

ла произведена адаптация препроцессорного и постпроцессорного блоков разработанного программного обеспечения. Время генерации карты раскроя листа 1000x500, содержащей 20 деталей составляет 5 мин аяШМРСХТ. Коэффициент раскроя равен 0.76.

Размеры листа

Координаты вершин многоугольников

Углы поворота слоев

Перечень команд станка с ЧПУ

Инженер Рис. 11

Карта раскроя

Программа для лазерного станка с ЧПУ

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

ПРИЛОЖЕНИЕ

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

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

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

В ходе проведенных исследований получены следующие научные и практические результаты:

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

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

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

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

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

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

дача является некорректно поставленной. В связи с этим разработан способ моделирования годографа на основе ДЛПИ и ЦК. На базе предложенного способа разработан метод построения годографа для двухмерного и трехмерного пространства. Выделены классифицирующие характеристики, влияющие на возможные способы построения годографа. Разработана структура элемента графической информации, позволяющая реализовать способ моделирования годографа на основе ДЛПИ и ЦК. Разработаны алгоритмы: построения годографа для различных случаев реализации ДЛПИ и ЦК; изменения области Р-У при занесении ГО в данную область и удалении ГО из неё; построения частей несвязного годографа.

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

4. На базе разработанных методологии и математического обеспечения создан комплекс программных средств "Cut-CAD", позволяющий в автономном режиме решать задачи Р-У любого вида (плоские и пространственные геометрические объекты сложной формы). Он может быть использован как при автоматизации деятельности промышленных и проектных организаций, связанных с решением задач Р-У, так и при проведении научно-исследовательских работ по рассматриваемой проблематике.

Для проверки качества разработанных методов и алгоритмов проведен вычислительный эксперимент, а также произведено сравнение решений с результатами, полученными другими методами. Эксперимент показал высокую эффективность созданных автором методов и алгоритмов за счет уменьшения времени проектирования карт Р-У (в 5-10 раз) и экономии материала (до 5%).

Результаты выполненных исследований внедрены на ряде предприятий и организаций различных отраслей промышленности, а в частности: на НПО БУММАШ (г.Ижевск) ("Система автоматизированного нормирования и расхода материала с обеспечением его рационального раскроя"); в Уральском филиале НИИД (г.Уфа) ("Рациональный раскрой материала с учетом ориентации волокон"); в Акционерном обществе «Химмаш» (г.Екатеринбург) '"САПР раскроя для рационального размещения заготовок на плоском материале в машиностроении"); на Уфимском унитарном агрегатном производст-зенном объединении «Гидравлика» (г.Уфа); в Акционерном обществе "Беле-эеевский опытный механический завод" (г.Белебей) ("АРМ технолога рас-фойко-заготоБительнсго производства"); в учебный процесс кафедры "Вы-

числительная математика и кибернетика" Уфимского государственного авиационного технического университета.

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

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

1. Верхотуров М.А., Приймак О.Б., Сорока Б.Н. Математическое моделирование криволинейных поверхностей по системе "Альфа"// Автоматизированная система проектирования авиационных двигателей (АСПАД-88):Прослект.-Уфа:УАИ,1988.-С.21.

2. Верхотуров М.А. Алгоритмы ппе- и пост - процессорной обработки в задаче рационального раскроя материала с учетом ориентации воло-кон//Отчет НИР N50788, ГР 2069436.-Уфа: УАИ,1989.-С.15-21, 48-55.

3. Верхотуров М.А., Драган Т.М. Подсистема первоначальной (входной) обработки информации в САПР технологической подготовки раскроя// Применение САПР в машиностроении: Тезисы докладов Всесоюзной конференции.-Свердловск:УПИ,1989.-С.12-13.

4. Болотовская Т.К., Верхотуров М.А. Некоторые аспекты проблемы построения рационального плана нерегулярного раскроя на заготовки сложных формШринятие решений в условиях неопределенности. - Уфа: УАИД990.-С.117-120.

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

6. Верхотуров М.А. Способ раскроя изотропного материала на фигурные заготовки // Автоматизация проектирования в энергетике и электротехнике: Тез. докладов республик, н.-т. конференции.-Иваново:ИЭИ,1991.-С.22-23.

7. Мухачева Э.А., Верхотуров М.А., Брусиловский Д.П. Об одном способе решения задачи нерегулярного фигурного раскроя // Теория и методы создания интеллектуальных САПР в машиностроении и приборостроении: Тезисы докладов всесоюзной н.-т. конференции. - Минск: 1992.-С.38.

8. Верхотуров М.А., Карамова Л.М., Мухачева Э.А., Тарасова Т.Д. Комплексная система рационального раскроя в условиях штамповочного про-изводства/Юбработка металлов давлением, Н5.т.4.-Познань:1993.-С.40-42.

. 9. Верхотуров М.А., Брусиловский Д.П. Использование в учебном процессе подсистемы фигурного раскроя САПР "Раскрой"// Проблемы качеств; высшего образования: Тезисы международной научно-методической кон ференции. -Уфа: 1993.-С.34.

Ю.Верхотуров М.А., Мухачева Э.А., Брусиловский Д.П. Способ решения задачи нерегулярного фигурного раскроя с использованием методов многомерного шкалирования // Математическое программирование и приложения: Тезисы региональной н.-т. конференции. -Екатеринбург:1993.-С.27.

11 .Верхотуров М.А., Брусиловский Д.П. Система классификации геометрических объектов// Актуальные вопросы современной инженерной графики: Тезисы межрегиональной научно-методической конференции. - Уфа: 1994.-С.59.

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

13.Верхотуров М.А. Дискретно - логическое представление информации для синтеза и анализа двухмерных и трехмерных сцен// Актуальные вопросы современной инженерной графики: Тезисы межрегиональной научно-методической конференции. - Уфа:1994.-С.64.

14.Мухачева Э.А., Верхотуров М.А., Ибатуллина С.М О рациональном распределении ресурсов// Экономика и управление.№3.-Уфа: 1994.-С.ЗЗ-40.

15.Мухачева Э.А., Верхотуров М.А., Шабрина Л.И. Многообразие задач раскроя и упаковки. - Депонировано в ВИНИТИ, №3023-В94.-М:1994.-8с.

16.Мухачева Э.А., Верхотуров М.А. Интегрированная система рационального раскроя// Актуальные проблемы математического моделирования и автоматизированного проектирования в машиностроении: Тезисы международной научно-технической конференции. - Казань: 1995.-С.61-63.

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

18.Верхотуров М.А., Сергеева О.Ю. Применение метода оценок для решения некоторых задач нелинейного программирования// Математическое программирование и приложения: Тезисы межрегиональной конференции. -Екатеринбург: 1995.-С.59-60.

19.Верхотуров М.А., Верхотурова Г.Н., Сергеева O.IO: О решении некоторых прикладных задач нелинейного программирования// Методы оптимизации и их приложения: Тезисы 10-ой Байкальской школы-семинара. - Иркутск: 1995.-С.51.

20.Верхотуров М.А., Мухачева Э.А. Метод оценок для решения задач раскроя - упаковки// Принятие решений в условиях неопределенности: Межвузовский сборник научных трудов. - Уфа: 1996.-С.22-24.

21 .Верхотуров М.А., Федулов C.B. Алгоритмы предпроцессорной и постпроцессорной обработки для задач упаковки трёхмерных геометрических объектов// Принятие решений в условиях неопределенности: Межвузовский сборник научных трудов. - Уфа: 1996.-С.49-53.

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

23.Мухачева Э.А., Верхотуров М.А. Интегрированная система рационального раскроя в условиях единичного и мелкосерийного производства// Куз-нечно-штамповочное производство, №5.-М.: 1996.-С.24-27.

24.Верхотуров М. А., Верхотурова Г.Н. О задаче трёхмерной упаковки объектов сложных геометрических форм// Роль геометрии в искусственном интеллекте и системах автоматизированного проектирования: Сборник докладов всероссийской н.-т. конференции. - Улан-Удэ: ВСГТУ, 1996.-С.43-45.

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

26.Верхотуров М.А. Математическое моделирование нерегулярной упаковки двух- и трёхмерных геометрических объектов// Комплексный анализ, дифференциальные уравнения и смежные вопросы: Сб. трудов международной конференции. - Уфа:1996.-С.37-44.

27.Мухачсва Э.А., Верхотуров М.А., Верхотурова Г.Н. Об использовании оценок в задачах трёхмерной упаковки//' Прикладная и индустриальная математика: Тезисы второго сибирского конгресса. - Новосибирск: 1996-С.139.

28.Верхотуров М.А., Верхотурова Г.Н. Дискретно-логическое представление информации для синтеза и анализа двухмерных и трёхмерных динамических сцен// Прикладная и индустриальная математика: Тезисы второго сибирского конгресса. - Новосибирск: 1996.-С.183-184.

29.Мухачёва Э.А., Верхотуров М.А. Метод оценок для решения задач раскроя - упаковки// Исследование операций: Тезисы 14 международной конференции. - Ванкувер: 1996.-С.24.

30.Верхотуров М.А., Верхотурова ГЛ. Новые информационные технологии в управлении и системы планирования и управления проектами // Проблемы совершенствования методики преподавания: Сборник докладов научно-методической конференции. - Уфа: БАГСУ, 1997.-С.80-83.

31.Мухачёва Э.А., Верхотуров М.А. Объективно - обусловленные оценки Л.В.Канторовича в задачах оптимального раскроя// Прикладная и индустриальная математика: Сб. Трудов Сибирского конгресса. - Новосибирск: 1997.-С.75-79.

32.Верхотуров М.А., Верхотурова Г.Н. Об одном решении задачи трехмерной упаковки сложных геометрических объектов// Математическое программирование и приложения: Тезисы всероссийской конференции. -Екатеринбург: 1997.-С.57-58.

33.Верхотуров М.А., Верхотурова Г.Н., Брусиловский Д.П. Методы и алгоритмы нерегулярной двухмерной упаковки объектов сложной геометрической формы: Депонировано в ВИНИТИ, №682-В97,- М.: 1997, 58с.

34.Верхотуров М.А., Верхотурова Г.Н. Метод псевдо - оценок в задачах трехмерной упаковки// Проблемы оптимизации и экономические приложения: Тезисы конференции по математическому программированию, Омск:1997.-С.40.

35.Верхотуров МА, Мухачёва Э.А., Мартынов В.В. О методах решения задач фигурного раскроя в условиях единичного производства // Технология машиностроения: Сб. трудов международной конференции, Болгария, София, 1997.-С.З-9.

36.Мартынов В.В., Верхотуров М.А., Мухачёва Э.А. Методы рационального периодического размещения заготовок в штамповочном производстве// Технология машиностроения: Сб. трудов международной конференции, Болгария, София, 1997.-С. 10-17.

37.Верхотуров М.А., Верхотурова Г.Н. Некоторые особенности подсчета оценок в задачах трехмерной упаковки// Принятие решений в условиях неопределенности: Межвузовский сборник. - Уфа: УГАТУ, 1997.-С.284-295.

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

ТО Л Тт^'п^тК«« О А "Пзт-л--"--1 а —-------- т> "П О-—- — -- »^.тг.-.то ,у .

А» 1 ^ Л.с11>(Л ^'риЬ ¿*х.«Г\., О.О. и^ПийпЫС ЛХидСЛЛ х1

тоды задач раскроя - упаковки// Межвузовский сборник научных статей УГАТУ, Уфа,1997.-С.59-67.

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

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

42.Верхотуров М.А., Верхотурова Г.Н. Особенности подсчета оценок в задачах трехмерной упаковки// Исследование операций: Тезисы международного конгресса Е1ЛЮ-ХУ1, Брюссель, 1998.-С.120.

43.Верхотуров М.А., Сергеева О.Ю. Некоторые комбинаторные алгоритмы для задач упаковки// Исследование операций: Тезисы международного конгресса ЕШО-ХУ1, Брюссель, 1998.-С.45.

44.Верхотуров М.А., Дьяконов Д.Б., Тархова Л.М. Об одном способе построения остова произвольного многоугольника// Прикладная и индустри-

альная математика: Тезисы третьего сибирского конгресса. Новосибирск: 1998.-С.60-61.

45.Мухачева Э.А., Верхотуров М.А., Сергеева О.Ю. Моделирование плотной упаковки геометрических объектов// Проблемы математики и теории управления. Межвузовский научный сборник, Уфа, 1998.-С.301-315.

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

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

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

49.Верхотуров М.А., Верхотурова Г.Н., Нугуманов А.Ш. Упаковка плоских геометрических объектов: постановка задачи и методы решения// Математическое программирование и приложения: Тезисы всероссийской конференции, Екатеринбург, 1999.-С.62-63.

50.Верхотуров М.А. О методе решения задачи нерегулярной упаковки плоских геометрических объектов// Вычислительная техника и новые информационные технологии: Межвузовский сборник научных трудов. -Уфа, 1999.-С.75-83.

51.Верхотуров М.А., Кардакова О.В., Логинов Е.В., Нугуманов А.Ш. О применении метода "simulated annealing" для решения задач нерегулярной упаковки// Интеллектуальное управление в сложных системах: Тезисы республиканской научно-технической конференции, Уфа, 1999.-С.19.

52.Верхотуров М.А. Классификация и методы решения задач упаковки геометрических объектов: Отчет по НИР (УГАТУ), ГР №01980010234.-М.: ВНТИЦ, 1999.-С.112-119,133-135.

53.Верхотуров М.А., Верхотурова Г.Н., Логинов Е.В. Структура решения задач нерегулярного раскроя - упаковки геометрических объектов// Моделирование, вычисления, проектирование в условиях неопределенности: Межвузовский сборник научных трудов, Уфа: УГАТУ, 2000.-С.375-379.

Диссертант

М.А. Верхотуров