Задача об упаковке в контейнеры
Ключевые слова и синонимы
Задача раскроя
Постановка задачи
В одномерной задаче упаковки контейнеров (bin packing) на входе имеется список [math]\displaystyle{ L = (a_1, a_2, ..., a_n) }[/math] предметов; каждый предмет [math]\displaystyle{ a_i }[/math] имеет размер [math]\displaystyle{ s(a_i) \in (0, 1] }[/math]. Задача состоит в том, чтобы упаковать предметы в минимальное число контейнеров единичной емкости, то есть разбить предметы на минимальное число наборов, каждый из которых имеет общий размер не более 1. Эта задача является NP-трудной, поэтому большая часть исследований по ней связана с разработкой и анализом аппроксимационных алгоритмов, которые и станут темой данной статьи.
У задачи упаковки в контейнеры множество применений, но самым важным из них, пожалуй, является роль, которую она сыграла в качестве полигона для новых алгоритмических и аналитических методов.
В этой области были доказаны одни из первых результатов по наихудшему и среднему случаю для аппроксимационных алгоритмов, а также получены первые нижние границы на коэффициенты конкурентоспособности онлайновых алгоритмов. Более подробно об этом можно прочитать в обзорах [4, 11].
Основные результаты
Поведение в наихудшем случае
Асимптотические отношения в наихудшем случае
Для большинства задач минимизации стандартной метрикой наихудшего случая для аппроксимационного алгоритма A является максимальное для всех экземпляров I отношение A(I)/OPT(I), где A(I) – величина решения, генерируемого A, а OPT(I) – величина оптимального решения. Однако в случае упаковки контейнеров имеются ограничения на эту метрику «абсолютно наихудшего отношения». Задача определения того, верно ли соотношение(I) = 2, уже является NP-трудной – и, следовательно, ни один аппроксимационный алгоритм с полиномиальным временем выполнения не может иметь абсолютное наихудшее отношение лучше 1,5, если не выполняется P = NP. Чтобы лучше понимать поведение алгоритмов упаковки в контейнеры в типичной ситуации, когда заданный список L требует большого количества контейнеров, исследователи используют более тонкую метрику упаковки – асимптотическое отношение в наихудшем случае, [math]\displaystyle{ R_A^{\infty} }[/math]. Оно определяется в два этапа следующим образом.
[math]\displaystyle{ R^n_A = max \{ A(L)/OPT(L): L }[/math] – список с [math]\displaystyle{ OPT(L) = n\} }[/math]
[math]\displaystyle{ R_A^{\infty} = lim_{n \to \infty} sup \; R^n_A }[/math]
Первым алгоритмом, поведение которого было проанализировано в этих терминах, был First Fit (FF). Этот алгоритм представляет себе бесконечную последовательность пустых контейнеров [math]\displaystyle{ B_1, B_2, ... }[/math] и, начиная с первого элемента входного списка L, помещает каждый предмет по очереди в первый контейнер, в котором для него еще есть место. В техническом отчете 1971 года, ставшем одной из первых работ, в которой изучались коэффициенты эффективности в наихудшем случае, Уллман [22] доказал следующее:
Теорема 1 [22]. [math]\displaystyle{ R^{\infty}_{FF} = 17/10. }[/math]
В дополнение к FF, еще пять простых эвристик были изучены в самом начале и послужили вдохновением для более поздних исследований. Best Fit (BF) – это вариант задачи FF, в котором каждый предмет упаковывается в контейнер, в который он может поместиться с наименьшим остатком свободного места; при наличии нескольких подходящих вариантов выбирается самый ранний из таких контейнеров. И FF, и BF могут быть реализованы за время O(n log n) [12]. Next Fit (NF) – еще более простой алгоритм с линейным временем выполнения, в котором первый предмет помещается в первый контейнер, а каждый следующий предмет упаковывается в последний непустой контейнер, если он в него помещается, в противном случае открывается новый контейнер. First Fit Decreasing (FFD) и Best Fit Decreasing (BFD) – варианты этих алгоритмов, в которых входной список сначала сортируется по размеру в порядке невозрастания, а затем применяется соответствующее правило упаковки. Для этих алгоритмов получены следующие результаты.
Теорема 2 [12]. [math]\displaystyle{ R^{\infty}_{NF} = 2. }[/math]
Теорема 3 [13]. [math]\displaystyle{ R^{\infty}_{BF} = 17/10. }[/math]
Теорема 4 [12, 13]. [math]\displaystyle{ R^{\infty}_{FFD} = R^{\infty}_{BFD} = 11/9 = 1,222... }[/math]
Приведенные выше алгоритмы относительно просты и интуитивно понятны. Если мы готовы рассмотреть более сложные алгоритмы, мы сможем добиться значительно лучших результатов. Лучший на сегодняшний день полиномиальный алгоритм упаковки в контейнеры работает весьма эффективно. Это алгоритм Кармаркара-Карпа 1982 года [15], который далее будет обозначаться как KK. Он использует метод эллипсоидов, аппроксимационные алгоритмы для задачи о рюкзаке и хитроумную схему округления для получения следующих гарантий:
Теорема 5 [15]. [math]\displaystyle{ R^{\infty}_{KK} = 1 }[/math] и существует константа [math]\displaystyle{ c }[/math] такая, что для всех списков L выполняется соотношение
[math]\displaystyle{ KK(L) \le OPT(L) + c \; log^2 \; (OPT(L)). }[/math]
К сожалению, время работы KK оказывается больше [math]\displaystyle{ O(n^8) }[/math], так что BFD и FFD остаются гораздо более практичными альтернативами.
Онлайновые алгоритмы
Три из вышеупомянутых алгоритмов (FF, BF и NF) являются онлайновыми, поскольку они упаковывают предметы в заданном порядке, не принимая во внимание размеры или количество последующих предметов. Как было замечено впоследствии во многих контекстах, ограничение онлайновыми ситуациями способно серьезно повлиять на способность алгоритма производить хорошие решения. Возможно, первым доказанным ограничением такого типа была теорема Яо [24], которая гласит, что ни один онлайновый алгоритм A для упаковки в контейнеры не может иметь [math]\displaystyle{ R^{\infty}_{A} \lt 1,5 }[/math]. С тех пор это ограничение было улучшено до следующего:
Теорема 6 [23]. Если A – онлайновый алгоритм для упаковки контейнеров, то [math]\displaystyle{ R^{\infty}_{A} \ge 1,540... }[/math]
В данном случае точное значение нижней границы является решением сложной линейной программы.
В работе Яо также был представлен онлайн-алгоритм Revised First Fit (RFF), который имел [math]\displaystyle{ R^{\infty}_{RFF} = 5/3 = 1,666... }[/math] и, следовательно, был ближе к этой нижней границе, чем FF и BF. Этот алгоритм работал путем разделения предметов на четыре класса по критериям размера и индекса, а затем использования различных правил упаковки (и самих упаковок) для каждого класса. Последующие алгоритмы улучшали его за счет введения все большего количества классов. В настоящее время самым эффективным является онлайновый алгоритм Harmonic++ (H++) из работы [21]:
Теорема 7 [21]. [math]\displaystyle{ R^{\infty}_{H++} \le 1,58889. }[/math]
Алгоритмы с ограниченным количеством контейнеров
Алгоритм NF, помимо того, что он работает в режиме онлайн, обладает еще одним свойством, которое стоит отметить: в любой момент времени для приема дополнительных предметов остается открытым не более чем постоянное число частично заполненных контейнеров. В случае NF эта константа равна 1 – поместить дополнительные предметы можно только в последний частично заполненный контейнер. Ограничение количества открытых контейнеров может быть необходимо в некоторых приложениях, например, при загрузке грузовиков на погрузочных платформах. Однако это обстоятельство накладывает дополнительные ограничения на поведение алгоритма.
Теорема 8 [17]. Для любого онлайнового алгоритма с ограниченным количеством контейнеров [math]\displaystyle{ R^{\infty}_{A} \ge 1,691... }[/math]
Константа 1,691 возникает и во многих других контекстах упаковки в контейнеры. Обычно она обозначается [math]\displaystyle{ h_{\infty} }[/math] и равна [math]\displaystyle{ \sum_{i = 1}^{\infty} (1/t_i) }[/math], где [math]\displaystyle{ t_1 = 1 }[/math], а для i > 1 [math]\displaystyle{ t_i = t_{i - 1}(t_{i - 1} + 1) }[/math]. Нижняя граница в Теореме 8 является строгой благодаря существованию алгоритмов Нarmonic[math]\displaystyle{ _k }[/math] ([math]\displaystyle{ H_k }[/math]) из работы [17]. [math]\displaystyle{ H_k }[/math] – это алгоритм, основанный на классах, в котором предметы делятся на классы [math]\displaystyle{ C_h, 1 \le h \le k }[/math], причем [math]\displaystyle{ C_k }[/math] состоит из всех предметов размером 1/k или меньше, а [math]\displaystyle{ C_h, 1 \le h \lt k }[/math], состоит из всех [math]\displaystyle{ a_i }[/math], таких, что [math]\displaystyle{ 1/(h + 1) \lt s(a_i) \le 1/h }[/math]. Затем алгоритм NF помещает предметы каждого класса в отдельную упаковку, предназначенную только для этого класса. Таким образом, в любой момент времени открыто не более k контейнеров. В [17] было показано, что [math]\displaystyle{ lim_{k \to \infty} R^{\infty}_{H_k} = h_{\infty} = 1,691... }[/math] Это даже лучше, чем асимптотическое наихудшее отношение 1,7 для алгоритмов FF и BF, работающих с неограниченным количеством контейнеров, хотя следует отметить, что вариант BF с ограниченным их количеством, в котором все контейнеры, кроме двух наиболее полных, закрыты, также имеет [math]\displaystyle{ R^{\infty}_A = 1,7 }[/math].
Поведение в среднем случае
Непрерывные распределения
Задача об упаковке в контейнеры также послужила ранним испытательным полигоном для изучения поведения аппроксимационных алгоритмов в среднем случае. Пусть F – распределение на интервале (0, 1], а [math]\displaystyle{ L_n }[/math] – список из n элементов с размерами элементов, выбранными независимо в соответствии с распределением F. Для любого списка L обозначим за s(L) нижнюю границу OPT(L), полученную суммированием размеров всех элементов в L. Далее определим
[math]\displaystyle{ ER^n_A(F) = E [ A(L_n) / OPT(L_n)], }[/math]
[math]\displaystyle{ ER^{\infty}_A(F) = lim_{n \to \infty} sup \; ER^n_A, }[/math]
[math]\displaystyle{ EW^n_A(F) = E [ A(L_n) - s(L_n)]. }[/math]
Последнее определение включено, поскольку [math]\displaystyle{ ER^{\infty}_A(F) = 1 }[/math] встречается достаточно часто, чтобы более тонкие различия имели смысл. Например, в начале 1980-х годов было замечено, что для распределения F = U(0, 1], в котором размеры элементов равномерно распределены на интервале (0, 1], [math]\displaystyle{ ER^{\infty}_{FFD}(F) = ER^{\infty}_{BFD}(F) = 1 }[/math], как следствие последующих более детальных результатов.
Теорема 9 [16, 20]. Для [math]\displaystyle{ A \in \{ FFD, BFD, OPT \} }[/math] имеет место соотношение [math]\displaystyle{ EW^n_A(U(0, 1]) = \Theta(\sqrt{n}). }[/math]
К некоторому удивлению, позже было обнаружено, что онлайновые алгоритмы FF и BF также имеют сублинейные ожидаемые потери и, следовательно, [math]\displaystyle{ ER^{\infty}_A(U(0, 1]) = 1. }[/math]
Теорема 10 [5, 19].
[math]\displaystyle{ EW^n_{FF}(U(0, 1]) = \Theta(n^{2/3}) }[/math]
[math]\displaystyle{ EW^n_{BF}(U(0, 1]) = \Theta(n^{1/2} \; log^{3/4} \; n) }[/math]
Однако это хорошее поведение не распространяется на алгоритмы с ограниченным количеством контейнеров NF и [math]\displaystyle{ H_k }[/math]:
Теорема 11 [6, 18].
[math]\displaystyle{ ER^{\infty}_{NF}(U(0, 1]) = 4/3 = 1,333... }[/math]
[math]\displaystyle{ lim_{k \to \infty} ER_{H_k}(U(0, 1]) = \pi^2/3 - 2 = 1,2899... }[/math]
Все приведенные выше результаты, кроме двух последних, используют тот факт, что распределение U(0, 1] симметрично относительно 1/2; и, следовательно, оптимальная упаковка состоит в основном из двухэлементных контейнеров, причем элементы размера s > 1/2 сопоставляются с элементами меньшего размера, очень близкого к 1 – s. Доказательства, по сути, показывают, что рассматриваемые алгоритмы хорошо справляются с построением таких паросочетаний. Однако на практике, очевидно, будут возникать ситуации, когда требуется нечто большее, чем простое соответствие. Для моделирования таких ситуаций исследователи сначала обратились к распределениям U(0, b], 0 < b < 1, где размеры элементов выбираются равномерно из интервала (0, b]. Моделирование показало, что такие распределения ухудшают работу онлайновых алгоритмов FF и BF, у которых [math]\displaystyle{ ER^{\infty}_A(U(0, b]) \gt 1 }[/math] для всех [math]\displaystyle{ b \in (0, 1) }[/math]. Как ни удивительно, они улучшают ситуацию для FFD и BFD (и оптимальной упаковки).
Теорема 12 [2, 14].
1. Для [math]\displaystyle{ 0 \lt b \le 1/2 }[/math] и [math]\displaystyle{ A \in \{FFD, BFD\} }[/math] выполняется [math]\displaystyle{ EW^n_A(U(0, b]) = O(1). }[/math]
2. Для [math]\displaystyle{ 1/2 \lt b \lt 1 }[/math] и [math]\displaystyle{ A \in \{FFD, BFD\} }[/math] выполняется [math]\displaystyle{ EW^n_A(U(0, b]) = \Theta(n^{1/3}). }[/math]
3. Для [math]\displaystyle{ 0 \lt b \lt 1 }[/math] выполняется [math]\displaystyle{ EW^n_{OPT}(U(0, b]) = O(1). }[/math]
Дискретные распределения
Во многих приложениях размеры предметов берутся из конечного множества, а не из непрерывного распределения, рассмотренного выше. Поэтому в последнее время при изучении поведения алгоритмов упаковки контейнеров в среднем случае обращаются к дискретным распределениям. Такое распределение задается конечным списком [math]\displaystyle{ s_1, s_2, ..., s_d }[/math] рациональных размеров и соответствующей рациональной вероятностью [math]\displaystyle{ p_i }[/math] для каждого [math]\displaystyle{ s_i }[/math]. Замечательный результат Куркубетиса и Вебера [7] гласит:
Теорема 13 [7]. Для любого дискретного распределения F значение [math]\displaystyle{ EW^n_{OPT}(F) }[/math] равно [math]\displaystyle{ \Theta(n) }[/math], [math]\displaystyle{ \Theta(\sqrt{n}) }[/math] либо [math]\displaystyle{ O(1) }[/math].
Дискретным аналогом непрерывного распределения U(0, b] является распределение U{j, k}, где размеры равны 1/k, 2/k, ... j/k, а все вероятности равны 1/j. Моделирование показывает, что поведение FF и BF в дискретном случае качественно схоже с поведением в непрерывном случае, в то время как поведение FFD и BFD значительно более причудливо [3]. Особо следует отметить распределение F = U{6, 13}, для которого [math]\displaystyle{ ER^{\infty}_{FFD}(F) }[/math] строго больше [math]\displaystyle{ ER^{\infty}_{FF}(F) }[/math], что противоречит всем ранее проведенным сравнениям между двумя алгоритмами.
Однако в случае дискретных распределений все стандартные алгоритмы уступают новому онлайновому алгоритму, которые называется алгоритмом суммы квадратов (SS). Обратите внимание, что поскольку все размеры предметов рациональны, их можно масштабировать так, чтобы они (также как размер контейнера B) были целочисленными. Тогда в любой момент работы онлайнового алгоритма текущую схему упаковки можно обобщить, указав для каждого [math]\displaystyle{ h, 1 \le h \le B }[/math], количество [math]\displaystyle{ n_h }[/math] контейнеров, содержащих предметы общей величиной h. В алгоритме SS каждый предмет упаковывается таким образом, чтобы минимизировать [math]\displaystyle{ \sum_{h = 1}^{B - 1} \; n^2_h }[/math].
Теорема 14 [9]. Для любого дискретного распределения F справедливы следующие утверждения:
1. Если [math]\displaystyle{ EW^n_{OPT}(F) = \Theta(\sqrt{n}) }[/math], то [math]\displaystyle{ EW^n_{SS}(F) = \Theta(\sqrt{n}); }[/math]
2. Если [math]\displaystyle{ EW^n_{OPT}(F) = O(1) }[/math], то [math]\displaystyle{ EW^n_{SS}(F) \in \{ O(1), \Theta(log \; n) \}. }[/math]
Кроме того, простая модификация SS позволяет исключить член [math]\displaystyle{ \Theta(log \; n) }[/math] в условии 2.
Применение
Существует множество потенциальных применений одномерной задачи об упаковке в контейнеры – от упаковки запросов на пропускную способность в каналы с фиксированной пропускной способностью до упаковки рекламных роликов в перерывы между передачами. На практике обычно используются простые эвристики, такие как FFD и BFD.
Открытые вопросы
Возможно, наиболее фундаментальной нерешенной проблемой, связанной с упаковкой контейнеров, является следующая. Как было отмечено выше, существует алгоритм с полиномиальным временем выполнения (KK), упаковка которого находится в пределах [math]\displaystyle{ O(log^2 \; (OPT)) }[/math] контейнеров от оптимальной. Возможно ли улучшить этот коэффициент? Насколько известно на данный момент, может существовать алгоритм с полиномиальным временем выполнения, который всегда отличается на один контейнер от оптимального, даже если [math]\displaystyle{ P \ne NP }[/math].
Экспериментальные результаты
Данная задача является благодатной почвой для экспериментального анализа, и многие из приведенных выше теорем были впервые предположены на основе экспериментальных результатов. Например, эксперименты, описанные в работе [1], послужили основой для теорем 10 и 12, а исследования в [10] – для теоремы 14.
См. также
Литература
1. Bentley, J.L.,Johnson, D.S., Leighton, F.T., McGeoch, C.C.: An experimental study of bin packing. In: Proc. of the 21st Annual Allerton Conference on Communication, Control, and Computing, Urbana, University of Illinois, 1983 pp. 51-60
2. Bentley, J.L., Johnson, D.S., Leighton, F.T., McGeoch, C.C., McGeoch, L.A.: Some unexpected expected behavior results for bin packing. In: Proc. of the 16th Annual ACM Symposium on Theory of Computing, pp. 279-288. ACM, New York (1984)
3. Coffman Jr, E.G., Courcoubetis, C., Garey, M.R., Johnson, D.S., McGeoch, L.A., Shor, P.W., Weber, R.R., Yannakakis, M.: Fundamental discrepancies between average-case analyses under discrete and continuous distributions. In: Proc. of the 23rd Annual ACM Symposium on Theory of Computing, New York, 1991, pp. 230-240. ACM Press, New York (1991)
4. Coffman Jr., E.G., Garey, M.R., Johnson, D.S.: Approximation algorithms for bin-packing: A survey. In: Hochbaum, D. (ed.) Approximation Algorithms for NP-Hard Problems, pp. 46-93. PWS Publishing, Boston (1997)
5. Coffman Jr., E.G., Johnson, D.S., Shor, P.W., Weber, R.R.: Bin packing with discrete item sizes, part II: Tight bounds on first fit. Random Struct. Algorithms 10,69-101 (1997)
6. Coffman Jr., E.G., So, K., Hofri, M., Yao, A.C.: A stochastic model of bin-packing. Inf. Cont. 44,105-115 (1980)
7. Courcoubetis, C., Weber, R.R.: Necessary and sufficient conditions for stability of a bin packing system. J. Appl. Prob. 23, 989-999(1986)
8. Csirik, J., Johnson, D.S.: Bounded space on-line bin packing: Best is better than first. Algorithmica 31, 115-138 (2001)
9. Csirik,J.,Johnson, D.S., Kenyon, C., Orlin,J.B., Shor, P.W., Weber, R.R.: On the sum-of-squares algorithm for bin packing. J. ACM 53,1-65(2006)
10. Csirik, J.,Johnson, D.S., Kenyon, C., Shor, P.W., Weber, R.R.: A self-organizing bin packing heuristic. In: Proc. of the 1999 Workshop on Algorithm Engineering and Experimentation. LNCS, vol. 1619, pp. 246-265. Springer, Berlin (1999)
11. Galambos, G., Woeginger, G.J.: Online bin packing - a restricted survey. ZOR Math. Methods Oper. Res. 42, 25-45 (1995)
12. Johnson, D.S.: Near-Optimal Bin Packing Algorithms. Ph.D. thesis, Massachusetts Institute of Technology, Department of Mathematics, Cambridge (1973)
13. Johnson, D.S., Demers, A., Ullman, J.D., Garey, M.R., Graham, R.L.: Worst-case performance bounds for simple one-dimensional packing algorithms. SIAM J. Comput. 3, 299-325 (1974)
14. Johnson, D.S., Leighton, F.T., Shor, P.W., Weber, R.R.: The expected behavior of FFD, BFD, and optimal bin packing under U(0; a]) distributions (in preparation)
15. Karmarkar, N., Karp, R.M.: An efficient approximation scheme for the one-dimensional bin packing problem. In: Proc. of the 23rd Annual Symposium on Foundations of Computer Science, pp. 312-320. IEEE Computer Soc, Los Alamitos, CA (1982)
16. Knodel, W.: A bin packing algorithm with complexity O(n log n) in the stochastic limit. In: Proc. 10th Symp. on Mathematical Foundations of Computer Science. LNCS, vol. 118, pp. 369-378. Springer, Berlin (1981)
17. Lee, C.C., Lee, D.T.: A simple on-line packing algorithm. J. ACM 32,562-572(1985)
18. Lee, C.C., Lee, D.T.: Robust on-line bin packing algorithms. Tech. Rep. Department of Electrical Engineering and Computer Science, Northwestern University, Evanston, IL (1987)
19. Leighton, T., Shor, P.: Tight bounds for minimaxgrid matching with applications to the average case analysis of algorithms. Combinatorica 9 161 -187 (1989)
20. Lueker, G.S.: An average-case analysis of bin packing with uniformly distributed item sizes. Tech. Rep. Report No 181, Dept. of Information and Computer Science, University of California, Irvine, CA (1982)
21. Seiden, S.S.: On the online bin packing problem. J. ACM 49, 640-671 (2002)
22. Ullman, J.D.: The performance of a memory allocation algorithm. Tech. Rep. 100, Princeton University, Princeton, NJ (1971)
23. van Vliet, A.: An improved lower bound for on-line bin packing algorithms. Inf. Proc. Lett. 43, 277-284 (1992)
24. Yao, A.C.: New algorithms for bin packing. J. ACM 27, 207-227 (1980)