2.2.Параллельные машины.Полиномиально разрешимые задачи
.pdf
Курс Основы теории расписаний |
06/19 |
Система с параллельными машинами. Полиномиальные и псевдополиномиальные точные алгоритмы
Тахонов Иван Иванович
Новосибирский государственный университет Механико-математический факультет
ÍÃÓ, 2015
Полиномиально разрешимые задачи Псевдополином. точные алгоритмы
Выяснили ранее: сложность P m|| (m ¥ 2)
|
|
|
Cmax |
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Lmax |
|
PCj |
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
PUj |
P |
|
Tj |
|
PwjCj |
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
PwjUj |
|
PwjTj |
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Тахонов Иван Иванович |
Параллельные машины. Точное решение задач |
|
|
Полиномиально разрешимые задачи Псевдополином. точные алгоритмы
Выяснили ранее: сложность P ||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Cmax |
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Lmax |
|
|
PCj |
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
PUj |
|
|
P |
|
Tj |
|
|
PwjCj |
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
PwjUj |
|
|
PwjTj |
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Тахонов Иван Иванович |
Параллельные машины. Точное решение задач |
|
|
Полиномиально разрешимые задачи Псевдополином. точные алгоритмы
Вспомним:
1 |
задача P m|| ° wjCj трудна с прерываниями и без; |
2 |
решения P m|| ° wjCj è P m|prmp| ° wjCj совпадают; |
3задачи P m||Cmax è P m|| ° wjCj не являются трудными в сильном смысле;
4задачи P ||Cmax, P || ° wjCj и более сложные трудны в сильном смысле, поэтому для них не существует ни псевдополиномиальных точных алгоритмов, ни FPTAS.
Тахонов Иван Иванович |
Параллельные машины. Точное решение задач |
|
|
Полиномиально разрешимые задачи Псевдополином. точные алгоритмы
Рассмотрим полиномиально разрешимые задачи:
P pQ; Rq|prmp|Cmax,
P pQ; Rq|| ° Cj è P pQq|pj 1| ° wjCj.
Также опишем псевдополиномиальные точные алгоритмы для задач:
P m||Cmax, 
P m|| ° wjCj.
Тахонов Иван Иванович |
Параллельные машины. Точное решение задач |
|
|
Полиномиально разрешимые задачи |
Кратчайшее расписание с прерываниями |
Псевдополином. точные алгоритмы |
Суммарное взвешенное время прохождения работ |
|
|
Полиномиально разрешимые задачи
Тахонов Иван Иванович |
Параллельные машины. Точное решение задач |
|
|
Полиномиально разрешимые задачи |
Кратчайшее расписание с прерываниями |
Псевдополином. точные алгоритмы |
Суммарное взвешенное время прохождения работ |
|
|
Идентичные машины
Задача P ||Cmax как задача булевого лин. прог.:
$ |
Cmax |
Ñ min; |
|
|
n |
txu |
|
|
|
|
|
&' |
xijpj |
¤ Cmax |
pi 1; : : : ; mq; |
j°1 |
|
|
|
m |
|
|
|
xij |
1 |
pj 1; : : : ; nq; |
|
' |
i°1 xij |
P t0; 1u |
äëÿ âñåõ i è j: |
Как выглядит%задача с прерываниями?
Тахонов Иван Иванович |
Параллельные машины. Точное решение задач |
|
|
Полиномиально разрешимые задачи |
Кратчайшее расписание с прерываниями |
Псевдополином. точные алгоритмы |
Суммарное взвешенное время прохождения работ |
|
|
Задача P |prmp|Cmax как задача лин. прог.:
$Cmax Ñ min;
txu
|
n |
|
|
|
&' |
|
|
xijpj |
|
j°1 |
||||
|
|
m |
||
|
|
|
xij |
|
' |
|
i°1 |
||
|
|
|
n |
|
% |
|
|
|
xij |
|
|
1 |
|
|
Решение: C |
|
|
||
max |
|
|
m |
|
j°1
¤ Cmax |
pi 1; : : : ; mq; |
1 |
pj 1; : : : ; nq; |
P r0; 1s |
äëÿ âñåõ i è j: |
1 |
i è j). |
pj, xij m (äëÿ âñåõ |
Тахонов Иван Иванович |
Параллельные машины. Точное решение задач |
|
|
Полиномиально разрешимые задачи |
Кратчайшее расписание с прерываниями |
Псевдополином. точные алгоритмы |
Суммарное взвешенное время прохождения работ |
|
|
Пример
Имеются две машины и две работы. Длительности работ
p p1; 2q. Очевидно, оптимальное расписание имеет длину 2, а решение задачи 1.5.
M1 |
|
|
J1 |
|
|
|
|
M1 |
|
|
J1 |
|
J2 |
|
|
M2 |
|
|
J2 |
|
|
M2 |
|
|
J2 |
|
|
||||
|
|
0 |
|
|
1 |
|
2 |
|
|
0 |
|
|
1 |
|
1.5 |
|
|
|
|
|
|
||||||||||
Не хватает еще одного ограничения.
Тахонов Иван Иванович |
Параллельные машины. Точное решение задач |
|
|
Полиномиально разрешимые задачи |
Кратчайшее расписание с прерываниями |
Псевдополином. точные алгоритмы |
Суммарное взвешенное время прохождения работ |
|
|
Задача P |prmp|Cmax как задача лин. прог.:
$Cmax Ñ min;
txu
|
n |
|
|
|
|
' |
xijpj |
¤ Cmax |
pi 1; : : : ; mq; |
||
j°1 |
|
|
|
|
|
& |
|
|
|
|
|
pj |
¤ Cmax |
pj 1; : : : ; nq; |
|||
|
m |
|
|
|
|
' |
xij |
1 |
pj 1; : : : ; nq; |
||
i°1 xij |
P r0; 1s |
äëÿ âñåõ i è j: |
|||
% |
|
|
1 |
|
n |
|
|
|
|
||
Решение: C |
C max #pmax; |
m |
pj+. Несложно |
||
max |
|
|
|
||
j°1
понять, как получить расписание такой длины.
Тахонов Иван Иванович |
Параллельные машины. Точное решение задач |
|
|