Проблема с упаковкой ленты

Задача упаковки полосок представляет собой двумерную задачу геометрической минимизации. Дан набор прямоугольников, выровненных по осям, и полоса ограниченной ширины и бесконечной высоты. Определите бесперекрывающуюся упаковку прямоугольников в полосу, минимизирующую ее высоту. классифицируется как проблема открытого измерения . Эта проблема представляет собой проблему резки и упаковки и согласно Wäscher et al.

Эта проблема возникает в области планирования, где моделируются задания, требующие непрерывной части памяти в течение заданного периода времени. Другим примером является область промышленного производства, где прямоугольные куски необходимо вырезать из листа материала (например, ткани или бумаги), имеющего фиксированную ширину, но бесконечную длину, и хочется свести к минимуму потери материала.

Впервые эта проблема была изучена в 1980 году. Это сильно NP-трудно, и не существует алгоритма аппроксимации за полиномиальное время с отношением меньшим, чем $3/2$ пока не $P=NP$. Однако лучший коэффициент аппроксимации, достигнутый на данный момент (с помощью алгоритма полиномиального времени Харрена и др. ) является $(5/3+\varepsilon )$, ставя открытым вопрос о том, существует ли алгоритм с коэффициентом аппроксимации $3/2$.

Определение

Экземпляр $I=({\mathcal {I}},W)$ состоит задачи упаковки полосы из полосы шириной $W=1$ и бесконечной высоты, а также множество ${\mathcal {I}}$ прямоугольных предметов. Каждый предмет $i\in {\mathcal {I}}$ имеет ширину $w_{i}\in (0,1]\cap \mathbb {Q}$ и высота $h_{i}\in (0,1]\cap \mathbb {Q}$. Упаковка предметов — это отображение, которое отображает каждый левый нижний угол предмета. $i\in {\mathcal {I}}$ на позицию $(x_{i},y_{i})\in ([0,1-w_{i}]\cap \mathbb {Q} )\times \mathbb {Q} _{\geq 0}$ внутри полосы. Внутренняя точка размещенного элемента $i\in {\mathcal {I}}$ это точка из множества $\mathrm {inn} (i)=\{(x,y)\in \mathbb {Q} \times \mathbb {Q} |x_{i}<x<x_{i}+w_{i},y_{i}<y<y_{i}+h_{i}\}$. Два (размещенных) элемента перекрываются, если они имеют общую внутреннюю точку. Высота упаковки определяется как $\max\{y_{i}+h_{i}|i\in {\mathcal {I}}\}$. Цель состоит в том, чтобы найти упаковку предметов внутри полосы без перекрытия, минимизируя при этом высоту упаковки.

Это определение используется для всех алгоритмов с полиномиальным временем. Для псевдополиномиального времени и FPT -алгоритмов определение немного изменено для упрощения обозначений. В этом случае все фигурирующие величины являются целыми. В частности, ширина полосы задается произвольным целым числом, большим 1. Обратите внимание, что эти два определения эквивалентны.

Варианты

Исследовано несколько вариантов задачи об упаковке полос. Эти варианты касаются геометрии объектов, размера задачи, возможности вращения предметов и структуры упаковки.

Геометрия: В стандартном варианте этой задачи набор заданных предметов состоит из прямоугольников. В часто рассматриваемом подслучайе все элементы должны быть квадратными. Этот вариант уже рассматривался в первой статье о стриповой упаковке. Кроме того, были изучены варианты круглой или даже неправильной формы. В последнем случае это называется нерегулярной ленточной упаковкой .

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

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

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

Твердость

Задача упаковки полосами содержит задачу упаковки корзин как особый случай, когда все предметы имеют одинаковую высоту 1. По этой причине он сильно NP-труден, и не может быть алгоритма аппроксимации с полиномиальным временем , который имел бы коэффициент аппроксимации меньше, чем $3/2$ пока не $P=NP$. Кроме того, если только $P=NP$, не может быть псевдополиномиального алгоритма по времени, который имел бы коэффициент аппроксимации меньше, чем $5/4$, что можно доказать путем редукции к сильно NP-полной задаче трех разбиений . Заметим, что обе нижние оценки $3/2$ и $5/4$ также справедливо для случая, когда разрешен поворот элементов на 90 градусов. Кроме того, это было доказано Ashok et al. что полосовая упаковка является W[1]-жесткой , если параметризовать ее высотой оптимальной упаковки.

Свойства оптимальных решений

Существуют две тривиальные нижние оценки оптимальных решений. Во-первых, это высота самого большого предмета. Определять $h_{\max }(I):=\max\{h(i)|i\in {\mathcal {I}}\}$. Тогда считается, что

$OPT(I)\geq h_{\max }(I)$.

Другая нижняя граница определяется общей площадью объектов. Определять $\mathrm {AREA} ({\mathcal {I}}):=\sum _{i\in {\mathcal {I}}}h(i)w(i)$ тогда это справедливо

$OPT(I)\geq \mathrm {AREA} ({\mathcal {I}})/W$.

Следующие две нижние границы учитывают тот факт, что некоторые элементы не могут быть размещены рядом друг с другом в полосе и могут быть вычислены в ${\mathcal {O}}(n\log(n))$. Для первой нижней границы предположим, что элементы отсортированы по невозрастающей высоте. Определять $k:=\max\{i:\sum _{j=1}^{k}w(j)\leq W\}$. Для каждого $l>k$ определять $i(l)\leq k$ первый индекс такой, что $w(l)+\sum _{j=1}^{i(l)}w(j)>W$. Тогда считается, что

$OPT(I)\geq \max\{h(l)+h(i(l))|l>k\wedge w(l)+\sum _{j=1}^{i(l)}w(j)>W\}$.

Для второй нижней границы разделите набор элементов на три набора. Позволять $\alpha \in [1,W/2]\cap \mathbb {N}$ и определить ${\mathcal {I}}_{1}(\alpha ):=\{i\in {\mathcal {I}}|w(i)>W-\alpha \}$, ${\mathcal {I}}_{2}(\alpha ):=\{i\in {\mathcal {I}}|W-\alpha \geq w(i)>W/2\}$, и ${\mathcal {I}}_{3}(\alpha ):=\{i\in {\mathcal {I}}|W/2\geq w(i)>\alpha \}$. Тогда считается, что

$OPT(I)\geq \max _{\alpha \in [1,W/2]\cap \mathbb {N} }{\Bigg \{}\sum _{i\in {\mathcal {I}}_{1}(\alpha )\cup {\mathcal {I}}_{2}(\alpha )}h(i)+\left({\frac {\sum _{i\in {\mathcal {I}}_{3}(\alpha )h(i)w(i)-\sum _{i\in {\mathcal {I}}_{2}(\alpha )}(W-w(i))h(i)}}{W}}\right)_{+}{\Bigg \}}$, где $(x)_{+}:=\max\{x,0\}$ для каждого $x\in \mathbb {R}$.

С другой стороны, Штейнберг показал, что высота оптимального решения может быть ограничена сверху величиной

$OPT(I)\leq 2\max\{h_{\max }(I),\mathrm {AREA} ({\mathcal {I}})/W\}.$

Точнее, он показал, что при $W\geq w_{\max }({\mathcal {I}})$ и $H\geq h_{\max }(I)$ затем предметы ${\mathcal {I}}$ можно поместить в коробку шириной $W$ и высота $H$ если

$WH\geq 2\mathrm {AREA} ({\mathcal {I}})+(2w_{\max }({\mathcal {I}})-W)_{+}(2h_{\max }(I)-H)_{+}$, где $(x)_{+}:=\max\{x,0\}$.

Алгоритмы аппроксимации полиномиального времени

Поскольку эта задача является NP-трудной, аппроксимационные алгоритмы для нее были изучены . Большинство эвристических подходов имеют коэффициент аппроксимации между $3$ и $2$. Нахождение алгоритма с соотношением ниже $2$ кажется сложным и сложность соответствующих алгоритмов возрастает относительно времени их работы и их описания. Наименьший коэффициент аппроксимации, достигнутый на данный момент, равен $(5/3+\varepsilon )$.

Обзор аппроксимаций полиномиального времени

Год	Имя	Гарантия аппроксимации	Источник
1980	Снизу вверх по левому краю (BL)	$3OPT(I)$	Бейкер и др.
1980	Следующая установка уменьшающейся высоты (NFDH)	$2OPT(I)+h_{\max }(I)\leq 3OPT(I)$	Коффман и др.
	Уменьшающаяся высота первой подгонки (FFDH)	$1.7OPT(I)+h_{\max }(I)\leq 2.7OPT(I)$
	Раздельная посадка (SF)	$1.5OPT(I)+2h_{\max }(I)$
1980		$2OPT(I)+h_{\max }(I)/2\leq 2.5OPT(I)$	Слейтор
1981	Сплит-алгоритм (SP)	$3OPT(I)$	Голаны
	Смешанный алгоритм	$(4/3)OPT(I)+7{\frac {1}{18}}h_{\max }(I)$
1981	Вверх-Вниз (UD)	$(5/4)OPT(I)+6{\frac {7}{8}}h_{\max }(I)$	Бейкер и др.
1994	Обратная посадка	$2OPT(I)$	Ширмейер
1997		$2OPT(I)$	Стейнберг
2000		$(1+\varepsilon )OPT(I)+{\mathcal {O}}(1/\varepsilon ^{2})h_{\max }(I)$	Кеньон, Ремила
2009		$1.9396OPT(I)$	Их, ван Сти
2009		$(1+\varepsilon )OPT(I)+h_{\max }(I)$	Янсен, Солис-Оба
2011		$(1+\varepsilon )OPT(I)+{\mathcal {O}}(\log(1/\varepsilon )/\varepsilon )h_{\max }(I)$	Бужере и др.
2012		$(1+\varepsilon )OPT(I)+{\mathcal {O}}(\log(1/\varepsilon )/\varepsilon )h_{\max }(I)$	Свириденко
2014		$(5/3+\varepsilon )OPT(I)$	Харрен и др.

Снизу вверх по левому краю (BL)

Пример решений, сгенерированных алгоритмом «Снизу вверх и выравниванием по левому краю».

Этот алгоритм был впервые описан Бейкером и др. Это работает следующим образом:

Позволять $L$ быть последовательностью прямоугольных элементов. Алгоритм повторяет последовательность в заданном порядке. По каждому рассматриваемому пункту $r\in L$, он ищет самое нижнее положение для его размещения, а затем сдвигает его как можно дальше влево. Следовательно, он помещает $r$ в самой нижней левой возможной координате $(x,y)$ в полосе.

Этот алгоритм имеет следующие свойства:

• Коэффициент аппроксимации этого алгоритма не может быть ограничен константой. Точнее, они показали, что для каждого $M>0$ существует список $L$ прямоугольных элементов, упорядоченных по увеличению ширины так, что $BL(L)/OPT(L)>M$, где $BL(L)$ — высота упаковки, созданной алгоритмом BL, и $OPT(L)$ – высота оптимального решения для $L$.
• Если элементы упорядочены по уменьшению ширины, то $BL(L)/OPT(L)\leq 3$.
• Если все элементы квадратные и упорядочены по уменьшению ширины, то $BL(L)/OPT(L)\leq 2$.
• Для любого $\delta >0$, существует список $L$ прямоугольников, упорядоченных по уменьшению ширины, таких, что $BL(L)/OPT(L)>3-\delta$.
• Для любого $\delta >0$, существует список $L$ квадратов, упорядоченных по уменьшению ширины, таких, что $BL(L)/OPT(L)>2-\delta$.
• Для каждого $\varepsilon \in (0,1]$, существует экземпляр, содержащий только квадраты, где каждый порядок квадратов $L$ имеет соотношение $BL(L)/OPT(L)>{\frac {12}{11+\varepsilon }}$, т. е. существуют случаи, когда BL не находит оптимума даже при переборе всех возможных порядков элементов. В 2024 году эта нижняя граница была улучшена Хугарди и Зондерваном до $BL(L)/OPT(L)>{\frac {4}{3+\varepsilon }}$.

Следующая установка с уменьшающейся высотой (NFDH)

Пример NFDH и FFDH, примененный к одному и тому же экземпляру.

Этот алгоритм был впервые описан Коффманом и др. в 1980 году и работает следующим образом:

Позволять ${\mathcal {I}}$ — заданный набор прямоугольных элементов. Сначала алгоритм сортирует элементы в порядке невозрастания высоты. Затем, начиная с позиции $(0,0)$, алгоритм размещает элементы в полосе рядом друг с другом до тех пор, пока следующий элемент не перекроет правую границу полосы. На этом этапе алгоритм определяет новый уровень вверху самого высокого элемента текущего уровня и размещает элементы рядом друг с другом на этом новом уровне.

Этот алгоритм имеет следующие свойства:

• Время работы может быть ограничено ${\mathcal {O}}(|{\mathcal {I}}|\log(|{\mathcal {I}}|))$ и если элементы уже отсортированы даже по ${\mathcal {O}}(|{\mathcal {I}}|)$.
• Для каждого набора предметов ${\mathcal {I}}$, он производит упаковку высотой $NFDH({\mathcal {I}})\leq 2OPT({\mathcal {I}})+h_{\max }\leq 3OPT({\mathcal {I}})$, где $h_{\max }$ это наибольшая высота предмета в ${\mathcal {I}}$.
• Для каждого $\varepsilon >0$ существует набор прямоугольников ${\mathcal {I}}$ такой, что $NFDH({\mathcal {I}}|)>(2-\varepsilon )OPT({\mathcal {I}}).$
• Созданная упаковка представляет собой гильотинную упаковку. Это означает, что предметы можно получить путем последовательной горизонтальной или вертикальной резки от края до края.

Уменьшение высоты при первой подгонке (FFDH)

Этот алгоритм, впервые описанный Coffman et al. в 1980 году работает аналогично алгоритму NFDH. Однако при размещении следующего элемента алгоритм сканирует уровни снизу вверх и помещает элемент на первый уровень, на котором он поместится. Новый уровень открывается только в том случае, если предмет не помещается ни в один из предыдущих.

Этот алгоритм имеет следующие свойства:

• Время работы может быть ограничено ${\mathcal {O}}(|{\mathcal {I}}|^{2})$, поскольку существует не более $|{\mathcal {I}}|$ уровни.
• Для каждого набора предметов ${\mathcal {I}}$ он производит упаковку высотой $FFDH({\mathcal {I}})\leq 1.7OPT({\mathcal {I}})+h_{\max }\leq 2.7OPT({\mathcal {I}})$, где $h_{\max }$ это наибольшая высота предмета в ${\mathcal {I}}$.
• Позволять $m\geq 2$. Для любого набора предметов ${\mathcal {I}}$ и полоска шириной $W$ такой, что $w(i)\leq W/m$ для каждого $i\in {\mathcal {I}}$, он утверждает, что $FFDH({\mathcal {I}})\leq \left(1+1/m\right)OPT({\mathcal {I}})+h_{\max }$. Более того, для каждого $\varepsilon >0$, существует такой набор элементов ${\mathcal {I}}$ с $FFDH({\mathcal {I}})>\left(1+1/m-\varepsilon \right)OPT({\mathcal {I}})$.
• Если все элементы в ${\mathcal {I}}$ являются квадратами, то считается, что $FFDH({\mathcal {I}})\leq (3/2)OPT({\mathcal {I}})+h_{\max }$. Более того, для каждого $\varepsilon >0$, существует набор квадратов ${\mathcal {I}}$ такой, что $FFDH({\mathcal {I}})>\left(3/2-\varepsilon \right)OPT({\mathcal {I}})$.
• Созданная упаковка представляет собой гильотинную упаковку. Это означает, что предметы можно получить путем последовательной горизонтальной или вертикальной резки от края до края.

Алгоритм расщепления (SF)

Этот алгоритм был впервые описан Коффманом и др. Для заданного набора предметов ${\mathcal {I}}$ и полоска шириной $W$, это работает следующим образом:

1. Определенный $m\in \mathbb {N}$, наибольшее целое число, такое, что данные прямоугольники имеют ширину $W/m$ или меньше.
2. Разделять ${\mathcal {I}}$ на два набора ${\mathcal {I}}_{wide}$ и ${\mathcal {I}}_{narrow}$, такой, что ${\mathcal {I}}_{wide}$ содержит все предметы $i\in {\mathcal {I}}$ с шириной $w(i)>W/(m+1)$ пока ${\mathcal {I}}_{narrow}$ содержит все элементы с $w(i)\leq W/(m+1)$.
3. Заказ ${\mathcal {I}}_{wide}$ и ${\mathcal {I}}_{narrow}$ за счет неувеличения высоты.
4. Упакуйте вещи в ${\mathcal {I}}_{wide}$ с алгоритмом FFDH.
5. Измените порядок уровней/полок, построенных FFDH, так, чтобы все полки общей шириной превышали $W(m+1)/(m+2)$ находятся ниже более узких.
6. Получается прямоугольная область $R$ с $W/(m+2)$, рядом с более узкими уровнями/полками, на которых нет предметов.
7. Используйте алгоритм FFDH для упаковки элементов в ${\mathcal {I}}_{narrow}$ используя территорию $R$ также.

Этот алгоритм имеет следующие свойства:

• Для каждого набора предметов ${\mathcal {I}}$ и соответствующий $m$, он утверждает, что $SF({\mathcal {I}})\leq (m+2)/(m+1)OPT({\mathcal {I}})+2h_{\max }$. Обратите внимание, что для $m=1$, он утверждает, что $SF({\mathcal {I}})\leq (3/2)OPT({\mathcal {I}})+2h_{\max }$
• Для каждого $\varepsilon >0$, есть набор предметов ${\mathcal {I}}$ такой, что $SF({\mathcal {I}})>\left((m+2)/(m+1)-\varepsilon \right)OPT({\mathcal {I}})$.

Алгоритм Слейтора

Для заданного набора предметов ${\mathcal {I}}$ и полоска шириной $W$, это работает следующим образом:

1. Найдите все элементы шириной больше $W/2$ и сложите их внизу полоски (в произвольном порядке). Назовите общую высоту этих предметов $h_{0}$. Все остальные элементы будут размещены выше. $h_{0}$.
2. Отсортируйте все оставшиеся элементы в порядке невозрастания высоты. Элементы будут размещены в этом порядке.
3. Рассмотрим горизонтальную линию в точке $h_{0}$ в качестве полки. Алгоритм размещает предметы на этой полке в порядке невозрастания высоты до тех пор, пока не останется ни одного предмета или не подойдет следующий.
4. Нарисуйте вертикальную линию в $W/2$, который разрезает полосу на две равные половины.
5. Позволять $h_{l}$ быть самой высокой точкой, покрытой любым предметом в левой половине и $h_{r}$ соответствующую точку на правой половине. Нарисуйте два горизонтальных отрезка длиной $W/2$ в $h_{l}$ и $h_{r}$ через левую и правую половину полосы. Эти две строки создают новые полки, на которых алгоритм будет размещать предметы, как на шаге 3. Выберите половину с нижней полкой и размещайте предметы на этой полке до тех пор, пока ни один другой предмет не подойдет. Повторяйте этот шаг, пока не останется ни одного элемента.

Этот алгоритм имеет следующие свойства:

• Время работы может быть ограничено ${\mathcal {O}}(|{\mathcal {I}}|\log(|{\mathcal {I}}|))$ и если элементы уже отсортированы даже по ${\mathcal {O}}(|{\mathcal {I}}|)$.
• Для каждого набора предметов ${\mathcal {I}}$ он производит упаковку высотой $A({\mathcal {I}})\leq 2OPT({\mathcal {I}})+h_{\max }/2\leq 2.5OPT({\mathcal {I}})$, где $h_{\max }$ это наибольшая высота предмета в ${\mathcal {I}}$.

Алгоритм разделения (SP)

Этот алгоритм является расширением подхода Слейтора и впервые был описан Голаном. Он размещает элементы в невозрастающем порядке ширины. Интуитивная идея состоит в том, чтобы разделить полосу на подполосы при размещении некоторых предметов. По возможности алгоритм помещает текущий элемент $i$ рядом с уже размещенным элементом $j$. В этом случае соответствующая подполоса разбивается на две части: одна содержит первый элемент. $j$ а другой содержит текущий элемент $i$. Если это невозможно, он помещает $i$ поверх уже размещенного элемента и не разделяет подполосу.

Этот алгоритм создает набор С из субполос. Для каждой субполосы s ∈ S мы знаем его левый нижний угол s.xposition и позиция , его ширина ширина , горизонтальные линии, параллельные верхней и нижней границе элемента, помещенного последним внутри этой подполосы. ужин и помедленнее , а также его ширина с.itemWidth .

function Split Algorithm (SP) is
    input: items  I, width of the strip W
    output: A packing of the items
    Sort I in nonincreasing order of widths;
    Define empty list S of sub-strips;
    Define a new sub-strip s with s.xposition = 0, s.yposition = 0, s.width = W, s.lower = 0, s.upper = 0, s.itemWidth = W;
    Add s to S;
    while I not empty do
        i := I.pop(); Removes widest item from I
        Define new list S_2 containing all the substrips with s.width - s.itemWidth ≥ i.width; 
        S_2 contains all sub-strips where i fits next to the already placed item
        if S_2 is empty then
            In this case, place the item on top of another one.
            Find the sub-strip s in S with smallest s.upper; i.e. the least filled sub-strip
            Place i at position (s.xposition, s.upper);
            Update s: s.lower := s.upper; s.upper := s.upper+i.height; s.itemWidth := i.width;
        else 
            In this case, place the item next to another one at the same level and split the corresponding sub-strip at this position.
            Find s ∈ S_2 with the smallest s.lower;
            Place i at position (s.xposition + s.itemWidth, s.lower);
            Remove s from S;
            Define two new sub-strips s1 and s2 with 
            s1.xposition = s.xposition, s1.yposition = s.upper, s1.width = s.itemWidth, s1.lower = s.upper, s1.upper = s.upper, s1.itemWidth = s.itemWidth;
            s2.xposition = s.xposition+s.itemWidth, s2.yposition = s.lower, s2.width = s.width - s.itemWidth, s2.lower = s.lower, s2.upper = s.lower + i.height, s2.itemWidth = i.width;
            S.add(s1,s2);
    return 
end function

Этот алгоритм имеет следующие свойства:

• Время работы может быть ограничено ${\mathcal {O}}(|{\mathcal {I}}|^{2})$ поскольку количество подполос ограничено $|{\mathcal {I}}|$.
• Для любого набора предметов ${\mathcal {I}}$ он утверждает, что $SP({\mathcal {I}})\leq 2OPT({\mathcal {I}})+h_{\max }\leq 3OPT({\mathcal {I}})$.
• Для любого $\varepsilon >0$, существует набор элементов ${\mathcal {I}}$ такой, что $SP({\mathcal {I}})>(3-\varepsilon )OPT({\mathcal {I}})$.
• Для любого $\varepsilon >0$ и $C>0$, существует набор элементов ${\mathcal {I}}$ такой, что $SP({\mathcal {I}})>(2-\varepsilon )OPT({\mathcal {I}})+C$.

Обратная посадка (RF)

Этот алгоритм был впервые описан Ширмейером. Описание этого алгоритма нуждается в некоторых дополнительных обозначениях. Для размещенного предмета $i\in {\mathcal {I}}$, его левый нижний угол обозначается $(a_{i},c_{i})$ и его верхний правый угол $(b_{i},d_{i})$.

Дан набор предметов ${\mathcal {I}}$ и полоска шириной $W$, это работает следующим образом:

1. Сложите все прямоугольники шириной больше $W/2$ друг на друга (в случайном порядке) внизу полоски. Обозначим через $H_{0}$ высота этого стека. Все остальные предметы будут упакованы выше $H_{0}$.
2. Отсортируйте оставшиеся элементы в порядке неувеличения высоты и рассмотрите элементы в этом порядке в следующих шагах. Позволять $h_{\max }$ быть высотой самого высокого из этих оставшихся предметов.
3. Поместите предметы один за другим, выровняв их по левому краю, на полке, определенной $H_{0}$ до тех пор, пока на этой полке не окажется другого предмета или не останется ни одного предмета. Назовите эту полку первым уровнем .
4. Позволять $h_{1}$ быть высотой самого высокого неупакованного предмета. Определите новую полку в $H_{0}+h_{\max }+h_{1}$. Алгоритм заполнит эту полку справа налево, выравнивая предметы вправо так, чтобы предметы касались этой полки своим верхом. Назовем эту полку вторым обратным уровнем .
5. Размещайте предметы на двух полках по принципу First-Fit, т. е. размещая предметы на первом уровне там, где они подходят, и на втором в противном случае. Продолжайте до тех пор, пока не закончатся предметы или общая ширина предметов на второй полке не станет не менее $W/2$.
6. Смещайте второй реверс-уровень вниз до тех пор, пока предмет из него не коснется предмета первого уровня. Определять $H_{1}$ как новое вертикальное положение сдвинутой полки. Позволять $f$ и $s$ быть самой подходящей парой трогательных предметов с $f$ размещены на первом уровне и $s$ на втором обратном уровне. Определять $x_{r}:=\max(b_{f},b_{s})$.
7. Если $x_{r}<W/2$ затем $s$ — последний прямоугольник, помещенный на второй обратный уровень. Все остальные предметы с этого уровня сдвиньте дальше вниз (все на столько же), пока первый из них не коснется предмета с первого уровня. Алгоритм снова определяет самую правую пару соприкасающихся предметов. $f'$ и $s'$. Определять $h_{2}$ как величина, на которую полка была сдвинута вниз.
   1. Если $h_{2}\leq h(s)$ затем сдвинь $s$ влево, пока не коснется другого предмета или границы полосы. Определите третий уровень вверху $s'$.
   2. Если $h_{2}>h(s)$ затем сдвинь $s$ определить третий уровень вверху $s'$. Место $s$ на этом третьем уровне выровнен по левому краю, так что он касается элемента первого уровня слева от него.
8. Продолжайте упаковывать предметы, используя эвристику First-Fit. Каждый последующий уровень (начиная с третьего уровня) определяется горизонтальной линией, проходящей через верх самого большого элемента предыдущего уровня. Обратите внимание, что первый предмет, помещенный на следующем уровне, может касаться не границы полосы левой стороной, а предмета первого уровня или предмета. $s$.

Этот алгоритм имеет следующие свойства:

• Время работы может быть ограничено ${\mathcal {O}}(|{\mathcal {I}}|^{2})$, поскольку существует не более $|{\mathcal {I}}|$ уровни.
• Для каждого набора предметов ${\mathcal {I}}$ он производит упаковку высотой $RF({\mathcal {I}})\leq 2OPT({\mathcal {I}})$.

Алгоритм Штейнберга (ST)

Алгоритм Стейнберга является рекурсивным. Дан набор прямоугольных предметов. ${\mathcal {I}}$ и прямоугольную целевую область шириной $W$ и высота $H$, он предлагает четыре правила сокращения, которые помещают некоторые элементы и оставляют меньшую прямоугольную область с теми же свойствами, что и раньше, в отношении остаточных элементов. Рассмотрим следующие обозначения: Учитывая набор элементов ${\mathcal {I}}$ мы обозначаем через $h_{\max }({\mathcal {I}})$ самая высокая высота предмета в ${\mathcal {I}}$, $w_{\max }({\mathcal {I}})$ наибольшая ширина элемента, появляющаяся в ${\mathcal {I}}$ и по $\mathrm {AREA} ({\mathcal {I}}):=\sum _{i\in {\mathcal {I}}}w(i)h(i)$ общая площадь этих предметов. Стейнбергс показывает, что если

$h_{\max }({\mathcal {I}})\leq H$, $w_{\max }({\mathcal {I}})\leq W$, и $\mathrm {AREA} ({\mathcal {I}})\leq W\cdot H-(2h_{\max }({\mathcal {I}})-h)_{+}(2w_{\max }({\mathcal {I}})-W)_{+}$, где $(a)_{+}:=\max\{0,a\}$,

тогда все элементы можно разместить внутри целевой области размера $W\times H$. Каждое правило сокращения будет создавать меньшую целевую область и подмножество элементов, которые необходимо разместить. Если условие выше выполняется до запуска процедуры, то созданная подзадача также будет иметь это свойство.

Процедура 1 : Ее можно применять, если $w_{\max }({\mathcal {I}}')\geq W/2$.

1. Найдите все предметы $i\in {\mathcal {I}}$ с шириной $w(i)\geq W/2$ и удалить их из ${\mathcal {I}}$.
2. Отсортируйте их по неувеличению ширины и поместите их с выравниванием по левому краю внизу целевой области. Позволять $h_{0}$ быть их общая высота.
3. Найдите все предметы $i\in {\mathcal {I}}$ с шириной $h(i)>H-h_{0}$. Удалите их из ${\mathcal {I}}$ и поместите их в новый набор ${\mathcal {I}}_{H}$.
4. Если ${\mathcal {I}}_{H}$ пусто, определите новый целевой регион как область выше $h_{0}$, то есть имеет высоту $H-h_{0}$ и ширина $W$. Решите проблему, состоящую из этой новой целевой области и сокращенного набора элементов, с помощью одной из процедур.
5. Если ${\mathcal {I}}_{H}$ не пуст, отсортируйте его по невозрастающей высоте и поместите элементы по одному в правом верхнем углу целевой области. Позволять $w_{0}$ быть общей шириной этих элементов. Определите новую целевую область шириной $W-w_{0}$ и высота $H-h_{0}$ в левом верхнем углу. Решите проблему, состоящую из этой новой целевой области и сокращенного набора элементов, с помощью одной из процедур.

Процедура 2 : Ее можно применять, если выполняются следующие условия: $w_{\max }({\mathcal {I}})\leq W/2$, $h_{\max }({\mathcal {I}})\leq H/2$, и существуют два разных элемента $i,i'\in {\mathcal {I}}$ с $w(i)\geq W/4$, $w(i')\geq W/4$, $h(i)\geq H/4$, $h(i')\geq H/4$ и $2(\mathrm {AREA} ({\mathcal {I}})-w(i)h(i)-w(i')h(i'))\leq (W-\max\{w(i),w(i')\})H$.

1. Находить $i$ и $i'$ и удалить их из ${\mathcal {I}}$.
2. Поместите более широкий в нижний левый угол целевой области, а более узкий — по левому краю вверху первого.
3. Определите новую целевую область справа от этих обоих элементов так, чтобы она имела ширину $W-\max\{w(i),w(i')\}$ и высота $H$.
4. Поместите оставшиеся предметы в ${\mathcal {I}}$ в новую целевую область с помощью одной из процедур.

Процедура 3 : Ее можно применять, если выполняются следующие условия: $w_{\max }({\mathcal {I}})\leq W/2$, $h_{\max }({\mathcal {I}})\leq H/2$, $|{\mathcal {I}}|>1$, а при сортировке элементов по уменьшению ширины существует индекс $m$ такой, что при определении ${\mathcal {I'}}$ как первый $m$ предметы, которые он содержит, которые $\mathrm {AREA} ({\mathcal {I}})-WH/4\leq \mathrm {AREA} ({\mathcal {I'}})\leq 3WH/8$ а также $w(i_{m+1})\leq W/4$

1. Набор $W_{1}:=\max {W/2,2\mathrm {AREA} ({\mathcal {I'}})/H}$.
2. Определите две новые прямоугольные целевые области: одну в левом нижнем углу исходной, с высотой $H$ и ширина $W_{1}$ а другой слева от него высотой $H$ и ширина $W-W_{1}$.
3. Используйте одну из процедур для размещения элементов в ${\mathcal {I'}}$ в первую новую целевую область и предметы в ${\mathcal {I}}\setminus {\mathcal {I'}}$ во второй.

Обратите внимание, что процедуры с 1 по 3 имеют симметричную версию при изменении высоты и ширины элементов и целевой области.

Процедура 4 : Ее можно применять, если выполняются следующие условия: $w_{\max }({\mathcal {I}})\leq W/2$, $h_{\max }({\mathcal {I}})\leq H/2$, и существует элемент $i\in {\mathcal {I}}$ такой, что $w(i)h(i)\geq \mathrm {AREA} ({\mathcal {I}})-WH/4$.

1. Поместите предмет $i$ в левом нижнем углу целевой области и удалите ее из ${\mathcal {I}}$.
2. Определите новую целевую область справа от этого элемента так, чтобы она имела ширину $W-w(i)$ и высота $H$ и поместите оставшиеся элементы внутри этой области, используя одну из процедур.

Этот алгоритм имеет следующие свойства:

• Время работы может быть ограничено ${\mathcal {O}}(|{\mathcal {I}}|\log(|{\mathcal {I}}|)^{2}/\log(\log(|{\mathcal {I}}|)))$.
• Для каждого набора предметов ${\mathcal {I}}$ он производит упаковку высотой $ST({\mathcal {I}})\leq 2OPT({\mathcal {I}})$.

Алгоритмы аппроксимации псевдополиномиального времени

Чтобы улучшить нижнюю границу $3/2$ для алгоритмов с полиномиальным временем рассмотрены псевдополиномиальные алгоритмы для задачи упаковки полос. При рассмотрении алгоритмов этого типа все размеры предметов и полосы задаются как интегралы. Кроме того, ширина полосы $W$ разрешено появляться полиномиально во время выполнения. Обратите внимание, что это больше не считается полиномиальным временем работы, поскольку в данном случае ширина полосы требует размера кодирования $\log(W)$.

Разработанные алгоритмы псевдополиномиального времени в основном используют тот же подход. Показано, что каждое оптимальное решение можно упростить и преобразовать в решение, имеющее одну из постоянного числа структур. Затем алгоритм повторяет все эти структуры и помещает элементы внутрь, используя линейное и динамическое программирование. Наилучшее соотношение, достигнутое на данный момент, составляет $(5/4+\varepsilon )OPT(I)$. в то время как не может быть псевдополиномиального алгоритма по времени с соотношением лучше, чем $5/4$ пока не $P=NP$

Обзор псевдополиномиальных аппроксимаций времени

Год	Коэффициент аппроксимации	Источник	Комментарий
2010	$(3/2+\varepsilon )$	Янсен, Тёле
2016	$(7/5+\varepsilon )$	Надирадзе, Визе
2016	$(4/3+\varepsilon )$	Гальвес, Грандони, Ингала, Хан	также для поворота на 90 градусов
2017	$(4/3+\varepsilon )$	Янсен, Рау
2019	$(5/4+\varepsilon )$	Янсен, Рау	также для поворотов на 90 градусов и смежных формовочных работ

Онлайн-алгоритмы

В онлайн-варианте стрип-упаковки товары приходят со временем. Когда предмет прибывает, его необходимо разместить немедленно, прежде чем станет известен следующий предмет. Были рассмотрены два типа онлайн-алгоритмов. В первом варианте не допускается изменение упаковки после размещения товара. Во втором случае товары могут быть переупакованы при поступлении другого товара. Этот вариант называется моделью миграции.

Качество онлайн-алгоритма измеряется (абсолютным) коэффициентом конкуренции.

$\mathrm {sup} _{I}A(I)/OPT(I)$,

где $A(I)$ соответствует решению, сгенерированному онлайн-алгоритмом, и $OPT(I)$ соответствует размеру оптимального решения. Помимо коэффициента абсолютной конкуренции, изучался асимптотический коэффициент конкуренции онлайн-алгоритмов. Для экземпляров $I$ с $h_{\max }(I)\leq 1$ это определяется как

$\lim \mathrm {sup} _{OPT(I)\rightarrow \infty }A(I)/OPT(I)$.

Обратите внимание, что все экземпляры можно масштабировать так, что $h_{\max }(I)\leq 1$.

Обзор онлайн-алгоритмов без миграции

Год	Конкурентное соотношение	Асимптотическое соотношение конкуренции	Источник
1983	6.99	$\approx 1.7$	Бейкер и Шварц
1997		$1.69+\varepsilon$	Цирик и Вегингер
2007	6.6623		Хуринк и Паулюс
2009	6.6623		Йе, Хан и Чжан
2007		$1.58889$	Хан и др. + Шелк

В рамках Han et al. применимо в онлайн-настройке, если онлайн-упаковка контейнера алгоритм принадлежит к классу Super Harmonic. Таким образом, онлайн-алгоритм упаковки контейнеров Сейдена Гармоника++ подразумевает алгоритм онлайн-упаковки полос с асимптотическим отношением 1,58889.

Обзор нижних границ онлайн-алгоритмов без миграции

Год	Конкурентное соотношение	Асимптотическое соотношение конкуренции	Источник	Комментарий
1982	$2$		Браун, Бейкер и Кацев
2006	2.25		Йоханнес	также справедливо для задачи планирования параллельных задач
2007	2.43		Хуринк и Паулюс	также справедливо для задачи планирования параллельных задач
2009	2.457		Керн и Паулюс
2012		$1.5404$	Балог и Бекеси	нижняя граница из-за основной проблемы упаковки контейнеров
2016	2.618		Ю, Мао и Сяо