Введение
Задача двумерного раскроя и упаковки материалов была сформулирована в классических работах П. Гилмора и Р. Гомори [1] и с тех пор остается предметом интенсивных исследований. В литературе предложен широкий спектр методов: от жадных и конструктивных алгоритмов до метаэвристик и точных методов целочисленного программирования [2–4]. Тем не менее разработка алгоритмов, пригодных для практического использования в конкретных отраслях промышленности, остается актуальной задачей [5; 6, с. 3; 7].
В мебельной отрасли нестинг не может рассматриваться как чисто геометрическая задача минимизации отходов. Производственный процесс предъявляет дополнительные требования, связанные с ориентацией деталей по текстуре, связностью с изделиями и заказами, логистикой, технологией раскроя и последующими операциями (облицовывание кромок, сверление отверстий в пласть и торец, сборка). Игнорирование этих факторов приводит к формированию карт раскроя, формально оптимальных по проценту использования материала, но неудобных или непригодных для практического применения [8; 9].
Цель исследования – разработка и обоснование метода управляемого поиска производственно допустимых решений для задачи мебельного нестинга, интегрирующего отраслевые ограничения (ориентация по текстуре, связность деталей, требования к воспроизводимости) и многокритериальную производственную оценку, на основе гибридной архитектуры, сочетающей жесткие правила, конструктивные эвристики и ограниченный приоритетный поиск.
Материалы и методы исследования
В качестве объекта исследования рассматриваются процессы оптимального раскроя листовых материалов (ЛДСП, МДФ) при производстве корпусной мебели в условиях единичного и серийного производства. Исходными данными служат:
− спецификации изделий (номенклатура деталей, их геометрические размеры, ориентация текстуры, материал);
− требования к связности (принадлежность деталей к конкретному изделию/заказу);
− производственные ограничения (форматы листов, доступное оборудование, требования к воспроизводимости карт раскроя).
Разработка и экспериментальная проверка алгоритма выполнялись в среде, совместимой с промышленной САПР «БАЗИС» (ООО «БАЗИС-Центр», Россия). Алгоритмическая часть реализована на языке C++ с использованием объектно-ориентированной архитектуры, позволяющей подключать модули:
− формирования пространства состояний;
− ветвления с учетом отраслевых ограничений;
− многокритериальной оценки решений.
Для валидации использовались реальные производственные данные мебельных предприятий: 15 типовых наборов изделий (шкафы-купе, кухонные гарнитуры, корпусная мебель) с общим количеством деталей от 50 до 500 на один заказ.
Задача мебельного нестинга (nesting) представлена как задача управляемого поиска производственно допустимых решений (ПДР) в дискретном пространстве раскладки деталей на листе. Пространство состояний структурировано в виде дерева решений, где каждый узел соответствует частично заполненному листу.
В схему ветвления и структуру состояния интегрированы:
− ориентация по текстуре – детали имеют допустимые углы поворота (0°, 90°, 180°, 270°) в зависимости от направления текстуры материала;
− связность деталей с изделиями – введены ограничения на совместное размещение деталей одного изделия на минимальном количестве листов для упрощения сборки;
− требования к воспроизводимости – карты раскроя детерминированы путем фиксации правил приоритетов, исключающих случайный перебор.
Оценка решений выполняется по критериям, ориентированным на производственный результат:
− коэффициент использования материала (отходы);
− количество листов;
− сложность сборки (количество листов, содержащих детали разных изделий);
− логистическая сложность (количество перемещений, группировка деталей по картам).
Функция агрегируется с весовыми коэффициентами, настраиваемыми под производственные приоритеты. Реализована комбинация:
− жестких правил (отсев недопустимых размещений по геометрии и ориентации);
− конструктивных эвристик (алгоритмы упаковки «первый подходящий», группировка по связности);
− ограниченного приоритетного поиска (поиск с возвратом с ограничением глубины и ширины ветвления, управляемый эвристической оценкой узлов).
Сравнение проводилось:
− с базовым алгоритмом, реализованным в штатном модуле раскроя САПР «БАЗИС»;
− с коммерческим пакетом оптимизации раскроя (название скрыто по условиям конфиденциальности, но указана версия).
Критерии сравнения: коэффициент использования материала (%), время расчета (с), количество карт раскроя, стабильность результатов (детерминированность при повторных запусках).
Для каждого набора данных выполнялось не менее 10 запусков алгоритма (с разными начальными условиями, где это допускалось архитектурой). Результаты усреднялись, для оценки воспроизводимости рассчитывалось среднеквадратическое отклонение по коэффициенту использования материала. Сравнение с референсными методами выполнено с использованием t-критерия Стьюдента для связанных выборок.
Результаты исследования и их обсуждение
Фундаментальными особенностями мебельного производства, принципиально отличающими его от многих других отраслей, являются [10, с. 58] строгая ориентация деталей по текстуре материала, связанность деталей с изделиями и заказами, массовость, повторяемость и воспроизводимость и технологические ограничения оборудования.
Ламинированные древесно-стружечные плиты (ЛДСП), шпон и массив древесины обладают выраженным направлением рисунка, волокон или декоративного слоя. Нарушение этого направления приводит к визуальному браку изделия.
В классических задачах нестинга вращение деталей используется как основной инструмент повышения плотности укладки. В мебельном раскрое такая свобода отсутствует: для подавляющего большинства деталей поворот на 90° запрещен, а поворот на 180° допустим лишь в части случаев. Таким образом, деталь описывается не просто геометрией, а геометрией с набором допустимых ориентаций, зачастую сведенным к одному варианту.
Дополнительную сложность создает необходимость согласованной ориентации деталей внутри изделия: элементы одного фасада или корпуса должны восприниматься визуально целостно, что требует единообразной направленности текстуры. Алгоритмы, рассматривающие детали изолированно, могут формально соблюдать ограничение для каждой детали, но при этом нарушать визуальную целостность изделия в целом [8].
Требования к ориентации зависят от типа детали, материала, конкретного заказа и дизайнерских решений. Это требует гибкой, параметрической модели ориентации, поддерживающей приоритеты и исключения. Большинство существующих алгоритмов не поддерживают такие ограничения или сводят их к бинарному признаку «вращение разрешено/запрещено», что для мебельного производства недостаточно.
В мебельном производстве детали не являются независимыми объектами оптимизации. Каждая деталь принадлежит конкретному изделию или модулю и проходит последовательность операций после раскроя. Эффективность использования листового материала и полная контролируемость технологического процесса являются важнейшими критериями качества алгоритма. Даже если алгоритм предлагается оптимальный с точки зрения расхода материала, нельзя говорить о его практической применимости если он существенно увеличит трудозатраты, усложнит контроль качества и повысит риск ошибки. В основном алгоритмы нестинга решают именно геометрическую версию задачи и не учитывают связей деталей между собой и внешними по отношению к задаче укладки ограничениями. В их модели оптимизации отсутствуют понятия изделия, заказа, партии. Это приводит к конфликту между локальной геометрической оптимальностью и глобальной производственной эффективностью [11]. Отдельным недостатком целой группы стохастических эвристик, значимым в случае ручного изготовления продукции, является высокая чувствительность к начальному состоянию, порядку перечисления деталей и случайным параметрам. При высокой повторяемости это приводит к нестабильности: каждый запуск дает иное решение, формально сопоставимое по целевой функции, но отличающееся по структуре карт раскроя. Подобный «хаос» повышает риск ошибки оператора и осложняет стандартизацию, обучение персонала, внедрение регламентов и накопление статистики. Как следствие, подобные алгоритмы с трудом внедряются в серийное производство.
Реальный раскрой выполняется на конкретных станках с ЧПУ, каждый из которых обладает собственным набором технологических ограничений: ширина пропила, минимальные зазоры между деталями, требования к зонам вакуумной фиксации, ограничения по последовательности резов и направлениям движения инструмента, зоны недопустимого размещения.
Часть параметров зависит от типа материала, толщины плиты, используемого инструмента и состояния оборудования. Они изменяются во времени и плохо поддаются описанию в виде фиксированного набора универсальных ограничений. Кроме формализуемых требований существуют и практические: удобство съема деталей, снижение риска повреждения кромок, предпочтительные схемы реза для конкретного оператора.
Большинство универсальных алгоритмов учитывают оборудование в упрощенном виде либо не учитывают вовсе. В результате возможна генерация карт раскроя, корректных с точки зрения геометрии, но проблемных или непригодных для стабильной работы на конкретном станке.
При серийном выпуске изделий требуются стабильные и воспроизводимые карты раскроя, пригодные для тиражирования и регламентации.
Изменение материала, толщины, типа станка или технологии резки часто требует ручной перенастройки входных данных, использования обходных приемов или даже отказа от части функциональности системы. Глубокая интеграция с производственными регламентами и возможность быстрой адаптации под реальные ограничения, как правило, не обеспечивается.
В машиностроении задачи раскроя и размещения решаются для деталей со сложной геометрией, высокой стоимостью материала и, как правило, без жестких ограничений по ориентированию деталей. Основное внимание уделяется геометрической точности [12] и минимизации отходов, а не серийности и логистике.
Такие алгоритмы имеют ряд недостатков:
− слабо учитывают массовую повторяемость деталей;
− оперируют относительно небольшими объемами партий;
− не ориентированы на детерминированность при серийном запуске.
Для мебельной отрасли подобные методы оказываются избыточно сложными по вычислительным затратам и одновременно недостаточно ориентированными на производственную специфику.
Задачи раскроя в текстильной промышленности существенно отличаются от мебельных [9, c. 10]. Текстиль – это гибкий материал без толщины, допускающий деформацию; рез часто выполняется непрерывным способом, а критерии брака и требования к ориентации имеют иной характер. Даже при наличии направленности рисунка ограничения и последствия ее нарушения принципиально другие.
Алгоритмы, разработанные для текстиля:
− не учитывают толщину и жесткость плитного материала;
− не моделируют ширину пропила и зазоры;
− ориентированы на другие технологические схемы резов.
Прямое перенесение таких методов на плитные материалы приводит к некорректным решениям и противоречит реальной технологии раскроя в мебельном производстве.
Анализ существующих алгоритмов нестинга
Алгоритмы класса Bottom-Left Fill (BLF) и их модификации относятся к простейшим конструктивным методам раскроя. Они формируют решение последовательным размещением деталей в определенном порядке, как правило, начиная с нижнего левого угла, выбирая первое подходящее положение, удовлетворяющее ограничениям [3–5].
Преимущества этих методов – высокая скорость и детерминированность результата. Однако в условиях мебельного раскроя их недостатки становятся критичными:
− фиксированный порядок размещения и локальный характер решений приводят к неэффективному использованию материала при жестких ограничениях по ориентации;
− отсутствует учет связности деталей с изделиями и заказами;
− нет возможности исправления ранних неудачных решений за счет глобальной перестройки карты раскроя.
В итоге BLF и аналогичные алгоритмы годятся лишь как основа для более сложных гибридных подходов.
Генетические алгоритмы
Генетические алгоритмы (GA) широко применяются к задачам комбинаторной оптимизации, включая нестинг. Их сильной стороной является способность исследовать обширное пространство решений и избегать локальных минимумов за счет стохастического поиска [3; 5; 12]. В то же время в мебельном раскрое GA сталкиваются с рядом проблем:
− высокая повторяемость деталей приводит к резкому росту размерности пространства решений и усложняет кодирование хромосом;
− время расчета становится неприемлемым для оперативного использования;
− результаты носят вероятностный характер, что противоречит требованию воспроизводимости.
Кроме того, многие важные для производства критерии (удобство сортировки, технологичность карт, логистика изделий) плохо поддаются формализации в виде числовой целевой функции, что снижает практическую ценность получаемых решений.
Алгоритмы имитации отжига
Алгоритмы имитации отжига (SA) основаны на стохастическом поиске с постепенным снижением вероятности принятия ухудшающих шагов. Они способны находить качественные решения даже при сложных ограничениях и неровном ландшафте целевой функции.
Основной недостаток SA в производственных условиях – высокая вычислительная стоимость. Для получения устойчивых результатов необходимо большое число итераций, что противоречит требованиям оперативного планирования. Как и в случае GA, решения нестабильны, зависят от выбора начальной конфигурации и параметров «охлаждения», что делает их малопригодными для серийного мебельного производства.
Точные методы и математическое программирование
Целочисленное и смешанно-целочисленное программирование позволяют формально описать задачу раскроя и гарантированно находить оптимальные решения. Однако размерность реальных мебельных задач (сотни и тысячи деталей, многокритериальная целевая функция, сложные ограничения) приводит к экспоненциальному росту времени решения.
Формализация всех отраслевых особенностей: ориентации по текстуре, группировки по изделиям, технологических ограничений – в рамках строгих математических моделей оказывается сложной и приводит к перегруженным постановкам, малопригодным для повседневной эксплуатации.
Анализ существующих методов показывает, что:
− большинство алгоритмов ориентированы преимущественно на геометрическую оптимизацию, а ограничения мебельного производства игнорируются;
− детерминированность и воспроизводимость решений не рассматриваются как ключевые свойства;
− масштабирование к реальным задачам серийного и позаказного мебельного производства затруднено.
Это обосновывает необходимость разработки специализированных производственно-ориентированных алгоритмов, учитывающих как геометрию, так и производственную семантику.
Постановка задачи мебельного нестинга
Рассмотрим прямоугольный лист материала (L) с размерами W ∙ H. Пусть задано множество деталей D = {d1, d2, …, dn}, где каждая деталь di характеризуется:
− размерами (wi, hi);
− принадлежностью к изделию или узлу gi ∈ G;
− материалом mi;
− множеством допустимых ориентаций Oi ⊆ {0°, 90°, 180°, 270°}
− технологическими зазорами δi.
В многолистовой постановке каждая деталь дополнительно имеет номер листа ki.
Геометрические ограничения
Для всех деталей должно выполняться условие принадлежности листу:
где (xi, yi) – координаты нижнего левого угла детали, а wi(oi), hi(oi) – ее размеры при выбранной ориентации oi.
Непересечение деталей с учетом пропила описывается условием
.
Ограничения ориентации и связности
Ориентация каждой детали должна принадлежать множеству допустимых:
.
При необходимости может вводиться согласованность ориентаций внутри изделия:
,
если это необходимо по требованиям визуальной целостности изделия.
Группировка деталей по изделиям задается через штраф за пространственную разобщенность:
где dist – выбранная метрика расстояния.
Целевая функция
Задача мебельного нестинга многокритериальна. Обобщенная целевая функция может быть записана как взвешенная сумма площади отходов (Swaste), штрафов за разобщенность деталей изделий (Pgroup) и технологическую сложность карт раскроя (Pcomplexity), количества используемых листов (Nsheets):
.
Предлагаемый производственно-ориентированный алгоритм
Предлагаемый алгоритм рассматривает задачу мебельного нестинга как задачу управляемого поиска ПДР. В отличие от универсальных подходов он изначально проектируется с учетом отраслевых ограничений и логики производственного процесса [13].
Алгоритм строится как гибридная система, сочетающая:
− жесткие правила, исключающие недопустимые варианты раскроя;
− детерминированные конструктивные эвристики, формирующие начальное решение;
− ограниченный приоритетный поиск, улучшающий решение в пределах пространства допустимых решений.
Каждое состояние поиска S задается кортежем, состоящим из множеств: листов и их заполнения (L), размещенных деталей с координатами и ориентациями (D), связей деталей с изделиями, узлами и заказами (G), актуальных ограничений ориентации (O) и актуальных технологических параметров, таких как пропил, зазоры, зоны запрета и др. (T).
.
Такое представление делает состояние одновременно геометрически и производственно осмысленным.
Перед выполнением поиска и на каждом шаге ветвления применяется система жестких правил, гарантирующих производственную допустимость:
− запрет недопустимых поворотов относительно текстуры;
− согласованность ориентации деталей внутри изделия, где это требуется;
− ограничения на разрыв кластеров деталей одного изделия по листам;
− учет технологических зон запрета и ограничений оборудования.
За счет этого пространство поиска существенно сокращается, а заведомо непригодные решения не порождаются.
Для формирования начального решения используются детерминированные эвристики:
− сортировка деталей по приоритетам (размер, принадлежность к изделию, критичность ориентации);
− первичное размещение крупногабаритных и критичных деталей;
− использование модифицированных BLF/BAF-схем с учетом группировки по изделиям;
− формирование компактных кластеров деталей одного изделия на листах.
Результирующее решение является допустимым, воспроизводимым и служит точкой старта для дальнейшего улучшения.
Ограниченный приоритетный поиск
Для улучшения начального решения применяется ограниченный поиск с приоритетами:
− поддерживается очередь состояний фиксированного размера;
− на каждом шаге расширяется наиболее перспективное состояние по функции оценки;
− при превышении лимита худшие состояния отбрасываются.
Функция оценки имеет вид
,
где Waste(S) – отходы;
Fragmentation(S) – показатель разобщенности деталей изделий;
OrderSplit(S) – среднее количество листов на изделие;
Complexity(S) – оценка технологической сложности карт раскроя.
Алгоритм обладает свойством anytime: при ограничении по времени он всегда возвращает допустимое решение, постепенно повышая его качество по мере продолжения работы.
Отличия от существующих поисковых методов
Предлагаемый алгоритм отличается от аналогов (MBA* и подходами группы Beam Search) тем, что:
− оперирует расширенным состоянием, включающим производственные связи;
− использует многокритериальную функцию оценки вместо сугубо геометрических критериев;
− не требует сопоставимости состояний по глубине дерева поиска;
− ограничивает ветвление как геометрией объектов, так и отраслевыми правилами.
Основным отличием от BLF является возможность глобального улучшения решения за счет управляемого поиска.
Экспериментальная методология и результаты
Для оценки предлагаемого алгоритма использовались данные, моделирующие типичные заказы мебельного предприятия: прямоугольные детали с габаритами, характерными для мебельных изделий; наличие требований к ориентации по текстуре; различные размеры листов и толщины материала; набор заказов с разным количеством и наборами составных элементов; технологические параметры, соответствующие раскрою на станках с ЧПУ. Дополнительно в наборы деталей для нестинга искусственно вводились изделия со строгими эстетическими требованиями [14].
Для сравнения рассматривались:
1. BLF – базовый детерминированный жадный алгоритм.
2. Геометрически ориентированный приоритетный поиск (аналог MBA* с геометрической функцией оценки).
3. Предлагаемый производственно-ориентированный алгоритм.
Все методы работали с одинаковыми входными данными и ограничениями по времени.
При сравнении алгоритмов использовался комплекс метрик:
− процент отходов материала;
− среднее количество листов на изделие;
− коэффициент группировки деталей по изделиям (пространственная близость);
− оценка технологической сложности карт (количество резов, плотность размещения, наличие «узких мест»);
− воспроизводимость решений при повторных запусках.
Полученные результаты (рисунок) показали, что:
− по уровню отходов предлагаемый алгоритм уступает чисто геометрическому поиску в среднем на 1–3 процентных пункта и сопоставим с BLF;
− количество листов, используемых для одного изделия, снижается в среднем на 15–30 % по сравнению с BLF и геометрическим поиском;
− коэффициент группировки деталей существенно выше, что упрощает сортировку и сборку;
− карты раскроя характеризуются более умеренной технологической сложностью без избыточной фрагментации (трудно формализуемый результат, оцениваемый с применением методов нечеткой логики [15]);
− алгоритм демонстрирует полную детерминированность: при фиксированных параметрах повторные запуски приводят к одинаковым картам.
Результаты сравнения алгоритмов по всем метрикам Примечание: составлен авторами по результатам данного исследования
Результаты подтверждают, что ориентация исключительно на минимизацию отходов не обеспечивает оптимальности на уровне всего производственного процесса. Небольшое увеличение отходов (в пределах 1–3%) оказывается экономически оправданным при условии снижения сложности последующих операций, уменьшения рисков пересортицы и повышения стабильности процесса.
Предлагаемый алгоритм демонстрирует именно такой производственный компромисс: он жертвует частью потенциала геометрической оптимизации ради устойчивости, управляемости и технологичности решений.
Заключение
Нестинг для мебельного производства следует рассматривать не как абстрактную геометрическую задачу, а как составную часть комплексной производственной системы. Попытки прямого применения универсальных алгоритмов, разработанных для других отраслей или для «чистых» постановок задач раскроя, приводят к частичным решениям и не обеспечивают устойчивого повышения эффективности производства.
Предложенный производственно-ориентированный алгоритм нестинга демонстрирует практическую применимость в условиях реального мебельного производства. Экспериментальные результаты подтверждают, что умеренный отказ от жесткой минимизации отходов в пользу производственной целесообразности позволяет достичь лучшего баланса между экономией материала, стабильностью процесса и качеством готовой продукции. Дальнейшие исследования могут быть направлены на расширение метода на случаи сложной геометрии деталей, интеграцию с планированием последующих операций и более глубокую адаптацию параметров алгоритма под конкретные предприятия.
Конфликт интересов
Финансирование
Библиографическая ссылка
Бунаков П. Ю., Липатов А. М., Плеханова М. В., Федоров М. А. ПРОИЗВОДСТВЕННО-ОРИЕНТИРОВАННЫЙ АЛГОРИТМ НЕСТИНГА ДЛЯ МЕБЕЛЬНОЙ ОТРАСЛИ // Современные наукоемкие технологии. 2026. № 4. С. 33-40;URL: https://top-technologies.ru/ru/article/view?id=40726 (дата обращения: 10.05.2026).
DOI: https://doi.org/10.17513/snt.40726