CutStockPatt_PLN_DP1. Раскрой листов, рулонов, Канторович. Минимум отходов, выпуск не меньше заказов, заданы карты раскроя. Объемное агрегированное планирование. 1 рулон. * В процессе оформления.

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

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

Дано:

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

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

Требуется:

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

кратко

Одна установка, которая отражает выбор одной из карт раскроя для разрезки одного рулона.

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

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

•  Кроме того, карты раскроя являются неупорядоченными, т.е. не учитывается порядок разрезов в одной карте раскроя (карта ->1520->1880->2200 эквивалентна картам ->1520->2200->1880, ->1880->1520->2200, ->1880->2200->1520, ->2200->1520->1880, ->2200->1880->1520)

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

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

Интервалы отражают последовательно разрезаемые на куски рулоны.

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

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

•  Стоимость операций выбора карт раскроя равна получаемому от разреза по данной карте раскроя остатку. Наша цель минимизировать остатки.

кратко

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

кратко