close

Вход

Забыли?

вход по аккаунту

?

Задача упаковки в полосу асимптотически точный подход.

код для вставкиСкачать
1997
ИЗВЕСТИЯ ВЫСШИХ УЧЕБНЫХ ЗАВЕДЕНИЙ
МАТЕМАТИКА
Є 12 (427)
УДК 519.852
Э.Х. ГИМАДИ, В.В. ЗАЛЮБОВСКИЙ, П.И. ШАРЫГИН
ЗАДАЧА УПАКОВКИ В ПОЛОСУ:
АСИМПТОТИЧЕСКИ ТОЧНЫЙ ПОДХОД
1. Введение
Задача упаковки в полосу (ЗУП) формулируется следующим образом. Пусть имеется полубесконечная полоса ширины W и список прямоугольных предметов S = fai j i = 1; : : : ; ng.
Предмет ai 2 S имеет ширину wi W и высоту hi . Требуется упаковать все предметы из списка
S в полосу минимальной высоты. Упакованные предметы не должны перекрывать друг друга,
их стороны должны быть параллельны сторонам полосы, вращение предметов не допускается.
В литературе эта задача встречается также под названием \двумерная ортогональная задача
упаковки".
Нетрудно заметить, что частными случаями рассматриваемой задачи являются известные
NP -трудные задачи упаковки в контейнеры (при hi const; i = 1; : : : ; n) и задача многопроцессорного расписания (при wi const; i = 1; : : : ; n). В силу этого задача упаковки в полосу также
NP -трудна.
Имеется множество работ, посвященных анализу наихудшего поведения приближенных алгоритмов для решения ЗУП [1]. Гораздо меньшее количество статей содержит анализ среднего
поведения таких алгоритмов. В настоящей статье для исследования поведения приближенного
алгоритма на списках со случайными значениями wi и hi применяется асимптотически точный
подход, предложенный в [2]. Предполагается знакомство читателя с работой [3].
В разделе 2 приводятся основные определения, обозначения и формулируются некоторые
предварительные утверждения. Раздел 3 содержит формулировку и доказательство основных
утверждений, касающихся условий асимптотической точности предложенного алгоритма для
ЗУП. В разделе 4 рассматривается обобщение ЗУП, связанное с введением частичного порядка
на множестве предметов. Раздел 5 посвящен исследованию связи ЗУП с задачей календарного
планирования с нескладируемым ограниченным ресурсом.
2. Основные определения и предварительные сведения
Напомним ряд определений, содержащихся в [3].
Пусть имеется некоторый алгоритм A для решения оптимизационной задачи на минимум.
Обозначим через FA (S ), F (S ) значения целевых функций на решении индивидуальной задачи
S , получаемом с помощью алгоритма A, и оптимальном решении соответственно. Будем говорить, что алгоритм A удовлетворяет оценкам ("n ; n ) на классе задач Kn размерности n, если
для всех S 2 Kn выполнено неравенство
PrfFA (S ) > (1 + "n)F (S )g n :
Алгоритм A называется асимптотически точным на классе задач K, если существуют такие
последовательности ("n ), (n ), что для любого n алгоритм A удовлетворяет оценкам ("n ; n ) на
подмножестве Kn K задач размерности n и при этом "n ! 0, n ! 0, когда n ! 1.
Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований
(код проектов 96-01-01591 и 97-01-00890).
34
Параметры "n и n можно рассматривать как оценки относительной погрешности и вероятности несрабатывания алгоритма соответственно.
Неотрицательную функцию f целочисленного аргумента r 2 Ib = f1; 2; : : : ; B g будем называть b-асимметричной (b{симметричной), если f (r) f (b ; r) (соответственно f (r) = f (b ; r))
при r = 1; : : : ; bb=2c и f (r) = 0 при r > b.
Нетрудно заметить, что класс B -асимметричных функций включает в себя B -симметричные
функции, неубывающие функции, функции с постоянным значением на сегменте [1; B ].
Функцию f будем назвать B -регулярной при B = 2Q , Q целое, если она представима в виде
суммы 2k -симметричных функций f (k) , k 2 IQ ,
f (r) =
Q
X
k=1
f (k)(r); r 2 IB :
В [3] показано, что разложение B -регулярной функции f на 2k -симметричные составляющие
может быть записано в виде
Q
X
f (r) = f (k)(r); r 2 IB ;
где
k=kr
kB = Q; kr = minfk j r < 2k g = dlog2 (r + 1)e; 1 r < B:
Такое разложение будем называть каноническим.
Будем называть b-связкой предмет веса b либо пару предметов с весами r и b ; r при r =
1; : : : ; bb=2c.
В [3] предложен приближенный алгоритм A1 упаковки предметов в контейнеры. В случае
B = 2Q , Q целое, алгоритм A1 последовательно для k = Q; Q ; 1; : : : ; 1 образует список 2k связок и упаковывает этот список в контейнеры по принципу алгоритма NFD (\следующий
пригодный с предварительным упорядочением по невозрастанию"). Предметы подсписка S 0 S ,
не вошедшие в полностью заполненные контейнеры, алгоритм A1 упаковывает с помощью NF {
алгоритма (\следующий пригодный"). Описание алгоритмов NFD и NF можно найти в [1].
В случае B -асимметричных списков, а также при B 6= 2Q , Q целое, используется упрощенная
версия алгоритма A1 : сначала заполняем контейнеры B -связками, а оставшиеся предметы ai 2
S 0 размещаем с помощью NF -алгоритма.
Для решения задач упаковки в контейнеры со случайными весами предметов в [3] применяется модифицированный приближенный алгоритм Ae1 , который использует решение, полученное
с помощью алгоритма A1 для некоторого оценочного списка Se при условии, что он мажорирует
исходный список S .
Далее считаем, что класс Kn2 состоит из задач упаковки двумерных предметов (прямоугольников) в полосу со следующей моделью формирования случайного списка S : производится серия
n независимых испытаний, в каждом из которых очередной предмет ai, i = 1; : : : ; n, принимает
свои размеры | ширину wi и высоту hi | в соответствии с одинаковой дискретной функцией
распределения
pwh = Prfwi = w; hi = hg 0; w = 1; : : : ; W; h = 1; : : : ; H;
W X
H
X
w=1 h=1
pwh = 1:
Введем обозначения:
Sh = fai j hi = h; i = 1; : : : ; ng | подсписок, состоящий из предметов высоты h, h = 1; : : : ; H ;
(wh) | матрица с компонентами wh = 2(n ln npwh(1 ; pwh ))1=2 , где w = 1; : : : ; W , h =
1; : : : ; H ;
Ae2 | алгоритм, состоящий в последовательном применении к подспискам S1; : : : ; SH описанного ранее алгоритма Ae1 решения одномерной задачи упаковки в контейнеры (при этом под
весом предмета понимается его ширина);
35
p =
1
WH
W P
H
P
w=1 h=1
whpwh | отношение математического ожидания площади прямоугольника,
задаваемого размерами предмета, к максимально возможной площади предмета;
FAhe1 | количество контейнеров, полученное в результате применения алгоритма Ae1 к списку
Sh, h = 1; : : : ; H ;
H
FAe2 = P hFAhe1 | высота полосы, полученная в результате упаковки предметов списка S с
h=1
помощью алгоритма Ae2.
Говорим, что алгоритм Ae2 срабатывает применительно к конкретной реализации случайного
списка S , если для всех w = 1; : : : ; W , h = 1; : : : ; H выполнено неравенство
jS (w; h) ; npwhj wh;
(1)
где S (w; h) | число предметов ширины w и высоты h в списке S .
Матрицу назовем W -регулярной (W -асимметричной, W -симметричной, неубывающей), если
W -регулярна (W -асимметрична, W -симметрична, неубывающая) каждая строка матрицы. Напомним, что в случае W -регулярной матрицы предполагаем, что W = 2Q , Q целое.
3. Условия асимптотической точности
Если
WH
= o(n= ln n), то вероятность несрабатывания алгоритма Ae2 ограни
чена величиной o n ln1 n .
wh событие, противоположное (1), имеем
Доказательство. Обозначив через A
Лемма 1.
Ae2 = Pr
W [
H
n[
w=1 h=1
o
Awh W X
H
X
w=1 h=1
Pr(Awh):
При оценивании вероятности несрабатывания
алгоритма понадобятся неравенства для веn
P
роятностей больших отклонений суммы Sn = i независимых случайных величин 1 ; : : : ; n ,
i=1
распределенных по закону Бернулли
Prfi = 1g = p; Prfi = 0g = 1 ; p; i = 1; : : : ; n:
При = o(n2=3 ) справедливо неравенство [3]
2 ;
PrfjSn ; npj g c exp ; 2np(1
; p)
где c = 2(1 + o(1)). Воспользовавшись этим неравенством (поскольку wh = o(n2=3 )), с учетом
условия леммы получим
W X
H
W X
H
2
X
X
npwh(1 ; pwh) =
Ae2 c
exp ; 2np (1wh; p ) = c
exp ; 4n2ln
npwh(1 ; pwh)
wh
wh
w=1 h=1
w=1 h=1
W X
H
X
1
CWH
o
(
n=
ln
n
)
1
=c
2 = n2 =
n2 = o n ln n : w=1 h=1 n
Теорема 1. Если матрица (pwh ) W {асимметрична, то при WH = o(n= ln n) алгоритм
e
A2 приводит к асимптотически точному решению ЗУП из класса Kn2 ; при этом справедливы
следующие оценки вероятности несрабатывания и относительной погрешности:
s
!
W
1
Ae2 = o n ln n ; "Ae2 = O n= ln n :
36
Оценка Ae2 = o n ln1 n ! 0 при n ! 1 следует из леммы 1. Отсюда с
вероятностью, стремящейся к 1 при n ! 1, Ae2 имеет дело со списком S , в котором для всяких
w = 1; : : : ; W и h = 1; : : : ; H выполнены неравенства
dnpwh + whe S (w; h) bnpwh + whc
(2)
Доказательство.
и в качестве оценочного может быть взят список Se с характеристической функцией S (w; h) =
bnpwh + whc. Взятый в таком виде оценочный список является W -асимметричным [3].
Для вычисления относительной погрешности "Ae2 = FAe2 =FS ; 1 понадобятся оценки величин
FS и FAe2 соответственно снизу и сверху.
Оптимальное значение целевой функции FS для ЗУП со списком S не меньше, чем
H
H
P
h P S (w; h) плюс (в случае четных W ) P hS (B=2; h)=2. Отсюда
h=1
h=1
w>B=2
H
X
F h
S
h=1
X
w>W=2
S (w; h) + S
W ; h W + 1 2
2
и с учетом (2)
H
X
F h
S
h=1
X
(npwh ; wh) + (npbW=2c;h ; bW=2c;h
W + 1 :
2
w>W=2
Для оценивания сверху величины FAe2 воспользуемся свойствами оценочности списка Se и его
W {асимметричности
FAe2 =
H
X
hF h
Ae2
H X
X
h
l
j
W k; hn W + 1 om Se(w; h) + Se 2
2
W
+
1
h
(npwh + wh ) + (npbW=2c;h + bW=2c;h ) 2
+ 1:
h=1
w>W=2
h=1
H
X
X
h=1
w>W=2
Для величины "Ae2 имеем
F
"Ae2 = FAe2 ; 1 S
2
H
P
h=1
H
P
h=1
h
P
H
P
h=1
w>W=2
wh + bW=2c;h
n
W +1
2
o
+ 21
n
w>W=2 (npwh ; wh ) + (npbW=2ch ; bW=2ch )
H
P
P
hn
P
h
h=1
w>W=2
h2
P
wW=2
o
2
wh + 1
pwh + pbW=2ch
W +1
n
W +1
2
o
;
P
wW=2
wh
:
В силу W {асимметричности функции pwh для всякого h = 1; : : : ; H справедливы неравенства
X
pwh + pb W2 ch W 2+ 1 12 :
w>W=2
Кроме того,
X
wW=2
wh W
X
w=1
p
wh = 2 n ln n
W q
X
w=1
37
p
pwh(1 ; pwh) 2 Wn ln n:
С учетом последних соотношений имеем
H
P
"Ae2 p
q
(4 Wn ln n + 1)h
h=1
H ;
P
n
h=1
2
p
; 2 Wn ln n h
Таким образом, "Ae2 = O
q
W
n= ln n
=
8
W ;
n= ln n
q
1 + 4pW1n ln n 8
q
1 ; 4 n=Wln n
W ;
n= ln n
1 + pW n1 ln n
q
:
1 ; 4 n=Wln n
. По условию теоремы имеем
W
WH
n= ln n n= ln n ! 0 при n ! 1;
т. е. W = o(n= ln n) и "Ae2 ! 0 при n ! 1.
Теорема 2. Если матрица (pwh ) W {регулярна, то при
WH=p = o(n= ln n)
(3)
алгоритм Ae2 приводит к асимптотически точному решению задачи упаковки предметов в
полосу из класса Kn2 ; при этом справедливы оценки качества алгоритма
s
1
WH=
p
Ae2 = o n ln n ; "Ae2 = O n= ln n :
Доказательство. С учетом соотношения (3) и леммы 1 для вероятности несрабатывания
Ae2 имеем
1
Ae2 = o n ln n ! 0 при n ! 1:
Итак, с вероятностью, стремящейся к 1 при n ! 1, алгоритм Ae2 имеет дело со списком S , в
котором для всяких w = 1; : : : ; W и h = 1; : : : ; H
dnpwh ; whe S (w; h) bnpwh + whc:
Определим список Se по его характеристической функции
;
Se(w; h) = b' p(whQ) c +
где
Q
;1
X
k=kw
d';p(whk)e; w = 1; : : : ; W; h = 1; : : : ; H;
'(x) = nx + 2(nx ln x)1=2;
(
fk j w < 2k g = dlog2 (w + 1)e при 1 w < W;
kw = min
Q
при w = W;
а fp(whk) ; w = 1; : : : ; W g, k = 1; : : : ; Q, | совокупность 2k -симметричных составляющих в каноническом разложении W -регулярной строки матрицы (pwh).
Убеждаемся, что список Se является оценочным:
S (w; h) bnpwh + whc bnpwh + 2(n ln npwh)1=2 c = n
n
Q
X
k=kw
p
k
wh
Q
X
1
=
2
(pk
+ 2(n ln n)
k=kw
wh
)1=2
38
=
Q
X
k=kw
Q
X
k=kw
pkwh + 2 n ln n
; (Q) wh
'p
Q
X
k=kw
pkwh
Se(w; h):
1=2 Лемма 2.
где "bn =
В условиях доказываемой теоремы справедливы оценки
FS nHp(1 ; 2"bn );
FAe2 nHp(1 + 2"bn + "bn2 = ln n);
W H=p
n= ln n
1=2
.
Оценка снизу
W X
H
X
FS W1
whS (w; h) > W1
Доказательство.
w=1 h=1
p
n ln n
nHp ; 2 W
p
n ln n
nHp ; 2 W
W X
H
X
wh(npwh ; wh) w=1 h=1
W X
H
X
whppwh w=1 h=1
W H
W X
H
XX
X
w=1 h=1
q
wh w=1 h=1
whpwh
1=2
p
nHp ; 2H n ln n WHp = nHp(1 ; 2"bn ):
Оценка сверху
FAe2 =
H X
h=1
H
X
h=1
F h
Ae1
h 1 + W1
H X
h W1
h=1
Q
W
X
X
w
W
X
w=1
wSe(w; h) ; (k) wh
'p
w=1
k=kw
Q W
X
X
(k)
wh
w=1 k=kw
+ Q ; kw
=
;
1
S
1
(k )
(k) 1=2
np + 2 n ln npwh(1 ; pwh)
= h 1+ W + W w
h=1
p
H W
W
q
X
X
X
n
2
n
ln
n
h W + W wpwh + W
w (Q ; kw + 1)pwh w=1
w=1
h=1
p
2
n ln n S;
2
WH + nHp + W
W
P
где S1 = w(Q ; kw ) W 2=4;
H X
w=1
S=
откуда
W H
XX
w=1 h=1
W X
H
X
w=1 h=1
W X
H
X
whpwh p
q
wh (Q ; kw + 1)pwh w=1 h=1
1=2
wh(Q ; kw + 1)
q
WH WHp;
q
FAe2 nHp + 2 n ln nH WHp + WH 2 = nHp(1 + 2"bn + "bn2 = ln n): Продолжим доказательство теоремы. Оценим относительное отклонение значения целевой
функции FAe2 , полученного в результате работы алгоритма Ae2 , от оптимального значения FS ,
F
(1 + 2"bn + "bn2 = ln n) ; 1 = 4"bn + "bn2 = ln n) = O("b ):
"Ae2 = FAe2 ; 1 nHpnH
n
1 ; 2"bn
p (1 ; 2"bn )
S
Поскольку "bn =
q
W H=p
n= ln n
, то "Ae2 = O
q
W H=p
n= ln n
! 0 при n ! 1: .
39
4. Учет частичного порядка
Рассмотрим теперь класс задач упаковки в полосу двумерных предметов, на множестве которых задан частичный порядок в виде ориентированного графа без контуров. Пусть алгоритм
A2 состоит в последовательном применении алгоритма Ae2 к подмножествам правильного разбиения 0списка S 00= fai j i = 1; : : : ; ng, т. е. такого разбиения (S ), = 1; : : : ; , что из ai aj ,
ai 2 S , aj 2 S следует 1 0 < 00 . Класс Kn случайных списков образуем с помощью схемы n последовательных независимых испытаний: на i-м шаге предмет ai принимает вес
wi = w, длину hi = h и помещается в подмножество S i согласно дискретному распределению
pwh = Prfwi = w; hi = h; i = g 0;
w = 1; : : : ; W ; h = 1; : : : ; H ; = 1; : : : ; ;
W X
H X
X
w=1 h=1 =1
pwh = 1:
Будем говорить, что список S обладает некоторым свойством, если им обладает вектор
(p1h ; p2h ; : : : ; pW h ) для всех h = 1; : : : ; H ; = 1; : : : ; .
Проведем вероятностный анализ алгоритма A2 для W -регулярных списков. Обозначим
wh = 2(npwh(1 ; pwh) ln n)1=2:
Считаем, что алгоритм A2 срабатывает на конкретной реализации случайного списка S , если
для всякой тройки индексов w, h, осуществилось событие Awh , т.е. выполнено неравенство
jS (w; h; ) ; npwhj < wh:
(4)
В алгоритме A2 будем использовать оценочный список с характеристической функцией вида
Q)
Se(w; h; ) = b'(p(wh
)c +
Q
;1
X
k=kw
k)
d'(p(wh
)e;
w = 1; : : : ; W ; h = 1; : : : ; H ; = 1; : : : ; ; где выделенные для любой пары (h; ) векторы
(pk1h ; pk2h ; : : : ; pkW h ), k = 1; : : : ; Q, | суть 2k -симметричные составляющие в каноническом разложении W -регулярного вектора (p1h ; p2h ; : : : ; pW h ).
Теорема 3. Алгоритм A2 на классе Kn c W -регулярными случайными списками предметов при
WH =p = o(n= ln n)
(5)
асимптотически точен с оценками
s
1
WH
=
p
A2 = o n ln n ; "A2 = O
n= ln n ;
где
W X
H
X
1 X
p = WH
whpwh; pwh = pwh:
w=1 h=1
Доказательство
=1
проводим по той же схеме, что и в теореме 2.
A2 = Pr
C1
n [
w;h;
o
Awh W X
H X
X
w=1 h=1 =1
Pr(Awh) npwh(1 ; pwh) C1 WH exp ; 4n2ln
npwh(1 ; pwh)
n2
w=1 h=1 =1
= o 1 ! 0 при n ! 1;
C1nWH
2 p
n ln n
W X
H X
X
40
где Awh | событие, противоположное (4).
W X
H X
X
1
F wh (w; h; ) > 1
W w=1 h=1 =1
S
S
W X
H X
X
W w=1 h=1 =1 wh(npwh ; wh) p
W X
H X
n ln n X
whppwh nHp ; 2 W
w=1 h=1 =1
W H W X
H X
X XX
X
p
1=2
n ln n
nHp ; 2 W
wh whpwh w=1 h=1 =1
w=1 h=1 =1
p
2
2
n ln n WH W H 1=2 = nH (1 ; p2");
nHp ; 2 W
p
p
n
2
где
=p 1=2 ! 0 при n ! 1;
"n = WH
n= ln n
FA2 X
H X
h W1
=1 h=1
W
X
H X
X
=1 h=1
Wn
W
X
h W1 wSe(w; h; ) w=1
=1 h=1
Q;1
W
X
X
k)
Q)
h W1 w
d'(p(wh
)e + b'(p(wh
)c + 1 w=1
=1 h=1
k=kw
X
H X
X
H X
h W1
w=1
W X
H
X
w=1 h=1
W
X
w=1
(k)
w npwh +
p
w
Q
X
k=kw
Q
X
k=kw
2(n ln np(k) )1=2
whpwh + W2 n ln n
'(pwh ) + Q ; kw + 1 (k)
wh
X
W X
H
X
=1 w=1 h=1
p
X
H
X
S
1
+
h 1+ W =1 h=1
wh (Q ; kw + 1)pwh
;
1=2
+
W X
H
n ln n X
+ H (H2 + 1) 1 + W4 nHp + WH 2 + 2 W
whpwh((Q ; kw + 1)pwh)1=2 =
w=1 h=1
p
q
= nH + WH 2 + 2 n ln n S nH + WH 2 + 2H WH n ln n =
p
p
W
= nHp (1 + 2"n + ("n )2 = ln n);
p
2
F
"A2 = FA2 ; 1 = nHp(1 + 2"np+ ("n ) = ln n) 1 ; 2"n
S
2
3:5"n (1 +1 ;("n1:)5"=(3:5 ln n)) = O("n ) ! 0 при n ! 1: n
Скорректируем условие асимптотической точности алгоритма A2 на случай
весов, принимающих значения в целочисленном сегменте [1; R], R W . Условие (5) заменяется
на менее жесткие соотношения
HR = o n ; HW = o(n);
p
ln n
Rp
или
HR=p = o(n=n );
(6)
Замечание.
41
;q
=p
где n = max R1 ; RWln n . При этом "A2 = O RH
n= ln n .
Понятно, что при R = W условия (5) и (6) совпадают, а при R p
< W класс асимптотически
точно
решаемых задач
W= ln n имеем n = 1=R p
p становится шире. Действительно,
p при R lnpn=W , а при R W= ln n имеем n = (R ln n)=W ln n=W и, таким образом, если R < W ,
то W= ln n n < ln n.
Приведем без доказательства аналог теоремы 1 для класса Kn .
Теорема 4. Алгоритм A2 на классе Kn c W -асимметричными случайными списками предметов при
WH = o(n= ln n)
асимптотически точен с оценками
s
W
1
A2 = o n ln n ; "A2 = O n= ln n :
5. Связь с задачей календарного планирования
Рассмотрим частный случай задачи календарного планирования (ЗКП) в условиях ограниченных ресурсов, формулировку которой можно найти в [5]. Предполагаем, что выполнены
следующие условия:
| имеется ограниченный нескладируемый ресурс одного вида, интенсивность выделения
которого постоянна на всем протяжении времени выполнения проекта;
| на множестве работ не задано отношение предшествования;
| начальные и директивные сроки выполнения работ отсутствуют, интенсивность потребляемого работой ресурса постоянна на всем протяжении времени выполнения работы.
Если каждой работе сопоставить прямоугольник, ширина и высота которого равны соответственно интенсивности потребления ресурса и длительности выполнения работы, то задачу
нахождения допустимого расписания можно интерпретировать как укладку прямоугольников
в полубесконечную полосу, ширина которой равна интенсивности выделения ресурса. При этом
каждый исходный прямоугольник разрешается разрезать горизонтальными линиями на полосы,
которые будем называть ломтиками. Во всякой допустимой укладке совокупность вертикальных проекций ломтиков образует отрезок, равный высоте прямоугольника. Допускаются также
горизонтальные смещения ломтиков. Очевидно, эта задача является NP -трудной. Действительно, если мы рассмотрим ЗКП, в которой длительности всех работ равны, то полученная задача
будет эквивалентна задаче упаковки в контейнеры.
Из приведенной постановки легко заметить, что без разбиения прямоугольников на ломтики
предложенная ЗКП в точности совпадает с ЗУП. Разрешение перемещения ломтиков позволяет
в ряде случаев построить из оптимального решения ЗУП (которое, очевидно, является допустимым решением ЗКП) еще более короткое расписание для ЗКП. Следовательно, решение ЗКП
можно рассматривать как нижнюю оценку для ЗУП. Решение ЗУП в свою очередь является
верхней оценкой для ЗКП. Представляет несомненный интерес отношение оптимальных значений целевых функций ЗУП и ЗКП.
Обозначим оптимальные значения функционалов ЗУП и ЗКП на списке предметов S через
ЗУП(S ) и ЗКП(S ) соответственно. Пусть
ЗУП(S ) :
= sup ЗКП(
S)
S
Из доказательства верхней оценки для ЗУП(S ), полученной в [7] с помощью алгоритма
NFDH, имеем оценку 3.
С другой стороны, в [5] содержится пример списка работ, в котором 6=5. В работе [6]
этот результат усилен следующим образом. Рассмотрим список из 9 предметов, представленных
42
в нижеследующей таблице при упаковке их в полосу с шириной W = 12. В [6] доказано, что
минимальные высоты полос в ЗКП и ЗУП равны соответственно 4 и 5. Отличие минимальных
значений целевых функций обеих задач для рассматриваемого списка составляет 25 процентов.
На рисунке представлены точные решения обеих задач.
Таким образом, справедливы неравенства
5 3:
4
Предмет Ширина Высота Время
1
3
2
0
2
2
1
2
3
5
1
3
4
2
2
1
5
8
1
0
6
5
1
1
7
6
2
2
8
1
3
0
9
1
3
1
Обозначим через Ke n2 класс задач календарного планирования с постоянным по времени однотипным нескладируемым ограниченным ресурсом и работами | прямоугольниками в случае
отсутствия директивных событий. Если на множестве работ дополнительно задано отношение
частичного порядка, то такой класс задач будем обозначать через Kn . Соответствующие приближенные алгоритмы обозначим через Ae2 и A2 .
5
3
2
8
7
4
1
3
4
9
6
5
0 1 2 3 4 5 6 7 8 9 10 11 12
Оптимальное расписание: ЗКП(S )=4
4
3
2
8
1
0
1
7
2
9
6
5
0 1 2 3 4 5 6 7 8 9 10 11 12
Оптимальная упаковка: ЗУП(S )=5
Непосредственно из формулировок задач следует
Лемма 3. Задача упаковки в полосу является оценочной сверху для ЗКП из класса Kn .
Тем не менее, из теорем 2 и 3, полученных для ЗУП с W -регулярными случайными списками,
вытекают следующие утверждения для упомянутого частного случая ЗКП.
2
e при
Теорема 5. В случае W -регулярных случайных списков из класса Kn алгоритм A
2
WH=p = o(n= ln n)
приводит к асимптотически точному решению ЗКП.
43
В случае W {регулярных случайных списков из класса Kn алгоритм A2 при
WH =p = o(n= ln n)
приводит к асимптотически точному решению ЗКП.
Теорема 6.
Литература
1. Coman E.G., Garey M.R., Johnson D.S. Approximation algorithms for bin-packing. | An
updated survey // Algorithm Design for Computer System Design. CISM courses and lectures.
{ 1984. { Є 284. { P. 49{106.
2. Гимади Э.Х., Глебов Н.И., Перепелица В.А. Алгоритмы с оценками для задач дискретной
оптимизации // Проблемы кибернетики. { М.: Наука, 1975. { Вып. 31. { С. 35{42.
3. Гимади Э.Х., Залюбовский В.В. Задача упаковки в контейнеры: асимптотически точный
подход // Изв. вузов. Математика. { 1997. { Є 12. { C. 25{33.
4. Frederickson G.N. Probabilistic analysis for simple one- and two-dimensional bin packing
algorithms // Information Processing Letters. { 1980. { V. 11. { Є 4{5. { P. 156{161.
5. Гимади Э.Х. О некоторых математических моделях и методах планирования крупномасштабных проектов //Тр. Ин-та математики СО АН СССР. { Новосибирск: ИМ СО АН СССР,
1988. { Т. 10. { С. 89{115.
6. Шарыгин П.И. Оценки приближенного решения одной задачи календарного планирования //
Дискретный анализ и исследование операций. { 1995. { T. 2. { Є 1. { С. 57{67.
7. Coman E.G., Garey M.R., Johnson D.S., Tarjan R.E. Performance bounds for level-oriented
two-dimensional packing algorithms // SIAM J. Comput. { 1980. { V. 9. { Є 4. { P. 808{826.
Институт математики Сибирского отделения
Российской Академии наук
Новосибирский государственный университет
44
Поступила
23.09.1997
Документ
Категория
Без категории
Просмотров
9
Размер файла
223 Кб
Теги
асимптотическое, полоса, подход, упаковки, точных, задачи
1/--страниц
Пожаловаться на содержимое документа