Software & Systems

Среди задач оптимизации раскроя листовых материалов наиболее исследованными являются задачи прямоугольного раскроя. По существующей в настоящее время типологии они относятся к классу задач 2DBPP (Two-Dimensional Bin Packing Problem) [1], для которых неизвестны алгоритмы решения полиномиальной сложности (NP-трудные задачи). Задачу прямоугольного раскроя в общем виде можно сформулировать следующим образом.

Пусть A1, A2, …, An – двухмерные геометрические объекты (точечные множества), ограниченные прямоугольными контурами и заданные своими размерами li (длина) и hi (высота), i=1, …,n. Данные объекты являются геометрическими моделями заготовок, которые необходимо получить из листового материала. Пусть также заданы B1, B2, …, Bm  – области размещения объектов – прямоугольные листы (в общем случае различные) c размерами Wj и Dj, j=1,…,m. Местоположение каждой заготовки Ai  в области размещения определяется тремя параметрами, где xi, yi  – абсцисса и ордината фиксированной точки (полюса) в некоторой системе координат; pi – параметр, задающий признак поворота объекта на плоскости. В качестве полюса объекта обычно задается какая-либо угловая точка прямоугольника. Предполагается также, что среди всех вариантов раскроя рассматриваются только такие, при которых стороны прямоугольников параллельны сторонам прямоугольной области размещения (ортогональная упаковка). В этом случае параметр pi может принимать два значения: 0 – прямоугольник имеет исходную ориентацию, 1 – прямоугольник повернут на 90°. Задачи с анизотропным материалом предполагают фиксированную ориентацию объектов.

Таким образом, необходимо определить 3n параметров размещения заготовок, при которых некая целевая функция F=F(x1, y1, p1, x2, y2, p2, …, xn, yn, pn) достигает своего экстремума и выполняются условия взаимного непересечения объектов, условия размещения объектов внутри одной из областей размещения В1, В2, ..., Вm, а также ряд дополнительных условий, определяемых свойствами раскраиваемого материала и особенностями технологического оборудования, используемого для раскроя. Примером технологических условий может служить требование гильотинности раскроя, которое разрешает только сквозные резы (от одного края прямоугольного листа до другого). Отметим, что алгоритмы гильотинного раскроя пригодны для решения задач негильотинного раскроя (задачи упаковки), но не наоборот. Будем считать, что раскраиваемый материал Вj используется в соответствии с заданной последовательностью. На практике в качестве целевой функции F чаще всего используют функцию, значение которой равно так называемому коэффициенту раскроя  , где P – суммарная площадь занятой части областей размещения (использованного материала). Если для раскроя использован один прямоугольный лист, P=W1´L, где L – длина занятой части листа. Если для раскроя использовано r листов, 1<, где L – длина занятой части последнего листа, использованного для раскроя. Рассматриваемая в литературе постановка задачи, в которой необходимо просто минимизировать число используемых для раскроя прямоугольных листов [1], в условиях единичного производства уравнивает заведомо разные по качеству варианты раскроя, поэтому на практике целесообразно ее применение с описанной выше целевой функцией.

При решении задач прямоугольного раскроя используются в основном приближенные методы, описанные, например, в [2]. Среди них преобладают эвристики и метаэвристики. Алгоритмы, гарантирующие получение глобального и локальных экстремумов (точные методы), из-за NP-труд­ности задачи применимы в основном к задачам небольшой размерности n. Первый конструктивный алгоритм поиска глобального экстремума был описан в [3]. Эффективность методов автоматического проектирования прямоугольного раскроя существенно зависит от условий задачи: ассортимента заготовок, их количественных характеристик, размеров материала и пр., причем характер этой зависимости остается крайне малоисследованным. Это приводит к тому, что при решении практических задач пользователь системы прямоугольного раскроя вынужден экспериментировать с имеющимся у него программным продуктом, содержащим несколько различных вычислительных алгоритмов, с целью выбора наилучшего, что приводит к дополнительным временным затратам и, в конечном итоге, к получению неоптимальных вариантов раскроя. Вместе с тем представляется целесообразным в составе программного обеспечения для расчетов прямоугольного раскроя иметь модуль, определяющий для конкретной задачи наиболее перспективный метод решения на основе предварительного анализа задачи.

Предлагаемый подход можно реализовать следующим образом.

1. Вводим некоторую классификацию задач прямоугольного раскроя листового материала, то есть разбиение множества заданий на группы (классы) по определенным признакам.

2. Проводим тестирование имеющихся в распоряжении разработчика методов раскроя с целью выявления наиболее эффективного для каждого класса заданий.

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

4. Разрабатываем и включаем в состав программного обеспечения прямоугольного раскроя процедуру автоматического выбора метода.

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

Целесообразна реализация схемы автоматического выбора метода с функцией самообучения (то есть с возможностью продолжения тестирования всех методов и изменением алгоритма выбора на основании результатов тестирования) при условии наличия достаточного временного ресурса у пользователя. Сформулируем два основных утверждения, касающихся процедуры самообучения:

·     постоянное изменение схемы автоматического выбора в процессе самообучения свидетельствует о неточной классификации задач раскроя; в этом случае критерии классификации должны быть пересмотрены;

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

Существующие методы прямоугольного раскроя, как правило, содержат несколько числовых параметров, определяющих конкретный вычислительный алгоритм. Например, одна из реализаций эвристического метода эмуляции отжига [2] содержит 14 параметров, влияющих на алгоритм расчета. Это означает, что при проведении тес- тирования разработчик должен определить несколько наборов параметров для каждого метода и рассматривать каждый набор как отдельный метод. Важно также обеспечить равноправность методов по времени использования, предусмотрев при программной реализации каждого метода управляющий параметр, ограничивающий время расчета.

Для реализации сформулированного подхода все тестируемые задания для прямоугольного раскроя были разбиты на четыре класса по двум признакам: серийность производства и преобладание крупных заготовок над мелкими. Поясним эти понятия.

Существующая в настоящее время типология производства по степени его серийности подразумевает три типа производства: единичное, мелкосерийное, крупносерийное (массовое). В качестве формального разделения заданий по признаку серийности используем следующее правило: если число прямоугольников одинакового размера для каждого элемента списка прямоугольников в задании не превосходит шести, то задание будем относить к классу единичных. Остальные задания будем считать серийными. Отметим, что данное разделение заданий сделано для проведения тестирования и не может служить определением понятия серийности производства.

По степени преобладания крупных заготовок все задания раскроя листового материала также разобьем на две группы. Задание считается состоящим из крупных заготовок, если их число составляет не менее 60 % от всех заготовок в задании. Крупной будем называть заготовку, один из габаритов которой составляет более половины ширины листа.

Для тестирования в качестве областей размещения использовались стандартные прямоугольные листы с размерами W=1500 мм, D=4000 мм. Диапазон размеров прямоугольников – от 200 до 1200 мм. Максимальное число одинаковых прямоугольников в серийном задании – 36. Числовые параметры методов фиксированные, время расчета для каждого теста – до 2 сек. Допускался поворот прямоугольников на 90°. Требование гильотинного раскроя не задавалось.

В качестве тестируемых методов были выбраны пять методов прямоугольного раскроя, входящих в состав систем CETAMI-CUT [4] и NCL [5]: рекурсивный метод (RCAPlus), метод эмуляции отжига (SA), метод поиска с запретами (TS), метод выбора корзин (VBSPlus), гибридный детерминированный метод KAPRAL (NCL-K). В таблице показаны результаты тестирования для 400 тестов (по 100 для каждого класса заданий).

Результаты тестирования методов прямоугольного раскроя

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

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

Литература

1.   Waesher G., Haussner H., Shumann H. An improved typology of cutting and packing problems // European Journal of Operational research. 2007, 183, pp. 1109–1130.

2.   Мухачева Э.А., Валеева А.Ф., Картак В.М., Мухачева А.С. Методы локального поиска оптимума в задачах ортогонального раскроя и упаковки: аналитический обзор и перспективы развития // Информационные технологии. 2004. № 5. C. 2–18.

3.   Липовецкий А.И. Свойства прямоугольных укладок: препринт. УрО АН ССР, Ин-т машиновед. Свердловск, 1988.

4.   Мухачева Э.А., Ермаченко А.И., Сиразетдинов Т.М., Жукова Т.Ю. Комплекс алгоритмов и программ расчета гильотинного раскроя // Информационные технологии. 2004. № 8. C. 18–25.

5.   Петунин А.А., Полевов А.В., Куреннов Д.В. Об одном подходе к решению задач раскроя-упаковки // Конструирование и технология изготовления машин: сб. науч. тр. Ч. 2. Вестник УГТУ-УПИ. Екатеринбург: УГТУ–УПИ. № 18 (70). 2005. C. 212–216.