Вероятностный анализ одного алгоритма упаковки прямоугольников в полосу

Вероятностный анализ одного алгоритма упаковки прямоугольников в полосу

Н.Н. Кузюрин, А.II. Поспелов

Анотация. В статье предлагается и теоретически исследуется on-line алгоритм упаковки прямоугольников в полубесконечную полосу. Получено, что для незаполненной площади упаковок, порождаемых алгоритмом в среднем, справедлива оценка G^jV''^[.jV)1 ;j)

1. Введение

В задаче упаковки в полубесконечную полосу (strip packing) цель состоит в упаковке множества прямоугольников в вертикальную полосу единичной ширины так, что стороны прямоугольников должны быть параллельны сторонам полосы (вращения запрещены). При анализе по худшему случаю обычно минимизируют необходимую для упаковки высоту полосы, а при анализе в среднем — математическое ожидание незаполненной площади (от нижней границы прямоугольников в упаковке до верхней) [9, 4].

Таким образом входом задачи является конечный список прямоугольников L  : V .н . Каждый прямоугольник р.- из списка L задан высотой J’.- и

шириной и-';. Эта задача возникает во многих контекстах и имеет много приложений, в частности, при разработке СБИС, построении оптимальных расписаний для кластеров и т.д. Ее частными случаями являются задача упаковки в контейнеры (bin packing) и задача об гп-процессорном расписании Так, если высоты всех прямоугольников из входного списка равны, то получаем задачу об упаковке в контейнеры, где высота заполнения как раз и равна числу контейнеров. Эти задачи интенсивно исследовались ранее. В общей постановке задача об упаковке в полосу также привлекала внимание исследователей с начала 80-х годов [1]. Известно, что эта задача NP-трудна. Интерес, поэтому, представляет построение приближенных алгоритмов с гарантированными оценками точности.

Различные приближенные алгоритмы были предложены для этой задачи [1, 2, 14, 11]. С точки зрения приложений интерес представляют алгоритмы.

работающие в оперативном режиме, т.е. размещающие очередной прямоугольник из списка, не используя информацию о последующих прямоугольниках (on-line алгоритмы).

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

Всюду в дальнейшем будем считать, что для каждого прямоугольника высота h, и ширина и-v имеют равномерное распределение на отрезке .0.1]. Будем предполагать, что все случайные величины u-у, — независимы в совокупности. В дальнейшем будем обозначать через I математическое ожидание площади, не заполненной прямоугольниками, между основанием полосы и верхней границей самого верхнего прямоугольника. Будем предполагать, что число прямоугольников JV — бесконечно большая величина (£f -г (В). Отметим, что вероятностному анализу различных эвристик одно и двумерной упаковки посвящено много работ [3, 4, 5, 6, 7, 8].

2. Описание алгоритма

Прежде чем перейти к описанию алгоритма, введём некоторые обозначения. Будем обозначать через — максимальное целое, непревосходящее х. Пусть S (I — некоторый параметр, от которого будет зависеть поведение алгоритма. Будем предполагать, что мы знаем число прямоугольников Лг, которые надо будет разместить (как избавиться от данного предположения для подобного типа эвристик показано в [10]).

Далее, пусть  BfS + YfffiMF, а где с —

некоторая положительная константа, значение которой мы определим позже.

В основании полосы рассмотрим прямоугольную область высоты и

ширины 1, где к = ть*;] Разобьём на прямоугольные области высоты ОД и ширины 1. Область \ в 1,2, ш rf разрежем на две подобласти Р‘< и В .-i.-fiL высоты и ширины 1—^, соотвественно. Таким

образом, мы получим 2к областей (см- Рис- !)•

Опишем теперь сам алгоритм упаковки. Алгоритм выбирает прямоугольники из списка по очереди и сразу же определяет место расположения, при этом прямоугольники упаковываются в одну из областей Р1, или в область — часть полосы выше /ЙЦЙТ Упаковка происходит либо на основание области, либо на верхнюю границу упакованных в данную область прямоугольников. Пусть уже упаковано некоторое число прямоугольников и опишем упаковку очередного прямоугольника ї  £ и-', І і. Область для упаковки выбирается по следующим правилам.

• Если к йі 1 — £, то рассматривается область Р'-, имеющая наименьшую ширину, превосходящую '.Г.

- Если суммарная высота прямоугольников, упакованных к текущему моменту в Р':, не превосходит величины — і1}, то упаковываем ; в Р1-.

- Если суммарная высота больше ЛЦВ — й, то е упаковывается в Р‘-.

• если А йг 1 — Л, то V упаковывается в Р'р.

Алгоритм заканчивает работу, когда упакован последний прямоугольник из L. Ясно, что при выполнении правил упаковки внутренности упакованных прямоугольников не будут пересекать границы полос и пересекаться между собой. Будем обозначать описанный алгоритм Для краткости будем

говорить, что прямоугольники 5 = (vv,. h'j является прямоугольником /-го типа (или s s Г-)- если w £ 1 — й и ширина w больше ширины области и меньше ширины области F'.

3. Оценка качества алгоритма

Естественным критериями оценки качества упаковки, создаваемой алгоритмами подобного типа, является высота и незаполненная площадь. Зная ширину полосы и общую площадь всех упаковываемых прямоугольников, эти критерием могут быть пересчитаны один в другой. Понятно, что в общем случае описанный алгоритм не даёт оптимального качества упаковки с точки зрения этих критериев. Целью данной статьи является оценка эффективности данного алгоритма в среднем, точнее оценка величины

tftf-T Atm)

где Н — общая высота упаковки.

Теорема Пусть 1 ™ — набор прямоугольников, причём h,: и и-у

независимы и равномерно распределены на отрезке |0Д], tfyff-1 \ где с:

— некоторая положительная константа, тогда для упаковки, получаемой с помощью алгоритма , справедливо

£ -ffMW + VSiff

Ранее в [10] было показано, что для шельфового алгоритма, использующего эвристику First Fit Z  ; . а для шельфового алгоритма, использующего

эвристику Best Fit Z

Параметр S может быть подбираться в зависимости от Лг. При этом эффективность алгоритма будет меняться. Понятно, что выбирая J  ('Ltlkl[J  1 можно получить для .41 (и} оценку, несколько

улучшающую результаты, полученные в [10]

Оценки получаемые в теореме предполагают, что число прямоугольников JV известно заранее. Однако, как было показано в [10], если упаковывать

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

Перейдем теперь к доказательству теоремы.

Доказательство теоремы Рассмотрим I!. В силу свойств суммы и произведения математического ожидания и независимости случайных величин и г, имеем

: - -2Г.1.М? - ейг -4.

Оценим IН. В силу используемого алгоритма упаковки высота Я складывается из детерминированной величины ЙА (и суммы высот прямоугольников, упакованных в область ;. Прямоугольники попадают в Р!: либо если их ширина больше 1—5, либо если не вместились в подходящую для них область Рг,;. Оценим эти две составляющих по отдельности.

Математическое ожидание суммарной высоты прямоугольников, имеющих ширину больше 1 — £, равна

I к) - Ц—1—;——*} = —

Теперь оценим суммарную высоту остальных прямоугольников, попавших в . Пусть Л’- — число прямоугольников /-го типа (т.е. область г', является минимальной, в которую они вмещаются по ширине). Поскольку вероятность попадания в подполосу равна 5, а общее число прямоугольников равно Лг. имеем

Щ ш М.

Пусть Т.; множество прямоугольников /-го типа, размещенных в . Обозначим через И. суммарную высоту прямоугольников ИЗ Т’~ т.е.

щ-2 л,

Так как Г  С 7-. математическое ожидание Н. может быть оценено следующим образом

Щ = ^ А А =

Для того, чтобы оценить рассмотрим два события. Первое —

прямоугольников /-го больше чем п . Второе — прямоугольников /-го не

больше чем ), но не всех их удалось разместить в ?'\. Понятно, что эти два события не пересекаются, и их объединение содержит событие 7  н <?. Таким образом, 1{; ч ф] можно оценить как

я ЩИ * Р [2с,, АсВД Щ й «£5>].

Для оценки первого из слагаемых в правой части (4) воспользуемся неравенством для вероятностей больших уклонений [12]:

- Щ У оВДДОй /ЗШЩ

или, вычисляя математические ожидания

РО^ ^ & 2екр Ч-

тэ л

Выбирая с = с ^ —, получаем:

ВД; - №3 * П ЖЗГ; £ С-&Е/а?ВД

Откуда получаем, что

: % * £ 2 акр | - (у) 1 нА:} - £^: до

Для оценки второго слагаемого в правой части (4) воспользуемся оценкой больших уклонений сумм независимых одинаково распределенных случайных величин Г|, Й, Л; £ Й; [13]:

Г^.1 «Ьс-ч?

1Р Ь За

В нашем случае Я[  К. Ь[  1 для всех : = 1.,,,, и,  -/гг  1^2, п  .

Полагая г = г,,. 1гт£ф/«(Д). получаем:

; Iа; > вд я, а м(а>| а г *, > ьвд! 1

а чи

Из (3), (4), (5) и (6) получаем, что

В силу независимости случайных величин иу, Лс, математическое ожидание вклада прямоугольников таких, что область Р . является минимальной, в которую они вмещаются по ширине, не зависит от /. Поэтому из (1), (2) и (7) следует

^ й Щ&) "ТГ" : " -р

Учитывая, что 'i f;*V"' ", и выбирая Г S’- S.'V-. не сложно получить, что

не превосходит некоторой константы С|. Следовательно

2 S + fffiSlib¥+ + VBFiKlnff)lii£ffiS + VffiSftLff+

iY _______________ ffiS

—^-----------— i el ifNGhiif -b p2 —.

что даёт утверждение теоремы.

Литература

[1] B.S. Baker, Е..Т. Coffman and R.L. Rivest, Orthogonal packings in two dimensions, SIAM J. Computing, (1980) 9, 846-855.

[2] B.S. Baker, J.S. Schwartz, Shelf algorithms for two dimensional packing problems. SIAM J. Computing, (1983) 12, 508-525

[3] E.G. Coffman, Jr., C. Courcoubetis, M.R. Garey, D.S. Johnson, P.W. Shor, R.R. Weber, M. Yaimakakis, Perfect packing theorems and the average-case bahavior of optimal and online bin packing, SIAM Review, (2002) 44 (1), 95—108.

[4] R.M. Karp, M. Luby, A. Marchetti-Spaccamela, A probabilistic analysis of multidimensional bin packing problems, In: Proc. Aimu. ACM Symp. on Theorty of Computing, 1984, pp. 289—298.

[5] P. W. Shor, The average-case analysis of some on-line algorithms for bin packing. Combinatorica (1986) 6,179-200.

[6] P. W. Shor, How to pack better than Best Fit: Tight bounds for average-case on-line bin packing, Proc. 32nd Annual Symposium on Foundations of Computer Science, (1991) pp. 752-759.

[7] E. G. Coffman, Jr., D. S. Johnson, P. W. Shor and G. S. Lueker. Probabilistic analysis of packing and related partitioning problems, Statistical Science (1993) 8, 40-47.

[8] E. G. Coffman, Jr., P. W. Shor. Packings in two dimensions: Asymptotic average-case analysis of algorithms, Algorithmica (1993) 9, 253-277.

[9] J. Csirik, G. J. Woeginger, Shelf Algorithms for On-Line Strip Packing. Inf. Process.

Lett. (1997), 63(4), 171-175.

[10] Кузюрин H.H., Поспелов А.И., Вероятностный анализ шельфовых алгоритмов упаковки прямоугольников в полосу, Дискретная математика, 2006, т. 18, N 1, с. 76-90.

[11] С. Kenyon and Е. Remila, A near optimal solution to a two-dimensional cutting stock problem, Mathematics of Operations Research, (2000) 25, 645—656.

[12] R. Motwani and P. Raghavan, Randomized algorithms, Cambridge Univ. Press, 1995.

[13] W. Hoeffding, Probability inequalities for sums of bounded random variables, J. Amer. Sattist. Assoc., 1963, v. 58, N 301, pp. 13—30.

[14] E. J. Coffman, M.R. Garey, D.S. Johnson and R.E. Taijan, Performance bounds for level-oriented two-dimensional packing algorithms, SIAM J. Computing, (1980) 9, 808—826.