Следующая посадка-убывающая упаковка контейнера

Next-fit-decreasing (NFD) — это алгоритм упаковки контейнеров . Его входные данные — список элементов разных размеров. Его выход — упаковка — разбиение элементов на контейнеры фиксированной емкости, так что сумма размеров элементов в каждом контейнере не превышает емкость. В идеале мы хотели бы использовать как можно меньше контейнеров, но минимизация количества контейнеров — это NP-трудная задача. Алгоритм NFD использует следующую эвристику :

Расположите предметы от большего к меньшему.
Инициализируйте пустой контейнер и назовите его «открытый контейнер».
Для каждого товара в заказе проверьте, может ли он поместиться в открытый контейнер:
- Если он подходит, поместите в него новый предмет.
- В противном случае закройте текущую корзину, откройте новую корзину и поместите в нее текущий элемент.

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

Верхняя граница производительности

Бейкер и Коффман ^[1] доказали, что для каждого целого числа r , когда размер всех элементов не превышает 1/ r , асимптотическое отношение аппроксимации RFD удовлетворяет условию

$R_{NFD}^{\infty }({\text{size}}\leq 1/r)=h_{\infty }(r)$ ,

где — последовательность, первые элементы которой приблизительно равны 1,69103, 1,42312, 1,30238. В частности, взятие r = 1 подразумевает, что $h_{\infty }(r)$

$R_{NFD}^{\infty }=h_{\infty }(1)\приблизительно 1,69103$ .

Позднее NFD также был проанализирован вероятностно. ^[2]

Варианты

Next-Fit упаковывает список и его обратный список в одинаковое количество ячеек. Поэтому Next-Fit-Increasing имеет ту же производительность, что и Next-Fit-Decreasing. ^[3]

Однако Next-Fit-Increase работает лучше, когда существуют общие структуры затрат. ^[4]

Ссылки

^ Бейкер, Б. С.; Коффман, младший, Э. Г. (1981-06-01). «Жесткая асимптотическая граница для упаковки контейнеров с уменьшением числа подходящих ячеек». Журнал SIAM по алгебраическим и дискретным методам . 2 (2): 147– 152. doi :10.1137/0602019. ISSN 0196-5212.{{cite journal}}: CS1 maint: несколько имен: список авторов ( ссылка )
^ Csirik, J.; Galambos, G.; Frenk, JBG; Frieze, AM; Rinnooy Kan, AHG (1986-11-01). "Вероятностный анализ эвристики следующей подгонки с уменьшением упаковки контейнеров". Operations Research Letters . 5 (5): 233– 236. doi :10.1016/0167-6377(86)90013-1. hdl : 1765/11645 . ISSN 0167-6377.
^ Фишер, Дэвид К. (1988-12-01). «Next-fit упаковывает список и его обратный список в то же количество ячеек». Operations Research Letters . 7 (6): 291– 293. doi :10.1016/0167-6377(88)90060-0. ISSN 0167-6377.
^ Анили, Шошана; Брамель, Жюльен; Симчи-Леви, Дэвид (1 апреля 1994 г.). «Анализ наихудшего случая эвристики для задачи упаковки в контейнеры с общими структурами затрат». Исследование операций . 42 (2): 287– 298. doi :10.1287/opre.42.2.287. ISSN 0030-364X.

[1] Бейкер, Б. С.; Коффман, младший, Э. Г. (1981-06-01). «Жесткая асимптотическая граница для упаковки контейнеров с уменьшением числа подходящих ячеек». Журнал SIAM по алгебраическим и дискретным методам . 2 (2): 147– 152. doi :10.1137/0602019. ISSN 0196-5212.{{cite journal}}: CS1 maint: несколько имен: список авторов ( ссылка )

[2] Csirik, J.; Galambos, G.; Frenk, JBG; Frieze, AM; Rinnooy Kan, AHG (1986-11-01). "Вероятностный анализ эвристики следующей подгонки с уменьшением упаковки контейнеров". Operations Research Letters . 5 (5): 233– 236. doi :10.1016/0167-6377(86)90013-1. hdl : 1765/11645 . ISSN 0167-6377.

[:0-3] Фишер, Дэвид К. (1988-12-01). «Next-fit упаковывает список и его обратный список в то же количество ячеек». Operations Research Letters . 7 (6): 291– 293. doi :10.1016/0167-6377(88)90060-0. ISSN 0167-6377.

[4] Анили, Шошана; Брамель, Жюльен; Симчи-Леви, Дэвид (1 апреля 1994 г.). «Анализ наихудшего случая эвристики для задачи упаковки в контейнеры с общими структурами затрат». Исследование операций . 42 (2): 287– 298. doi :10.1287/opre.42.2.287. ISSN 0030-364X.