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

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

Следствие 2

Пусть " ¡ 0 и k Pm			k ¤ n). Тогда
	" T (считаем
	Cmaxp pkqq		1		1
					m
		¤ 1					¤ 1 ":
	Cmaxp OP T q			1 X	k
					m \

Ðàñï. k может быть найдено, например, полным перебором с трудоемкостью Opmkq. Таким образом, трудоемкость

построения p1 "q-приближенного решения не превышает

m

O mr " s nm"

или, при фиксированных m è ", Opnq.

То есть, Алгоритм 4 дает P T AS для задачи P m||Cmax.

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

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

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

Задача P |prec|Cmax

J tJ1; : : : ; Jnu работы,

M tM1; : : : ; Mmu машины (идентичные),

p pp1; : : : ; pnq длительности работ,

G pV; Aq граф ограничений предшествования,

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

L соответствующее L списочное расписание.

Выясним, как будет меняться длина списочного расписания при изменении параметров m, p, G è L.

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

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

Пример 1

Пусть n 9, m 3, p p3; 2; 2; 2; 4; 4; 4; 4; 9q,

L pJ1; J2; J3; J4; J5; J6; J7; J8; J9q. Граф ограничений представлен на рисунке.

Расписание 1 L длины 12 является оптимальным.

3

2

2

2

J1

J2

J3

J4

J1

J9

G

J2

J4

J5

J7

J3

J6

J8

J9

J5

J6

J7

J8

0

12

9

4

4

4

4

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

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

Пример 1

Пусть n 9, m 3, p p3; 2; 2; 2; 4; 4; 4; 4; 9q,

L pJ1; J2; J3; J4; J5; J6; J7; J8; J9q. Граф ограничений представлен на рисунке.

Изменим список: L1 pJ1; J2; J4; J5; J6; J3; J9; J7; J8q

Расписание 2 L1

не оптимально и имеет длину 14.

3

2

2

2

J1

J2

J3

J4

J1

J3

J9

G

J2

J5

J7

J4

J6

J8

J9

J5

J6

J7

J8

0

14

9

4

4

4

4

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

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

Пример 1

Пусть n 9, m 3, p p3; 2; 2; 2; 4; 4; 4; 4; 9q,

L pJ1; J2; J3; J4; J5; J6; J7; J8; J9q. Граф ограничений представлен на рисунке.

Увеличим число машин: m 4. Расписание 3 имеет длину 15.

3	2	2	2	J1		J8
J1	J2	J3	J4	J2	J5	J9
G				J3	J6
				J4	J7

J9	J5	J6	J7	J8	0	15
9	4	4	4	4

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

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

Пример 1

Пусть n 9, m 3, p p3; 2; 2; 2; 4; 4; 4; 4; 9q,

L pJ1; J2; J3; J4; J5; J6; J7; J8; J9q. Граф ограничений представлен на рисунке.

Уменьшим длительности на 1: p p2; 1; 1; 1; 3; 3; 3; 3; 8q. Расписание 4 имеет длину 13.

3

2

2

2

J1

J2

J3

J4

J1

J5

J8

G

J2

J4

J6

J9

J3

J7

J9

J5

J6

J7

J8

0

13

9

4

4

4

4

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

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

Пример 1

Пусть n 9, m 3, p p3; 2; 2; 2; 4; 4; 4; 4; 9q,

L pJ1; J2; J3; J4; J5; J6; J7; J8; J9q. Граф ограничений представлен на рисунке.

Ослабим ограничения предш.: уберем дуги J4 Ñ J5 è J4 Ñ J6. Расписание 5 имеет длину 16.

3

2

2

2

J1

J2

J3

J4

J1

J6

J9

G′

J2

J4

J7

J3

J5

J8

J9

J5

J6

J7

J8

0

16

9

4

4

4

4

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

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

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

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

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

Пример 2

Пусть n 7, m 2, p p4; 2; 2; 5; 5; 10; 10q. Граф ограничений представлен на рисунке. Оптимальное расписание 1 имеет длину 19 и является списочным

J1 J2

J3

J5

J4

J6

σ1

J1

J4

J6

J7

J2

J3

J5

J7

19

0

σ2

J1

J4

J5

J7

J2

J3

J6

0

20

σ3

J1

J4

J7

J2

J3

J5

J6

0

16

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

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

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

Пример 2

Пусть n 7, m 2, p p4; 2; 2; 5; 5; 10; 10q. Граф ограничений представлен на рисунке. Оптимальное расписание 1 имеет длину 19 и является списочным

Уменьшим длительности на 1: p p3; 1; 1; 4; 4; 9; 9q. Кратчайшее списочное расписание 2 имеет длину 20.

Îïò. ðàñï. 3 имеет длину 16 (длина цепи J1 Ñ J5 Ñ J7 â G), но не является списочным.

σ1

J1

J4

J6

J1

J2

J2

J3

J5

J7

19

0

J3

σ2

J1

J4

J5

J7

J2

J3

J6

J5

J4

J6

0

20

σ3

J1

J4

J7

J7

J2

J3

J5

J6

0

16

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