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

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

Теорема 4

Рассмотрим два примера P |prec|Cmax, содержащие n работ. Пример I: работы выполняются на m машинах,

p вектор длительностей работ,

L некоторое упорядочение работ,

G граф ограничений предшествования, ! длина L-расп. для I.

Пример I1: работы выполняются на m1 машинах,

p1 ¤ p длительности уменьшены,

L1 некоторое упорядочение работ,

G1 G ограничения предш. ослаблены, !1 длина L1-ðàñï. äëÿ I1.

Верна оценка:

!!1 ¤ 1 mm1 1:

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

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

Доказательство. Далее будем писать J2 J1 (J2 1 J1), åñëè работа J2 предш. J1 (возможно, не непосредственно) в G (G1).

 I1 все работы выполняются в интервале r0; !1q. Обозначим:

i tt P r0; !1q|в момент t простаивает машина Miu,

p iq мера этого множества.

Верно равенство:

n		m1
m1!1	p1	p iq	(6)
	j
j¸1		i¸1

(сумма длин работ и простоев). Оценим длину простоев.

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

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

Разобьем интервал r0; !1q на два множества:

A tt P r0; !1q|в момент t все машины занятыu,

B r0; !1qzA.

A è B наборы не пересекающихся полуоткрытых интервалов. Без ограничения общности считаем, что 0 P A.

Пусть работа Jj1 завершается последней в расписании L1 : Cj1 p L1 q !1. Время начала этой работы обозначим через tj1 . Возможны два случая:

1 tj1 внутренняя точка B,

2 tj1 не принадлежит внутренности B.

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

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

Случай 1: tj1 P IntpBq. Существует " ¡ 0 : tj1 " P B. По определению B, â tj1 " одна из машин простаивает.

Работа Jj1 не была назначена в этот момент, значит, тогда не была завершена одна из предшествующих работ, обозначим ее через Jj2 : Jj2 1 Jj1 è Cj2 p L1 q tj1 .

Jj2

Jj1

tj1 ω′

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

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

Случай 2: tj1 R IntpBq. Обозначим t suptx tj1 |x P Bu. Если множество пусто, полагаем t 0.

Пусть t 0. Äî tj1 все машины заняты. Простои возможны в моменты rtj1 ; !1q на всех машинах, кроме той, где Jj1 .

m1

p iq ¤ pm1 1qp1j1 :

i¸1

Пусть t 0. Найдется " ¡ 0: t " P B. Работа Jj1 не назначена в это время, значит, не завершен предшественник. То есть, существует Jj2 1 Jj1 : Cj2 p L1 q ¤ tj1 è rCj2 p L1 q; tj1 q A.

Jj1

Jj2

Jj1

tj1 ω′			t	tj1 ω′

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

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

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

m1

p iq ¤ pm1 1qp1j1 ;

i¸1

либо найдется Jj2 1 Jj1 , которая покрывает предшествующий интервал множества B.

Аналогично отыскиваем Jj3 1	Jj2 , также выполняющуюся в B,
и так далее. То есть, в графе G1 есть последовательность
работ, покрывающая множество B:
Jjr 1 Jjr 1	1 1 Jj1 :

Возможно, в этой цепи всего одна работа Jj1 (åñëè äî tj1 íåò простоев).

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

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

Все работы цепи выполняются последовательно. Каждая из них покрывает простои на не более чем pm1 1q машинах,

следовательно:

m1	r
p iq ¤ pm1	1q pBq ¤ pm1 1q p1 :	(7)
	jl
i¸1	l¸1
Òàê êàê G1 G, òî â G работы из цепи также предшествуют
друг другу:
Jjr	Jjr 1 Jj1 :

Они выполняются последовательно, и сумма их длительностей является нижней оценкой на длину оптимального расписания:

rr

! ¥ pj	l	¥	p1 :	(8)
			jl
l¸1			l¸1

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

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

Подставляя (7) и (8) в (6), а также, учитывая, что

! ¥	1		n
			pj, получаем:
	m
			j°1
						n					r
			m1!1 ¤				p1		m1 1q p1
							l p				jl
						l¸1					l¸1
						n
			¤				pl pm1 1q!
						l¸1
				¤ m! pm1 1q!;
èëè,			!1					m 1
						¤ 1				:
				!
								m1

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

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

Замечание 5

Можно построить примеры, показывающие, что граница в оценке достижима.

Замечание 6

Оптимальное решение задачи P ||Cmax является списочным с для произвольного списка L выполняется неравенство:

Cmaxp Lq	¤	m 1		1 2	1	:
Cmaxp OP T q		m			m

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

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

Литература к лекции

1Blazewicz J. et al. Handbook on Scheduling. From Theory to Applications раздел 5.1

2Pinedo M. Scheduling. Theory, Algorithms, and Systems раздел 5.1.

3Коффман Э.Г. (ред.) Теория расписаний и вычислительные машины. -М.: Наука, 1984 разделы 5.1, 5.2.

4Graham R.L. Bounds on Multiprocessing Timing Anomalies // SIAM Journal on Applied Mathematics, Vol. 17, No. 2. (Mar., 1969), pp. 416-429.

5 P.Shuurman, G.Woeginger Approximation Schemes - A Tutorial

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