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

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

ЯГУДИН Рустем Расламович

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

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

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

Уфа-2012

2 О ДЕК 2012

005047683

Работа выполнена в ФГБОУ ВПО «Уфимский государственный авиационный технический университет» на кафедре вычислительной математики и кибернетики

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

д-р техн. наук, проф.

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

Официальные оппоненты

д-р техн. наук, проф. МУНАСЫПОВ Рустэм Анварович

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

д-р техн. наук, доц.

ПЕТУНИЯ Александр Александрович

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

Ведущая организация

ОАО «Уфимское моторостроительное производственное объединение»

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

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

Автореферат разослан «_2~Ь> ноября 2012 г.

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

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

Актуальность темы. Среди проблем экономии ресурсов, наиболее интенсивно изучаемых на сегодняшний день, можно выделить класс задач, связанных с поиском оптимального размещения трехмерных объектов в некотором ограниченном пространстве. В частности, к ним относятся задачи: упаковка грузов (папример, при транспортировке или хранении), раскрой материалов (например, алмаза), компоновка деталей изделия (например, двигателя), размещение 3-D объектов при синтезе объемных изделий с использованием инновационных технологий быстрого прототипирования и изготовления (RP&M — Rapid Prototyping & Manufacturing) (например, при селективном лазерном спекании) и т. д.

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

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

- Харьковская школа раскроя-упаковки академика Ю. Г. Стояна: Н. И. Гиль, А. В. Панкратов, JI. Д. Пономаренко, А. А. Черноморец, А. М. Чугай (Институт проблем машиностроения HAH Украины);

- Уфимская школа раскроя-упаковки Э. А. Мухачевой: В. В. Мартынов, М. А. Верхотуров, А. Ф. Валеева, А. С. Филиппова, В. М. Картак (Уфимский государственный авиационный технический университет);

- В. Д. Фроловский (Новосибирский государственный технический университет);

- А. А. Петунии (Уральский государственный технический университет);

- J. Egeblad (Datalogisk Institut pa Kobenhavns Universitet)\

- I. Ikonen (University of Louisville)-,

- J. Cagan & S. Szykman (Canegie Mellon University) и другие.

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

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

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

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

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

3. Разработать метод генерации трехмерных карт.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

— в открытом акционерном обществе «Уфимское моторостроительное производственное объединение»;

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

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

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

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

— международной конференции "Компьютерные науки и информационные технологии" (С57Т), Уфа, 2012;

— зимней школе для аспирантов и молодых ученых (Уфа, 2008-2009);

- IV Всероссийской молодежной научной конференции «Мавлютовские чтения», 2010.

Публикации

По теме диссертации опубликованы 10 работ, в том числе 8 статей (3 из которых в рецензируемых журналах из списка ВАК), 2 доклада в трудах научно-технических конференций, получено 1 свидетельство об официальной регистрации программы для ЭВМ.

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

Диссертация состоит из введения, четырех глав, выводов и списка литературы. Работа изложена на 138 страницах машинописного текста, кроме того содержит 53 рисунка и 12 таблиц. Библиографический список включает 116 наименований и занимает 12 страниц.

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

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

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

Упаковка грузов ^___^ Учет центров тяжести ] Учет хрупкости ]

Компановка ----^Учет областей приоритета/запрета ]

1Мишш т и \iioio яп Д Возможность отделения объектов друг от друга 1

/ '

_____( Вертикальное расположение округлых поверхностей ] Стереолшпографи» г 1 -| Концентрация объектов в центре зоны размещения 1

---— £ Учет неоднородностираскраиваемого материала ' }

Укладка декоративного камня Учет распределения больших и малых камней

Учет нанесения цемента

Рисунок 1. Конструктивно-технологические ограничения в задачах размещения трехмерных объектов (курсивом выделены рассматриваемые в данной работе)

В работе произведен анализ наиболее распространенных конструктивно-технологических ограничений (рис. 1).

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

- чувствительны к типу входных данных (работают только с выпуклыми многогранными объектами или оперируют только простыми формами, в частности прямоугольными параллелепипедами, цилиндрами, сферами и пр.);

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

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

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

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

Дано: набор трехмерных геометрических объектов (ГО)

Матрица Л/ = {Р! 1),/ = 0, и, у" = 1, и . Каждый элемент матрицы описывает область в относительной системе координат объекта Т,-, запрещенную для размещения объекта 7}. Если г = 0, то рассматривается относительная система координат области размещения £).

Пусть Г, (¡7,) объект 7}, имеющий параметры размещения в системе координат области (2 - й, = е 1П', где {х^у^г,}- вектор смещения, а {а,, Д, /,} - углы поворота.

и - («, ,м2,...,й„) - параметры размещения объектов Т-{Тх,Т2,...,Тп} Условия непересечения ГО между собой можно записать как:

Область размещения Q с. 9t .

(1)

где int 7] - внутренние точки объекта 7). Условия нахождения ГО в области размещения:

T,(ül)f}Q = Ti(ü,),Vi = l,n. Условие непересечения ГО и областей запрещенных для размещения:

(2)

= 0>Vi = = * J ■

(3)

Система условий (1), (2), (3) связывает параметры размещения U объектов множества Г в области Q и является для них ограничениями.

Найти: Такой набор параметров размещения U = (u]tü2,...,un), который для целевой функции С = C(U) минимизирует ее величину, т. е.

С*=ф-)=1ШпФ). (4)

UsV

где V - область допустимых решений, задаваемых неравенствами (1), (2) и (3).

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

Пусть F' = {fj},a = hA , Е' ={e'b},b = hB и V = {vj},c = 1,С - множества полигонов, ребер и вершин объекта Tt. В такой постановке условия (1) можно разбить на две составляющие (без учета граничных случаев):

ie'b е £',// e FJ : intе'ьfj * 0,V/ = \rt, j = 1,п,i * j - условия непересечения внутренних точек ребер Г( и граней многогранного объекта 7}.

е V',Tj eТ:v^ еintТ],V» = 1,п, j = 1,п,- условия нерасположения

многогранного объекта Tt внутри 7}.

Условия непересечения внутренних точек ребер Г, и граней многогранного объекта 7}:

Параметрическое уравнение ребра е[, заданного парой точек {q'bl,q'br}, далее просто {q, = {x„y,,z,},qr = {xr,yr,zr}}, выражается так:

q = q,+(.qr-4i)t'tsl°< Ц-Параметрическое уравнеш!е плоскости, определенной полигоном fj, заданным множеством точек {р'аа,р'а^-,р'ат) . далее просто [р0 = {x0,y0,z0},

{Po ={ха>Уа>2ъ}<Р\ = {*,.*•».}.....Рш ={х„,Л,,*„}}, выражается так:

Р = Ра + (Pi - Ро>+ (Рг ~Ро>> w 6 ЭТ, v € 91. Приравняем уравнения ребра и плоскости:

qa + (Яь ~ 1 а)* = Ра + Oi ~Ро> + (Рг ~РоУ"; qa-Po= (<1а ~Чь)* + (Р\ ~Ро> + (Рг ~Ро>-В матричном виде:

~ХГ *1 х2 t

У1 ~Уо = Л -У г У\ ~Уо У2 ~Уо w

-zl zi ~zr z\ ~zo Z2 ~z0_ V

*1 ~*0 *2 -V -1 Х[ ~х0

= У; -Д'г л ~Уо ~Уо У1 ~Уо

V ~20 г2 -го. о.

Если /е(0, 1), то точка пересечения / ребра е'ь и плоскости, определенной полигоном // может быть найдена по формуле / = д, + - ?,)/.

Ребро е'ь пересекает полигон f¿ в точке I, если I принадлежит //. Пусть фк - угол (в радианах со знаком) между лучами (/, />,_,) и (/, рк):

<,1, ЛчМЛ Рк)

фк = атссоя

т

Если сумма ^¡Фк = 0, то I не является внутренней точкой полигона //,

иначе является и многогранные объекты 7} и 7} имеют общие внутренние точки. Условия нерасположения многогранного объекта Г; внутри 7}.

Пусть у/1" — величина телесного угла образованного лучами: (у[>Рк-\)> (Ус'Рк) и со знаком. Знак зависит от направления обхода

точек полигона fl наблюдаемого из точки . Величина угла ц/{", выраженная через составные двугранные углы а[а , р[а и ук имеет вид: К = а{° + РГ + у? - л, тогда:

А т .

т. е. если сумма Е V* = 0> то вершина ус многогранного объекта Т( не является 0=1 ,к=0

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

В качестве области размещения 2 с Л3 возьмем прямоугольный параллелепипед с фиксированными длиной Ь, шириной IV, и переменной высотой Н. Обозначим как Н(Т(Ц)) минимально необходимую высоту зоны 2 для размещения многогранных объектов множества Т = Щ,Т2,...,Тп} с параметрами размещения и = {щ,й2.....н„}, С(Ц) = Н(Т(Ц)). В соответствии с (4) необходимо найти такое II, чтобы Н(Т(Ц))-*тт, и выполнялись условия взаимного непересечения объектов между собой и с границами зоны размещения (1), (2), а также непересечения объектов с областями, запрещенными для размещения (3).

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

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

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

1. Геометрическая (внешняя) часть. Содержит в себе две подзадачи:

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

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

2. Оптимизационная (внутренняя, комбинаторная) часть. Содержит в себе также две подзадачи:

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

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

Рассмотрим подробнее каждый из этих этапов.

1. Геометрическая (внешняя) часть.

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

Годографом вектор-функции плотного размещения (ГФПР) СХ1 или <3(Г,(0),Т2(й2)) подвижного объекта Т2{и2) относительно зафиксированного 7",(0) называется такое множество положений центра объекта Т2, при котором он плотно расположен относительно объекта 7;, то есть 7} и Тг имеют общие граничные точки и не пересекаются внутренними.

Годограф Сп подвижного объекта Т2(и2) относительно зафиксированного ^(0) может быть определен через операции Минковского следующим образом:

6,2= г,(0) Ф-Ш"2)),

где А® В = { а+Ь | аеЛ, ЪеВ } - сумма Минковского множеств А и В, -А={ -а | аеА } - отражение объекта Л относительно начала координат.

Рисунок 2. Схемы использования ГФПР (на примере плоского случая)

Существует две основные схемы использования ГФПР в задачах размещения:

1. Предварительная. ГФПР всех объектов между собой и с областью рассчитываются перед началом этапа размещения, рис. 2, а. После занесения объекта в область все относящиеся к нему ГФПР смещаются в соответствии с его параметрами размещения.

2. Итеративная. ГФПР размещаемого объекта и области рассчитывается с учетом того, что все ранее размещенные объекты считаются ее частью, рис. 2, б.

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

Особенности динамической схемы использования ГФПР:

Пусть размещены первые (т - 1) объектов множества {7'ь Т2 ,..., Тп}, (т- 1) < п и выполняется размещение объекта Тт.

- Построение ГФПР объекта Тт относительно зоны размещения и уже упакованных объектов производится в соответствии с приоритетным списком: К={К0 ,.:., КтЛ). К{-<2, {К\ ,..., Кт.]} является множеством уже размещенных объектов {Ти ..., Тт-\), отсортированном в порядке увеличения координаты г самой нижней точки объекта.

- При построении очередного ГФПР С1 (К,, Т„) его параметры размещения {й,} анализируются на допустимость. Параметр размещения и, считаются

допустимыми если: й, £ ЫО,(КгТт),Ч} = 0, м- * г", при этом в случае, если

параллелепипедные оболочки объектов Тт(и, ) и Kj не пересекаются, то можно утверждать, что м, <£ intGj(Kj,Tm) без построения ГФПР Gj{Kj, Тт).

- Если определено, что параметр размещения й, является допустимым, то для объектов {Щ}: minZ(£,) > maxZ(7Цй,)) ГФПР не строится.

Предложенная схема инвариантна относительно вида представления размещаемых геометрических объектов. В случае рассмотрения многогранных объектов параметры размещения {м(}, принадлежащие ГФПР G,{Kb Тт), могут быть найдены в результате объединения следующих точек:

1) Вершин вогнутости ГФПР G,(Kh Тт).

2) Точек пересечения ребер вогнутости одного ГФПР из множества i-l _

IJG)(Ks,Tm\j = 0,г -1 и граней ГФПР G{Kb Тт) и наоборот.

1=о

3) Точек пересечения граней двух различных ГФПР из множества (jGjiK^TJJ = <V-~1 И граней ГФПР G,(Kh Тт).

В результате построения необходимых ГФПР, среди всех найденных допустимых параметров размещения выбирается тот, который минимизирует высоту расположения многогранного объекта Тт.

2. Оптимизационная (внутренняя, комбинаторная) часть

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

- «Первый подходящий с упорядочиванием»;

- детерминированно-вероятностный метод GRASP.

Метод «Первый походящий с упорядочиванием» (ППсУ) предполагает начальное ранжирование размещаемых объектов в порядке увеличения их объемов. Для улучшения качества размещения применяется локальный поиск (Jill), заключающийся в итеративной перестановке элементов лучшего найденного решения.

Метод GRASP (Greedy Randomized Adaptive Search Procedure) - жадно-рандомизированная адаптивная процедура поиска. Является итеративным методом, состоящим из двух стадий: конструкции и локального поиска. Его основные параметры:

N - количество запусков генерации размещения.

L - количество запусков локального поиска (ЛП) при каждой генерации.

as [0, 1] — параметр соотношения случайности/жадности метода.

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

Разработанный метод основан на построении «псевдограней» (понятие введено А. А. Черноморцем1). Построение каждой «псевдограни» ГФПР сопряжено с рассмотрением одного из вариантов соприкосновения объектов. Всего существует 4 базовых типа соприкосновения: грань-грань, грань-ребро, грань-вершина, ребро-ребро. В случае, если рассматриваемые объекты выпуклы, множество «псевдограней» 5 точно равно искомому ГФПР б, иначе «псевдограни» 5 всегда будут содержать самопересечения, однако все точки, принадлежащие 5 и не принадлежащие О, будут являться внутренними точками ГФПР С (5 \ Ос^хтО). ГФПР невыпуклых объектов может содержать внутренние области не связанные с внешней поверхностью, при этом внутренние точки будут описывать расположение одного объекта внутри другого, что нарушает технологические ограничения о возможности разделения объектов при практической реализации. С целью удовлетворения описанного технологического ограничения, а также с целью сокращения вычислительного времени построения ГФПР, предложен метод построения внешней составляющей в ГФПР О (всв^К в сЫО ).

х х

Рисунок 3. Подвижный ТэО,) и зафиксированный Т^О) многогранные объекты

Алгоритм построения внешней составляющей Оп ГФПР Ои подвижного многогранного объекта Т2(и7) относительно зафиксированного Т,(0) (рис. 3):

1. Построить набор «псевдограней» {э,} = 5 ГФПР Сп в результате рассмотрения всех вариантов соприкосновения объектов Т\ и Т2. Процесс конструирования изображен на рис. 4.

Грань-грань Грань-ребро Грань-еершина Ребро-ребро

Рисунок 4. Этапы построения «псевдограней» 5 ГФПР й\2

1 Метод построения поверхности 0-уровня Ф-функции: препринт / Н. И. Гиль, А. А. Черноморец. Харьков: АН Украины, Ин-т проблем машиностроения, 1992. 29 с.

2. Определить «псевдограни», находящиеся с внешней стороны полученного объекта 5.

3. Произвести рекурсивный обход объекта 5 с внешней стороны, с целью нахождения контуров принадлежащих внешней составляющей йп ГФПР 0124. Объединить грани построенные в результате обхода объекта 5, что эквивалентно искомой внешней составляющей <512 ГФПР Си (рис. 5, справа).

Рисунок 5. Результат построения «псевдограней» S (слева) и внешней составляющей Gl2

ГФПР (справа)

Как видно из рис. 5, места, в которых у объекта S были самопересечения, являются ребрами вогнутости внешней составляющей Gn ГФПР (они выделены жирными линиями).

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

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

- на исходных наборах данных, использованных в статье академика Ю. Г. Стояна 20052 года. Результаты сравнения эффективности размещения изображены на рис. 6, а на рис. 7 - лучшие полученные карты;

- на исходных наборах данных, использованных в статье Дж. Эгблада 20093 года. Результаты сравнения эффективности размещения изображены на рис. 8.

2 Packing non-convex polytopes into a parallelepiped / Yu. Stoyan, M. Gil, G. Scheithauer, A. Pankratov. Preprint MATH-NM-06-2004. TU Dresden, 2005. 32 p.

3 Translational packing of arbitrary polytopes / J. Egeblad, K. Benny, B. Marcus // Computational geometry. Elsevier,2009. Vol. 42, Iss. 4. P. 269-288.

Максимальное время размещения 75 объектов методом GRASP + JUT составило 4 часа, минимальное методом ППсУ - 1 мин. (Характеристики компьютера: Core2Duo 2.3Ghz, 2Gb RAM).

Для сравнения также был использован широко распространенный модуль SmartSpace программного продукта Magics© компании Materialise©.

30 25 20 15 10 5

Стоян 1 С! Стоян2 гаСтоян 3 ыППсУ аППсУ + ЛП Я GRASP ■ GRASP + ЛП

0 --1--—|---г-- ■SmartSpace

Здание! Здание? Здание 3 Здание 4

Рисунок 6. Процент заполнения зоны размещения для примеров из статьи Ю.Г. Стояна

Рисунок 7. Демонстрация лучших найденных карт для примеров из статьи Ю. Г. Стояна

' Метол Дж. Эгблада пППсУ а ППсУ + ЛП еGRASP в GRASP+ЛП a SmartSpace

Здание! Здание2 Здание 3 Здание 4 Здание 5 Рисунок 8. Процент заполнения зоны размещения для примеров Дж. Эгблада.

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

Рисунок 9. Результат размещения деталей

На основе данных, полученных в ходе вычислительного эксперимента, можно сделать следующие выводы относительно эффективности предложенных модели, методов и алгоритмов:

1. Применение методов и алгоритмов построения ГФПР сложных невыпуклых многогранных объектов позволяет уменьшить время расчета на величину до 40 %.

2. Применение «динамической» схемы использования ГФПР повысило скорость работы алгоритмов размещения на величину от 5 до 30 %.

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

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

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

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

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

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

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

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

1. Об одном решении задачи плотной упаковки выпуклых многогранников на основе годографа функции плотного размещения / М. А. Верхотуров, Г. Н. Верхотурова, Р. Р. Ягудин // Информационные системы и технологии: на-уч.-техн. журнал ГУ УНПК. Орел, 2012. № 4 (72). С. 31-39.

2. Оптимизация компоновки трехмерных геометрических объектов на основе годографа вектор-функции плотного размещения / Р. Р. Ягудин // Инженерный вестник Дона. 2012. № 3. ЬПр:/Ауёоп.ш/таеагте/агсЫуе/пЗу2012/915/.

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

размещения / Р. Р. Ягудин // Научно-технические ведомости. С.-Петербургск. гос. политехи, ун-та. Системный анализ и управление. 2012.. № 5 (157).

4. О некоторых подходах к решению задачи плотной упаковки многогранников / Г. Н. Верхотурова, Р. Р. Ягудин // IV Всероссийская зимняя школа-семинар аспирантов и молодых ученых. Т. 1. Уфа: УГАТУ, 2009. С. 577-581.

5. Построение годографа функции плотного размещения двух выпуклых многогранников / Г. Н. Верхотурова, Р. Р. Ягудин // Принятие решений в условиях неопределенности: межвуз. науч. сб. Уфа: УГАТУ, 2010. Вып. 7. С. 150-157.

6. Быстрый алгоритм поиска пересечения двух выпуклых многогранников / М. А. Верхотуров, Г. Н. Верхотурова, Р. Р. Ягудин // Принятие решений в условиях неопределенности: Межвузовский научный сборник. Вып. 7, Уфа: УГАТУ, 2010. С. 102-108.

7. Подход к разбиению многосвязного многоугольника на выпуклые с целью минимизации количества выпуклых частей / М. А. Верхотуров, Р. Р. Ягудин // V Всероссийская зимняя школа-семинар аспирантов и молодых ученых. Т. 1. Уфа: УГАТУ, 2010. С. 126-132.

8. Решение задачи плотной упаковки выпуклых многогранников с использованием годографа вектор-функции плотного размещения / Г. Н. Верхотурова, Р. Р. Ягудин // Принятие решений в условиях неопределенности: межвуз. науч. сб. Уфа: УГАТУ, 2011. Вып. 8. С. 68-73.

9. Алгоритм построения ГФПР двух произвольных многогранников / Г. Н. Верхотурова, Р. Р. Ягудин // Принятие решений в условиях неопределенности: межвуз. науч. сб. Уфа: УГАТУ, 2011. Вып. 8. С. 62-67.

10. Оптимизационное геометрическое моделирование в системах размещения трехмерных объектов / М. А. Верхотуров, Г. Н. Верхотурова, Р. Р. Ягудин // Компьютерные вычисления и информационные технологии (CSIT'2012): 14-я междунар. конф. Уфа: УГАТУ, 2012. С. 144-152. (Опубл. на англ. яз.)

11. Свид. об офиц. регистр, программы для ЭВМ № 2012614822. 3DNCPacker / Р. Р. Ягудин. Зарег. 13.06.2012. М. : Федеральная службы по интеллектуальной собственности,2012.

С. 58-63.

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

Диссертант

ЯГУДИН Рустем Расламович

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

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

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

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

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