Введение к работе
Актуальность темы. Определяющими факторами успеха в
промышленном производстве сегодня и в обочримом будущем являются уменьшение времени выхода продукции на рыно'с, снижение стоимости и повышение качества. Темпы морального старения промышленных изделий сегодня таковы, что поставленные в конце концов, на конвейер новые образцы часто уже не соответствуют современным требованиям. Только значительное сокращение цикла проектирования и подготовки производства, подразумевающее внедрение систем автоматизации проектирования (САПР) и автоматизированных систем технологической подготовки производства (АСТГШ), может способствовать созданию конкурентоспособной продукции и своевременному выходу ее на рынок.
Среди множества задач,, возникающих в проектировании, особое место занима.'ог задачи, связанные с компоновкой и размещением в заданных ииЛ.-к'гях трехмерных геометрических ооъоктов. iv таким задачам откосятся, например, оптимизация складирования грузов, планирование помещений, проектирование систем, конструктивно выполненных в виде набора блоков, компоновка двигателей. От качества решения эти* задач зависит стоимость строительства, эффективность использования площадей, транспорта, складских помещений, технологичность, сокращение сроков и стоимости проектирования.
Важной составной частью технологической подготовки производства являете я объемный раскрой материалов, который решает задачи раскроя кристаллов при произчодсіве ювелирных изделие, производстве подложек БИС, специальной оптики, пенополиуретана в авиапромышленности. Проектирование планов (карт) раскроя пз сути является задачей оптимизационного геометрического проектировшпш, заключающейся в оптимизации размещения геометрических объектов в заданных областях. От
2 того насколько рационально эта задача решается зависит эффективность использования материала при раскрое.
Несмотря на конкретное практическое наполнение круг работ по размещению трехмерных геометрических объектов ограничен. Это объясняется сложностью задач и трудоемкостью их решения. Поэтому разработка эффективных алгоритмов решения задач объемного раскроя -упаковки остается актуальной.
В диссертационной работе предлагается новый подход к решению задачи рационального размещения трехмерных геометрических объектов, базирующийся на использовании дискретно - логического представления информации и понятии "псевдо-оценок".
Целью диссертационной работы является разработка методов и алгоритмов моделирования процесса плотного размещения произвольных многогранников в заданных областях размещения, позволяющих найти решение, близкое к оптимальному, разработка на этой базе программного обеспечения.
Задачи исследования. Для достижения поставленной цели в работе сформулированы и решены следующие задачи:
разработана структура решения задачи размещения трехмерных геометрических объектов методом «первый подходящий» с упорядочиванием по «псевдо-оценкам»;
предложен новый подход к решению задачи размещения трехмерных геометрических объектов, базирующийся на использовании дискретно-логического представления информации;
разработан и исследован механизм моделирования плотного движения объектов в области размещения;
разработаны алгоритмы аппроксимации трехмерных геометрических объектов для представления их в виде, удобном для реализации
условий взаимного непересечения (УВН) на базе дискретно-логического представления информации:; разработано программное обеспечение, реализующее разработанные
методы и алгоритмы. Методы исследования, Результаты исследований, выполненных в работе, базируются на основных положениях аналитической и вычислительной геометрии, геометрического моделирования, машинной графики. Научная новизна работы заключается в следующем:
разработан метод решения задачи размещения трехмерных геометрических объектов сведением трехмерной задачи упаковки к двухмерной путем представления объектов и областей размещения множеством связанных параллельных сечений, описанных цепными кодами;
- разработаны способы аппроксимации трехмерных объектов цепным!!
кодами;
раіраиоїан и исследован падежный и oCf/фсктивньлї алгоритм моделирования процесса плотною движения объектов в области размещения на основе их дискретно - логического представления;
разработан и теоретически обоснован оптимизационный алгоритм трехмерной упаковки с использованием метода "первый подходящий" с упорядочиванием по "псевдо-оценкам";
выведены формулы подсчета "псевдо - оценок" с учетом специфики решения задачи размещения трехмерных геометрических объектов.
Практическая ценность. Разработанные в диссертации методы и алгоритмы применимы для решения большого круга прикладных задач. Разработанное программное обеспечение может использоваться для решения задачи объемного раскроя, нерегулярной упаковки 3D - объектов.
На защиту выносятся: 1. Методы и алгоритмы аппроксимации трехмерных геометрических объектов и областей размещения цепными кодами,
-
Алгоритм моделирования процесса плотного движения трехмерных объектов на основе их дискретно - логического представления.
-
Оптимизационный алгоритм, использующий понятие "псевдо - оценок".
-
Программное обеспечение, реализующее разработанные алгоритмы размещения многогранников.
Апробация работы. Основные результаты диссертационной работы докладывались и обсуждались на международных конференциях "Математическое программирование и приложения" (1995, 1997 гг., г.Екатеринбург), "Проблемы оптимизации и экономические приложения" (1997г., г. Омск), на "Втором Сибирском Конгрессе по Прикладной и Индустриальной математике" (1996 г., г. Новосибирск), на Всероссийской научно-технической конференции (1996 г., г. Улан-Удэ), на семинарах кафедры вычислительной математики и кибернетики Уфимского государственного авиационного технического университета.
Публикации. По теме диссертации опубликовано 9 работ.
Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы из 93 названий и приложения. Основная часть работы содержит 122 страницы машинописного текста, 30 рисунков.
