BinPackingObj_PLN_DP1. Упаковка в контейнеры. Минимум контейнеров, распределение предметов. Объемное агрегированное планирование. 1 интервал.

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

Задача об упаковке в контейнеры – NP-трудная комбинаторная задача. Задача заключается в упаковке объектов предопределённой формы в конечное число контейнеров предопределённой формы таким способом, чтобы число использованных контейнеров было наименьшим или количество, или объём объектов (которые упаковывают) были наибольшими.

Дано:

•  Набор предметов предопределенной формы для упаковки в контейнеры.

•  Набор контейнеров заданного объема, которые можно использовать для упаковки.

Требуется:

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

кратко

Число установок первого типа соответствует числу вещей для упаковки.

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

Число установок второго типа соответствует числу вещей, т.е. максимально возможному числу контейнеров – предельный случай, когда каждый предмет пакуется в отдельный контейнер.

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

Критерий – минимум числа занятых контейнеров. Для минимизации числа используемых контейнеров используется критерий «Выполнение». Для этого стоимость выполнения операций, что контейнер занят равна 1. Этот критерий не регулирует ни заполнение контейнеров, ни количество свободного места в них.

кратко

Рисунок. Общий вид потоковой схемы объекта «краткая»

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

кратко

Минимизация числа контейнеров для упаковки 7 предметов.

Объем занимаемого места предметов, пакуемых в контейнер: Предмет1 – 2 куб.м., Предмет2 – 5 куб.м., Предмет3 – 4 куб.м., Предмет4 – 7 куб.м., Предмет5 – 1 куб.м., Предмет6 – 3 куб.м., Предмет7 – 8 куб.м.

кратко

Предметы для упаковки

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

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

Задействованные в упаковке контейнеры:

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

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

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

Рисунок. Ограничения на операции в интервалах времени

кратко

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

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

Упакованные в контейнеры предметы:

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

Занятое место контейнеров:

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

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

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

кратко