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

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

А. И. Поспелов

Аннотация. Рассматривается задача минимизации высоты заполнения при упаковке прямоугольников в несколько полубесконечных полос, фиксированной ширины каждая. Предложен эвристический алгоритм упаковки и доказана гарантированная оценка точности этого алгоритма. Описанный алгоритм может использоваться для составления расписания для набора кластеров.

1. Введение

Двумерные задачи упаковки возникают в различных ситуациях. В связи с этим рассматриваются различные модели. Как одна из возможных постановок может быть предложена, например, рассмотренная в [8] задача поиска прямоугольника минимальной площади, в котором без наложений можно разместить заданный набор прямоугольников. Другая интенсивно изучаемая модель — это упаковка заданного списка прямоугольников в минимальное число прямоугольников заданного размера [5]. В данной работе будет рассмотрен третий тип моделей, который заключается в поиске оптимальной в некотором смысле упаковки прямоугольников в полубеско-нечную полосу.

Задача упаковки прямоугольников в полосу состоит в следующем. Пусть заданы полубесконечная полоса некоторой ширины и набор прямоугольников. Причём каждая сторона каждого прямоугольника параллельна либо основанию, либо вертикальной границы полосы. Требуется упаковать все прямоугольники без наложений и без вращений в полосу, минимизирую высоту заполнения, т.е. максимальную высоту, измеренную от основания полосы, пространства занятого прямоугольниками. Эта задача может возникать в различных ситуациях и интенсивно исследовалась ранее [3]. Некоторые её приложения связаны с задачей составления расписаний для многопроцессорных систем. Прямоугольник соответствует описанию вычислительной задачи при этом, ширина определяет необходимые ресурсы (процессоры/память), а высота — время выполнения

Работа выполнена при поддержке РФФИ, проект 02-01-00713.

задачи. Ширина полосы соответствует общему числу процессоров на вычислительном устройстве.

В данной работе мы будем рассматривать обобщение указанной задачи. А именно, мы рассмотрим задачу упаковки прямоугольников из некоторого списка L в несколько полубесконечных полос, заданной ширины каждая. В качестве критерия эффективности упаковки, который минимизируется, рассматривается максимальная среди всех полос высота заполнения (make-span).

В [10] показано, что даже более частная задача, заключающаяся в упаковке в полосу прямоугольников равной ширины, NP-полная, поэтому для решения подобных задач обычно рассматривают эвристические алгоритмы, которые позволяют найти приближённое решение. Одна из таких эвристик основана на последовательном выборе прямоугольников из списка, и упаковке их на минимально возможную высоту в самую левую из возможных позиций (bottom-left). В общем случае упаковка, получаемая данной эвристикой, может быть в произвольное число раз хуже оптимальной. С другой стороны, для любого упорядоченного списка может быть показано, что гарантированная оценка точности равна трём, т.е. для любого упорядоченного по убыванию ширины списка прямоугольников высота заполнения, полученная с помощью эвристики, превосходит не более чем в три раза высоту оптимального заполнения [3].

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

2. Формулировка результата

Пусть задано множество полос , ограниченных снизу. Ширина г-й

полосы — Wi. Требуется упаковать прямоугольники из списка L в полосы. В качестве критерия эффективности упаковки используется максимальная среди всех полос высота заполнения.

Рассмотрим следующий эвристический алгоритм упаковки. Прямоугольники выбираются последовательно из списка L. Для размещения прямоугольника среди всех полос выбирается та, на которой прямоугольник может быть размещён на минимальной высоте. На выбранной полосе прямоугольник размещается на минимальной высоте в самой левой позиции из возможных. Пусть Нвl — максимальная высота заполнения среди всех полос при использование описанной эвристики.

Пусть НоР — минимально возможное значение критерия при заданном списке прямоугольников.

Теорема 1. Если в списке Ь прямоугольники упорядочены по ширине, тогда

— >-• (1) Явь ~ 3 К ]

3. Доказательство теоремы 1

Пусть Н.1 высота заполнения в г-й полосе при использовании эвристики, тогда

Нвь = тах Я,:.

1 <г<М

В каждой полосе 5,: выделим какой-нибудь прямоугольник с высотой /г.,-и шириной га,-, верхняя граница которого находится на высоте Н^. Пусть нижняя граница прямоугольника р^ находится на высоте у,-, тогда

II: .'/• '

Пусть максимальное значение высоты у, достигается в полосе 5^0, т.е.

г0 € Аг^аху*.

1<г<М

Обозначим через П множество всех полос, в которых возможно разместить Рг0 :

п = {5,: I 1 < г < М, > ш,:0} .

Покажем, что для каждой полосы из П область, ограниченная высотой у,0, имеет плотность упаковки не меньше ^ прямоугольниками ширины, не превосходящей га,;0. Для доказательства воспользуемся техникой описанной в [3] для одной полосы. Рассмотрим момент, в который был упакован прямоугольник рг0. Так как список Ь упорядочен, то все прямоугольники, упакованные к этому моменту, не меньше р,0 по ширине. Рассмотрим произвольную полосу 5,: € П. Любую горизонтальную прямую пересекающую г-ю полосу можно разбить на участки внутри полосы занятые и незанятые прямоугольниками. Степень заполнения можно получить «интегрируя» по высоте относительную длину заполненных участков на каждой из таких прямых. Покажем, что в выбранной полосе 5,: для любой горизонтальной прямой проходящей ниже у10 суммарная длина занятых частей не меньше суммарной длины незанятых. Так как множество прямых, содержащих верхние или нижние стороны прямоугольником, имеет меру нуль,

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

В силу того, что р10 упакован выше у,;0, любая горизонтальная прямая ниже г/ъ0 пересекает хотя бы один прямоугольник в полосе 5,:. Докажем, что левая сторона первого слева прямоугольник р', пересекаемого любой прямой, лежит на левой границе полосы. Предположим это не так, тогда, в силу используемого алгоритма упаковки, должен существовать прямоугольник р", к которому р' прилегает справа. Ширина незаполненного отрезка прямой лежащего левее р' не меньше ги" > ги,:0. В силу используемого способа упаковки не один прямоугольник не был упакован над незаполненным отрезком. Следовательно, мы пришли к противоречию, так как прямоугольник р.щ можно было бы разместить над р" и его нижняя граница оказалась бы ниже высоты у,;0.

Теперь рассмотрим отрезок в незаполненного пространства произвольной прямой, лежащий ниже гц0. Пусть р — прямоугольник, граничащий с в слева. Так как р,:0 упакован выше у,;0, длина в должна быть меньше ш,;0 (иначе существовал бы прямоугольник, который мог быть упакован ниже). Прямоугольник р упакован раньше р,:0, поэтому ширина р больше ги,:0. Таким образом, для каждого отрезка незаполненного пространства существует прямоугольник, имеющий ширину больше, чем длина этого отрезка, примьткаютций непосредственно слева к нему отрезку. Следовательно, суммарная длина занятых частей меньше суммарной длины незанятых, откуда получаем, что полоса 5,: ниже у,;0 заполнена хотя бы наполовину. В силу произвольности выбора полосы мы получаем, что для любой полосы из П область, лежащая ниже уровня у,;0, имеет плотность заполнения не меньше \ прямоугольниками, которые нельзя разместить ни в одной из полос не принадлежащих П. Таким образом, получаем нижнюю оценку на высоту оптимальной упаковки:

Среди всех полос выберем полосу с максимальной высотой заполнения:

Тогда с одной стороны можно выразить значения высоты упаковки при использовании эвристики,

к € А^тахД,; = Ащтах (у,; + /?,;) .

1 <г<М

1 <г<М

Нвь = Нк = у к + Ьк,

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

Н0р > hk-

Собирая вместе (2), (3), (4), (5) и (6), получаем

Нрр max (\yi0,hk) _ max (\yio, hk) max(|yio,fet) 1 Hbl ~ Hk yk + hk ~ 2/i + hk ~ 3 ’

откуда следует утверждение теоремы.

4. Составление расписаний для кластеров

Рассмотрим следующую упрощённую модель управления вычислительными ресурсами. Имеется набор кластеров, каждый с заданным числом процессоров. Распределитель (брокер) распределяет имеющиеся у него задачи среди этих кластеров. Для каждой задачи известно необходимые для её выполнения время и число процессоров. При этом брокер не занимается напрямую составлением расписаний на каждом кластере. Тогда описанный в разделе 2 алгоритм может быть использован для составления расписаний следующим образом.

Брокер последовательно выбирает задачи из имеющегося у него списка, и опрашивает кластеры, определяя, когда каждый из кластеров может выполнить задачу в соответствие с очередью на нем. Для размещения задачи брокер выбирает тот кластер, на котором задача завершится раньше всего. Каждый из кластеров, получая задачу от брокера, размещает её как можно раньше, используя по возможности процессоры с меньшими номерами.

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

Аналогично тому, как это было проделано в предыдущей части, можно оценить точность эвристики. При этом для оценки плотности заполнения можно воспользоваться тем, что суммарная длина свободного пространства вдоль каждой горизонтальной прямой меньше ширины р,:0, и таким образом получить, что плотность заполнения ниже у,:0 не меньше половины. Так как оценка на плотность не изменится, то и не изменится оценка

на высоту оптимального заполнения. Таким образом, останется в силе гарантированная оценка на точность упаковки.

Литература

[1] A. Abraham, R. Buyya, В. Nath, Nature’s heuristics for scheduling jobs on Computational Grids, International Conference on Advanced Computing and Communications (2000).

[2] B. S. Baker, D. J. Brown and H. P. Ivatseff, A 5/4 algorithm for two-dimensional packing, J. of Algorithms, 1981, v. 2, pp. 348-368.

[3] B. S. Baker, E. J. Coffman and R. L. Rivest, Orthogonal packings in two dimensions, SIAM J. Computing, 1980, v. 9, pp. 846-855.

[4] P. Brucker, Scheduling Algorithms, Springer Ferlag (1998), 217-218.

[5] E. G. Coffman, Jr., M. R. Garey, and D. S. Johnson. Approximation Algorithms for Bin-Packing - An Updated Survey. In Algorithm Design for Computer System Design, ed. by Ausiello, Lucertini, and Serafini. Springer-Verlag, 1984.

[6] E. J. Coffman, M. R. Garey, D. S. Johnson and R. E. Tarjan, Performance bounds for level-oriented two-dimensional packing algorithms, SIAM J. Computing, 1980, v. 9, pp. 808-826.

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

[8] R. E. Ivorf, Optimal rectangle packing: Initial results, in Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS-03), Trento, Italy, June 2003, pp. 287-295.

[9] D. D. Sleator, A 2.5-times optimal algorithm for bin packing in two dimensions, Inf. Processing Letters, 1980, v. 10, pp. 37-40.

[10] J.D. Ullman, Complexity of sequencing problems, Computer and Job-shop Scheduling Theory, E. G. Coffman, Jr. (ed), John Wiley and Sons, New York, 1975.