2.3.Параллельные машины.Приближенное решение

FPTAS для задачи Pm||Cmax	Точность жадных алгоритмов
Списочные расписания	Аномалии списочных расписаний

σLPT

σLP′ T

Jn

Jj

Jj

0tj tn Cn Cj = Cmax

По определению LP T , работа Jn начинается последней. Предположим, что последней завершается Jj (j n).

Обозначим:

I1 пример, полученный из I удалением Jn;

OP1 T оптимальное расписание для I1; LP1 T LP T -расписание для I1.

Тахонов Иван Иванович	Параллельные машины. Приближенное решение

FPTAS для задачи Pm||Cmax

Точность жадных алгоритмов

Списочные расписания

Аномалии списочных расписаний

σLPT

σLP′ T

Jn

Jj

Jj

0tj tn Cn Cj = Cmax

Очевидно, 1

отличается от LP T только отсутствием Jn.

LP T

Она не заверш. последней, след.-но:

Cmaxp LP T q Cmaxp 1

q:

LP T

Кроме того, так как пример I1 I, òî

Cmaxp OP T q ¥ Cmaxp 1

q:

OP T

Таким образом,

Cmaxp 1

q

Cmaxp LP T q

4

1

LP T

¥

¡

:

Cmaxp 1

Cmaxp OP T q

q

3

3m

OP T

Противоречие с выбором I.

Тахонов Иван Иванович	Параллельные машины. Приближенное решение

FPTAS для задачи Pm||Cmax	Точность жадных алгоритмов
Списочные расписания	Аномалии списочных расписаний

Таким образом, Cmaxp LP T q Cn. Пусть tn Cn pn. По Алгоритму, до момента tn все машины должны быть заняты. Также, все остальные работы к этому моменту уже начаты. След.-но,

					n 1
mtn mpCmaxp LP T q pnq ¤							pj;
					j¸1
èëè				1			n
1
Cmaxp LP T q ¤ pn 1							pj:	(2)
		m			m
							j¸1
Кроме того, очевидно,
1				n
Cmaxp OP T q ¥				pj:				(3)
	m
				j¸1

Тахонов Иван Иванович	Параллельные машины. Приближенное решение

FPTAS для задачи Pm||Cmax	Точность жадных алгоритмов
Списочные расписания	Аномалии списочных расписаний

Из (2) и (3) следует:

pn 1

1

1

n

pj

1

4

1

p

LP T

q

m m °

p

n

1

Cmax

¤

j 1

¤

m

1;

Cmaxp OP T q

Cmaxp OP T q

3

3m

Cmaxp OP T q

откуда

Cmaxp OP T q

3pn:

Òàê êàê pn это минимальная продолжительность работы, то вOP T для примера I на каждую машину назначено не более двух работ. Согласно Лемме 1, в этом случае

Cmaxp LP T q	1 ¤	4			1	:
Cmaxp OP T q		3			3m

Противоречие.

Тахонов Иван Иванович	Параллельные машины. Приближенное решение

FPTAS для задачи Pm||Cmax	Точность жадных алгоритмов
Списочные расписания	Аномалии списочных расписаний

Замечание 4

Оценка достижима. Рассмотрим пример: n 2m 1,

p p2m 1; 2m 1; 2m 2; 2m 2; : : : ; m 1; m 1; m; m; mq.

В расписании LPT :

первые 2m работ назначаются на Mi парами: Ji è J2m i 1,

суммарная длительность Ji è J2m i 1 равна 3m 1,

Jn назначена на M1 и заверш. последней в 4m 1.

В расписании OPT :

íà Mi (i ¤ m 1) выполняются работы Ji è J2m i 1,

íà Mm выполняются работы J2m 1, J2m è J2m 1,

все работы завершаются в 3m.

M1

J1

J6

J7

M1

J1

J4

M2

J2

J5

M2

J2

J3

M3

J3

J4

M3

J5

J6

J7

9

0

4

8

11

0

3

6

Тахонов Иван Иванович

Параллельные машины. Приближенное решение

FPTAS для задачи Pm||Cmax	Точность жадных алгоритмов
Списочные расписания	Аномалии списочных расписаний

Algorithm 4 (Приближенное решение P ||Cmax)

1: Перенумеровать работы по невозрастанию длительностей:

p1 ¥ p2 ¥ ¥ pn:

2: Найти точное решение P |J tJ1; : : : ; Jku|Cmax на первых k (самых длинных) работах. Пусть

k оптимальное расписание, а

Lk соотв. список ( k Lk ).

3:Построить список Lpkq для исходной задачи, добавив к кон- öó Lk оставшиеся работы в произв. порядке:

Lpkq Lk Y tJk 1; : : : ; Jnu:

4: Применяя Алгоритм 3, построить спис. расп. pkq Lpkq.

Тахонов Иван Иванович	Параллельные машины. Приближенное решение

FPTAS для задачи Pm||Cmax	Точность жадных алгоритмов
Списочные расписания	Аномалии списочных расписаний

Теорема 3

Алгоритм 4 строит прибл. реш. P ||Cmax с оценкой точности

Cmaxp pkqq		1		1
	¤ 1		m			:
Cmaxp OPT q		1 X		k
			m \

Доказательство. Заметим, что:

Cmaxp kq ¤ Cmaxp OPT q;

â pkq è â k первые k работ назначены одинаково.

Следовательно, если Cmaxp pkqq Cjp pkqq äëÿ j ¤ k, òî

Cmaxp OPT q ¤ Cmaxp pkqq Cjp pkqq Cjp kq ¤ Cmaxp kq

¤Cmaxp OPT q:

Òî åñòü, Cmaxp pkqq Cmaxp OPT q, и неравенство верно.

ñ далее полагаем, что Cmaxp pkqq Cjp pkqq äëÿ j ¥ k 1.

Тахонов Иван Иванович	Параллельные машины. Приближенное решение

FPTAS для задачи Pm||Cmax	Точность жадных алгоритмов
Списочные расписания	Аномалии списочных расписаний

Пусть Jj завершается последней в pkq. Время начала работы: tj Cjp pkqq pj. Òàê êàê j ¥ k 1, òî pj ¤ pk 1.

Алгоритм строит расписание без простоев, след.-но, до tj âñå машины заняты, и сумма длин назначенных ранее работ не менее mtj. Оценим длину расписания.

	n
mCmaxp OP T q ¥	pl ¥ mtj pj mpCjp pkqq pjq pj
	l¸1
¥ mCmaxp pkqq pm 1qpk 1:
Таким образом,
		m 1
Cmaxp OP T q ¥ Cmaxp pkqq			pk 1	:	(4)
		m

Тахонов Иван Иванович	Параллельные машины. Приближенное решение

FPTAS для задачи Pm||Cmax	Точность жадных алгоритмов
Списочные расписания	Аномалии списочных расписаний

Имеется k 1 работа длительности не менее pk 1. ñ в любом допустимом расп. найдется машина, выполняющая не менее

Pk 1

1

X

k

m T

m \ этих длинных работ. Длину оптимального

расписания можно оценить снизу загрузкой этой машины:

Cmaxp OP T q ¥ 1 Z

k

^ pk 1:

(5)

m

Выражая pk 1 из (5) и подставляя в (4), получаем:

1

1

Cmaxp OP T q ¥ Cmaxp pkqq

m

Cmaxp OP T q:

1

X k

m \

Тахонов Иван Иванович	Параллельные машины. Приближенное решение

FPTAS для задачи Pm||Cmax	Точность жадных алгоритмов
Списочные расписания	Аномалии списочных расписаний

Следствие 1

Ïðè k 0: ðàñï. p0q L произвольное списочное расписание, строится за Opnq. Верна оценка:

Cmaxp Lq	¤ 2	1		:
Cmaxp OP T q		m

Ïðè k m: расп. pmq строится за Opnmq. Верна оценка:

Cmaxp pmqq 3 1

Cmaxp OP T q ¤ 2 2m:

Ïðè k 2m: расп. p2mq строится за Opnm fpmqq. Верна оценка:

Cmaxp p2mqq 4 1

Cmaxp OP T q ¤ 3 3m:

Тахонов Иван Иванович	Параллельные машины. Приближенное решение