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

Павел Бунаков

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

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

Условия автоматизированного производства расширяют этот список ограничениями второго типа — технологическими, которые определяются характеристиками раскройного оборудования и организационно-технологическими особенностями производства:

• максимальная и минимальная ширина отрезаемой полосы;
• необходимость и размер предварительной обрезки края листа;
• ресурс непрерывной работы режущего инструмента;
• ширина режущей части инструмента;
• максимальная длина сквозного реза;
• вектор первых резов (продольный или поперечный раскрой);
• количество одновременно раскраиваемых листов (размер пакета);
• максимальное количество поворотов пакета;
• минимальное расстояние между пилами в многопильных станках;
• направление укладки заготовок на листе;
• операционные припуски на сторону заготовки для последующей обработки.

Как видно, количественно технологические ограничения значительно превосходят геометрические. Кроме того, они могут варьироваться в широком диапазоне в зависимости от специфики конкретного предприятия.

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

,

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

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

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

Рис. 1. Геометрическая интерпретация алгоритма линейного раскроя

Как известно, задача оптимального линейного раскроя имеет точное математическое решение, геометрическая интерпретация которого показана на рис. 1 для случая, когда мощность исходного множества заготовок равна двум. Оси системы координат размечаются с шагом, кратным типоразмерам заготовок (N и K), до значения, не превышающего линейного размера области размещения (L). Таким образом, на плоскости генерируется сетка, каждый узел которой соответствует некоторому варианту раскроя. Отрезок, соединяющий точки на осях координат, значения которых равны размеру области размещения, является границей подмножества узлов, соответствующих реальным вариантам раскроя (расположенных ниже границы). Тот из них, который находится ближе других к границе, и будет определять вариант раскроя, оптимальный по количеству отходов материала. Для ускорения поиска рассматриваются только те ячейки сетки, которые пересекает построенный отрезок (на рис. 1 они заштрихованы).

Единственным критерием оптимизации при линейном раскрое является минимизация отходов, поэтому получаемые варианты раскроя априорно являются технологичными.

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

• нахождение оптимального варианта раскроя в двумерной постановке, каждая из которых соответствует проекции многомерной сетки на одну из координатных плоскостей (количество таких задач равно C²_N, где N — количество типоразмеров заготовок);
• нахождение минимального элемента в полученном векторе решений.

Эксперименты, проведенные с данными, которые соответствуют реальным мебельным изделиям, выпускаемым на ряде предприятий, показали, что эта замена обеспечивает приемлемые временные показатели, причем зависимость времени счета от количества типоразмеров заготовок носит экспоненциальный характер (рис. 2).

Рис. 2. Характер зависимости времени раскроя от количества типоразмеров заготовок

Исходя из этого сделан вывод о возможности перехода от площадного раскроя к суперпозиции линейных раскроев. Соответствующий алгоритм является рекурсивным и реализуется за три шага.

На первом шаге из исходного множества M формируется подмножество Mk(δ) , объединяющее заготовки, главный линейный размер которых находится в диапазоне

Lmax • (1- δ),

где Lmax  — максимальный размер заготовки, 0 ≤ δ < 1  — допустимый разброс размеров. Под главным линейным размером понимается тот размер заготовки, который соответствует текущему направлению текстуры. При отсутствии или игнорировании направления текстуры он определяется как максимальное значение, выбранное из длины и ширины заготовки.

Величина получаемого при раскрое КИМ зависит от выбранного значения коэффициента δ :K ИМ = F ( δ ) . Теоретически это означает необходимость перебора вариантов формирования подмножества Mk(δ) для всего возможного диапазона значений δ. Это неизбежно приведет к недопустимому увеличению времени раскроя. Экспериментальные исследования, проведенные на ряде мебельных предприятий, позволили сделать три вывода (рис. 3):

Рис. 3. Зависимость КИМ от величины разброса размеров заготовок в полосе

• наибольшие изменения значений F(δ) приходятся на диапазон 0,05 ≤ d ≤ 0,2;
• в указанном диапазоне изменение функции F(δ) носит плавный характер;
• при значении δ > 0,2 величина КИМ практически не зависит от дальнейшего его увеличения.

На основании этих выводов при формировании Mk(δ) берется фиксированное количество значений δ, что позволяет добиться приемлемого времени перебора вариантов раскроя. Практика показала, что без существенной потери качества раскроя можно варьировать значение δ в указанном диапазоне с шагом от 0,01 до 0,2.

На втором шаге заготовки из подмножества Mk(δ) раскраиваются по алгоритму линейного раскроя. Это означает, что, во-первых, получается локально оптимальная по значению КИМ карта раскроя полосы для выбранного значения δ, а во-вторых, она является технологичной. Процедура формирования подмножества Mk(δ) и линейный раскрой полосы выполняются для всех значений δ, после чего выбирается оптимальная карта раскроя, которой соответствует оптимальное подмножество M^opt_k.

Остаток материала в полосе для оптимальной карты раскроя, так же как и его остатки при размещении любого элемента подмножества M^opt_k , соответствующего значению δ ≠ 0, образует множество псевдополноформатных листов. Для каждого элемента этого множества рекурсивно повторяются рассмотренные выше операции. Это означает, что при выполнении каждой пары шагов мощность исходного множества заготовок уменьшается не только со стороны более «крупных» его элементов, но и со стороны более «мелких».

После раскроя всех псевдополноформатных листов проверяется мощность множества

M \ M^opt_k \ M ⁱ_k,

где  M ⁱ_k — подмножество заготовок, размещенных на остатках материала, полученного при формировании k-й полосы. Если она имеет ненулевое значение, то по отношению к указанному множеству вновь выполняются вышеописанные шаги, то есть формируется подмножество M_k-1 (δ), из которого выбирается  M_k+1^opt.

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

На третьем шаге элементы множества S рассматриваются в качестве исходных заготовок для линейного раскроя полноформатных листов.

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

Для сравнительной оценки значений КИМ, получаемых при использовании традиционного алгоритма площадного раскроя и предлагаемого алгоритма, была произведена случайная выборка из 50 мебельных ансамблей, выпускаемых различными предприятиями. Для каждого ансамбля были выполнены два варианта раскроя. Результаты эксперимента представлены на рис. 4. Из него видно, что в большинстве случаев предлагаемый алгоритм (график красного цвета) дает большее значение КИМ. Таким образом, раскрой площадных материалов по рассмотренному алгоритму подходит не только для пильных центров, но и для обычных форматно-раскройных станков.

Рис. 4. Сравнительный анализ КИМ

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

Практическая реализация рассмотренного алгоритма выполнена в программе БАЗИС-Раскрой.

САПР и графика 11`2007