Модели и алгоритмы расчета параллелепипедной упаковки с использованием метода динамического перебора тема диссертации и автореферата по ВАК РФ 05.13.16, кандидат технических наук Тоцков, Игорь Евгеньевич

• Тоцков, Игорь Евгеньевич
• кандидат технических наук
• 1999

Оглавление диссертации кандидат технических наук Тоцков, Игорь Евгеньевич

ВВЕДЕНИЕ.

ГЛАВА 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

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

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

Заключение

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