|
ИСТИНА |
Войти в систему Регистрация |
ИПМех РАН |
||
Исследование алгоритмов решения задачи нерегулярного размещения плоских геометрических фигурстатья
- Авторы: Порывай М.В., Чупахин А.А.
- Сборник: Программные системы и инструменты: тематический сборник № 22
- Редактор: Писковский Виктор Олегович
- Том: 22
- Год издания: 2022
- Издательство: ООО "МАКС Пресс"
- Местоположение издательства: Москва
- Первая страница: 113
- Последняя страница: 128
- Номер статьи: 8
- Аннотация: Во многих областях промышленности, таких, как, например, сталелитейная, кожевенная, текстильная, часто возникает задача вырезания из больших фрагментов материала заданных фигур произвольной формы. При этом группировать места размещения контуров фигур для раскроя фрагмента материала требуется максимально плотно, чтобы минимизировать остаток. Так, экономия 1% материала с каждого исходного фрагмента может предотвратить потерю предприятием в сумме нескольких миллионов долларов США. Задачи такого типа называются в литературе задачами раскроя, или задачами упаковки. Они могут варьироваться по параметрам входных данных, таких, как, например, форма и размеры фрагментов материала и размещаемых фигур, ограничения на полезный остаток. В данной работе рассматривается двумерная нерегулярная задача раскроя. Нерегулярность означает, что фигуры могут быть не только прямоугольниками, но и иметь достаточно сложную форму. Двумерная задача — это означает, что фигуры заданы на двумерной плоскости. Задача раскроя является NP-трудной, и на практике нахождение ее точного решения требует много как временных, так и вычислительных ресурсов. Поэтому при ее решении часто применяются приближенные (эвристические) алгоритмы, которые позволяют за приемлемое время получать пусть не оптимальный, но хороший результат. Известно большое количество классических эвристических алгоритмов. Среди них можно выделить, например, класс природных алгоритмов, основанных на естественных природных процессах. Также на основе процесса отжига металлов в конце прошлого века был разработан алгоритм имитации отжига. Эти алгоритмы хорошо зарекомендовали себя при решении таких NP-трудных задач, как построение расписания выполнения работ без прерываний, построение оптимального маршрута, распознавание структуры белков, финансовое прогнозирование. В данной работе задача раскроя решается с помощью алгоритма имитации отжига и жадного алгоритма. Результатом проведенного исследования является создание программной библиотеки, содержащей реализации данных алгоритмов, решающих задачу раскроя в заданной постановке, оформленных в едином стиле, с единой иерархией классов.
- Добавил в систему: Чупахин Андрей Андреевич