Введение к работе
Актуальность проблемы
Среди множества ресурсосберегающих задач важное место занимают дачи, связанные с раскроем и упаковкой (компоновкой) (Р-У) в заданных 5ластях объектов различного вида и имеющих различную физическую при-эду. К таким задачам относятся:
задачи оптимального раскроя материала на заготовки произвольной формы, решаемые при производстве изделий в машиностроительной, авиастроительной, судостроительной, текстильной, кожевенной, деревообрабатывающей, мебельной и многих других отраслях промышленности;
задачи компоновки: грузов в разнообразного вида контейнеры, схем генеральных планов промышленных предприятий, двигателей, радиоэлементов на платах и т.д.;
задачи распределения - ог памяти вычислительных машин до участков леса, предназначенных для вырубки или посадки.
Все вышеперечисленные задачи по своей сути относятся к проблеме чтимизационпого геометрического моделирования, заключающейся в оп-шизации размещения данного вида объектов в заданных областях.
Сложность решения этих задач заключается в том, что они относятся о своей сложности к классу NP- трудных проблем оптимизации, т.е. для ко-зрых пока не существует методов и алгоритмов, находящих точное решение і полиномиальное время.
Текущий этап развития экономики России определяется переходому ромышленных предприятий к функционированию в условиях рыночной <ономики и характеризуется серьезными финансовыми проблемами и жест-эй конкуренцией, как со стороны отечественных, так и зарубежных товаро-роизводителей. Имея ограниченные ресурсы, предприятия должны действо-іть быстро и эффективно, проникать на мировые рынки, использовать но-ые технологии, совершенствовать организационную структуру, товарные, инансовые и информационные потоки, внутренний и внешний документо-борот. Ключ к разрешению этих проблем лежит в сквозной автоматизации, источающейся в разработке и использовании интегрированных систем правления, базирующихся на современных методологиях "планирования и V правления различного вида ресурсами {MRP, MRPII, CRP, FRP, ERP, CSRP т.д.), отражающих необходимость дальнейшей автоматизации управления 1 азличнымя процессами, происходящими как внутри сферы производства, їк и при его взаимодействии с потребителем.
Обе эти задачи: раскроя-упаковки и автоматизации тесно переплетайся в проблеме разработки автоматизированных систем размещения \СР) объектов разного вида в заданных областях на базе адекватных мате-атических моделей и эффективных современных методов их решения. Эта
задача должна рассматриваться с точки зрения создания различных интегр рованных систем управления, одной из составляющих которых являют АСР.
В классе задач Р-У на верхних ступенях сложности, по отношению другим задачам Р-У, находятся задачи двух- и трехмерного нерегулярно размещения геометрических объектов (ГО) сложных форм. Это связано трудоемкостью формализации условий взаимного непересечения объектов условий их размещения в заданных областях Р-У.
Анализ отечественной и зарубежной литературы, информационнъ Internet-источников позволяет сделать следующее заключение:
исследованием и разработкой методов решения задач двумерно, нерегулярного размещения занимаются несколько коллективов и о дельных авторов, это: Харьковская школа Р-У академика Стояі Ю.Г.; Институт алгоритмов и научных вычислений Германии (Леї гауэр Т.); Миленковик В., Даниэльс К. (США); Доусланд К., Доу ланд В.(Великобритания); и ряд ученых в различных странах мира;
исследование и разработка методов решения задач трехмерного и регулярного размещения является новым научным направлением классе задач раскроя - упаковки, которым занимается несколько а: торских коллективов: Иконен И., Билес В. и др., Баллинг Р., Ландс М. и др., Зукман С, Каган И., Coca М. (США); Дикинсон и Кноп (Канада); Такаюки Осогами (Япония). Активно работы в этом н: правлении развернулись во второй половине 90-х годов в связи развитием одного из практических приложений этих задач - быстр( го прототипирования.
Несмотря на заметное продвижение в области решения задач раскроя упаковки:
- до сих пор в большинстве случаев на производстве карты Р-У прс
*-ivilzI^/^iwTl>i. ііруЧИj 1.0 «del IIpliwillTHBIILLiizI mrrCpUKTIIScxblivHI npc
граммными средствами. Это нарушает непрерывность процесса ш томатизации и приводит к нерациональному использованию дороге стоящих материалов и высокопроизводительного оборудования дл Р-У. Причиной такого состояния является отсутствие эффективног математического обеспечения для автоматизации решения задач т регулярного размещения ГО для двух- и для трехмерного простраї ства.
профессиональные укладчики при ручном размещении при решени задач нерегулярного размещения часто получают результаты луч шие, чем сгенерированные на ЭВМ;
известные реализации условий взаимного непересечения геометрк ческих объектов между собой и их нахождения в области размеще ния не отвечают требованиям к скорости и надежности при работе
составе АСР, в связи с тем, что эта задача является некорректно поставленной; - в настоящее время не существует методологии создания автоматизированных систем нерегулярного размещения двух- и трехмерных геометрических объектов, функционирующих в составе интегрированных систем управления и взаимодействующих с такими их подсистемами, как САПР, АСУП, АСТПП. Основную сложность при создании таких автоматизированных систем, оставляет разработка математических методов, моделей и алгоритмов обра-отки информации, используемых при функционировании системы. Для эф->ективного решения рассматриваемого класса задач необходимо использо-ание современных методов оптимизации, что позволяет получать более ка-ественные решения при меньших временных затратах. Дискретность работы редств цифровой вычислительной техники, трудоемкость базирующихся на
юсть математических моделей и, как следствие, неустойчивость работы созываемого математического обеспечения. Возникает потребность работы с юделями дискретными, цифровыми.
Все вышесказанное определяет актуальность решаемой в данной ра-іоте научно-технической проблемы разработки ресурсосберегающих тех-юлогий, ведущих к экономии магйериальных и временных ресурсов за чет рационального размещения объектов различного вида при решении адач раскроя и упаковки промшиленных материалов.
В современных условиях эта проблема может быть решена с помощью надежной и эффективной работы автоматизированных систем раз-іещения ГО, функционирующих в составе интегрированных систем управ- [/' '.гния современным рыночным предприятием.
Цель работы: разработка методологических основ и инвариантного
математического обеспечения автоматизированных систем нерегулярного
зазмещения двух- и трехмерных геометрических объектов, функционирую--!
цих в составе интегрированных систем управления современным предпри- | ''
ітием и направленных на рациональное использование материальных ресур- !
;ов. ;
Основные задачи исследования в соответствии с поставленной целью формулированы следующим образом:
1. Разработать методологию создания автоматизированных систем нерегулярного размещения двух- и трехмерных геометрических объектов в составе интегрированных систем управления современным предприятием.
-
Разработать теоретические основы оптимизации нерегулярного ра: мещения двух- и трехмерных геометрических объектов на базе ди< кретных методов локального поиска, направленные на создани гибкого математического обеспечения АСР ГО.
-
Разработать теоретические основы применения дискретне логического способа представления информации для реализации у< ловий взаимного непересечения размещаемых геометрических обт ектов между собой и областью размещения, ориентированные и создание надежного математического обеспечения АСР ГО.
-
Исследовать эффективность разработанного математического обес печения и внедрить в промышленность программное обеспечеїш автоматизированных систем нерегулярного размещения ГО с прі менением предложенных дискретных моделей.
Методы исследования.
Результаты теоретических исследований, выполненных в работе, бази руются на основных положениях системного анализа, исследования опера цкй, аналитической и вычислительной геометрии, математического прс граммирования, машинной графики, а также структурного и модульного прс граммирования. В процессе исследований использовались методы и средств организации комплексов программных средств, машинные эксперименты да определения эффективности алгоритмов.
В связи с высокой сложностью задач оптимизации нерегулярного раз мещения двух- и трехмерных геометрических объектов особое внимани уделено метаэвристическим методам локального поиска, а также методу по следовагельного улучшения оценок, основанному на использовании объек тивно - обусловленных оценок Л.В. Канторовича.
Для реализации методов и алгоритмов моделирования условий взанм ного непересечения геометрических объектов между собой и с областью раз мещения были использованы разделы машинной графики, посвященные гео метрии дискретной плоскости и дискретного трехмерного пространства.
Результаты, выносимые на защиту:
1. Методология создания автоматизированных систем нерегулярной размещения двух- и трехмерных геометрических объектов, позво ляющая разрабатывать автоматизированные системы, взаимодейст вующие с различными подсистемами (САПР, АСУ, АС ТІШ и т.д.) работающими в составе интегрированных систем управления со временным предприятием и базирующиеся на структуре, содержа щей блоки оптимизации и обработки данных о геометрии, а такж< интерфейс раскроя-упякоеки, регламентирующий взаимодействи; АСР ГО с различными подсистемами ПСУ.
-
Теоретические основы оптш.сізацин нерегулярного размещения двух- и трехмерных геометрических объектов, базирующиеся на адаптации и интеграции методов дискретной оптимизации: "Поиска с запретами" (TS), "Моделирования отжига" (SA), "Генетических алгоритмов" (GA), "Муравьиной колонии" (АС), "Объективно - обусловленных оценок Л.В.Канторовича" (SVC) и на построении годографа функции плотного размещения, позволяющие разрабатывать инвариантное различным подсистемам в составе ИСУ математическое обеспечение оптимизационного ядра АСР ГО.
-
Теоретические основы применения дискретно-логического способа представления информации и цепного кодирования для построения годографа функции плотного размещения двух- и трехмерных геометрических объектов, позволяющие создавать надежное и быстродействующее математическое обеспечение геометрической подсистемы АСР ГО.
-
Математическое и программное обеспечение систем нерегулярного размещения геометрических объектов с применением разработанных дискретных моделей, позволяющее решать задачи, возникающие в различных подсистемах ИСУ современным предприятием.
-
Результаты анализа эффективности разработанного математического обеспечения автоматизированных систем нерегулярного размещения двух- и трехмерных геометрических объектов, включающие сравнительные характеристики экспериментальных данных, полученных автором и другими исследователями, а также внедрение разработанного программного обеспечения на ряде предприятий различных отраслей промышленности.
Научная новизна работы заключается в следующем:
-
Предложена структура автоматизированной системы размещения геометрических объектов, которая включает в себя блок оптимизации и блок обработки данных о геометрии, взаимодействующие через интерфейс математического программирования. Для регламентирования взаимосвязи АСР ГО с различными подсистемами, функционирующими в составе ИСУ предприятия, выделен интерфейс раскроя - упаковки. Такая структура АСР ГО инвариантна к различным, используемым в системе, способам представления информации, методам моделирования различного типа геометрических преобразований, а также к всевозможным видам оптимизационных механизмов.
-
Разработано эффективное математическое обеспечение оптимизационного ядра АСР ГО, включающее класс годограф - ориентированных алгоритмов решения задач нерегулярного размещения двух- и трехмерных геометрических объектов, основанных на применении
следующих метаэвристцнеских методов локального поиска: "Пои ка с запретами" (75), "Моделирования отжига" (SA), "Генетт ских алгоритмов" {GA), "Муравьиной колонии" {АС). Это позволяї получать допустимые и близкие к оптимальным решения задач н регулярного размещения ГО.
-
Разработаны и исследованы метод и ряд комбинаторных детермі нированных алгоритмов решения задач нерегулярного размещеш двух- и трехмерных геометрических объектов на базе объективно обусловленных оценок Л.В.Канторовича. Разработаны способы по, счета оценок для двух видов непокрытой геометрическими объект ми области размещения - несвязной и многосвязной. Это позволж быстро получать эффективные допустимые решения задач нерег лярного размещения ГО.
-
Разработано эффективное математическое обеспечение геометричі ской подсистемы АСР ГО, включающее теоретические основы м< делирования нерегулярного размещения двух- и трехмерных ге< метрических объектов в заданных областях на базе дискретш логического представления информации и цепного кодирования, п< зволяющие осуществить формализацию и решение широкого круї важных практических задач и включающие в себя различные епосі бы построения годографа функции плотного размещения и алгори' мы аппроксимации ценными кодами объектов с линейно - заданнь ми границами. Особенностью данного представления информаци является то, что оно позволяет реализовать моделирование услоья взаимного непересечения ГО между собой и с областью размещеш: надежно и быстро, а также дает возможность варьирования скорі стью получения результатов в зависимости от применяемой точн< сти аппроксимации.
Практическая значимость работы.
Разработанные в диссертации теоретические основы, методы и алп ритмы решения задач нерегулярного размещения двух- и трехмерных ге< метрических объектов произвольной пространственной формы в заданны областях дают возможность на единой основе создавать надежное и гибке математическое и программное обеспечение, легко адаптируемое к любы производственным условиям и допускающее возможность широкого ИСП0Л1 зования в различных отраслях промышленности. Кроме того, разработаннь: на основе метаэврнстических методов локального поиска и метода оценс комбинаторные методы и алгоритмы оптимизации позволяют создать кор. плекс программных средств, быстро генерирующих высокоэкономичкь карты раскроя - упаковки. Все это дало возможность применить полученнь: результаты для разработки соответствующего программного обеспечени которое может быть использовано в составе различных подсистем ИСІ
\.СУП, САПР п АСТПП, а также для создания на этой основе автономного юмплекса программных средств. На базе проведенных исследований разра-іотан работающий в среде Microsoft Windows 95/98 комплекс программных редств для решения задач Р-У - "Cut-CAD", который на практике показал іьісокую эффективность за счет быстрой адаптации к условиям работы про-оводств различного вида в разнообразных отраслях промышленности, хо-юшей совместимости с различными подсистемами, функционирующими в оставе ИСУ, уменьшения времени проектирования карт Р-У (в 5-10 раз) и ікономии материала (до 5%).
Основания для выполнения работы
Работы в данном направлении проводились автором в Уфимском авиа-цюнном институте в 1989-1992 годах в рамках поисковых НИР по заказам Уральского филиала НИИД ("Рациональный раскрой материала с учетом !риектацик волокон") а НПО БУММЛЫ1 ("Система автоматизированного гармирования и расхода материала с обеспечением его рационального рас-;роя"). В дальнейшем работы были продолжены в рамках выполнения хоздо-оворных научно-исследовательских работ с Уфимским производственным объединением "Гидравлика" по темам №ИФ-ВК 01-92-ОГ (1992-1993 г.г.), ШФ-ВК-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 г.;
Международный конгресс по исследованию операций. EURO-XVI, Брюссель, Бельгия, 1998 г.;
Международная научная конференция "Моделирование, вычисления, проектирование в условиях неопределенности, Уфа, 2G00 г.
Публикации.
По теме диссертации опубликованы 53 работы, в том числе 1 монография (в соавторстве), 26 статей, 24 тезисов докладов, а также 2 научно-ехнических отчета.
Структура работы.
Диссертация состоит из введения, шести глав, выводов, списка литера-уры и приложения. Объем основной части диссертации составляет 324 стра-шцы, кроме того, работа содержит 69 рисунков и 12 таблиц, расположенных m 44 страницах. Библиографический список включает 300 наименований.
