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

005049877

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

ТЕЛИЦКИЙ Станислав Владиславович

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

Специальность 05.13.01 - Системный анализ, управление и обработка информации (в промышленности)

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

Уфа - 2013

г 1 ФЕВ 2013

005049877

Работа выполнена на кафедре компьютерной математики Федерального государственного бюджетного образовательного учреждения высшего профессионального образования «Уфимский государственный авиационный технический университет»

Научный руководитель Д-р техн. наук, доцент

Филиппова Анна Сергеевна

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

Официальные оппоненты д-р техн. наук, проф.

Мунасыпов Рустэм Анварович

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

канд. физ.-мат. наук, доц. Панюкова Татьяна Анатольевна

Национальный исследовательский Южно-Уральский государственный университет, доцент кафедры экономико-математических методов и статистики, г. Челябинск

Ведущая организация ФГБОУ ВПО «Башкирский государствен-

ный университет»

Защита состоится 6 марта 2013 г. в 10 часов на заседании диссертационного совета Д-212.288.03 при Уфимском государственном авиационном техническом университете по адресу: 450000, г. Уфа, ул. К. Маркса, 12

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

Автореферат разослан « »г.

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

д-р техн. наук, проф. В. В. Миронов

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

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

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

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

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

Проблема оптимизации решения задач ортогонального раскроя и размещения хорошо исследована, среди ключевых деятелей этого направления выделяются российские ученые Л. В. Канторович, В. А. Залгаллер, И. П. Норенков, Э. А. Мухачева, И. В. Романовский, В. М. Картак, В. Д. Фроловский, а также зарубежные А. ВогйЫ&, в. 8с11е1£Ьаиег, Н. БукЬоГГ и др. Однако известные методы и алгоритмы не предназначены для решения многокритериальной комплексной задачи геометрического покрытия и раскроя. Поэтому разработка эффективных алгоритмов для решения многокритериальной задачи геометрического покрытия многосвязного полигона ортогональным ресурсом с учетом технологических ограничений является актуальной проблемой.

Дели и задачи исследования

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

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

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

Основные задачи исследования:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Достоверность результатов

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

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

Связь темы исследования с научными программами

Работа выполнялась в рамках исследований по информационным системам, решения практических задач упаковки многомерных ортогональных многогранников, проводимых в Уфимском государственном авиационном техническом университете при поддержке гранта Российского фонда фундаментальных исследований (РФФИ), проект 12-07-00631-а.

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

По основным результатам работы были сделаны доклады на конференциях: Всероссийские зимние школы-семинары аспирантов и молодых ученых «Акту-

альные проблемы науки и техники» (Уфа, 2010-2012); III международная научно-практическая конференция «Наука и современность-2010» (Новосибирск, 2010); международная школа-конференция «Фундаментальная математика и ее приложения в естествознании» (Уфа, 2011); Всероссийская молодежная научная конференция «Мавлютовские чтения» (Уфа, 2011); VIII международная научно-практическая конференция «Стратегические вопросы мировой науки» (Пере-мышль, 2012), научных семинарах кафедры компьютерной математики Уфимского государственного авиационного технического университета.

Публикации

Основные результаты диссертации отражены в 15 научных трудах, в том числе в 4 статьях в изданиях, рекомендованных ВАК, 10 - в других изданиях, 1 свидетельство о регистрации программы для ЭВМ.

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

Диссертация (163 с.) состоит из введения, четырех глав, заключения, списка литературы (122 наимен.).

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

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

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

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

Концепция решения базируется на системном подходе, состоит из следующих основных уровней:

1. Декомпозиция проблемы геометрического покрытия: представление многокритериальной задачи в виде однокритериальных оптимизационных подзадач: разбиение многосвязного полигона (МП) на прямоугольные области (боксы); геометрическое покрытие прямоугольной области и определение размеров покрывающих элементов; раскрой прямоугольных элементов из ортогонального ресурса (рис. 1).

2. Анализ взаимосвязей и преобразование информации между подзадачами.

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

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

I п.

П, Я,

п ^

Рисунок 1 - Этапы решения задачи покрытия полигона ортогональным ресурсом

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

Задача ППОР. Дана область - многосвязный полигон Р ширины РУи длины Ь, а также множество В прямоугольных препятствий заданных размеров юуД„,у = 1,ц, где (I - количество препятствий, со , А. - ширина и длина у-го препятствия. Введем прямоугольную систему координат: оси Ох и Оу совпадают соответственно с нижней и левой боковой сторонами огибающего прямоугольника полигон Р. Положение каждого прямоугольного препятствия Ву задается координатами (%У) т^) его нижнего левого угла. Таким образом, полигон можно представить следующим набором исходных данных:

Р = = = (рис- 2)- Кроме того, имеется неог-

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

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

т

или ^(Д Г) =£(',- + */),

г=1

ramFcut(RT) =

РП

N , если ресурс - прямоуголь ные листы;

L — max (xj + /,-), если ресурс-полубесконечная полоса. i=\..m

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

{х2 > У2 )

U2

"6

б)

Рисунок 2 - Данные задачи ППОР: а - исходный полигон с препятствиями; б - покрытая область полигона; в - ортогональный ресурс

Необходимо выполнения следующих условий. Для этого введем дополнительно двойственные переменные г*, ги такие, что: =1, если проекция прямоугольного элемента I на ось Ох находится левее проекции прямоугольного элемента у на ось Ох, иначе г,у = 0 ; аналогично г?, =1, если проекция

прямоугольного элемента г на ось Оу находится ниже проекции прямоугольного элемента j на ось Оу, иначе г? =0; г? =1, если проекция прямоугольного элемента ¡" на ось Ох находится левее проекции препятствия у на ось Ох, иначе ? * = 0; аналогично г? = 1, если проекция прямоугольного элемента г на ось Оу

находится ниже проекции препятствия V на ось Оу, иначе = 0.

Необходимо найти:

1. Множество КТ прямоугольных элементов, покрывающих полигон Р, и соответствующий план покрытия, т. е. для каждого е КТ требуется отыскать набор значений (х,-ж,), где х^у1 - координаты левого нижнего угла элемента в системе координат полигона Р, /,• и wi — соответственно длина и ширина

прямоугольного элемента, таких, что:

/,<й,/ = 1Я (1)

м>1 <0, 1=1,/и, (2)

xi+li<L (3)

У1+ч>1<1¥, (4)

х,->0, (5)

у1>0, ¡ = 1т, (6)

+ + г? + >1, /'= 1,т,7 = 1,от,г */, (7)

1-2$), г=Т^г,]=йп, (8)

= (9)

+ г + + >1, г=1,от,у = 1,|1, (10)

^>^+^--^(1-2^), г = (11)

Хч>Х1+^-Щ-2*), г = 1,/и,у = 1,ц, (12) т

ХЧЧ'=%77- (13) ¿=1

2. План раскроя К(ЯТ) ортогонального ресурса на прямоугольные элементы множества Л 7' такой, что выполняются следующие условия:

х\>0, 1=йтй, (14)

у\>Ъ, / = ТЯ_ (15)

х\+11 <0, 1 = 1,от, (16)

(17)

+ гу,-+ + г]1,- >1, i = l,m,j = l,m,i*J, (18)

у} >>-; (19)

х) >х\ + /,- -1(1 -ф, i = 1 ,m,j = 1 ,m. (20)

Условия (1), (2) накладывают ограничения на размеры покрывающих прямоугольных элементов, причем для задач с ортогональным ресурсом в виде полубесконечной полосы следует принять 0 = а>. Условия (3)-(б) задают допустимое положение прямоугольного элемента в области полигона. Условия (7)-{9) обеспечивает неперекрытие прямоугольных элементов между собой, (10)—(12) - неперекрытие прямоугольных элементов с препятствиями. Условие (13) описывает необходимость полного геометрического покрытия полезной площади полигона прямоугольными элементами. Условия (14Й17) обеспечивают допустимое размещение прямоугольных элементов внутри ортогонального ресурса, условия (18)-(20) обеспечивают неперекрытие прямоугольных элементов между собой.

Критерием оптимизации при решении задачи раскроя является минимизация расхода используемого ортогонального ресурса Fcul(RT) (количество прямоугольных листов NPJ1 или длины занятой части полосы Ьрп).

Для решения задачи ППОР в данной работе предлагается использовать эвристический метод анализа и пересчета условных оценок, которые позволяют получить лучшие варианты разбиения полигона на прямоугольные боксы. Лучшими считаются те, размеры которых кратны (близки к целому значению) линейным размерам ресурса. На начальном этапе заданный Р разбивают на боксы Д-, для которых на последующих этапах определяется план покрытия и размеры прямоугольных элементов. План покрытия боксов определяется на основе оценок g¡ =W'/h или g¡ = L'/h, i-\,..,k, где Wl - ширина, L' - длина прямоугольной области П„ h - ширина исходного материала. Длина исходного материала считается неограниченной для задачи РП.

Помимо того вводятся вспомогательные условные ог^нки g¡ = min(l - {gj},{gi}), г-1,-А где {g,} - дробная часть оценочного значения g¡. Чем меньше оценочное значение g'¡ (т.е. чем ближе g¡ к целому), тем оно считается лучше (тем экономичнее будет разрезаться рулон или листы материала). Оценка g\, удовлетворяющая условию g\ <val, va/e [О; 0,5], где val - критическое задаваемое значение g¡, считается удовлетворительной.

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

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

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

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

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

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

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

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

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

данного пользователем количества итераций с сохранением множества лучших решений. Блок-схема алгоритма НЕЛУ приведена на рис. 4.

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

Рисунок 3 - Блок-схема алгоритма с оценкой остатка ЛУК

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

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

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

• определение рационального набора входных параметров для алгоритма с оценкой остатка АУЛ и гибридного эволюционного алгоритма с оценками НЕАУ;

• сравнение эффективности РРО+Ог (жадные алгоритмы решения задач покрытия и раскроя без взаимосвязи), АУК. и НЕАУ для решения многокритериальной задачи ППОР.

Рисунок 4 - Блок-схема гибридного эволюционного алгоритма с оценками НЕАУ

Эксперименты № 1 и № 2 направлены на исследование эффективности разработанной модификации послойного алгоритма с оценками (ЪАУК.) и сравнения с известными для решения задач раскроя листов и полубесконечной полосы соответственно. Результаты эксперимента позволяют заключить, что разработанный послойный алгоритм конкурентоспособен. Так как структура алгоритмов АУЛ и

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

Алгоритм матричной .декомпозиции

Параметры .

Алгоритм LAVR

Рисунок 5 — Общая схема построения решения задачи 111 ЮР проблемно-ориентированной системой

Для исследования эффективности алгоритмов AVR и HEAV решения задачи Ш ЮР были сгенерированы специальные тестовые примеры: 9 классов задач. На этих классах задач были поставлены эксперименты № 3 и № 4. Эксперимент № 3 направлен на определение рационального критического значения оценки val. Все 900 задач были прорешаны при помощи алгоритмов AVR и HEAV при каждом значении параметра val из диапазона [0.1 ... 0.49] с шагом 0.01. Для каждого значения параметра val рассчитывалась средняя по всем задачам величина коэффициента раскроя для обоих алгоритмов. Результаты эксперимента показали, что для алгоритма AVR целесообразно принять val = 0.28, а для алгоритма HEAV val =0.23. Дальнейшее снижение значения этого параметра не приводит к значительному устойчивому улучшению получающихся карт раскроя, однако влечет за собой увеличение вычислительного времени работы алгоритмов.

Эксперимент № 4 проводился при найденных рациональных значениях параметра val для обоих алгоритмов. Цель эксперимента состояла в определении целесообразности использования разработанных алгоритмов AVR и HEAV на различ-

ных классах задач, и последующем вынесении рекомендаций относительно их применения. Показателем эффективности работы алгоритмов в данном эксперименте служит коэффициент раскроя £си1 -Б^/Я, где 5 - площадь израсходованной части ресурса, - суммарная площадь прямоугольных элементов. Результаты работы алгоритмов АУЯ и НЕАУ сравнивались с однопроходным процессом решения задач покрытия и раскроя на основе принципа «жадности» - для этапа определения размеров покрывающих элементов и покрытия, для этапа раскроя ортогонального ресурса — алгоритм «первый подходящий» с упорядочиванием (РРЕН-Сг). Последний моделирует действия мастера при формировании планов покрытия и раскроя. В среднем алгоритм АУЛ позволяет улучшить решения, полученные при помощи ББЕН-Ог на 5.5 %. В лучшем случае, на задачах по некоторым классам, улучшение достигает 8 %. Для алгоритма НЕАУ среднее улучшение по сравнению с алгоритмом РБО+Сг достигает 7.3 %, а наибольшее составляет 11.4 %. Средние значения коэффициента раскроя по трем классам задач представлены на рис. 6. Классы характеризуются отношением суммарной площади препятствий к площади полигона г = , где для класса 81 - х е [0..0.2], для Б2 -т е [0.2..0.7], для БЗ те[о.7..1].

Рисунок 6 - Значения коэффициента раскроя на различных классах задач для алгоритмов FFD+Gr, AVR и HEAV

Кроме того, в работе приведено исследование решений практических задач, возникших на предприятии по судостроению, а именно задачи ППОР и задачи раскроя. В случае решения задач ППОР среднее улучшение составляет 5% по сравнению с решениями, имеющимися на предприятии ОАО «Судостроительный завод «Северная верфь». Пример полученного плана покрытия полигона приведен на рис. 7, размер листового ресурса 1220x2440, коэффициент условной стоимости

г Sifrj Рресурс „

резов &cov = -----г , где Prt — суммарный периметр покрывающих прямо-

Prt $ресурс

угольных элементов, S^n - полезная площадь многосвязного полигона, Specypc - площадь ресурса, Рресурс " периметр ресурса.

Для задач раскроя имеющиеся на предприятии программные средства формируют карты в 86 % случаев хуже, чем предложенный алгоритм LAVR, в среднем на 2-3 %, что подтверждено актом об использовании результатов диссертационной работы.

область покрытия

iÜE

НШ

Рисунок 7 - Решение задачи ППОР: а - палуба судна снабжения (проект VS 470 PSV Mk И); б - многосвязный полигон покрытия; в - пример плана покрытия, kcov =0,679905, fccut=0,95, Fcov=329120, Fcut=65

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

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

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

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

3. Разработаны метод и алгоритмы (алгоритм с оценкой остатка и гибридный эволюционный алгоритм с оценками) для рационального решения многокри-

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

4. Разработано программное обеспечение, основанное на предложенных алгоритмах и модифицированном методе последовательного уточнения оценок, которое позволило исследовать эффективность предложенных методов и алгоритмов с помощью численного эксперимента и определить рациональные управляющие параметры в виде критических значений условных оценок: для алгоритма с оценкой остатка - val = 0.28; для гибридного эволюционного алгоритма с оценками — val = 0.23. В среднем при решении многокритериальной задачи геометрического покрытия алгоритм с оценкой остатка улучшает решение на 5.5 %, а гибридный эволюционный алгоритм с оценками - на 7.3 % по сравнению с последовательным и не взаимосвязанным решением задачи покрытия и раскроя жадным способом и алгоритмом «первый подходящий», применяемыми в ОАО «Судостроительный завод «Северная верфь».

СПИСОК ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ В рецензируемых журналах из списка ВАК

1. Проектирование размещения ортогональных объектов на полигонах с препятствиями / Э. А. Мухачева, Ю. И. Валиахметова, С. В. Телицкий, Э. И. Хасанова // Информационные технологии. 2010. № 10. С. 16-22.

2. Комплексный подход к решению задачи покрытия области заготовками неопределенных размеров / С. В. Телицкий, А. С. Филиппова // Научно-технические ведомости СПбГПУ. Информатика. Телекоммуникации. Управление. 2012. 2(145)/2012. С. 61-67.

3. Гибридный алгоритм на основе последовательного уточнения оценок для задач максимального ортогонального покрытия / С. В. Телицкий, Ю. И. Валиахметова, Э. И. Хасанова // Вестник Башкирского университета. 2012. Т. 17, № 1 (I), С. 421-425.

4. Применение систем автоматизированного проектирования карт раскроя в судостроении / С. В. Телицкий, Ю. И. Валиахметова // Вестник Воронежского государственного технического университета. 2012. Т. 8, № 6. С. 38-43.

В других изданиях

5. Задача ортогонального раскроя листового материала: метод декомпозиции исходных данных на базе гильотинного размещения деталей / С. В. Телицкий, JI. Ф. Розанова // Принятие решений в условиях неопределенности: межвуз. науч. сб. Уфа: УГАТУ, 2009. Вып. 6. С. 148-154.

6. Сравнение метода последовательного уточнения оценок и его модификация / С. В. Телицкий, М. В. Бойко // Актуальные проблемы науки и техники.

Информационные и инфокоммуникационные технологии и естественные науки: сб. тр. 5-й Всеросс. зимн. шк.-сем. асп. и молод, уч., 17-20 февраля 2010. Уфа: УГАТУ, 2010. Т. 2. С. 81-84.

7. Сравнение способов вычисления оценок в методе случайного уточнения оценок / С. В. Телицкий, М. В. Бойко // Актуальные проблемы науки и техники: сб. тр. 5-й Всеросс. зимн. шк.-сем. аспирантов и молодых ученых, 17-20 февраля 2010. Уфа: УГАТУ, 2010. Т. 1. С. 8-10.

8. Применение метода последовательного уточнения оценок для решения задач одномерного раскроя / С. В. Телицкий, JI. Ф. Розанова, М. В. Бойко // Наука и современность - 2010: сб. материалов П1 Междунар. науч.-практ. конф. Новосибирск: ЦРНС, 2010. Ч. 2. С. 200-206.

9. Совершенствование системы технологической подготовки раскройно-заготовительных производств в судостроении с использованием методов оптимизации прямоугольного раскроя / С. В. Телицкий // Фундаментальная математика и ее приложения в естествознании: сб. тез. Междунар. шк.-конф. для студ., аспир. и молод, уч. Уфа: РИЦ БашГУ, 2011. С. 268.

10. Конструктивные эвристики для решения задачи гильотинного размещения предметов / С. В. Телицкий // Мавлютовские чтения: сб. тез. докл. Всерос. молодежи, науч. конф. Уфа: УГАТУ, 2011. Т. 5. С. 73-74.

11. Применение оптимизации прямоугольного раскроя для совершенствования системы технологической подготовки раскройно-заготовительных производств в судостроении / С. В. Телицкий // Фундаментальная математика и ее приложения в естествознании. Математика: сб. ст. Междунар. шк.-конф. для студ., аспир. и молод, уч. Уфа: РИЦ БашГУ, 2011. Т. 1. С. 140-144.

12. Анализ методов решения задач гильотинного раскроя / С. В. Телицкий // Актуальные проблемы науки и техники: сб. ст. 7-й Всеросс. зимн. шк.-сем. аспир. и молод, уч. 14-16 февраля 2012. Информационные и инфокоммуникационные технологии. Уфа: УГАТУ, 2012. Т. 1. С. 345-347.

13. Оптимизация размещения технических объектов в системах автоматизированного проектирования / С. В. Телицкий, Э. И. Хасанова, А. С. Филиппова // Стратегические вопросы мировой науки: сб. труд. VIII междунар. науч.-практ. конф. Перемылить, Польша, 7-15 февраля 2012. Тех. науки. Т. 31. С. 61 - 65.

14. Алгоритмы пересчёта оценок для комплексного решения задачи геометрического покрытая / С. В. Телицкий // Проектирование и исследование технических систем: межвуз. науч. сб. Наб.Челны: ИНЭКА, 2012. №. 5. С. 12-21.

15. Свид. об офиц. per. программы для ЭВМ № 2013611029. Программа для комплексной задачи геометрического покрытия и раскроя / С. В. Телицкий, Р. А. Гарифуллин, Ю. И. Валиахметова. Зарег. 09.01.2013. М.: Федеральная служба по интеллектуальной собственности, 2013.

Диссертант

С. В. Телицкий

ТЕЛЙЦКИИ Станислав Владиславович

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

Специальность 05.13.01 Системный анализ, управление и обработка информации

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

Подписано в печать 28.01.2013 Формат 60x84 1/16. Бумага офсетная. Печать плоская. Гарнитура Тайме. Усл. печ. л. 1,0. Уч.-изд. л. 1,0. Тираж 100 экз. Заказ № 40.

ФБГОУ ВПО «Уфимский государственный авиационный технический университет» Центр оперативной полиграфии 450000, Уфа-центр, ул. К. Маркса, 12