В статье рассказывается о производственно-ориентированном алгоритме раскроя материалов по технологии нестинга, сочетающего жесткие отраслевые правила, детерминированные конструктивные эвристики и ограниченный приоритетный поиск.
Задача раскроя листовых материалов (размещение деталей на плите так, чтобы осталось как можно меньше отходов) давно изучается учеными. Еще в середине XX века ее исследовали такие математики, как Поль Гилмор (Paul Gilmore) и Ральф Гомори (Ralph Gomory). С тех пор появилось множество методов: от простых правил «клади сначала самое большое» до сложных вычислительных подходов.
Однако существует важная проблема: большинство этих методов создавались как абстрактные математические модели, стремящиеся к идеальному использованию материала, но почти не учитывающие реалии конкретного производства.
Для мебельной отрасли подобной оптимизации недостаточно. Здесь раскрой — это не просто геометрическая задача, а часть целостного производственного процесса, где важно всё: направление текстуры, принадлежность деталей к конкретному изделию и заказу, удобство сортировки, сборки и даже особенности конкретного станка. Игнорирование этих факторов приводит к получению формально «идеальных» карт раскроя, но при этом крайне неудобных для реализации, а зачастую и просто неисполнимых.
Особенности раскроя в мебельной отрасли
В мебельном производстве широко используются древесные материалы, которые имеют выраженное направление рисунка или волокон. Если на карте раскроя повернуть деталь «не так», то изделие может потерять эстетичность и привлекательность, а иногда и вовсе стать непригодным для продажи. Таким образом, правильное расположение деталей на картах раскроя является ключевым фактором качества готовой продукции и минимизации производственного брака.
В классических задачах раскроя поворот детали является одним из главных способов уменьшения отходов. В мебельном производстве такой свободы почти нет, поскольку поворот на 90° чаще всего запрещен, а поворот на 180° допустим не всегда. Более того, иногда вообще допустим только один вариант ориентации.
Другой нюанс связан с тем, что детали одного фасада или корпуса должны выглядеть как единое целое. Даже если каждая деталь по отдельности ориентирована правильно, их сочетание может нарушать визуальную логику изделия. Исходя из этого алгоритм раскроя должен учитывать не просто форму детали, а форму вместе с допустимыми вариантами ориентации и связями внутри изделия. Большинство универсальных программ либо вообще не поддерживают подобные ограничения, либо сводят их к разрешению или запрещению поворотов.
Еще одна особенность раскроя для мебельного производства определяется тем, что каждая деталь — это не самостоятельный объект, а часть изделия, заказа, партии. Если детали одного изделия на картах раскроя будут «разбросаны» по многим листам, это создаст серьезные производственные проблемы:
- сложность сортировки и маркирования деталей;
- высокий риск пересортицы;
- увеличение времени на комплектование изделия;
- сложности при контроле качества.
Большинство универсальных алгоритмов не оперируют понятиями изделия или заказа. Они оптимизируют размещение каждой детали по отдельности. В результате возникает конфликт между математической оптимальностью карт раскроя и реальной эффективностью их реализации на производстве.
Особенностью мебельного производства является также высокая повторяемость, когда одни и те же детали встречаются сотни и тысячи раз, причем не только в серийном производстве, но в позаказном. Многие современные методы поиска оптимальных решений используют случайность, то есть при каждом запуске они выдают немного другой результат. Формально карты раскроя могут быть идентичны по коэффициенту использования материала, но их структура может существенно отличаться. Для мебельного производства это проблема, поскольку ему нужна стабильность, которая позволяет:
- при одинаковых входных данных получать одинаковый результат;
- стандартизировать производственные процессы;
- обучать персонал на типовых схемах;
- накапливать статистику.
Алгоритмы, которые не обеспечивают воспроизводимость, сложно внедрять в серийное и позаказное мебельное производство.
Последний нюанс: раскрой выполняется на конкретных станках с ЧПУ, у каждого из которых есть свои особенности, например ширина пропила, минимальные зазоры, зоны вакуумного прижима, ограничения по последовательности резов, зоны, где размещать детали нельзя. Есть еще параметры, зависящие от материала, инструмента и состояния оборудования, которые могут со временем меняться. Помимо учета этих параметров, есть еще ряд практических требований к картам раскроя, например удобство съема деталей, снижение риска повреждения кромок или типовые схемы исполнения пропилов.
Универсальные алгоритмы либо упрощенно учитывают особенности оборудования, либо не учитывают их вовсе. Это повышает вероятность появления карт раскроя, которые выглядят корректными, но оказываются сложными для исполнения на реальном оборудовании.
Таким образом, в мебельной отрасли нельзя рассматривать раскрой, как чисто математическую задачу минимизации отходов. Он является управляемым производственным процессом, в котором необходимо учитывать ориентацию текстуры, целостность изделия, удобство логистики, повторяемость решений и реальные ограничения оборудования.
Существующие программные решения и их проблемы
Сегодня на рынке программного обеспечения можно выделить несколько типов решений для оптимизации раскроя материалов:
- модули внутри CAD/CAM-систем;
- отдельные программы-оптимизаторы;
- универсальные математические «решатели», которые можно настроить под задачу раскроя;
- облачные сервисы с закрытой логикой работы.
Интерфейсы и способы лицензирования у них разные, но в основе работы большинства их них лежат схожие принципы. Прежде всего, они ориентированы на один показатель — коэффициент использования материала. В теории это выглядит логично: чем меньше отходов, тем ниже себестоимость продукции. Однако в реальности производство устроено сложнее, и для него важны понятность карты раскроя для оператора, удобство сортировки деталей, логистика внутри заказа, технологичность исполнения и устойчивость процесса. При игнорировании этих факторов нередко возникает ситуация, когда полноформатный лист заполнен идеально, но оператору неудобно работать, а детали трудно комплектовать и, как результат, возрастает риск брака.
Во многих случаях алгоритмы программ работают в режиме «черного ящика», когда пользователь видит результат, но практически не может повлиять на логику размещения, например жестко задать правила группировки деталей, установить приоритеты по изделиям, ограничить повороты для конкретных групп деталей или задать производственные предпочтения. Соответственно, сложно понять, почему программа выдала именно такое решение, а следовательно, добиться повторяемости. В силу этого возникают проблемы встраивания алгоритма в стандарты предприятия, что снижает доверие к системе и делает ее использование рискованным на ответственных участках производства.
Как было отмечено выше, для серийного производства особенно важна повторяемость: при одинаковых данных результаты тоже должны быть одинаковыми. Однако многие алгоритмы при малейшем изменении входных данных (а иногда и без изменений) выдают разные схемы раскроя. Это особенно характерно для методов, использующих элементы случайности.
В мебельном производстве часто меняются «исходные данные», например раскраиваются разные материалы или изменяется их толщина. Во многих системах эти изменения требуют ручной перенастройки, обходных решений или частичного отказа от функциональности, поскольку у них обычно нет глубокой интеграции с реальными регламентами предприятия.
Если говорить об адаптации для мебельного производства алгоритмов раскроя из других отраслей промышленности, то это весьма проблематично.
В машиностроении задачи раскроя решаются для деталей сложной формы, не имеющих текстуры, и часто дорогих по стоимости, поэтому основной акцент — точность и минимизация отходов. По сравнению с мебельным производством размер партии обычно меньше, повторяемость деталей ниже, а логистика внутри изделия не так критична. Соответственно, используемые алгоритмы плохо учитывают массовую повторяемость, не ориентированы на стабильность при серийном запуске и слишком тяжеловесны по вычислениям для типичных мебельных задач. В результате они одновременно избыточно сложны и недостаточно адаптированы к мебельной специфике.
Более близкая к мебельной — текстильная промышленность, но в ней совсем другие физические законы. Здесь материал гибкий и без параметра толщины, при этом он может деформироваться. Резы часто выполняются непрерывно, а требования к ориентации рисунка имеют другую природу. Алгоритмы раскроя в текстильной промышленности не учитывают толщину материала, не моделируют ширину реза, не работают с жесткими зазорами и рассчитаны на другую технологию исполнения. Прямой перенос их на плитные материалы приводит к некорректным решениям.
Анализ популярных алгоритмов раскроя
Пошаговые алгоритмы класса Bottom-Left Fill размещают детали последовательно, например, начиная с нижнего левого угла, занимая первое подходящее место. Их достоинствами являются высокая скорость расчетов, предсказуемость результата и простота реализации. Однако их применение для мебельного производства имеет серьезные ограничения:
- решения принимаются локально, без учета общей картины;
- нельзя «пересобрать» карту, если на раннем этапе допущена неудачная компоновка;
- не учитываются связи деталей внутри изделия;
- при жестких ограничениях по текстуре эффективность резко падает.
Такие методы могут использоваться в программах раскроя для мебельной промышленности, но только как часть более сложной системы.
Генетические алгоритмы имитируют естественный отбор, создавая множество вариантов решений и «скрещивая» их для постепенного улучшения результата. Их сильная сторона — это возможность исследования большого количества вариантов, но в мебельном раскрое возникают проблемы:
- резкий рост размерности пространства вариантов при высокой повторяемости деталей;
- высокие затраты времени на расчет;
- нестабильность результатов, когда каждый запуск дает немного другой вариант;
- сложность числового представления таких критериев, как удобство сортировки или технологичность.
Имитация отжига — еще один алгоритм, теоретически подходящий для оптимизации раскроя плитных материалов. Его особенность в том, что он позволяет принимать «худшие» решения с некоторой вероятностью, но использует понятие «охлаждения», которое со временем уменьшает эту вероятность. Это позволяет на начальном этапе исследовать широкое пространство вариантов, а затем перейти к улучшению решения. Алгоритм имитации отжига не гарантирует нахождения оптимального решения, однако при правильной настройке может находить качественные варианты при сложных ограничениях. В качестве недостатков можно отметить большое количество итераций, чувствительность к настройке параметров и нестабильность результатов.
Применение строгих математических методов, которые формально описывают задачу и гарантированно находят оптимальное решение, проблематично в силу того, что реальные задачи мебельного раскроя включают сотни и тысячи деталей, множество ограничений и несколько критериев оптимальности одновременно. По этим причинам время расчета резко возрастает, а кроме того, формализация всех отраслевых нюансов приводит к слишком громоздким моделям, неудобным для повседневного использования.
Таким образом, большинство существующих алгоритмов ориентированы в первую очередь на геометрию, слабо учитывают специфику мебельного производства, не рассматривают воспроизводимость в качестве ключевого свойства и плохо адаптируются к условиям серийного и позаказного мебельного производства. Это делает актуальной разработку специализированного производственно-ориентированного подхода к задаче мебельного раскроя.
Постановка задачи мебельного раскроя
В упрощенном виде задача раскроя плитных материалов по технологии нестинга выглядит так. Есть полноформатные листы материала определенных размеров и множество деталей, каждая из которых имеет размеры, относится к конкретному изделию или заказу, выполнена из конкретного материала, допускает только определенные варианты ориентации и требует технологических зазоров. Размещение деталей на листах должно удовлетворять системе следующих ограничений:
- каждая деталь должна полностью помещаться на листе;
- детали не должны пересекаться с учетом ширины пропила и технологических зазоров;
- ориентация должна быть допустимой для конкретной детали;
- при необходимости детали одного изделия должны быть ориентированы согласованно;
- детали одного изделия должны быть расположены «близко» друг к другу, а не «разбросаны» по разным листам.
Задача мебельного раскроя в такой постановке является многокритериальной с возможностью задания шкалы приоритетов действия критериев непосредственно пользователем.
Производственно-ориентированный алгоритм раскроя
Предлагаемый алгоритм рассматривает задачу мебельного раскроя по технологии нестинга как задачу управляемого поиска допустимых решений с точки зрения производственных ограничений. В отличие от универсальных подходов, он изначально проектировался с учетом отраслевых ограничений и логики производственного процесса.
В основе алгоритма лежит гибридный подход, который сочетает в себе:
- жесткие правила, исключающие заведомо непригодные варианты;
- детерминированные эвристические методы построения начального решения;
- ограниченный поиск улучшений внутри разумного пространства вариантов, допустимых с точки зрения производственных ограничений.
Каждый промежуточный вариант раскроя описывается не только геометрией, но и набором производственно-ориентированных параметров, таких как показатели «заполненности» полноформатных листов, принадлежность деталей к изделиям, допустимые варианты ориентации, технологические параметры оборудования и т.д. Таким образом, алгоритм «понимает» не только форму деталей, но и их место в производственном процессе.
На каждом шаге оптимизации сразу отсекаются варианты, которые нарушают направление текстуры, создают несогласованность ориентации текстур в контексте изделия, допускают разрыв кластеров деталей одного изделия по листам и противоречат ограничениям оборудования. Это резко сокращает пространство поиска и не позволяет системе генерировать недопустимые решения.
Для формирования начального решения используются детерминированные эвристики:
- сортировка деталей по приоритетам (размер, принадлежность к изделию, критичность ориентации);
- первичное размещение крупногабаритных и критичных деталей;
- использование модифицированных BLF/BAF-схем с учетом группировки по изделиям;
- формирование компактных кластеров деталей одного изделия на листах.
Результирующее начальное решение является допустимым, воспроизводимым и служит точкой старта для дальнейших улучшений, выполняемых алгоритмом ограниченного приоритетного поиска, который:
- поддерживает очередь состояний фиксированного размера, одновременно анализируя ограниченное число перспективных вариантов;
- на каждом шаге расширяет множество перспективных состояний по функции оценки;
- при превышении лимита отбрасывает худшие состояния.
Функция оценки учитывает отходы материала, показатель разобщенности деталей изделий, среднее количество листов и оценку технологической сложности варианта. Важным преимуществом предлагаемого алгоритма является свойство «anytime», то есть он относится к классу прерываемых алгоритмов, которые способны выдавать допустимые промежуточные результаты, продолжая улучшать их по мере продолжения работы.
Дополнительно в рамках нового алгоритма разработан безразмерный параметр, характеризующий степень неустойчивости детали. Он носит сугубо эмпирический характер. Его назначение в том, чтобы помочь технологу определить, какие детали при обработке могут сместиться на станке с вакуумным столом независимо от площади и габаритов. Для таких деталей следует добавить припуск для последующей обработки их за несколько проходов.
По сравнению с рассмотренными выше алгоритмами предлагаемый подход:
- оперирует расширенным пространством состояний, включающим производственные связи;
- использует многокритериальную оптимизацию вместо геометрических критериев;
- не требует сопоставимости состояний по глубине дерева поиска;
- ограничивает ветвление отраслевыми правилами, а не только геометрией;
- сохраняет детерминированность, добавляя при этом возможность глобального улучшения решения за счет управляемого поиска.
Тестирование алгоритма
Для оценки разработанного алгоритма в модуль БАЗИС-Раскрой была добавлена соответствующая конфигурация (рис. 1). При сравнительном экспериментальном исследовании анализировались следующие показатели:
- пригодность и эффективность для решения реальных задач мебельного производства;
- приемлемость компромисса между уровнем отходов и производственными метриками;
- устойчивость и воспроизводимость решений при серийном запуске;
- преимущества по сравнению с распространенными подходами.
Рис. 1. Окно параметров нестинга
В качестве тестовых наборов использовались данные, моделирующие типичные заказы мебельного предприятия:
- детали типовых изделий корпусной мебели;
- обязательная ориентация по текстуре для значительной части деталей;
- разные размеры полноформатных листов;
- материал различной толщины;
- набор заказов с разным уровнем серийности (от позаказного изготовления изделий до крупных серий);
- технологические параметры, соответствующие раскрою на станках с ЧПУ.
В качестве альтернативных алгоритмов рассматривались алгоритмы BLF (базовый детерминированный жадный алгоритм) и геометрически ориентированный приоритетный поиск (аналог MBA — Modified Bat Algorithm) с геометрической функцией оценки. Все алгоритмы работали с одинаковыми входными данными и ограничениями по времени.
Для сравнительной оценки использовался комплекс метрик, охватывающий не только геометрию карт раскроя, но и их влияние на весь производственный процесс:
- коэффициент использования материала;
- среднее количество листов на изделие;
- коэффициент группировки деталей по изделиям (пространственная близость);
- показатели технологической сложности карт (количество резов, плотность размещения, наличие «узких мест»);
- воспроизводимость решений при повторных запусках.
Рис. 2. Примеры карт раскроя по технологии нестинга
На рис. 2 показаны варианты карт раскроя по технологии нестинга. Обработка результатов эксперимента показала, что предлагаемый алгоритм:
- по уровню отходов уступает геометрическому поиску в среднем на 1-3 процентных пункта и сопоставим с BLF;
- по количеству листов, используемых для раскроя деталей одного изделия, дает экономию в среднем на 15-30% по сравнению с BLF и геометрическим поиском;
- характеризуется существенно более высоким коэффициентом группировки деталей по сравнению с альтернативами, что упрощает сортировку и сборку;
- формирует карты раскроя, обладающие умеренной технологической сложностью без избыточной фрагментации;
- демонстрирует полную детерминированность — при фиксированных параметрах повторные запуски приводят к одинаковым картам.
Таким образом, экспериментальные данные подтверждают, что ориентация исключительно на минимизацию отходов не обеспечивает оптимальности на уровне всего производственного процесса. Небольшое увеличение отходов (в пределах 1-3%) оказывается экономически оправданным при условии снижения сложности последующих операций, уменьшения рисков пересортицы и повышения стабильности процесса (рис. 3). Предлагаемый алгоритм демонстрирует приемлемый производственный компромисс, «жертвуя» частью потенциала геометрической оптимизации ради устойчивости, управляемости и технологичности решений.
Рис. 3. Диаграмма сравнения алгоритмов
Заключение
Раскрой материалов по технологии нестинга в мебельном производстве нельзя рассматривать как абстрактную задачу оптимизации раскладки деталей на листах с минимальными отходами. Он является частью сложной производственной системы, поэтому попытки применения универсальных алгоритмов или алгоритмов, ориентированных на иные производства, дают лишь частичный эффект. Они могут снижать отходы, но не гарантируют повышения эффективности производства в целом.
Предлагаемый производственно-ориентированный алгоритм учитывает технологические процессы изготовления мебели на уровне логики своей работы. Экспериментальные результаты показывают его практическую применимость. В настоящее время проводятся работы по интеграции алгоритма в систему БАЗИС как специализированного модуля раскроя.
