CutStock_SCH_DP4. Раскрой листов, рулонов, Канторович. Минимум отходов, выпуск не меньше заказов, раскрой on-line, 1 рулон. Календарное планирование. 4 отреза.

Постановка задачи

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

Дано:

•  Некоторое число исходного материала заданного размера, для разрезки на куски.

•  Заказы на определенное количество кусков заданного размера.

Требуется:

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

кратко

Число установок соответствует числу задействованных для разрезки рулонов. Каждая установка отражает отдельный рулон, который нужно разрезать на куски.

Основные операции установки, соответствуют возможным отрезам куска.

Потоками операции являются: разрезаемый рулон, ширина которого уменьшается на ширину отрезаемого куска и кусок, который получается в результате разреза.

Дополнительная операция «*_исх», не имеющая потоков, используется для отражения начальной ситуации – разрезов нет и не выбрано, необходимо ли разрезать рулон вообще.

Дополнительная операция «*_без_разреза», не имеющая потоков, используется для отражения случая, когда разрезать рулон не требуется. Эта операция может работать только весь горизонт, переход с нее на другие операции невозможен, как и переходы с разрезов на нее.

Дополнительная операция «*_стоп_разрез», не имеющая потоков, используется для отражения случая, когда разрезать рулон на один из указанных кусков уже невозможно (т.е. остается остаток).

кратко

Рисунок. фрагмент потоковой схемы объекта «с именами»

кратко

Для минимизации отходов используется критерий «Выполнение». Для этого вводятся стоимости операций по следующим правилам:

•  Стоимость операции «*_без_разреза» = 0. Нам выгодно, чтобы для получения нужного числа кусков потребовалось меньше рулонов.

•  Стоимость операции «*_стоп_разрез» = 5600. Нам очень невыгодно, когда остается остаток.

•  Стоимость операции разреза равна 5600 — <ширина куска>. Отражается остатки, возникающие в результате разреза.

В результате, при разрезе без остатка значение критерия будет равно 4*5600 = 5600. При наличии остатка вычитаемая величина будет меньше на величину остатка.

Цены операций для критерия «Выполнение»

Рисунок. Фрагмент формы – стадия, установка, операция, поток

кратко

Разрез рулона на куски

Рисунок. Фрагмент формы – стадия, установка, операция, поток

Рулон и его разрезанные куски:

Рисунок. Фрагменты формы – стадия, емкость

кратко

Фрагменты расписания

Рисунок. Фрагмент расписания выполнения операций

Разрез рулона, выпуск кусков рулона:

Рисунок. Фрагмент расписания уровня запасов в емкостях

Отрезы рулона:

Рисунок. Гистограммы изменения состояния емкостей

Выпуск кусков рулона и суммарный выпуск кусков рулона:

Рисунок. Гистограммы изменения состояния емкостей

Объяснения решения

Рисунок. Фрагмент трассы объяснений хода рассуждений Решателя DP

Размерность задачи и характеристики расчета

Размерность задачи:

Стадий 1, Установок 1, Операций 16, Емкостей 1, Интервалов 4, Переменных 64.

Характеристики расчета:

Частичных решений 51; Полных решений 1;

Шагов до 1го полного 512; до наилучшего полного 512;

Минут до 1го полного 00:00; до наилучшего полного 00:00; до оптимального 00:00;

Решатель операций KS3, сервер Intel Core i5-4570 3,2GHz.

кратко