Проблема с упаковкой ленты
Задача упаковки полосок представляет собой двумерную задачу геометрической минимизации. Дан набор прямоугольников, выровненных по осям, и полоса ограниченной ширины и бесконечной высоты. Определите бесперекрывающуюся упаковку прямоугольников в полосу, минимизирующую ее высоту. классифицируется как проблема открытого измерения . Эта проблема представляет собой проблему резки и упаковки и согласно Wäscher et al. [1]
Эта проблема возникает в области планирования, где моделируются задания, требующие непрерывной части памяти в течение заданного периода времени. Другим примером является область промышленного производства, где прямоугольные куски необходимо вырезать из листа материала (например, ткани или бумаги), имеющего фиксированную ширину, но бесконечную длину, и хочется свести к минимуму потери материала.
Впервые эта проблема была изучена в 1980 году. [2] Это сильно NP-трудно, и не существует алгоритма аппроксимации за полиномиальное время с отношением меньшим, чем пока не . Однако лучший коэффициент аппроксимации, достигнутый на данный момент (с помощью алгоритма полиномиального времени Харрена и др. [3] ) является , ставя открытым вопрос о том, существует ли алгоритм с коэффициентом аппроксимации .
Определение
[ редактировать ]Экземпляр состоит задачи упаковки полосы из полосы шириной и бесконечной высоты, а также множество прямоугольных предметов. Каждый предмет имеет ширину и высота . Упаковка предметов — это отображение, которое отображает каждый левый нижний угол предмета. на позицию внутри полосы. Внутренняя точка размещенного элемента это точка из множества . Два (размещенных) элемента перекрываются, если они имеют общую внутреннюю точку. Высота упаковки определяется как . Цель состоит в том, чтобы найти упаковку предметов внутри полосы без перекрытия, минимизируя при этом высоту упаковки.
Это определение используется для всех алгоритмов с полиномиальным временем. Для псевдополиномиального времени и FPT -алгоритмов определение немного изменено для упрощения обозначений. В этом случае все фигурирующие величины являются целыми. В частности, ширина полосы задается произвольным целым числом, большим 1. Обратите внимание, что эти два определения эквивалентны.
Варианты
[ редактировать ]Исследовано несколько вариантов задачи об упаковке полос. Эти варианты касаются геометрии объектов, размера задачи, возможности вращения предметов и структуры упаковки. [4]
Геометрия: В стандартном варианте этой задачи набор заданных предметов состоит из прямоугольников. В часто рассматриваемом подслучайе все элементы должны быть квадратными. Этот вариант уже рассматривался в первой статье о стриповой упаковке. [2] Кроме того, были изучены варианты круглой или даже неправильной формы. В последнем случае это называется нерегулярной ленточной упаковкой .
Измерение: Если не указано иное, проблема упаковки полосок является двумерной проблемой. Однако оно также изучалось в трех или даже более измерениях. В данном случае объекты представляют собой гиперпрямоугольники , а полоса разомкнута в одном измерении и ограничена в остаточных.
Вращение. В классической задаче об упаковке полос элементы не могут вращаться. Однако были изучены варианты, где допускается поворот на 90 градусов или даже на произвольный угол.
Структура: В общей задаче упаковки полос структура упаковки не имеет значения. Однако существуют приложения, предъявляющие явные требования к структуре упаковки. Одним из таких требований является возможность вырезать изделия из полосы горизонтальными или вертикальными разрезами по краям. Упаковки, допускающие такую резку, называются гильотинными упаковками .
Твердость
[ редактировать ]Задача упаковки полосами содержит задачу упаковки корзин как особый случай, когда все предметы имеют одинаковую высоту 1. По этой причине он сильно NP-труден, и не может быть алгоритма аппроксимации с полиномиальным временем , который имел бы коэффициент аппроксимации меньше, чем пока не . Кроме того, если только , не может быть псевдополиномиального алгоритма по времени, который имел бы коэффициент аппроксимации меньше, чем , [5] что можно доказать путем редукции к сильно NP-полной задаче трех разбиений . Заметим, что обе нижние оценки и также справедливо для случая, когда разрешен поворот элементов на 90 градусов. Кроме того, это было доказано Ashok et al. [6] что полосовая упаковка является W[1]-жесткой , если параметризовать ее высотой оптимальной упаковки.
Свойства оптимальных решений
[ редактировать ]Существуют две тривиальные нижние оценки оптимальных решений. Во-первых, это высота самого большого предмета. Определять . Тогда считается, что
.
Другая нижняя граница определяется общей площадью объектов. Определять тогда это справедливо
.
Следующие две нижние границы учитывают тот факт, что некоторые элементы не могут быть размещены рядом друг с другом в полосе и могут быть вычислены в . [7] Для первой нижней границы предположим, что элементы отсортированы по невозрастающей высоте. Определять . Для каждого определять первый индекс такой, что . Тогда считается, что
. [7]
Для второй нижней границы разделите набор элементов на три набора. Позволять и определить , , и . Тогда считается, что
, [7] где для каждого .
С другой стороны, Штейнберг [8] показал, что высота оптимального решения может быть ограничена сверху величиной
Точнее, он показал, что при и затем предметы можно поместить в коробку шириной и высота если
, где .
Алгоритмы аппроксимации полиномиального времени
[ редактировать ]Поскольку эта задача является NP-трудной, аппроксимационные алгоритмы для нее были изучены . Большинство эвристических подходов имеют коэффициент аппроксимации между и . Нахождение алгоритма с соотношением ниже кажется сложным и сложность соответствующих алгоритмов возрастает относительно времени их работы и их описания. Наименьший коэффициент аппроксимации, достигнутый на данный момент, равен .
Год | Имя | Гарантия аппроксимации | Источник |
---|---|---|---|
1980 | Снизу вверх по левому краю (BL) | Бейкер и др. [2] | |
1980 | Следующая установка уменьшающейся высоты (NFDH) | Коффман и др. [9] | |
Уменьшающаяся высота первой подгонки (FFDH) | |||
Раздельная посадка (SF) | |||
1980 | Слейтор [10] | ||
1981 | Сплит-алгоритм (SP) | Голаны [11] | |
Смешанный алгоритм | |||
1981 | Вверх-Вниз (UD) | Бейкер и др. [12] | |
1994 | Обратная посадка | Ширмейер [13] | |
1997 | Стейнберг [8] | ||
2000 | Кеньон, Ремила [14] | ||
2009 | Их, ван Сти [15] | ||
2009 | Янсен, Солис-Оба [16] | ||
2011 | Бужере и др. [17] | ||
2012 | Свириденко [18] | ||
2014 | Харрен и др. [3] |
Снизу вверх по левому краю (BL)
[ редактировать ]Этот алгоритм был впервые описан Бейкером и др. [2] Это работает следующим образом:
Позволять быть последовательностью прямоугольных элементов. Алгоритм повторяет последовательность в заданном порядке. По каждому рассматриваемому пункту , он ищет самое нижнее положение для его размещения, а затем сдвигает его как можно дальше влево. Следовательно, он помещает в самой нижней левой возможной координате в полосе.
Этот алгоритм имеет следующие свойства:
- Коэффициент аппроксимации этого алгоритма не может быть ограничен константой. Точнее, они показали, что для каждого существует список прямоугольных элементов, упорядоченных по увеличению ширины так, что , где — высота упаковки, созданной алгоритмом BL, и – высота оптимального решения для . [2]
- Если элементы упорядочены по уменьшению ширины, то . [2]
- Если все элементы квадратные и упорядочены по уменьшению ширины, то . [2]
- Для любого , существует список прямоугольников, упорядоченных по уменьшению ширины, таких, что . [2]
- Для любого , существует список квадратов, упорядоченных по уменьшению ширины, таких, что . [2]
- Для каждого , существует экземпляр, содержащий только квадраты, где каждый порядок квадратов имеет соотношение , т. е. существуют случаи, когда BL не находит оптимума даже при переборе всех возможных порядков элементов. [2] В 2024 году эта нижняя граница была улучшена Хугарди и Зондерваном до . [19]
Следующая установка с уменьшающейся высотой (NFDH)
[ редактировать ]Этот алгоритм был впервые описан Коффманом и др. [9] в 1980 году и работает следующим образом:
Позволять — заданный набор прямоугольных элементов. Сначала алгоритм сортирует элементы в порядке невозрастания высоты. Затем, начиная с позиции , алгоритм размещает элементы в полосе рядом друг с другом до тех пор, пока следующий элемент не перекроет правую границу полосы. На этом этапе алгоритм определяет новый уровень вверху самого высокого элемента текущего уровня и размещает элементы рядом друг с другом на этом новом уровне.
Этот алгоритм имеет следующие свойства:
- Время работы может быть ограничено и если элементы уже отсортированы даже по .
- Для каждого набора предметов , он производит упаковку высотой , где это наибольшая высота предмета в . [9]
- Для каждого существует набор прямоугольников такой, что [9]
- Созданная упаковка представляет собой гильотинную упаковку. Это означает, что предметы можно получить путем последовательной горизонтальной или вертикальной резки от края до края.
Уменьшение высоты при первой подгонке (FFDH)
[ редактировать ]Этот алгоритм, впервые описанный Coffman et al. [9] в 1980 году работает аналогично алгоритму NFDH. Однако при размещении следующего элемента алгоритм сканирует уровни снизу вверх и помещает элемент на первый уровень, на котором он поместится. Новый уровень открывается только в том случае, если предмет не помещается ни в один из предыдущих.
Этот алгоритм имеет следующие свойства:
- Время работы может быть ограничено , поскольку существует не более уровни.
- Для каждого набора предметов он производит упаковку высотой , где это наибольшая высота предмета в . [9]
- Позволять . Для любого набора предметов и полоска шириной такой, что для каждого , он утверждает, что . Более того, для каждого , существует такой набор элементов с . [9]
- Если все элементы в являются квадратами, то считается, что . Более того, для каждого , существует набор квадратов такой, что . [9]
- Созданная упаковка представляет собой гильотинную упаковку. Это означает, что предметы можно получить путем последовательной горизонтальной или вертикальной резки от края до края.
Алгоритм расщепления (SF)
[ редактировать ]Этот алгоритм был впервые описан Коффманом и др. [9] Для заданного набора предметов и полоска шириной , это работает следующим образом:
- Определенный , наибольшее целое число, такое, что данные прямоугольники имеют ширину или меньше.
- Разделять на два набора и , такой, что содержит все предметы с шириной пока содержит все элементы с .
- Заказ и за счет неувеличения высоты.
- Упакуйте вещи в с алгоритмом FFDH.
- Измените порядок уровней/полок, построенных FFDH, так, чтобы все полки общей шириной превышали находятся ниже более узких.
- Получается прямоугольная область с , рядом с более узкими уровнями/полками, на которых нет предметов.
- Используйте алгоритм FFDH для упаковки элементов в используя территорию также.
Этот алгоритм имеет следующие свойства:
- Для каждого набора предметов и соответствующий , он утверждает, что . [9] Обратите внимание, что для , он утверждает, что
- Для каждого , есть набор предметов такой, что . [9]
Алгоритм Слейтора
[ редактировать ]Для заданного набора предметов и полоска шириной , это работает следующим образом:
- Найдите все элементы шириной больше и сложите их внизу полоски (в произвольном порядке). Назовите общую высоту этих предметов . Все остальные элементы будут размещены выше. .
- Отсортируйте все оставшиеся элементы в порядке невозрастания высоты. Элементы будут размещены в этом порядке.
- Рассмотрим горизонтальную линию в точке в качестве полки. Алгоритм размещает предметы на этой полке в порядке невозрастания высоты до тех пор, пока не останется ни одного предмета или не подойдет следующий.
- Нарисуйте вертикальную линию в , который разрезает полосу на две равные половины.
- Позволять быть самой высокой точкой, покрытой любым предметом в левой половине и соответствующую точку на правой половине. Нарисуйте два горизонтальных отрезка длиной в и через левую и правую половину полосы. Эти две строки создают новые полки, на которых алгоритм будет размещать предметы, как на шаге 3. Выберите половину с нижней полкой и размещайте предметы на этой полке до тех пор, пока ни один другой предмет не подойдет. Повторяйте этот шаг, пока не останется ни одного элемента.
Этот алгоритм имеет следующие свойства:
- Время работы может быть ограничено и если элементы уже отсортированы даже по .
- Для каждого набора предметов он производит упаковку высотой , где это наибольшая высота предмета в . [10]
Алгоритм разделения (SP)
[ редактировать ]Этот алгоритм является расширением подхода Слейтора и впервые был описан Голаном. [11] Он размещает элементы в невозрастающем порядке ширины. Интуитивная идея состоит в том, чтобы разделить полосу на подполосы при размещении некоторых предметов. По возможности алгоритм помещает текущий элемент рядом с уже размещенным элементом . В этом случае соответствующая подполоса разбивается на две части: одна содержит первый элемент. а другой содержит текущий элемент . Если это невозможно, он помещает поверх уже размещенного элемента и не разделяет подполосу.
Этот алгоритм создает набор С из субполос. Для каждой субполосы 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
Этот алгоритм имеет следующие свойства:
- Время работы может быть ограничено поскольку количество подполос ограничено .
- Для любого набора предметов он утверждает, что . [11]
- Для любого , существует набор элементов такой, что . [11]
- Для любого и , существует набор элементов такой, что . [11]
Обратная посадка (RF)
[ редактировать ]Этот алгоритм был впервые описан Ширмейером. [13] Описание этого алгоритма нуждается в некоторых дополнительных обозначениях. Для размещенного предмета , его левый нижний угол обозначается и его верхний правый угол .
Дан набор предметов и полоска шириной , это работает следующим образом:
- Сложите все прямоугольники шириной больше друг на друга (в случайном порядке) внизу полоски. Обозначим через высота этого стека. Все остальные предметы будут упакованы выше .
- Отсортируйте оставшиеся элементы в порядке неувеличения высоты и рассмотрите элементы в этом порядке в следующих шагах. Позволять быть высотой самого высокого из этих оставшихся предметов.
- Поместите предметы один за другим, выровняв их по левому краю, на полке, определенной до тех пор, пока на этой полке не окажется другого предмета или не останется ни одного предмета. Назовите эту полку первым уровнем .
- Позволять быть высотой самого высокого неупакованного предмета. Определите новую полку в . Алгоритм заполнит эту полку справа налево, выравнивая предметы вправо так, чтобы предметы касались этой полки своим верхом. Назовем эту полку вторым обратным уровнем .
- Размещайте предметы на двух полках по принципу First-Fit, т. е. размещая предметы на первом уровне там, где они подходят, и на втором в противном случае. Продолжайте до тех пор, пока не закончатся предметы или общая ширина предметов на второй полке не станет не менее .
- Смещайте второй реверс-уровень вниз до тех пор, пока предмет из него не коснется предмета первого уровня. Определять как новое вертикальное положение сдвинутой полки. Позволять и быть самой подходящей парой трогательных предметов с размещены на первом уровне и на втором обратном уровне. Определять .
- Если затем — последний прямоугольник, помещенный на второй обратный уровень. Все остальные предметы с этого уровня сдвиньте дальше вниз (все на столько же), пока первый из них не коснется предмета с первого уровня. Алгоритм снова определяет самую правую пару соприкасающихся предметов. и . Определять как величина, на которую полка была сдвинута вниз.
- Если затем сдвинь влево, пока не коснется другого предмета или границы полосы. Определите третий уровень вверху .
- Если затем сдвинь определить третий уровень вверху . Место на этом третьем уровне выровнен по левому краю, так что он касается элемента первого уровня слева от него.
- Продолжайте упаковывать предметы, используя эвристику First-Fit. Каждый последующий уровень (начиная с третьего уровня) определяется горизонтальной линией, проходящей через верх самого большого элемента предыдущего уровня. Обратите внимание, что первый предмет, помещенный на следующем уровне, может касаться не границы полосы левой стороной, а предмета первого уровня или предмета. .
Этот алгоритм имеет следующие свойства:
- Время работы может быть ограничено , поскольку существует не более уровни.
- Для каждого набора предметов он производит упаковку высотой . [13]
Алгоритм Штейнберга (ST)
[ редактировать ]Алгоритм Стейнберга является рекурсивным. Дан набор прямоугольных предметов. и прямоугольную целевую область шириной и высота , он предлагает четыре правила сокращения, которые помещают некоторые элементы и оставляют меньшую прямоугольную область с теми же свойствами, что и раньше, в отношении остаточных элементов. Рассмотрим следующие обозначения: Учитывая набор элементов мы обозначаем через самая высокая высота предмета в , наибольшая ширина элемента, появляющаяся в и по общая площадь этих предметов. Стейнбергс показывает, что если
, , и , где ,
тогда все элементы можно разместить внутри целевой области размера . Каждое правило сокращения будет создавать меньшую целевую область и подмножество элементов, которые необходимо разместить. Если условие выше выполняется до запуска процедуры, то созданная подзадача также будет иметь это свойство.
Процедура 1 : Ее можно применять, если .
- Найдите все предметы с шириной и удалить их из .
- Отсортируйте их по неувеличению ширины и поместите их с выравниванием по левому краю внизу целевой области. Позволять быть их общая высота.
- Найдите все предметы с шириной . Удалите их из и поместите их в новый набор .
- Если пусто, определите новый целевой регион как область выше , то есть имеет высоту и ширина . Решите проблему, состоящую из этой новой целевой области и сокращенного набора элементов, с помощью одной из процедур.
- Если не пуст, отсортируйте его по невозрастающей высоте и поместите элементы по одному в правом верхнем углу целевой области. Позволять быть общей шириной этих элементов. Определите новую целевую область шириной и высота в левом верхнем углу. Решите проблему, состоящую из этой новой целевой области и сокращенного набора элементов, с помощью одной из процедур.
Процедура 2 : Ее можно применять, если выполняются следующие условия: , , и существуют два разных элемента с , , , и .
- Находить и и удалить их из .
- Поместите более широкий в нижний левый угол целевой области, а более узкий — по левому краю вверху первого.
- Определите новую целевую область справа от этих обоих элементов так, чтобы она имела ширину и высота .
- Поместите оставшиеся предметы в в новую целевую область с помощью одной из процедур.
Процедура 3 : Ее можно применять, если выполняются следующие условия: , , , а при сортировке элементов по уменьшению ширины существует индекс такой, что при определении как первый предметы, которые он содержит, которые а также
- Набор .
- Определите две новые прямоугольные целевые области: одну в левом нижнем углу исходной, с высотой и ширина а другой слева от него высотой и ширина .
- Используйте одну из процедур для размещения элементов в в первую новую целевую область и предметы в во второй.
Обратите внимание, что процедуры с 1 по 3 имеют симметричную версию при изменении высоты и ширины элементов и целевой области.
Процедура 4 : Ее можно применять, если выполняются следующие условия: , , и существует элемент такой, что .
- Поместите предмет в левом нижнем углу целевой области и удалите ее из .
- Определите новую целевую область справа от этого элемента так, чтобы она имела ширину и высота и поместите оставшиеся элементы внутри этой области, используя одну из процедур.
Этот алгоритм имеет следующие свойства:
- Время работы может быть ограничено . [8]
- Для каждого набора предметов он производит упаковку высотой . [8]
Алгоритмы аппроксимации псевдополиномиального времени
[ редактировать ]Чтобы улучшить нижнюю границу для алгоритмов с полиномиальным временем рассмотрены псевдополиномиальные алгоритмы для задачи упаковки полос. При рассмотрении алгоритмов этого типа все размеры предметов и полосы задаются как интегралы. Кроме того, ширина полосы разрешено появляться полиномиально во время выполнения. Обратите внимание, что это больше не считается полиномиальным временем работы, поскольку в данном случае ширина полосы требует размера кодирования .
Разработанные алгоритмы псевдополиномиального времени в основном используют тот же подход. Показано, что каждое оптимальное решение можно упростить и преобразовать в решение, имеющее одну из постоянного числа структур. Затем алгоритм повторяет все эти структуры и помещает элементы внутрь, используя линейное и динамическое программирование. Наилучшее соотношение, достигнутое на данный момент, составляет . [20] в то время как не может быть псевдополиномиального алгоритма по времени с соотношением лучше, чем пока не [5]
Год | Коэффициент аппроксимации | Источник | Комментарий |
---|---|---|---|
2010 | Янсен, Тёле [21] | ||
2016 | Надирадзе, Визе [22] | ||
2016 | Гальвес, Грандони, Ингала, Хан [23] | также для поворота на 90 градусов | |
2017 | Янсен, Рау [24] | ||
2019 | Янсен, Рау [20] | также для поворотов на 90 градусов и смежных формовочных работ |
Онлайн-алгоритмы
[ редактировать ]В онлайн-варианте стрип-упаковки товары приходят со временем. Когда предмет прибывает, его необходимо разместить немедленно, прежде чем станет известен следующий предмет. Были рассмотрены два типа онлайн-алгоритмов. В первом варианте не допускается изменение упаковки после размещения товара. Во втором случае товары могут быть переупакованы при поступлении другого товара. Этот вариант называется моделью миграции.
Качество онлайн-алгоритма измеряется (абсолютным) коэффициентом конкуренции.
,
где соответствует решению, сгенерированному онлайн-алгоритмом, и соответствует размеру оптимального решения. Помимо коэффициента абсолютной конкуренции, изучался асимптотический коэффициент конкуренции онлайн-алгоритмов. Для экземпляров с это определяется как
.
Обратите внимание, что все экземпляры можно масштабировать так, что .
Год | Конкурентное соотношение | Асимптотическое соотношение конкуренции | Источник |
---|---|---|---|
1983 | 6.99 | Бейкер и Шварц [25] | |
1997 | Цирик и Вегингер [26] | ||
2007 | 6.6623 | Хуринк и Паулюс [27] | |
2009 | 6.6623 | Йе, Хан и Чжан [28] | |
2007 | Хан и др. [29] + Шелк [30] |
В рамках Han et al. [29] применимо в онлайн-настройке, если онлайн-упаковка контейнера алгоритм принадлежит к классу Super Harmonic. Таким образом, онлайн-алгоритм упаковки контейнеров Сейдена Гармоника++ [30] подразумевает алгоритм онлайн-упаковки полос с асимптотическим отношением 1,58889.
Год | Конкурентное соотношение | Асимптотическое соотношение конкуренции | Источник | Комментарий |
---|---|---|---|---|
1982 | Браун, Бейкер и Кацев [31] | |||
2006 | 2.25 | Йоханнес [32] | также справедливо для задачи планирования параллельных задач | |
2007 | 2.43 | Хуринк и Паулюс [33] | также справедливо для задачи планирования параллельных задач | |
2009 | 2.457 | Керн и Паулюс [34] | ||
2012 | Балог и Бекеси [35] | нижняя граница из-за основной проблемы упаковки контейнеров | ||
2016 | 2.618 | Ю, Мао и Сяо [36] |
Ссылки
[ редактировать ]- ^ Васер, Герхард; Хауснер, Хайке; Шуман, Хольгер (16 декабря 2007 г.). «Улучшенная типология проблем резки и упаковки». Европейский журнал операционных исследований . 183 (3): 1109–1130. дои : 10.1016/j.ejor.2005.12.047 . ISSN 0377-2217 .
- ^ Jump up to: а б с д и ж г час я дж Бейкер, Бренда С.; Коффман-младший, Эдвард Г.; Ривест, Рональд Л. (1980). «Ортогональные упаковки в двух измерениях». СИАМ Дж. Компьютер . 9 (4): 846–855. CiteSeerX 10.1.1.309.8883 . дои : 10.1137/0209064 .
- ^ Jump up to: а б Харрен, Рольф; Янсен, Клаус; Прадель, Ларс; ван Сти, Роб (февраль 2014 г.). «А (5/3 + эпсилон)-приближение для упаковки полос» . Вычислительная геометрия . 47 (2): 248–267. дои : 10.1016/j.comgeo.2013.08.008 .
- ^ Нойенфельдт Жуниор, Альваро Луис. «Задача упаковки двумерных прямоугольных полос» (PDF) . 10820228.
- ^ Jump up to: а б Хеннинг, Сёрен; Янсен, Клаус; Рау, Малин; Шмарье, Ларс (2019). «Результаты сложности и неаппроксимируемости для параллельного планирования задач и упаковки полос». Теория вычислительных систем . 64 : 120–140. arXiv : 1705.04587 . дои : 10.1007/s00224-019-09910-6 . S2CID 67168004 .
- ^ Ашок, Прадиша; Колай, Судешна; Меесум, С.М.; Саураб, Сакет (январь 2017 г.). «Параметризованная сложность стрип-упаковки и упаковки минимального объема» . Теоретическая информатика . 661 : 56–64. дои : 10.1016/j.tcs.2016.11.034 .
- ^ Jump up to: а б с Мартелло, Сильвано; Моначи, Мишель; Виго, Даниэле (1 августа 2003 г.). «Точный подход к проблеме упаковки полос». ИНФОРМС Журнал по вычислительной технике . 15 (3): 310–319. дои : 10.1287/ijoc.15.3.310.16082 . ISSN 1091-9856 .
- ^ Jump up to: а б с д Стейнберг, А. (март 1997 г.). «Алгоритм упаковки полос с абсолютным пределом производительности 2». SIAM Journal по вычислительной технике . 26 (2): 401–409. дои : 10.1137/S0097539793255801 .
- ^ Jump up to: а б с д и ж г час я дж к Коффман-младший, Эдвард Г.; Гэри, MR; Джонсон, Дэвид С.; Тарьян, Роберт Эндре (1980). «Границы производительности для алгоритмов двумерной упаковки, ориентированных на уровень». СИАМ Дж. Компьютер . 9 (4): 808–826. дои : 10.1137/0209062 .
- ^ Jump up to: а б Слитор, Дэниел Доминик (1980). «Алгоритм, в 2,5 раза оптимальный для упаковки в двух измерениях». Инф. Процесс. Летт . 10 :37–40. дои : 10.1016/0020-0190(80)90121-0 .
- ^ Jump up to: а б с д и Голаны, Игаль (август 1981 г.). «Границы производительности для ортогонально-ориентированных алгоритмов двумерной упаковки». SIAM Journal по вычислительной технике . 10 (3): 571–582. дои : 10.1137/0210042 .
- ^ Бейкер, Бренда С; Браун, Донна Дж; Кацев, Ховард П. (декабрь 1981 г.). «Алгоритм 5/4 для двумерной упаковки». Журнал алгоритмов . 2 (4): 348–368. дои : 10.1016/0196-6774(81)90034-1 .
- ^ Jump up to: а б с Ширмейер, Инго (1994). «Обратная подгонка: 2-оптимальный алгоритм упаковки прямоугольников». Алгоритмы — ЕСА '94 . Конспекты лекций по информатике. Том. 855. Шпрингер Берлин Гейдельберг. стр. 290–299. дои : 10.1007/bfb0049416 . ISBN 978-3-540-58434-6 .
- ^ Кеньон, Клэр ; Ремила, Эрик (ноябрь 2000 г.). «Почти оптимальное решение проблемы двумерной резки заготовки». Математика исследования операций . 25 (4): 645–656. дои : 10.1287/moor.25.4.645.12118 . S2CID 5361969 .
- ^ Харрен, Рольф; Ван Сти, Роб (2009). «Улучшенные абсолютные коэффициенты аппроксимации для двумерных задач упаковки». Аппроксимация, рандомизация и комбинаторная оптимизация. Алгоритмы и методы . Конспекты лекций по информатике. Том. 5687. стр. 177–189. Бибкод : 2009LNCS.5687..177H . дои : 10.1007/978-3-642-03685-9_14 . ISBN 978-3-642-03684-2 .
- ^ Янсен, Клаус; Солис-Оба, Роберто (август 2009 г.). «Прямоугольная упаковка с одномерным увеличением ресурсов». Дискретная оптимизация . 6 (3): 310–323. дои : 10.1016/j.disopt.2009.04.001 .
- ^ Бужере, Марин; Дюто, Пьер-Франсуа; Янсен, Клаус; Робенек, Кристина; Тристрам, Денис (5 апреля 2012 г.). «Алгоритмы аппроксимации для упаковки нескольких полос и планирования параллельных работ на платформах». Дискретная математика, алгоритмы и приложения . 03 (4): 553–586. дои : 10.1142/S1793830911001413 .
- ^ Свириденко, Максим (январь 2012 г.). «Заметка об алгоритме упаковки полос Кеньона – Ремилы». Письма об обработке информации . 112 (1–2): 10–12. дои : 10.1016/j.ipl.2011.10.003 .
- ^ Хугарди, Стефан; Зондерван, Барт (26 февраля 2024 г.), Нижний левый алгоритм для задачи упаковки полос , arXiv : 2402.16572
- ^ Jump up to: а б Янсен, Клаус; Рау, Малин (2019). Устранение пробелов в псевдополиномиальной полосковой упаковке . Международные труды Лейбница по информатике (LIPIcs). Том 144. Замок Дагштуль – Центр компьютерных наук Лейбница. стр. 62:1–62:14. doi : 10.4230/LIPIcs.ESA.2019.62 . ISBN 9783959771245 . S2CID 24303167 .
- ^ Янсен, Клаус; Тёле, Ральф (январь 2010 г.). «Алгоритмы аппроксимации для планирования параллельных заданий». SIAM Journal по вычислительной технике . 39 (8): 3571–3615. дои : 10.1137/080736491 .
- ^ Надирадзе, Георгий; Визе, Андреас (21 декабря 2015 г.). «Об аппроксимации упаковки полос с соотношением лучшим, чем 3/2». Материалы двадцать седьмого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам . Общество промышленной и прикладной математики. стр. 1491–1510. дои : 10.1137/1.9781611974331.ch102 . ISBN 978-1-61197-433-1 .
- ^ Гальвез, Уолдо; Грандони, Фабрицио; Ингала, Сальваторе; Хан, Ариндам (2016). Улучшенная аппроксимация псевдополиномиального времени для насадки полос . Международные труды Лейбница по информатике (LIPIcs). Том 65. Замок Дагштуль – Центр компьютерных наук Лейбница. стр. 9:1–9:14. doi : 10.4230/LIPIcs.FSTTCS.2016.9 . ISBN 9783959770279 . S2CID 3205478 .
- ^ Янсен, Клаус; Рау, Малин (29–31 марта 2017 г.). «Улучшенное приближение для двумерной упаковки полос с полиномиальной ограниченной шириной». WALCOM: Алгоритмы и вычисления . Конспекты лекций по информатике. Том. 10167. стр. 409–420. arXiv : 1610.04430 . дои : 10.1007/978-3-319-53925-6_32 . ISBN 978-3-319-53924-9 . S2CID 15768136 .
- ^ Бейкер, Бренда С.; Шварц, Джеральд С. (1 августа 1983 г.). «Алгоритмы полки для решения двумерных задач упаковки». SIAM Journal по вычислительной технике . 12 (3): 508–525. дои : 10.1137/0212033 . ISSN 0097-5397 .
- ^ Чирик, Янош; Вегингер, Герхард Дж. (28 августа 1997 г.). «Алгоритмы поточной стрип-упаковки». Письма об обработке информации . 63 (4): 171–175. дои : 10.1016/S0020-0190(97)00120-8 . ISSN 0020-0190 .
- ^ Хуринк, Иоганн Л.; Паулюс, Джейкоб Ян (2007). «Онлайн-алгоритм для параллельного планирования заданий и упаковки полос» (PDF) . Приближение и онлайн-алгоритмы . Конспекты лекций по информатике. Том. 4927. Шпрингер Берлин Гейдельберг. стр. 67–74. дои : 10.1007/978-3-540-77918-6_6 . ISBN 978-3-540-77917-9 .
- ^ Да, Деши; Хан, Синь; Чжан, Гоочуань (1 мая 2009 г.). «Заметка об онлайн-упаковке стрип». Журнал комбинаторной оптимизации . 17 (4): 417–423. дои : 10.1007/s10878-007-9125-x . ISSN 1573-2886 . S2CID 37635252 .
- ^ Jump up to: а б Хан, Синь; Ивама, Кадзуо; Да, Деши; Чжан, Гочуань (2007). «Упаковка в полоску или упаковка в контейнер». Алгоритмические аспекты информации и управления . Конспекты лекций по информатике. Том. 4508. Шпрингер Берлин Гейдельберг. стр. 358–367. arXiv : cs/0607046 . дои : 10.1007/978-3-540-72870-2_34 . ISBN 978-3-540-72868-9 . S2CID 580 .
- ^ Jump up to: а б Сейден, Стивен С. (2001). «О проблеме упаковки онлайн-контейнеров». Автоматы, языки и программирование . Конспекты лекций по информатике. Том. 2076. Шпрингер Берлин Гейдельберг. стр. 237–248. дои : 10.1007/3-540-48224-5_20 . ISBN 978-3-540-42287-7 .
- ^ Браун, Донна Дж.; Бейкер, Бренда С.; Кацев, Ховард П. (1 ноября 1982 г.). «Нижние оценки для онлайн-алгоритмов двумерной упаковки». Акта Информатика . 18 (2): 207–225. дои : 10.1007/BF00264439 . hdl : 2142/74223 . ISSN 1432-0525 . S2CID 21170278 .
- ^ Йоханнес, Берит (1 октября 2006 г.). «Планирование параллельных заданий для минимизации времени выполнения» (PDF) . Журнал планирования . 9 (5): 433–452. дои : 10.1007/s10951-006-8497-6 . hdl : 20.500.11850/36804 . ISSN 1099-1425 . S2CID 18819458 .
- ^ Хуринк, Дж.Л.; Паулюс, Джей-Джей (1 января 2008 г.). «Онлайн-планирование параллельных работ на двух машинах является 2-конкурентным» (PDF) . Письма об исследованиях операций . 36 (1): 51–56. дои : 10.1016/j.orl.2007.06.001 . ISSN 0167-6377 . S2CID 15561044 .
- ^ Керн, Уолтер; Паулюс, Джейкоб Ян (2009). «Примечание о нижней границе для онлайн-упаковки стрип» . Письма об исследованиях операций .
- ^ Балог, Янош; Бекеши, Йожеф; Галамбос, Габор (6 июля 2012 г.). «Новые нижние оценки для некоторых классов алгоритмов упаковки контейнеров» . Теоретическая информатика . 440–441: 1–13. дои : 10.1016/j.tcs.2012.04.017 . ISSN 0304-3975 .
- ^ Ю, Госун; Мао, Яньлин; Сяо, Цзяоляо (1 мая 2016 г.). «Новая нижняя граница онлайн-упаковки стрип». Европейский журнал операционных исследований . 250 (3): 754–759. дои : 10.1016/j.ejor.2015.10.012 . ISSN 0377-2217 .