Введение к работе
Актуальность темы. В научной и производственной деятельности задачи раскроя и упаковки встречаются очень часто: это и задачи раскроя материала на заготовки определенных форм и размеров, и задачи размещения совокупности предметов на ограниченной площади или в ограниченном пространстве. Среди многообразия постановок задач раскроя и упаковки самостоятельный интерес представляют задачи упаковки параллелепипедов. Это объясняется высокой долей заготовок такого вида в общей массе выкраиваемых и упаковываемых деталей, применением параллелепипедной упаковки и раскроя при получении фигурных детатей. К таким задачам относятся, например, оптимизация складирования грузов, планирование помещений, проектирование систем, конструктивно выполненных в виде набора блоков, компоновка деталей. К рассматриваемым проблемам сводится также и ряд задач планирования и распределения ресурсов.
Несмотря на конкретное практическое применение, круг работ по решению задач параллелепипедной упаковки невелик. Это объясняется сложностью задач и высокой трудоемкостью их решения. Поэтому разработка эффективных алгоритмов решения задач раскроя - упаковки параллелепипедов является актуальной: В данной работе предлагаются эффективные алгоритмы различной сложности для решения задач упаковки параллелепипедов.
Целью диссертационной работы является разработка и исследование методов и алгоритмов раскроя-упаковки трехмерных объектов (параллелепипедов), позволяющих найти рациональное решение, разработка на этой базе программного обеспечения.
Задачи исследования. Для достижения поставленной цели в работе сформулированы и решены следующие задачи:
разработана математическая модель задачи упаковки параллелепипедов;
разработаны и исследованы методы решения задачи параллелепипедной упаковки, основанные на ее декомпозиции;
найдено эффективное применение метода динамического перебора для решения задачи прямоугольной упаковки листов, возникающей при декомпозиции задачи упаковки параллелепипедов;
разработано программное обеспечение, реализующее предложенные методы и алгоритмы;
проведен вычислительный эксперимент, позволяющий сравнить и проанализировать эффективность разработанных методов.
Методы исследования. Результаты исследований, выполненных в работе, базируются на методах исследования операций, математического программирования, комбинаторной оптимизации, принципах модульного и структурного программирования, машинной графики. Для анализа эффективности алгоритмов применялся вычислительный эксперимент.
Научная новизна работы заключается в следующем:
на основе процедур динамического перебора разработан метод решения задачи упаковки параллелепипедов;
разработаны методы и алгоритмы, направленные на повышение эффективности решения задач параллелепипедной упаковки;
предложен метод вычисления нижней границы функции цели для задачи упаковки параллелепипедов, дающей возможность оценивать и сравнивать результаты работы различных алгоритмов трехмерной упаковки.
Практическая ценность. Разработанные в диссертации методы и алгоритмы служат оптимизационным ядром трехмерной упаковки в программном комплексе упаковки грузов, а также применимы для решения больиіого круга других прикладных задач. Разработанное программное обеспечение содержит развитый интерфейс и может использоваться как автономно, так и в составе комплексов программ раскроя-упаковки. Предложенные методы применимы также для решения более сложных задач фигурного и объемного раскроя-упаковки.
Работа проводилась в рамках госбюджетной темы «Несобственные задачи оптимального использования ресурса» (шифр ИФ-ВК-43-99-03) согласно плану Уфимского государственного авиационного технического университета. На заключительном этапе работа выполнялась при поддержке РФФИ, проект 99-01-000937.
На защиту выносятся:
-
Математические модели задачи упаковки параллелепипедов.
-
Применение метода динамического перебора для решения задачи параллелепипедной упаковки.
-
Методы и алгоритмы для повышения эффективности решения задачи упаковки параллелепипедов.
-
Метод вычисления нижней границы функции цели для задачи параллелепипедной упаковки.
-
Программное обеспечение, реализующее разработанные алгоритмы размещения параллелепипедов.
-
Анализ численного эксперимента с рекомендациями по применению алгоритмов.
Апробация работы. Основные результаты диссертационной работы докладывались и обсуждались:
на международной молодежной научно-технической конференции "Интеллектуальные системы управления и обработки информации" (1999г., г. Уфа);
на Всероссийской молодежной научно-технической конференции "Информационные и кибернетические системы управления и их элементы" (1997г., г. Уфа);
на научной конференции "Математическое программирование и приложения" (1997г., г. Екатеринбург);
на Республиканской научно-технической конференции "Интеллектуальное управление в сложных системах - 99" (1999г., г. Уфа).
Публикации. По теме диссертации опубликовано 9 работ.
Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы (48 наименований) и приложений. Основная часть работы содержит 98 страницы машинописного текста, 28 рисунков и 12 таблиц.
