Уменьшающаяся упаковка в следующий контейнер

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

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

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

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

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

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

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

$R_{NFD}^{\infty }=h_{\infty }(1)\approx 1.69103$ .

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

Варианты

Next-Fit упаковывает список и его инверсию в одинаковое количество ячеек. Таким образом, функция Next-Fit-Increasing имеет ту же производительность, что и Next-Fit-Decreasing. ^{[ 3 ]}

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

Ссылки

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

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

[2] Цирик, Дж.; Галамбос, Г.; Фрэнк, JBG; Фриз, AM; Риннуй Кан, AHG (1 ноября 1986 г.). «Вероятностный анализ следующей эвристики упаковки контейнеров, уменьшающей соответствие» . Письма об исследованиях операций . 5 (5): 233–236. дои : 10.1016/0167-6377(86)90013-1 . hdl : 1765/11645 . ISSN 0167-6377 .

[:0-3] Фишер, Дэвид К. (1 декабря 1988 г.). «Next-fit упаковывает список и его обратную сторону в одинаковое количество ячеек» . Письма об исследованиях операций . 7 (6): 291–293. дои : 10.1016/0167-6377(88)90060-0 . ISSN 0167-6377 .

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

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]