Упаковка контейнеров по принципу «первый подходит — уменьшается»

Алгоритм компьютерной науки

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

Описание

Алгоритм FFD работает следующим образом.

• Расположите предметы от большего к меньшему.
• Откройте новый пустой контейнер, контейнер №1.
• Для каждого предмета от самого большого к самому маленькому найдите первую ячейку, в которую этот предмет помещается, если таковая имеется.
  • Если такой контейнер найден, поместите новый предмет в него.
  • В противном случае откройте новый пустой контейнер и положите в него новый предмет.

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

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

• Расположите предметы от большего к меньшему.
• Пока остались следующие пункты:
  • Откройте новый пустой контейнер.
  • Для каждого элемента от наибольшего к наименьшему:
    • Если он помещается в текущую корзину, вставьте его.

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

Анализ производительности

Производительность FFD анализировалась в несколько этапов. Ниже обозначает количество бинов, используемых FFD для входного набора S и емкость бинов C. ${\displaystyle FFD(S,C)}$

• В 1973 году Д.С. Джонсон доказал в своей докторской диссертации ^[1] , что для любого примера S и емкости C. ${\displaystyle FFD(S,C)\leq 11/9\mathrm {OPT} (S,C)+4}$
• В 1985 году Б. С. Бэкер ^[2] дал несколько более простое доказательство и показал, что аддитивная константа не больше 3.
• Юэ Миньи ^[3] доказал это в 1991 году, а в 1997 году усовершенствовал этот анализ совместно с Ли Жунхэном. ^[4] ${\displaystyle FFD(S,C)\leq 11/9\mathrm {OPT} (S,C)+1}$ ${\displaystyle FFD(S,C)\leq 11/9\mathrm {OPT} (S,C)+7/9}$
• В 2007 году Дьёрдь Доса ^[5] доказал тесную границу и представил пример, для которого . ${\displaystyle FFD(S,C)\leq 11/9\mathrm {OPT} (S,C)+6/9}$ ${\displaystyle FFD(S,C)=11/9\mathrm {OPT} (S,C)+6/9}$

Пример наихудшего случая

Пример нижней границы, приведенный Досой, выглядит следующим образом: Рассмотрим две конфигурации ячеек:

• ${\displaystyle B_{1}:=\{1/2+\varepsilon ,1/4+\varepsilon ,1/4-2\varepsilon \}}$  ;
• ${\displaystyle B_{2}:=\{1/4+2\varepsilon ,1/4+2\varepsilon ,1/4-2\varepsilon ,1/4-2\varepsilon \}}$ .

Если в оптимальном решении имеется 4 копии и 2 копии , FFD вычислит следующие ячейки: ${\displaystyle B_{1}}$ ${\displaystyle B_{2}}$

• 4 контейнера с конфигурацией , ${\displaystyle \{1/2+\varepsilon ,1/4+2\varepsilon \}}$
• 1 контейнер с конфигурацией , ${\displaystyle \{1/4+\varepsilon ,1/4+\varepsilon ,1/4+\varepsilon \}}$
• 1 контейнер с конфигурацией , ${\displaystyle \{1/4+\varepsilon ,1/4-2\varepsilon ,1/4-2\varepsilon ,1/4-2\varepsilon \}}$
• 1 контейнер с конфигурацией , ${\displaystyle \{1/4-2\varepsilon ,1/4-2\varepsilon ,1/4-2\varepsilon ,1/4-2\varepsilon \}}$
• 1 один последний контейнер с конфигурацией , ${\displaystyle \{1/4-2\varepsilon \}}$

То есть всего 8 ячеек, тогда как оптимум имеет только 6 ячеек. Таким образом, верхняя граница узкая, потому что . ${\displaystyle 11/9\cdot 6+6/9=72/9=8}$

Этот пример можно распространить на все размеры : ^[5] в оптимальной конфигурации имеется 9 k +6 ячеек: 6 k +4 типа B ₁ и 3 k +2 типа B _2. Но для FFD требуется не менее 11 k +8 ячеек, что составляет . ${\displaystyle {\text{OPT}}(S,C)}$ ${\displaystyle {\frac {11}{9}}(6k+4)+{\frac {6}{9}}}$

Производительность с делимыми размерами элементов

Важным частным случаем упаковки в контейнеры является тот случай, когда размеры элементов образуют делимую последовательность (также называемую факторизованной ). Частный случай делимых размеров элементов возникает при распределении памяти в компьютерных системах, где размеры элементов являются степенями 2. В этом случае FFD всегда находит оптимальную упаковку. ^{[6] : Теор.2}

Свойства монотонности

Вопреки интуиции, не является монотонной функцией C. ^{[7] : Рис.4} Аналогично, не является монотонной функцией размеров элементов в S : возможно, что элемент уменьшится в размере, но количество ячеек увеличится. ${\displaystyle FFD(S,C)}$ ${\displaystyle FFD(S,C)}$

Однако алгоритм FFD обладает свойством «асимптотической монотонности», определяемым следующим образом. ^{[7] : Лем.2.1}

• Для каждого экземпляра S и целого числа m пусть MinCap( S,m ) будет наименьшей емкостью C такой, что ${\displaystyle OPT(S,C)\leq m}$
• Для каждого целого числа m пусть MinRatio( m ) будет инфимумом чисел r ≥1 таким образом, что для всех входных наборов S , . Это величина, на которую нам нужно «раздуть» ячейки, чтобы FFD достиг оптимального количества ячеек. ${\displaystyle FFD(S,r\cdot {\text{MinCap}}(S,m))\leq m}$
• Тогда для каждого входа S и для каждого r ≥ MinRatio( m ), . Это показывает, в частности, что инфимум в приведенном выше определении можно заменить минимумом. ${\displaystyle FFD(S,r\cdot {\text{MinCap}}(S,m))\leq m}$

Примеры

Например, предположим, что входные данные следующие:

44, 24, 24, 22, 21, 17, 8, 8, 6, 6.

Вместимостью 60, FFD упаковывает 3 контейнера:

• 44, 8, 8;
• 24, 24, 6, 6;
• 22, 21, 17.

Но при емкости 61 FFD вмещает 4 контейнера:

• 44, 17;
• 24, 24, 8;
• 22, 21, 8, 6;
• 6.

Это происходит потому, что при емкости 61 число 17 помещается в первый контейнер и, таким образом, блокирует путь к следующим 8, 8.

В качестве другого примера ^{[8] : Пример 5.1} предположим, что входы следующие: 51, 28, 28, 28, 27, 25, 12, 12, 10, 10, 10, 10, 10, 10, 10, 10. При емкости 75 FFD упаковывает 4 контейнера:

• 51, 12, 12
• 28, 28, 10
• 28, 27, 10, 10
• 25, 10, 10, 10, 10, 10

Но при вместимости 76 ему понадобится 5 контейнеров:

• 51, 25
• 28, 28, 12
• 28, 27, 12
• 10, 10, 10, 10, 10, 10, 10
• 10

Рассмотрим приведенный выше пример с емкостью 60. Если 17 станет 16, то результирующая упаковка будет следующей:

• 44, 16;
• 24, 24, 8;
• 22, 21, 8, 6;
• 6.

Модифицированный первый подходящий-убывающий

Модифицированное уменьшение первого соответствия (MFFD) ^[9] улучшает FFD для элементов, превышающих половину ячейки, классифицируя элементы по размеру на четыре класса: большой, средний, маленький и крошечный, что соответствует элементам с размером > 1/2 ячейки, > 1/3 ячейки, > 1/6 ячейки и меньшим элементам соответственно. Затем он проходит через пять фаз:

1. Выделите контейнер для каждого крупного предмета, расположив его от большего к меньшему.
2. Продвигайтесь вперед по корзинам. На каждой: Если наименьший оставшийся средний предмет не помещается, пропустите эту корзину. В противном случае поместите наибольший оставшийся средний предмет, который помещается.
3. Пройдите назад через те ячейки, которые не содержат средний предмет. На каждой: Если два самых маленьких оставшихся маленьких предмета не помещаются, пропустите эту ячейку. В противном случае поместите самый маленький оставшийся маленький предмет и самый большой оставшийся маленький предмет, который помещается.
4. Пройдите вперед через все ячейки. Если наименьший оставшийся предмет любого класса размеров не помещается, пропустите эту ячейку. В противном случае поместите наибольший помещающийся предмет и оставьте его в этой ячейке.
5. Используйте FFD, чтобы упаковать оставшиеся предметы в новые контейнеры.

Этот алгоритм был впервые изучен Джонсоном и Гэри ^[9] в 1985 году, где они доказали, что . Эта граница была улучшена в 1995 году Юэ и Чжаном ^[10], которые доказали, что . ${\displaystyle MFFD(S,C)\leq (71/60)\mathrm {OPT} (S,C)+(31/6)}$ ${\displaystyle MFFD(S,C)\leq (71/60)\mathrm {OPT} (S,C)+1}$

Другие варианты

Best-fit-decreasing (BFD) очень похож на FFD, за исключением того, что после сортировки списка он обрабатывается с помощью best-fit bin packing . Его асимптотическое отношение аппроксимации такое же, как у FFD - 11/9.

Реализации

• Python: Пакет prtpy содержит реализацию метода уменьшения по первому подходящему множеству.

Смотрите также

• Алгоритм Multifit — алгоритм планирования идентичных машин , использующий FFD в качестве подпрограммы.

Ссылки

1. Джонсон, Дэвид С. (1973). «Почти оптимальные алгоритмы упаковки контейнеров» (PDF) . Массачусетский технологический институт .
2. Бейкер, Бренда С. (1985). «Новое доказательство алгоритма убывающей упаковки контейнеров первым подходящим». J. Algorithms . 6 (1): 49–70. doi :10.1016/0196-6774(85)90018-5.
3. Юэ, Миньи (октябрь 1991 г.). «Простое доказательство неравенства FFD (L) ≤ 11/9 OPT (L) + 1, ∀L для алгоритма упаковки контейнеров FFD». Acta Mathematicae Applicatae Sinica . 7 (4): 321–331. дои : 10.1007/BF02009683. S2CID  189915733.
4. Ли, Ронгхэн; Юэ, Миньи (август 1997 г.). «Доказательство FFD(L) < -OPT(L) + 7/9». Chinese Science Bulletin . 42 (15): 1262–1265. Bibcode : 1997ChSBu..42.1262L. doi : 10.1007/BF02882754. S2CID  93280100.
5. Dósa, György (2007). "The Tight Bound of First Fit Decreasing bin-Packing Algorithm is FFD(I) ≤ 11/9OPT(I) + 6/9". В Chen Bo; Mike Paterson; Zhang Guochuan (ред.). Combinatorics, Algorithms, Probabilistic and Experimental Methodologies . First International Symposium, ESCAPE 2007, Hangzhou, China, April 7–9, 2007. Lecture Notes in Computer Science. Vol. 4614. pp. 1–11. doi :10.1007/978-3-540-74450-4_1. ISBN 978-3-540-74449-8.
6. Коффман, Э. Г.; Гарей, М. Р.; Джонсон, Д. С. (1987-12-01). «Упаковка контейнеров с делимыми размерами предметов». Журнал сложности . 3 (4): 406–428. doi :10.1016/0885-064X(87)90009-4. ISSN  0885-064X.
7. Coffman, EG Jr.; Garey, MR; Johnson, DS (1978-02-01). «Применение упаковки в контейнеры для многопроцессорного планирования». SIAM Journal on Computing . 7 (1): 1–17. doi :10.1137/0207001. ISSN  0097-5397.
8. Хуан, Синь; Лу, Пиньян (2021-07-18). «Алгоритмическая структура для аппроксимации распределения максиминной доли работы». Труды 22-й конференции ACM по экономике и вычислениям . EC '21. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 630–631. arXiv : 1907.04505 . doi : 10.1145/3465456.3467555. ISBN 978-1-4503-8554-1. S2CID  195874333.
9. Джонсон, Дэвид С.; Гари, Майкл Р. (октябрь 1985 г.). «Теорема 7160 для упаковки контейнеров». Журнал сложности . 1 (1): 65–106. doi : 10.1016/0885-064X(85)90022-6 .
10. Юэ, Миньи; Чжан, Лэй (июль 1995 г.). «Простое доказательство неравенства MFFD(L) ≤ 71/60 OPT(L) + 1,L для алгоритма упаковки ячеек MFFD». Acta Mathematicae Applicatae Sinica . 11 (3): 318–330. doi :10.1007/BF02011198. S2CID  118263129.