Введение в задачу раскроя материала

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

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

Классификация задач раскроя

Задачи раскроя можно разделить на несколько групп, в зависимости от некоторых параметров. В статье Harald Dyckhoff приводит достаточно полную классификацию задач раскроя. Они делятся на группы в зависимости от количества измерений, формы фигур...

Классификация по измерениям

Основная характеристика раскроя — количество измерений:

• раскрой в одномерном пространстве;
• раскрой в двумерном пространстве;
• раскрой в трёхмерном пространстве;
• раскрой в многомерном (более трёх измерений) пространстве;

Например загрузка поддонов является задачей в двумерном пространстве. В отличие от задач в двух и более измерениях, задача в одномерном пространстве имеет явное решение. Достаточно подробно данная задача описывается в книге Кантровича-Залгаллера — «Рациональный раскрой промышленных материалов».

Количественная классификация

Другая важная характеристика — способ измерения количества больших и маленьких объектов. Тут можно рассмотреть два варианта:

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

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

Классификация по форме

Фигуры могут быть определены как их геометрическое представление в пространстве. Части одной фигуры обладают одинаковым геометрическим представлением, исключая преобразования, применённые к фигурам. Отбрасывая такие изменения фигур, они могут быть уникально определены:

• формой;
• размером;
• ориентацией;
• правильной или неправильной формой.

Классификация по ограничениям на результат

По ограничениям на результат можно выделить четыре основные группы:

• минимальное расстояние между объектами;
• ориентация фигур относительно друг друга;
• ограничение на количество фигур;
• ограничение на количество совершаемых «резов»;

Автор выделяет ещё несколько групп по различным признакам, но данные являются основными.