УДК
Оптимизация раскроя рулонной продукции
,
Южно-Уральский государственный университет
Производство рулонной продукции часто выполняется в два этапа. На первом этапе из сырья формируется полуфабрикат – лист некоторой ширины (обычно предельной, которую допускает используемое оборудование) и достаточно большой длины. Затем полуфабрикат раскраивается на листы готовой продукции (или полуфабриката для следующего передела) заданной ширины и заданной длины, много большей ширины. Оборудование для раскроя имеет некоторое число точек резки ( обычно небольшое, 3 - 5 ) Набор требуемых длин и ширин продукции разнообразен и может меняться. При раскрое полуфабриката, как правило, образуются отходы. Основную долю отходов составляют излишки ширины полуфабриката, возникающие вследствие обычной некратности раскраиваемой и требуемых ширин. Отходы по ширине могут варьироваться от нуля до ~50% в зависимости от сочетания ширин изделий. Отходами, образующимися при поперечном разрезе полуфабриката, можно пренебречь. Возникает задача минимизации отходов при раскрое по ширине. Подобные задачи оптимизации раскроя листовой продукции возникают на предприятиях легкой промышленности [1-3]. Известные методы оптимизации раскроя заключаются в сведении её к задачам дискретного линейного программирования различной сложности и использовании для их решения стандартных пакетов программ. Используя особенности стоящей задачи, можно упростить её решение и уменьшить затраты времени на вычисления.
Формализуем задачу. Раскраиваемый лист имеет ширину Н и условно неограниченную длину L. Задан набор ширин и длин ( (h1,l1), (h2,l2), … (hk,lk)) изготавливаемой продукции (hi<=H) и максимально возможное число точек резки R на оборудовании раскроя. Фактическое число точек резки r может быть и меньше максимального. Число различных ширин для отдельной операции резки невелико (5 -7). Объем отходов Δ для отдельной операции равен
Δ = Н – Σ hi (1)
i
Требуется составить план раскроя, минимизирующий величину отходов Δ.
Данная задача относится к классу задач о ранце размерности 2. Известно, что она является NP-полной и оптимальное решение находится полным перебором вариантов заполнения полосы заготовками. Учитывая, что число вариантов заготовок невелико ( не более 10), полный перебор можно выполнить за приемлемое время. Исходя из особенностей технологии производства допускается деление на части заготовок по длине. Это позволяет упростить задачу, сведя ее к последовательности одномерных задач о ранце [4,5].
Предлагается следующий способ сведения. Для заданных ширин заготовок, выполняется оптимальное по критерию (1) размещение заготовок на исходном полуфабрикате. Если при этом список заготовок не исчерпан, то из него исключаются размещенные заготовки, тем самым список ширин уменьшается. Эти действия повторяются до полного исчерпания списка требуемых заготовок. Одномерная задача о ранце решается, исходя из принципа оптимальности Беллмана [4]. Он реализуется рекурсивной процедурой динамического программирования.
Qn(H, R) = max(h + Qn+1(H-h,R-1)) (2)
h
Конечность глубины рекурсии обуславливается неотрицательностью аргументов функции Беллмана в уравнении (2). В (2) h пробегает заданное множество значений.
Литература
1., Залгаллер раскрой промышленных материалов. – Новосибирск: наука:, 1971. – 299 с.
2.Бабаев раскрой материалов с помощью ЭВМ. – М.: Машиностроение, 1982.- 168 с.
3., , Павлов рационального использования сырья в рамках САМ – системы предприятия легкой промышленности.// Автоматизация в промышленности. Декабрь 2004, С. 14-17.
4.Bellman R., Dreyfus S/ Applied dynamic Programming. – Princeton: Princeton University Press, 1962.
5.Щербина аспекты динамического программирования // Динамические системы. – 2007. – Вып. 22. С. 21-36.
