Задача раскроя, объяснённая просто
Что такое задача раскроя, почему она NP-трудная и как 1D- и 2D-оптимизаторы (гильотинный рез и настоящая укладка) быстро находят хорошие решения.
Что такое задача раскроя?
Даны длины заготовок (прутки, доски, листы) и список нужных деталей — раскроить все детали из как можно меньшего количества материала. Звучит тривиально; математически это NP-трудная задача — число комбинаций взрывается с ростом списка деталей.
1D, 2D и гильотинные резы
1D — одно измерение: трубы, профили, стойки. 2D добавляет ширину — фанера, стекло, листовой металл. Гильотинные резы идут от кромки до кромки (как форматно-раскроечный станок); настоящая укладка допускает любой поворот и негильотинные раскладки (как лазеры и фрезеры).
Почему точные решения редкость
Точно решаются только маленькие экземпляры (динамическое или целочисленное программирование). Промышленность опирается на эвристики — First Fit Decreasing, Best Fit Decreasing, полочные алгоритмы — которые обычно попадают в несколько процентов от оптимума за миллисекунды.
Пропил и другие ловушки реального цеха
Каждый рез расходует материал: пропил 3 мм добавляет 3 мм за рез, и 50 резов молча съедают 150 мм заготовки. Повторное использование обрезков, направление волокна и потери на торцовку значат не меньше, чем сама укладка.
Попробуйте на своём раскрое
Линейный раскрой оптимизирует списки прутков и профилей; Раскрой листов делает гильотинные раскладки листов с поворотом и пропилом. Вставьте свой список и сравните расход материала до и после.