Особенности применения метода генерации столбцов
при решении задачи раскроя гофрополотна

ПетрГУ, Петрозаводск

Задачу планирования раскроя гофрополотна определим следующим образом. Задано множество заготовок M, каждая из которых – прямоугольник. Параметрами заготовки iM являются размеры этого прямоугольника (awi, bwi), границы bi – наименьший и Bi – наибольший объем выпуска. Требуется выпустить необходимое количество заготовок, используя раскрои с наименьшим средним процентом потерь, учитывая ряд технологических ограничений. Решением задачи является список планов раскроев jN с указанием объема реализации Xj каждого из них.

Введем Q – множество гофроагрегатов, Nk – множество возможных планов раскроя для г/а kQ, тогда N=Nk. Для каждого гофроагрегата заданы минимальная и максимальная границы выработки – dk, Dk.

При перенастройке гофроагрегата на новый раскрой некоторая часть гофрополотна идет в отходы, так как агрегат не останавливается, поэтому выпуск небольших по объему раскроев не экономичен (потери, связанные с переходом на новый раскрой, будут больше, чем выгода, получаемая при его выпуске). Поэтому вводится параметр minV – минимальный объем раскроя для выпуска.

Некоторые заготовки (такие как ящик или обечайка) требуют дальнейшей доработки на дополнительном оборудовании (сгиб, склейка и т. д.). По техническим причинам в одном раскрое может быть ограниченное число заготовок разного типа, требующих дальнейшей обработки.

Введем неизвестные Xj – планируемая выработка гофрополотна (в тыс. м2) в соответствии с раскроем jN. Каждому раскрою соответствует процент потерь δj.

Пусть aij – количество тыс. м2 заготовок iM при раскрое тысячи квадратных метров гофрополотна по схеме jN.

Целевая функция задачи определяется суммарными потерями материала:

(1)

Основные условия ограничивают объемы производства заготовок:

bi ≤ aij Xj ≤ Bi, iM, (2)

НЕ нашли? Не то? Что вы ищете?

их дополняют условия массовости объема выработки раскроя:

. (3)

Раскрой либо не используется в оптимальном плане (Xj = 0), либо он включен в план
и объем его выработки не менее minV.

Введем переменную gkj – флаг выполнения раскроя j на гофроагрегате k.

Требования на объемы выработки каждым из гофроагрегатов накладывают следующее ограничение:

(4)

Для решения поставленной задачи применяется модифицированный симплексный метод и метод генерации столбцов, при использовании которого проверка оптимальности текущего плана заменяется исследованием вспомогательной задачи линейного раскроя. На каждой итерации результаты решения этой задачи либо подтверждают оптимальность текущего плана, либо указывают план раскроя, использование которого "улучшает" его. Столбцы симплексной таблицы рассчитываются не предварительно, а по мере надобности, в процессе решения основной задачи ЛП. Для построения нового базисного столбца используется генератор раскроев. Рассмотрим его применение для решения некоторых вариантов задачи.

Пусть вектор vi (iM) – двойственные оценки для переменных, которые дает очередной шаг расчета симплексной таблицы;

L – ширина полотна гофроагрегата;

awi – ширина заготовки iM;

yi – кратность вхождения заготовки в раскрой (yi ≥ 0, целые).

Задача линейного раскроя формулируется следующим образом:

(5)

L - ∆max ≤ awi yi ≤ L - ∆min (6)

yi ≥ 0, целые (7),

где ∆min, ∆max – величина минимальной и максимальной обязательно обрезаемой кромки,
а δ(yi, yj) – потери из-за разницы высот заготовок i и j.

Задача (5)–(7) решается методами динамического программирования. Для ускорения счета заготовки iM сортируются по убыванию значения , при генерации раскроев сначала перебираются варианты объединения для заготовок, стоящих на первых местах в отсортированном массиве. Использование сортировки значительно сокращает перебор возможных вариан-тов, что влечет за собой ускорение работы алгоритма поиска линейного раскроя, что, в свою очередь, сказывается на уменьшении времени выполнения одной итерации симплексного метода.

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

Пользователю предлагается выбрать одну из схем построения раскроев:

–  "2 заготовки" (в раскрое может быть не более двух типов заготовок);

–  "3 заготовки" (в раскрое может быть не более трех заготовок разного типа, причем на одном столе могут быть разные заготовки только в том случае, если они одинаковы по высоте);

–  "Общий случай".

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

vi yi + vj yj + vk yk – δ(yj, yk) max

L – ∆max ≤ awi yi + awj yj + awk yk ≤ L – ∆min

yi, yj, yk ≥ 0, целые.

Все варианты расчета выполняет одна процедура (решение задачи линейного раскроя для n предметов), работа которой регулируется параметрами:

–  допустимое количество различных заготовок в раскрое;

–  допустимая разница по высоте между заготовками на одном столе (в случаях "2 заготовки" и "3 заготовки" это значение равно нулю);

–  допустимое количество в одном раскрое заготовок, требующих последующей обработки, и т. д.

Благодаря такой реализации достаточно просто добавить в программу по требованию заказчика новый вариант расчета.

Как видно, метод "2 заготовки" – самый простой, "3 заготовки" – это расширение первого варианта, а "общий случай" включает в себя совокупность решений двух предыдущих и множество новых вариантов. Соответственно, чем сложнее выбранная схема, тем больше вариантов раскроя на каждом шаге может получиться (несмотря на то, что количество операций при расчете более сложного варианта больше, при мощностях современных компьютеров это практически не заметно). Поэтому если текущая ситуация в цехе позволяет использовать более сложный вариант кроя, то целесообразно сделать именно так, потому что, чем больше выбор, тем меньше, чаще всего, процент отходов.

Литература

1.  Воронин система планирования и управления производством гофротары / , // Труды ПетрГУ. Сер. Прикл. матем. и информ. Вып. 5. Петрозаводск: Изд-во ПетрГУ, 1996. С. 3–11.

2.  Воронин оптимизационные задачи в целлюлозно-бумажной промышленности / , . Петрозаводск: Изд-во ПетрГУ, 20с.

3.  Кузнецов раскроя в целлюлозно-бумажной промышленности / . СПб.: Изд-во СПбЛТА, 20с.

4.  Таха, Хэмди, А. Введение в исследование операций: Пер. с англ. / Таха, Хэмди, А.
6-е изд. М.: Издательский дом "Вильямс", 20с.