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

V Го ОД

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

Тоцков Игорь Евгеньевич

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

Специальность 05.13.16 - Применение вычислительной техники, математического моделирования и математических методов в научных исследованиях

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

УФА 1999

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

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

профессор Мухачева Э.А. Научный консультант: кандидат технических наук,

доцент Валеева А.Ф. Официальные оппоненты: доктор физико-математических наук,

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

Ведущая организация: ОКБ «Гидромеханика»

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

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

Автореферат разослан «30 » дгкйбря 1999г.

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

доцент

Бакусов Л.М.

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

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

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

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

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

• разработана математическая модель задачи упаковки параллелепипедов;

• разработаны и исследованы методы решения задачи параллелепипедной упаковки, основанные на ее декомпозиции;

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

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

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

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

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

• на основе процедур динамического перебора разработан метод решения задачи упаковки параллелепипедов;

• разработаны методы и алгоритмы, направленные на повышение эффективности решения задач параллелепипедной упаковки;

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

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

Работа проводилась в рамках госбюджетной темы «Несобственные задачи оптимального использования ресурса» (шифр ИФ-ВК-43-99-03) согласно плану Уфимского государственного авиационного технического университета. На заключительном этапе работа выполнялась при поддержке РФФИ, проект 99-01-000937.

На защиту выносятся:

1. Математические модели задачи упаковки параллелепипедов.

2. Применение метода динамического перебора для решения задачи параллелепипедной упаковки.

3. Методы и алгоритмы для повышения эффективности решения задачи упаковки параллелепипедов.

4. Метод вычисления нижней границы функции цели для задачи параллелепипедной упаковки.

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

6. Анализ численного эксперимента с рекомендациями по применению алгоритмов.

Апробация работы. Основные результаты диссертационной работы докладывались и обсуждались:

• на международной молодежной научно-технической конференции "Интеллектуальные системы управления и обработки информации" (1999г., г. Уфа);

• на Всероссийской молодежной научно-технической конференции "Информационные и кибернетические системы управления и их элементы" (1997г., г. Уфа);

• на научной конференции "Математическое программирование и приложения" (1997г., г. Екатеринбург);

• на Республиканской научно-технической конференции "Интеллектуальное управление в сложных системах - 99" (1999г., г. Уфа).

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

Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы (48 наименований) и приложений. Основная часть работы содержит 98 страницы машинописного текста, 28 рисунков и 12 таблиц.

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

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

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

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

- задача раскроя запаса материала;

- задача загрузки рюкзака;

- задача упаковки ящиков (контейнеров);

- задача загрузки транспорта;

- задача выбора ассортимента;

- задача планировки помещений;

- задача обеспечения ритмичности производственного процесса;

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

- задача составления расписания многопроцессорных систем.

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

Впервые задачи раскроя геометрических объектов были рассмотрены великим русским математиком П.Л.Чебышевым. В начале 50-х годов Л.В.Канторовичем и В.А.Залгаллером была разработана теория оптимального раскроя, базирующаяся на методах линейного программирования. Гэри и Джонсон в своих работах установили N ['-трудность указанного класса задач. Последний факт породил целое направление исследований, нацеленных на построение приближенных и эвристических алгоритмов полиномиальной трудоемкости. Рациональное сочетание математических методов и эвристических приемов - путь успешного решения задач такого рода. Дальнейшее развитие и изучение различных аспектов задача рационального раскроя-упаковки получила в работах коллективов под руководством Э.А.Мухачевой, Ю.Г.Стояна, Л.Б.Беляковой по линейному, прямоугольному, фигурному и объемному раскроям. Разработка эффективных алгоритмов по-прежнему остается актуальной. Наименее исследованными из представленных классов задач являются задачи объемного, в частности, параллелепипедного раскроя-упаковки, решению которых и посвящена представляемая работа.

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

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

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

• метод должен быть достаточно общим и эффективно решать задачи различных классов и размерности;

• желательным условием является возможность получения нескольких вариантов решения поставленной задачи с одним и тем же значением целевой функции.

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

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

Имеется возможность увеличения плотности упаковки, в частности, за счет внесения в алгоритм элемента случайности.

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

В третьей главе формализуется и описывается следующая задача упаковки параллелепипедов и ее математическая модель.

Имеется контейнер (параллелепипед) заданной длины I, ширины IV и неограниченной высоты//, а также набор т предметов (параллелепипедов) 7', с

заданными параметрами /,, 1г„ Ъ„ где /,-длина; и-, - ширина; Л, - высота /-го параллелепипеда, 1=1..т.

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

Для описания предметов используются их линейные размеры - /„ 1г„ Л/, ¡=1...т. Для их взаимного положения - система координат, началом которой является левый ближний угол основания контейнера, а оси направлены вдоль его сторон таким образом, что длина предметов будет откладываться вдоль оси X, ширина - вдоль оси У, высота - вдоль оси X(рис. 1).

Рис. 1

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

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

Далее, для более плотного заполнения слоя предлагается использовать разбиение слоя на параллелепипедные блоки Вк длины Ь , ширины IV и высоты НЬк, к — 1..п, где п - количество блоков в данном слое. При этом начало первого блока 5/, как и в алгоритме Шайтхауэра, совпадает с дном контейнера, а конец - с концом самого короткого параллелепипеда, входящего в блок. Каждый следующий блок начинается, как только заканчивается предыдущий, и заканчивается вместе с окончанием одного из принадлежащих этому блоку параллелепипедов.

Тогда эвристический алгоритм упаковки л-го слоя высоты будет выглядеть следующим образом

I. Упаковка 1-го блока.

Прямоугольник Ь * упаковывается, как и в задаче двумерной упаковки, прямоугольниками, представляющими собой нижние грани параллелепипедов 7)еР„, до тех лор, пока не останется пространства для упаковки очередного параллелепипеда. Высота слоя устанавливается равной высоте самого высокого параллелепипеда, входящего в упаковку, = тах(ЬХ Г,

1-й блок закрывается. Его высота равна высоте самого низкого параллелепипеда блока, НЬ^ттЦг), Т^В,. Если все параллелепипеды упакованы (т.е. Р„ пусто), то упаковка слоя на этом заканчивается, в противном случае переходим к шагу 11.

II. Упаковка к-го блока.

Открывается следующий блок Вк. Его заполнение сводится к двумерной упаковке прямоугольников, представляющих собой нижние грани параллелепипедов Т^Р„, которые еще не упакованы, в прямоуголышк(и), представляющий(е) собой верхнюю грань самого низкого параллелепипеда предыдущего блока ThmmeBk.,, с размерами Ьк=\Шш Wk=whmn.

При этом выбор' параллелепипедов Г, для упаковки осуществляется из следующих условий:

1) h, + Hbi+...+Hbk < = Hss;

2) 1, <= /.,, w, <= Wk.

Для определения прямоугольника, который будет использоваться как основание упаковки для к-то блока, применяется массив А верхних граней упаковки, каждый из элементов которого А, содержит координаты х, у (смещение грани (прямоугольника) от левого нижнего угла основания контейнера), размеры прямоугольника /, w и координату г (высота грани, отсчитываемая от нижней границы слоя, г = //А, + ... + НЬк.{). В начальный момент массив А пуст. После упаковки первого блока массив А заполняется верхними гранями всех параллелепипедов, входящих в блок. При упаковке каждого следующего блока происходит добавление в массив А верхних граней всех предметов блока и исключение из него верхних граней, высота которых соответствует высоте основания блока.

Блок В к закрывается. Высота Вк вычисляется по формуле

Hbk = min ( hr(Hb,4-...+Hbk-i)), Т|еВк.

III. Формирование слоя.

Если не все параллелепипеды упакованы (Р„ не пусто), то шаг II повторяется для нового блока Де/.

Процесс упаковки слоя S, заканчивается, когда все параллелепипеды упакованы, либо когда ни один параллелепипед уже не может быть упакован (в рамках слоя).

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

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

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

Для устранения данного недостатка предлагается модификация метода, в которой вместо объединения доступных областей при поиске основания блока используется отсечение занятых участков. При этом первоначально в качестве основания блока выбирается прямоугольник Ь*И\ равный основанию контейнера, но на высоте, равной сумме высот уже упакованных блоков. Затем находятся наибольшие по площади прямоугольники, получаемые при пересечении основания блока с предметом из упаковки, имеющим верхнюю грань С наибольшей высоты. Максимальное количество этих прямоугольников - 4: а! отсекается прямой АцА^; а2- Ал А2г\ аз- А31А32; а4- А41А42 (рис. 2).

В

АЕ1 А41

АН А31

а: >

а1 С аЗ

а 4

А££

А1:

А32

Рис. 2

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

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

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

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

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

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

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

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

т

= использование оценок на основе методов

ы

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

Мысленно разрежем все предметы Т„ \ - 1..т, на параллелепипеды единичной длины и ширины и высоты И,. Будем называть их заготовками длины /г,. Каждый предмет Г, будет состоять из /,*н-, таких заготовок. Всю упаковку также мысленно разрежем на стержней единичной длины и ширины и высоты//.

Тогда исходную задачу упаковки можно представить в виде следующей одномерной задачи (см. рис.3).

Рис. 3

Имеются заготовки ш видов. Количество заготовок каждого вида к, = /,*п'„ длина - И„ ¡=1.т. Также имеем К--Ь*1¥ стержней одинаковой длины Н.

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

1)в одном стержне не может содержаться более одной заготовки одного вида;

2) если заготовка вида / в одном стержне упаковывается с определенным смещением ¿„ то и во всех остальных стержнях она должна располагаться с этим же смещением с!,.

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

алгоритма одномерной упаковки. Набор условий, которым должна

удовлетворять упаковка стержней, сокращается до двух - 1-го и 2-го - или до одного - только 1-го.

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

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

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

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

- блочной структуры параллелепипедной упаковки;

- метода динамического перебора для решения задачи параллелепипедной упаковки;

- метода отсечения для поиска основания блока.

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

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

1. Разработаны математические модели задачи упаковки параллелепипедов.

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

3. Получено эффективное применение метода динамического перебора для решения задачи упаковки параллелепипедов.

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

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

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

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

ПО ТЕМЕ ДИССЕРТАЦИИ ОПУБЛИКОВАНЫ СЛЕДУЮЩИЕ РАБОТЫ

1. Вапеева А.Ф., Тоцков И.Е. Решение задачи трехмерной упаковки // В кн. Комплексный анализ, дифференци&чьные уравнения, численные методы и приложения. Геометрические задачи - Уфа: ИМВЦ УИЦ РАН, 1996.- С.30-36.

2. Свид-во о гос.рег. программы на ЭВМ № 960295. Трехмерная упаковка предметов / Тоцков И.Е., Мухаметзянов Р.З. / -М.; РосАПО, 08.07.96.

3. Тоцков И.Е. Методы трехмерной упаковки параллелепипедов //Тезисы докладов Всероссийской молодежной научно-технической конференции "Информационные и кибернетические системы управления и их элементы". -Уфа: УГАТУ, 1997.-С.45.

4. Валеева А.Ф., Тоцков И.Е., Хакимов А.Т. Анализ эффективности методов трехмерной упаковки // Тезисы докладов научной конференции "Математическое программирование и приложения". - Екатеринбург: Институт математики и механики УрО РАН, 1997. - С.54.

5.A.F. Valeyeva and LE. Totskov. Developed of Three-Dimensional Methods Décision Making under Conditions of Uncertainty (Cutting-Packing Problems). Ufa, 1998.- P.198-206.

6. Тоцков И.Е., Валеева А.Ф. Метод отсечения для решения задачи трехмерной упаковки // Межвузовский научный сборник "Принятие решений в условиях неопределенности". - Уфа, 1999. - С.112-118.

7. Тоцков И.Е. Методы решения задачи трехмерной упаковки на базе алгоритма динамического перебора. Рукопись депонирована в ВИНИТИ, № 2589-В99, 1999г.

8. Тоцков И.Е. Вероятностный подход для решения задачи трехмерной упаковки // Тезисы докладов международной молодежной научно-технической конференции "Интеллектуальные системы управления и обработки информации". - Уфа: УГАТУ, 1999. - С.88.

9. Валеева А.Ф., Тоцков И.Е., Гареев И.Р. Методы решения трехмерной задачи в интеллектуальной системе раскроя-упаковки // Материалы Республиканской научно-технической конференции "Интеллектуальное управление в сложных системах - 99". - Уфа, 1999. - С.36-38.

г,S

ВВЕДЕНИЕ.

ГЛАВА 1. ЗАДАЧИ РАСКРОЯ-УПАКОВКИ.

1.1. Многообразие задач раскроя-упаковки.

1.2. Методы решения задачи одномерного раскроя - упаковки.

1.3. Методы решения задачи негильотинного прямоугольного раскроя.

1.4. Методы решения задачи параллелепипедной упаковки.

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

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

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

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

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

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

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

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

Работа проводилась в рамках госбюджетной темы «Несобственные задачи оптимального использования ресурса» (шифр ИФ-ВК-43-99-03) согласно плану Уфимского государственного авиационного технического университета. На заключительном этапе работа выполнялась при поддержке РФФИ, проект 99-01-000937.

На защиту выносятся:

Математические модели задачи упаковки параллелепипедов.

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

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

Метод вычисления нижней границы функции цели для задачи параллелепипедной упаковки.

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

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

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

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

1. Разработаны математические модели задачи упаковки параллелепипедов.

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

3. Получено эффективное применение метода динамического перебора для решения задачи упаковки параллелепипедов.

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

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

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

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

93

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

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

Заключение

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