CutStockPatt_SCH_DP219Pareto. Раскрой листов, рулонов, Канторович. Минимум отходов, выпуск не меньше заказов, заданы карты раскроя. Календарное планирование. 219 рулонов. 2 критерия, область Парето.

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

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

Дано:

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

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

Требуется:

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

кратко

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

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

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

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

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

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

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

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

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

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

кратко

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

кратко

Используются 2 критерия одновременно, строится область Парето по решениям за 5 минут.

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

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

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

Для минимизации числа разрезаемых рулонов используется критерий «Переключение». Для этого все переходы на карты разрезов, кроме переходов на операцию «Раскрой_нет» штрафуется заданной стоимостью использования рулона.

Цены операций для критерия «Выполнение», матрица переналадок для критерия «Переключение»

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

кратко

Раскрой рулонов

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

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

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

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

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

кратко

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

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

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

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

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

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

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

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

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

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

кратко