ВВЕДЕНИЕ 3
1. Обзор актуальных методов 5
1.1 Обзор неточных методов 5
1.2 Обзор точных методов 9
1.3 Особенности точного метода 11
2. Аппарат функций гильотинного размещения 13
2.1 Основы гильотинного размещения 13
2.2 Расширение функции гильотинного размещения 15
3. Построение таблиц РФГР 18
3.1. Суммирование РФГР 19
3.2. Минимизация РФГР 21
3.3. Алгоритм вычисления РФГР 23
4. Применение РФГР в методе ветвей и границ 25
5. Практические результаты 29
ЗАКЛЮЧЕНИЕ 34
СПИСОК ЛИТЕРАТУРЫ 36
ПРИЛОЖЕНИЕ
Задача двумерной упаковки - это широко известная оптимизационная задача размещения набора деталей на листе или полуполосе. Задача формулируется следующим образом: дан лист с размерностями Ах В, где А - длина листа, В - его ширина (при этом А > В). Требуется определить, возможно ли разместить на данном листе набор из n прямоугольных деталей размерностей аь х bt i = l,...,n (at < bt), а если это возможно, то определить положение деталей на листе. В ситуации полуполосы длина листа не ограничена. В случае компактного размещения деталей требуется также минимизировать длину листа, используемого для размещения. Также к задаче могут быть применены дополнительные требования гильотинного размещения (итоговая укладка должна быть воспроизводима серией разрезов, проводящихся от края до края параллельно одной из сторон листа). Некоторые методы могут дополнительно накладывать условия на возможность поворота деталей под прямым углом. В данной работе будет рассматриваться общий случай задачи размещения деталей на полуполосе без требований к гильотинности разрезов и строгой ориентации деталей.
Задача двумерной упаковки относится к классу NP-полных задач, а методы, решающие данную проблему, делятся на два класса: точные и эвристические. Эвристические включают в себя всевозможные реализации метаэвристик в виде различных генетических алгоритмов, роевых методов, и других метаэвристик высокого уровня. Класс точных методов состоит из полного перебора, усеченного перебора - метод ветвей и границ, - и методов динамического программирования.
Стоит отметить, что несмотря на то, что задача двумерной упаковки на листе или полуполосе была сформулирована достаточно давно, она до сих пор не теряет своей актуальности, так как она находит широкое применение в сфере промышленности, как в раскрое материалов различного рода, так и в задачах планирования использования ресурсов. Следовательно, повышение эффективности методов решения задач негильотинного раскроя, в свою очередь, позволит сделать его более доступным и применимым для большего числа случаев обеспечивая достаточно высокий уровень точности, а что позволит экономить имеющиеся ресурсы.
Цель работы состояла в попытке улучшить вычислительную эффективность точного негильотинного метода ветвей и границ [1], используя данные об оптимальном гильотинном раскрое через таблицы расширений функций гильотинного размещения (РФГР) [2] и отказавшись при этом от требования получения точного решения задачи. Для достижения данной цели были поставлены следующие задачи:
1) Исследование и анализ рассматриваемых алгоритмов и методов для определения их возможностей, свойств и особенностей, а затем реализация.
2) Разработка и реализация алгоритма, извлекающего необходимые данные из таблиц РФГР, в явном и удобном для использования методом ветвей и границ виде, без нарушения изначального гильотинного рекорда.
3) Сравнение, тестирование и анализ полученных результатов синергии методов через разработанный алгоритм.
4) Подведение итогов исследования, заключение о целесообразности применения данных РФГР в негильотинных раскладках.
В качестве информации, извлекаемой из РФГР, в итоге было использовано деление начального набора на поднаборы необходимой размерности на основании данных о разрезах функций РФГР. Необходимо также отметить, что из-за данных изменений метод ветвей и границ становится эвристическим. Более подробно методика разделения на блоки, их использование, а также теоретическая основа самих методов негильотинного раскроя и РФГР будет изучена в следующих разделах. Но в начале будут рассмотрены методы, применяемые в сфере на данный момент, а затем чуть более подробно методы, на которых основана данная работа.
По итогам работы был реализован подход к использованию данных об оптимальном гильотинном раскрое через таблицы РФГР, разработан и реализован алгоритм деления наборов деталей на подблоки, который позволяет значительно снизить нагрузку на точный алгоритм негильотинного размещения с использованием метода ветвей и границ. Также был реализован сам метод ветвей и границ для данной задачи. Данные подходы позволили методу ветвей и границ иметь возможность работать с гораздо большим числом деталей в диапазоне от 20 до 30, хоть и в ограниченном виде. Время, затрачиваемое на оптимизации подблоков по отдельности и в целом, не превышало времени работы РФГР более чем в 2 раза, благодаря параллельной оптимизации подблоков. В условиях NP-полноты рассматриваемых методов, данный результат можно считать приемлемым и достаточно быстрым.
В отношении улучшения рекордов были получены смешанные результаты. Начальная формулировка алгоритма не выявила набор с возможным улучшением рекордов относительно рекорда РФГР. Большей частью это в итоге связано с кардинально отличающимися раскладками между методами, что приводит к тому, что детали, которые оказываются критичными в оптимизации негильотинным методом, располагаются в различных блоках, а также связано с тем, что некоторые блоки состоят из излишне больших деталей, затрудняя возможности глобальной оптимизации. Однако последующие дополнительные оптимизации, решающие последнюю из вышеупомянутых проблем, позволили найти случаи с улучшением рекорда, который в итоге сравнялся с рекордом точного негильотинного метода, затрачивая при этом значительно меньшее время по сравнению с использованием метода ветвей и границ без блоков (точный метод может не завершить свою работу в течение нескольких месяцев).
В целом, можно подвести итог, что использование данных РФГР для повышения эффективности метода ветвей и границ можно считать вполне целесообразным, так как первоначальная задача ускорения была достигнута, с некоторой вероятностью улучшения рекорда при его принадлежности определенному подклассу, так как набор должен соответствовать множеству условий и ограничений для получения негильотинного рекорда. Увеличение времени работы относительного простого РФГР в связи с синергией двух алгоритмов можно считать незначительным в контексте NP-полноты рассматриваемой задачи.
Помощь студентам и аспирантам в выполнении работ от наших партнеров
