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

Р Г 5 ОД

- С, ¡43

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

ПЕРХОТУРОВЛ Галина Нпколаспла

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

В СИСТЕМАХ АВТОМАТИЗИРОВАННОГО ПРОЕКТИРОВАНИЯ РАСКРОЯ-УПАКОВКИ

05.13.12 — Системы автоматизации проектирования

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

УФА 1997

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

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

профессор Мухачева Э.А.

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

профессор Кабальнов Ю.С. кандидат технических наук, доцент Ибатуллина С.М.

Ведущая организация: - Уфимский государственный нефтяной

технический университет

Защита состоится «/¿'» января 1998 г. в ¿£_час. на заседании диссертационного совета К-063.17.01. при Уфимском государственном авиационном техническом университете по адресу: 450000, Уфа - центр, ул. К.Маркса, 12.

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

Автореферат разослан "/^Г' декабря 1997 г.

Ученый секретарь

диссертационного совета

Бакусов Л.М.

1_________ __________ _______________

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

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

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

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

того насколько рационально эта задача решается зависит эффективность использования материала при раскрое.

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

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

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

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

• разработана структура решения задачи размещения трехмерных геометрических объектов методом «первый подходящий» с упорядочиванием по «псевдо-оценкам»;

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

• разработан и исследован механизм моделирования плотного движения объектов в области размещения;

• разработаны алгоритмы аппроксимации трехмерных геометрических объектов для представления их в виде, удобном для реализации

условий взаимного непересечения (УВН) на базе дискретно-логического представления информации:;

• разработано программное обеспечение, реализующее разработанные методы и алгоритмы.

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

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

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

- разработаны способы аппроксимации трехмерных объектов цепными колами;

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

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

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

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

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

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

3. Оптимизационный алгоритм, использующий понятие "псевдо - оценок".

4. Программное обеспечение, реализующее разработанные алгоритмы размещения многогранников.

Апробация работы. Основные результаты диссертационной работы докладывались и обсуждались на международных конференциях "Математическое программирование и приложения" (1995, 1997 гг., г.Екатеринбург), "Проблемы оптимизации и экономические приложения" (1997г., г. Омск), на "Втором Сибирском Конгрессе по Прикладной и Индустриальной математике" (1996 г., г. Новосибирск), на Всероссийской научно-технической конференции (1996 г., г. Улан-Удэ), на семинарах кафедры вычислительной математики и кибернетики Уфимского государственного авиационного технического университета.

Публикации. По теме диссертации опубликовано 9 работ.

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

СОДЕРЖАНИЕ ДИССЕРТАЦИИ

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

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

Впервые задачи раскроя геометрических объектов были рассмотрены великим русским математиком П.Л.Чебышевым в его докладе "О кройке одежды" в 1878 г.. В 1885 г. была опубликована работа Е.С.Федорова, в которой рассматривался ряд вопросов, возникавших при изучении кристаллов как природных многогранников, В конце 40-х годов Л.В.Канторовичем и В.Д. Залгаллером была разработана теория оптимального раскроя, базирующаяся на метла* линейного программирования. Далтейшее развтие и изучение различных аспектов задача рационального раскроя-упаковки получила в работах коллективов под руководством Э.А.Мухачевой, Ю.Г.Стояна, Л.Б.Беляковой по линейному, прямоугольному и фигурному раскроям.

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

исследователя А.А.Черноморца.

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

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

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

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

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

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

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

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

Решение этого гнала состит из двух задач;

- нахождение вершин с минимальными и максимальными значениями координат относительно оси 7, соответственно, 7„,.пи 7;1их(Рис 1);

У

Ъ

- нахождение целочисленных значений координат X и У для точек, имеющих Хт1п и гтах (Рис 2).

Рис.2

2. Нахождение сечений многогранников (Рис.3).

У

Рис.з

3. Целочисленная аппроксимация многоугольников, полученных в результате пересечения многогранников множеством параллельных плоскостей (Рис.4).

4. Аппроксимация многоугольников с целочисленными координатами цепными кодами (Рис.5). Цепочка цепных кодов, начиная с точки Т] -12,2,2,1,2,2,2,1.1,1,0,0,0,0,0,3,3,0,3,3}.

5. Нахождение точек перехода от сечения к сечению и определение направлений перехода от сечения к сечению.

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

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

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

- первоначального занесения объекта в область;

- определения направления сдвига объекта;

- сдвига объекта;

Рис. 5

- восстановления объекта.

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

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

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

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

и

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

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

г.:с II - площадь непокрытой области в ^ом сечении,

\''-обьем ¡-го объекта, 2 - площадь ¡-го сечения, I) - расстояние между сечениями, М - число объектов, N - количество сечений ¡-го объекта.

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

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

Рис. 6

Подсчет псевдо-оценок с учетом вышеизложенного производится по следующей формуле:

1=ин (2)

Я, = \ ад - - ¿5((Р,П Л,) \ Л,) Ч^ПЛ)) X (3).

».I ¿(г») +

где Н» - площадь непокрытой области в ]-ом сечении ¡-го параллелепипеда, Б(г^) - площадь сечения ¡-го объекта в ,)-ом сечении, 8(Ру) - площадь сечения ¡-го параллелепипеда в .¡-ом сечении, V. - объем ¡-го объекта, Б - расстояние между сечениями,

М - число объектов и соответственно число параллелепипедов, N - количество сечений ¡-го объекта.

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

У„=У,+У1р (4)

На следующем этапе подсчитываются удельные оценки

1=1, М, (5)

где У0- оценка ¿-го объекта, VI - объем 1 - го объекта.

Согласно убыванию удельных оценок строится приоритетный список в

соответствии с которым объекты разметаются в области. Анализируется нол_\'¡синая упаковка. Снова подсчитываются опенки, строится приоритетный список. Производится размещение объектов согласно новому приоритетном) списку, подсчитываются оценки и так до тех пор пока коэффициент раскроя не досппнет требуемого значения.

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

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

использования.

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

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

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

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

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

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

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

ПО ТЕМИ ЛИС(-1-:ГГЛШ!И()ПУБЛИКО.ЧД1Ы СЛГДУЮШП" РАБОТЫ

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

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

3. Верхотурова Г.Н. О способах моделирования условий взаимного непересечения трехмерных геометрических объектов./'/! 1ринятие решений в условиях неопределенности.-Уфа, 1996.-С.41-49.

4. Мухачева Э.А., Верхотуров М А., Верхстрсва Г.Н. Об использовании оценок в задачах трехмерной упаковки.// Тезисы Второго Сибирского

л , > 1 ^ 1.1ПП .... т, Ыгт г-.-.-«,,.. т - ......-------.---- Г I .. ..---Г.------- I Г\ Г\ Г

тг 1 ^шулч.илОЬ »1 ппД ;1.1рИ(1.1опи11 ;У1 и 1 >..Л[а . и IV*...-1 11 1 ни*- Пип р^к, 1

с.139.

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

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

7. Верхотуров М.А., Верхотурова Г.Н. 05 одном решении задачи трехмерной упаковки сложных геометрических объектов.//Математическое программирование и приложения(тез.докладов).-Екатеринбург, 1997.-с.57-58.

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

9. Верхотуров М.А., Верхотурова Г.Н. Метод псевдо-оценок в задачах трехмерной упаковки. //Проблемы оптимизации и экономические приложения (тезисы докладов).-Омск, 1997.-с.40.