Тема: РАЗРАБОТКА АЛГОРИТМА МЕТОДА ВЕТВЕЙ И ГРАНИЦ ДЛЯ ПОСТРОЕНИЯ НЕГИЛЬОТИННОГО РАЗМЕЩЕНИЯ НАБОРА ПРЯМОУГОЛЬНИКОВ НА ЛИСТЕ

Задача размещения прямоугольников на прямоугольном листе или бесконечной полуполосе, также известная как задача двумерного раскроя и задача двумерной упаковки прямоугольников, известна с первой половины двадцатого века, но и сейчас не теряет актуальности, фигурируя в множестве публикаций и за последние десять лет. Задача описывается в разных формах, но в основе лежат следующие положения: набор прямоугольных деталей требуется разместить на прямоугольнике фиксированной ширины и произвольной длины. Производится поиск допустимого размещения прямоугольников с минимизацией необходимой длины полосы. К задаче существуют разные дополнительные ограничения, такие как условие гильотинного размещения , когда размещение может производится только путём разделения полосы на участки разрезом, перпендикулярным одной из сторон, разрешение, ограничение или запрет на поворот деталей, условие безотходной упаковки.
Первые научные публикации, связавшие линейное программирование и задачу раскроя, появилась в середине двадцатого века [1]; вместе с тем, автоматические системы стали применяться в различных индустриях, порождающих разные ограничения — так, резка стекла привела к появлению ограничения на гильотинные разрезы. Комбинаторная природа задач приводит к увеличению времени на вычисление размещения; необходимость выработки решения в реальном времени привела к появлению online-алгоритмов, как, например, алгоритм Копперсмита и Рагхавана [2].
Нахождение точного решения большинства задач этого семейства является NP-трудным, что вызвало разработку эвристических — итеративных [3] и генетических [4] алгоритмов для приближённого решения. Анализ и разбор
популярных алгоритмов приведён в [5]; так, существуют двухфазные алгоритмы, упаковывающие прямоугольники в слои, и оптимизирующие раскладку внутри слоя, однофазные, упаковывающие прямоугольники в набор контейнеров. Есть ряд работ, предлагающих для некоторых частных случаев задачи размещения точных решений, по большей части использующих методы класса ветвей и границ. Среди них алгоритмы для безотходной упаковки, такие как предложенные Лешем [6] и Мартелло [7].
Целью данной работы является изучение имеющихся методов решения задачи, разработка алгоритма семейства методов ветвей и границ, имплементация и сравнение его с имеющимися алгоритмами для решения задачи размещения прямоугольников на листе.
Постановка задачи
В рамках данной выпускной квалификационной работы ставятся следующие задачи:
1. Изучение моделей и методов решения задачи размещения набора прямоугольников на листе;
2. Разработка алгоритма метода ветвей и границ для построения негильотинного размещения набора прямоугольников на листе;
3. Разработка программного обеспечения для реализации разработанного алгоритма;
4. Разработка генератора для задач негильотинного размещения набора прямоугольников на листе;
5. Разработка программы для визуального представления полученного размещения;
6. Проведение вычислительного эксперимента и анализ его результатов.
Алгоритм должен основываться на модели представления негильотинного размещения как решения системы неравенств с частично булевыми переменными. Применение метода ветвей и границ должно обеспечить фиксацию булевых переменных за счет перебора возможных перестановок номеров деталей и сведение вспомогательной задачи узла к поиску любого решения системы неравенств с вещественными переменными.
Купить

В рамках данной работы были исследованы алгоритмы размещения прямоугольников на листе, предложены и реализованы алгоритмы метода ветвей и границ, основанные на введённом отношении следования для перестановок прямоугольников из заданного набора.
Испытания предложенных алгоритмов показали, что использование метода ветвей и границ улучшает результаты метода послойной раскладки с относительно небольшим увеличением трудоёмкости. Однако, такой алгоритм остаётся эвристическим и не даёт точного решения. Значительного улучшения решения можно добиться, если установить отношение следования на наборе прямоугольников и произвести раскладку на всех или на части перестановок исходного набора, что сильно увеличивает трудоёмкость задачи, использование же только одной перестановки позволяет уменьшить число рассматриваемых ветвей и снизить трудоёмкость алгоритма. Таким образом, можно сделать вывод о применимости разработанного алгоритма — модификации послойной раскладки к методу ветвей и границ с отношением следования на наборе прямоугольников — для приближённого решения задачи размещения прямоугольников на листе.

Купить