Автоматика и телемеханика, JVs 2, 2008
Дискретные системы
РАСЭ 02.60.Pn
© 2008 г. Э.А. МУХАЧЕВА, д-р техн. наук, Д.А. НАЗАРОВ
(Уфимский государственный авиационный технический университет)
КОНСТРУИРОВАНИЕ ПРЯМОУГОЛЬНЫХ УПАКОВОК: АЛГОРИТМ "ПЕРЕСТРОЙКИ" НА БАЗЕ БЛОЧНЫХ СТРУКТУР1
Рассматриваются задачи ортогональной упаковки прямоугольников в заданной области. Известны многие однопроходные эвристические методы их решения. Они служат в качестве декодеров в алгоритмах локального поиска оптимума. Некоторые из них применяются в качестве конструктивных эвристик. В том и другом случаях полезно применение гибридных методов с включением приемов, улучшающих качество упаковки. Обоснован и описан один из таких приемов - алгоритм "перестройки". Для его реализации удалось построить алгоритм с линейной вычислительной сложностью. Приведены результаты численного эксперимента.
1. Введение
Под задачами упаковки понимается широкий класс проблем, допускающих различное толкование. Общим является наличие двух групп объектов. Между элементами этих групп устанавливается и оценивается соответствие. Среди различных моделей важное место занимают задачи ортогональной упаковки в полубесконечную полосу (2D Strip Packing Problem (2DSPP)).
В 2DSPP требуется упаковать в полосу ширины W прямоугольные предметы заданной ширины wi и длины U, i = 1, m, так чтобы прямоугольники не перекрывались между собой и не выходили за границы полосы. Размещение прямоугольников в полосе, удовлетворяющее этим требованиям, называют допустимой прямоугольной упаковкой (Rectangular Packing (RP)). Если при этом длина L = тах(ж^ + ¡i)
i
занятой части полосы достигает минимума, то RP - оптимальная упаковка. Обзору методов решения задач раскроя и упаковки посвящены работы зарубежных и российских авторов [1-3]. Методы локального поиска на базе блочных структур для решения задач ортогональной упаковки рассмотрены в [4], а новые блочные декодеры в [5].
Ситуация, в которой полезно переставить детали в упаковке с сохранением ж-ко-ординат, была замечена Э.А. Мухачевой и названа "перестройкой" (Reconstruction
1 Работа выполнена при частичной финансовой поддержке Российского фонда фундаментальных исследований (проект № 03-01-07002).
4 Автоматика и телемеханика, № 2
97
(Ree)). Эта ситуация и переборные алгоритмы реализации перестройки подробно описаны в [6]. Е.М. Бронштейн предложил алгоритм перестройки на графах, используя. по существу, проверку планарности графа [7]. А.Ф. Валеева реализовала этот алгоритм для безотходных упаковок [8]. Его сложность O( ). Здесь проведено обоснование и описание двух новых версий "перестройки" с использованием графа упаковки. Первый алгоритм имеет сложность O(m log m), второй основан на блочной структуре упаковки и его вычислительная сложность O(m). Аналогичных Ree алгоритмов авторы в литературе не встретили.
При решении 2DSPP ВХОДНОЙ информацией является (W,m,w,l). Выходом служит код (x,y), x = (xi,... ,xm), y = (yi,... ,ym), где (xi,yi) - минимальные координаты вершин ¿-го прямоугольника. Этого достаточно для построения эскиза упаковки.
2. Общая схема алгоритма перестройки
Исходные данные основной задачи. Рассматривается частичная прямоугольная упаковка в полубесконечную полосу. Она задается информационным вектором
(1) (W; m; w; l; x; y),
w = (wi,... ,wTO), l = (li,... ,lm), x = (xi,... ,xTO), y = (yi,... ,ym), где W - ширина полосы; m - количество уже уложенных прямоугольников; wi, li - ширина и длина ¿-го прямоугольника; (xi,yi) - координаты его левого нижнего угла.
Определение 1. Разделительной линией для прямоугольной упаковки, заданной информационным вектором (W; m; w; l; x; y), называется прямая x = а, удовлетворяющая условиям:
1.1) существует такой прямоугольник Pi, что xi + li = а,
1.2) не существует такого прямоугольника Pi, что xi > а.
Условие 1.1 означает, что разделительная линия проходит через правую боковую сторону, по крайней мере, одного из прямоугольников в упаковке, а условие 1.2 гарантирует, что в упаковке не найдется прямоугольника целиком находящегося справа от разделительной линии (см. рис. 1).
Определение 2. Назовем прямоугольник Pi а-свободным для разделительной линии x = а, если для него выполняется xi + li > а. Мужество всех а-сво-бодных прямоугольников обозначим как ГЯ(а).
Задача перестройки (2D Strip Packing Reconstruction Problem (2DSPR)). По заданным разделительной линии x = а и множеству I = (li,... ,In), состоящему из
P IP Рз 1 Р4 Рз Р5 1
1 Р2 1
Pi Pi
Р4 |Р5 J Р4 Р5
Рз Рз
Р2 Р2
Pi Pi
Рис. 1. Пример разделительных ,11и:ни:й: а и б - проведенные .'шшш не являются разделительными, так как нарушаются условия 1.1 и 1.2 соответственно; о и г - примеры разделительных линии (д,1!я одной упаковки таких ,11и:ни:й может быть несколько).
а
попарно непересекающихся подмножеств FR(a), требуется перестроить прямоугольную упаковку так. чтобы
1) x-координаты всех прямоугольников не изменились;
2) для j = 1, n существовала перестановка ipj из номеров прямоугольников Pi G Ij такая, что yVjk = yVjkl + wVjk_i для k = 2, |Ij
Эта задача является NP-полной. В статье будет предложен алгоритм, который решает 2DSPR задачу с дополнительным ограничением, которое выводит ее из класса NP-полных задач. Это ограничение будет введено в 2.1. Общая схема алгоритма перестройки состоит их трех этапов. На первом этапе происходит преобразование исходных данных частичной упаковки (1) в граф упаковки. На втором этапе задача перестройки будет решена для полученного графа. Наконец, обратное преобразование из графа в перестроенную упаковку будет выполнено на третьем этапе.
2.1. Преобразование частичной упаковки в граф
Пусть имеется частичная упаковка (W; m; w; l; x; y). Дополним ее фиктивными прямоугольниками так, чтобы в упаковке не было пустого пространства перед разделительной линией x = а.
Для каждого не а-свободного прямоугольника Pi проведем линию через его правую боковую сторону до пересечения с другими прямоугольниками или границами полосы. Для всех прямоугольников проведем линию через их левую боковую сторону до пересечения с другими прямоугольниками или границами полосы. Разделитель-нэя линия дополнительно выделяет фиктивные прямоугольники (см. рис. 2). Такое допол нение фиктивными прямоугольниками назовем вертикальным.
еу т в g р jk j\ g h и е 1. Проведенные линии при вертикальном дополнении фиктивными прямоугольниками и исходные прямоугольники разбивают пустое пространство внутри упаковки до разделительной линии на прямоугольные области, количество которых не превосходит 4m.
Дополним исходную информацию так, чтобы в ней содержались и добавленные фиктивные прямоугольники. Дополненную информацию будем обозначать информационным вектором (W ; m; m ; w; l; x; y), где m - общее количество прямоугольни-
m
строим алгоритм, который получает расширенный информационный вектор из вектора (1).
Алгоритм 1. Нахождение фиктивных прямоугольников при вертикальном дополнении.
(W; m; w; l; x; y) а
линии.
Р8 i Р10 P4 1 Pi2
P3 P7
P2 P9
P5 P11
Pi /
Рб
Рис. '2. Пример вертикального дополнения (линии через боковые стороны прямоугольников проведены пунктиром (они выделили фиктивные прямоугольники P8, P9 и Pío), а жирная линия, пересекающая упаковку, является разделительной (она выделила фиктивные прямоугольники P11 и P12)).
4* 99
Выходные данные: (W; m; m; w; l; ж; y) дополненная информация.
1. Создать список p, в котором все прямоугольники упорядочены по неубыванию xj, а при равен стве xj - то возрастанию y^ Создать спи сок р, в котором все прямоугольники упорядочены по неубыванию xj + l j, а при равен стве xj + lino возрастанию yj.
2. Создать два сбалансированных дерева TD и TU. (В TD хранятся у-координаты препятствий, которые могут встретиться при проведении вертикального отрезка через боковую сторону некоторого прямоугольника вниз, а в Тц - вверх.) В TD поместить 0, а в Тц поместить W. Создать список LV. (В LV хранятся вертикальные отрезки.)
3. Прямоугольники в списке p означают появление препятствия, а в списке р -
исчезновение препятствия. Одновременно просматривая элементы списков p и р
левого нижнего угла прямоугольника из p и правого нижнего угла прямо-рр в ыб р&нн ыи
прямоугольник с номером i из p, то выполнить пункт 3.1, иначе - 3.2.
3.1. Выполнить пункт 3.3 для X = xj и Y = у^. Добавить в TD число yj + wj, а в TU число yj.
3.2. Удалить из TD число yj + wj; а из TU
yj
X = Xj + lj и Y = yj.
3.3. Найти в TD максимальное число, меньшее Y. Пусть это будет Y- Найти в TU минимальное число, большее Y. Пусть это будет Y. Добавить отрезок [(X,Y), (X,Y)] в список LV.
4. Пройтись по полученному списку вертикальных отрезков LV (он уже отсортирован) и отбросить повторяющиеся вертикальные отрезки. Отбросить из LV все вертикальные отрезки, расположенные не левее разделительной линии x = а. Добавить в конец списка вертикальный отрезок [(а, 0), (а, W)].
5. Взять первый вертикальный отрезок из LV и первый прямоугольник в соответствии с порядком, заданным списком p. Если рассматриваемый прямоугольник не опирается на текущий вертикальный отрезок, то вставить фиктивный прямоугольник с шириной, равной длине этого отрезка. Для определения длины фиктивного прямоугольника найти с помощью двоичного поиска в LV вертикальный отрезок, на который он опирается и расположенный правее его. Убрать первый вертикальный отрезок из LV и начать все заново. Если же прямоугольник опирается на вертикальный отрезок, то тогда вырезать ту часть отрезка, на которую опирается прямоугольник. В результате этой операции исходный отрезок мог выродиться или распасться на один или два отрезка. Все полученные отрезки добавить в начало LV, предварительно удалив из LV исходный отрезок, а рассматриваемый прямоугольник удалить из списка p. Если в p остались прямоугольники, то начать все заново. Иначе проверить, что в LV остался один отрезок. Если это не так, то для каждого "лишнего" отрезка (каждый такой отрезок является началом фиктивного прямоугольника) найти длину соответствующего фиктивного прямоуг
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.