Гильотинная задача упаковки
прямоугольников в контейнеры с запрещенными областями

Математическая модель

Обозначим исходные данные задачи следующими параметрами:

n — количество предметов

l — количество контейнеров с запрещенными областями

I = {1, 2,…, n} — множество предметов

w_i и h_i, iÎI, — ширина и высота i-го предмета

M = M₁ È M₂ — множество контейнеров

M₁ = {1, 2,…, l} — контейнеры с запрещенными областями

M₂ = {1, 2,…, n} — дополнительные контейнеры одинакового размера без запрещенных областей

W_m и H_m, mÎM — ширина и высота m-го контейнера (ширина и высота дополнительных контейнеров берутся не меньше максимальной ширины и высоты предметов, поэтому достаточное количество дополнительных контейнеров равняется n)

I⁰ = {1, 2,…, K} – множество запрещенных областей

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

Введем переменные задачи:

x_i и y_i — координаты левого нижнего угла i-го предмета

g_ijm =1, если при раскрое m-го контейнера i-м горизонтальным разрезом разрезается j-я область, = 0 в противном случае

v_ijm = 1, если при раскрое m-го контейнера i-м вертикальным разрезом разрезается j-я область, = 0 в противном случае

— дина отрезаемой i-м горизонтальным разрезом от j-й области m-го контейнера

— длина отрезаемой i-м вертикальным разрезом от j-й области m-го контейнера

 — координаты и размеры областей гильотинного раскроя контейнеров на каждом этапе раскроя

С использованием введенных обозначений оптимизационная постановка задачи в терминах частично-целочисленного линейного программирования записывается следующим образом:

Зададим порядок использования контейнеров от первого к последнему:

Использование контейнеров определяется с помощью следующего неравенства:

Каждый предмет находится только в одной области гильотинного раскроя одного из контейнеров:

В каждой области гильотинного раскроя находится не более одного предмета:

Начальные условия гильотинного раскроя каждого контейнера:

На каждом этапе гильотинного раскроя совершается не более одного разреза:

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

В результате разреза добавляется новая область:

Ограничения на размеры новых областей (длины отрезаемых частей). Здесь W_max и H_max – максимальные ширина и высота контейнеров:

Ограничения, определяющие значения переменных :

 

 

 

 

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

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

ЛИТЕРАТУРА

1.     Руднев А.С. Алгоритм имитации отжига для решения задач двумерной прямоугольной упаковки в контейнеры с запрещенными областями // Дискретный анализ и исследование операций. 2010. – Т. 17, № 4. – С. 43 – 66.