2.1.Параллельные машины.Модель.Сложность
.pdf
Описание модели |
Минимизация длины расписания |
|
Сложность задач |
||
Суммарное взвешенное время прохождения работ |
||
Неаппроксимируемость |
||
|
||
|
|
Аналогично, |
2F2p q Jk¸PJ2 ak |
2 |
|
|
|
|
||
|
|
|
|
|
||||
|
Jk¸PJ2 ak2; |
|
|
|||||
и, следовательно, |
|
|
|
|
|
|
|
|
F p q 2 Jk¸PJ1 ak |
2 |
Jk¸PJ2 ak |
2 |
J¸kPJ ak2 |
|
|||
2 |
2 |
|
||||||
1 |
|
1 |
|
|
1 |
|
|
|
2 Jk¸PJ1 ak |
2 |
|
|
2 |
J¸kPJ ak2 |
¤ Y: |
||
2 |
2b Jk¸PJ1 ak |
2 |
||||||
1 |
|
1 |
|
|
|
1 |
|
|
Несложно убедиться, что сумма первых двух слагаемых не меньше
b2, и равна этой величине лишь когда |
Jk°PJ1 ak Jk°PJ2 ak b |
. Òî |
есть, когда существует разбиение. |
|
Тахонов Иван Иванович |
Параллельные машины. Модель. Сложность |
|
|
Описание модели |
Минимизация длины расписания |
|
Сложность задач |
||
Суммарное взвешенное время прохождения работ |
||
Неаппроксимируемость |
||
|
||
|
|
Теорема 5 |
|
|
|
|
|
Задача P || °wjCj |
является NP-сложной в сильном смысле. |
||||
Доказательство. |
Аналогично, сведением 3-Разбиения . |
|
|
||
Строим пример P || °wjCj ¤ Y : |
1 |
3t |
tb2 |
||
|
|
|
¸ |
|
|
n 3t; m t; wj pj aj pj 1; : : : ; 3tq; Y |
2 |
aj2 |
2 |
: |
|
|
|
|
j 1 |
|
|
Пусть существует доп. расп. . Обозначим:
Ji множество работ, выполняющихся на Mi â ,
°
Fip q wjCjp q вклад Ji в целевую функцию,
Jj PJi
3t
°
F p q wjCjp q целевая функция.
j 1
Тахонов Иван Иванович |
Параллельные машины. Модель. Сложность |
|
|
Описание модели |
Минимизация длины расписания |
|
Сложность задач |
||
Суммарное взвешенное время прохождения работ |
||
Неаппроксимируемость |
||
|
||
|
|
Как показано ранее,
Fi |
2 |
aj |
2 |
aj2 ; |
|
|
|||||
p q |
1 |
Jj¸PJi |
Jj¸PJi |
|
|
|
|||||
|
|||||
2
t |
1 |
t |
|
|
1 |
3t |
|
tb2 1 |
3t |
||||
¸ |
|
¸ ¸PJ |
|
|
|
|
|
¸ |
|
|
|
|
¸ |
F p q Fip q |
2 |
i 1 Jj i |
aj |
|
2 |
j 1 |
aj2 ¤ 2 2 |
aj2: |
|||||
i 1 |
|
|
|
|
|
|
|
|
|
|
j 1 |
||
Òàê êàê i t1 |
Jj i aj tb, òî i t |
1 |
Jj i aj 2 |
¥ tb2, è ðàâ.-âî |
||
|
°PJ |
|
|
|
°P.JСледовательно, из сущ. |
|
° |
äëÿ°âñåõ |
|||||
достигается при Jj°PJi aj b |
|
|
|
i |
|
|
доп. расп. следует существование разбиения. И наоборот.
Тахонов Иван Иванович |
Параллельные машины. Модель. Сложность |
|
|
Описание модели |
Минимизация длины расписания |
|
Сложность задач |
||
Суммарное взвешенное время прохождения работ |
||
Неаппроксимируемость |
||
|
||
|
|
Замечание 3
°
Задача P m|| wjCj не является NP-сложной в сильном смысле. Существует алгоритм, строящий решение более общей
°
задачи Qm|| wjCj
Замечание 4
В отличие от P pmq||Cmax, допустимость прерываний не делает
°
задачу P pmq|| wjCj проще.
Тахонов Иван Иванович |
Параллельные машины. Модель. Сложность |
|
|
Описание модели |
Минимизация длины расписания |
|
Сложность задач |
||
Суммарное взвешенное время прохождения работ |
||
Неаппроксимируемость |
||
|
||
|
|
Теорема 6
°
Существует оптимальное решение задачи P pmq|prmp| wjCj, не содержащее прерываний.
Доказательство. Покажем, что любое опт. расп. с конечным числом прерываний может быть без увеличения критерия преобразовано в расп., не содержащее прерываний.
Пусть опт. расп. с минимальным числом работ, прерыв. в последний момент.
Обозначим через t и t1 (t ¡ t1) два последних момента прерывания (если момент только один, то t1 0). После t
прерываний нет, расписание содержит финальные фрагменты работ. Покажем, что можно переставить некоторые фрагменты, избавившись от прерываний в t и не увеличив значение ц. ф.
Тахонов Иван Иванович |
Параллельные машины. Модель. Сложность |
|
|
Описание модели |
Минимизация длины расписания |
|
Сложность задач |
||
Суммарное взвешенное время прохождения работ |
||
Неаппроксимируемость |
||
|
||
|
|
|
|
|
|
t |
|
|
|
|
|
t |
||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Ml |
|
Jj |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Ml |
|
Jj |
|
|
|
|
|
|
|
|
|
|
||||
Mk |
|
|
|
Jj |
|
|
|
|
|
|
|
|
|
|
|
Mk |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
Пусть некоторая работа Jj прерывается в момент t на машине Ml и в этот же момент начинается на машине Mk. Поменяем местами фрагменты расписания, начинающиеся в момент t.
Получившееся расписание:
допустимо,
оптимально (времена завершения работ не изменились),
содержит на одно прерывание меньше, что противоречит выбору .
Далее будем полагать, что все работы, прерванные в t, продолжают выполняться уже после t.
Тахонов Иван Иванович |
Параллельные машины. Модель. Сложность |
|
|
Описание модели |
Минимизация длины расписания |
|
Сложность задач |
||
Суммарное взвешенное время прохождения работ |
||
Неаппроксимируемость |
||
|
||
|
|
Пусть прерванные в момент t работы Jj1 ; : : : ; Jjr выполнялись на машинах M1; : : : ; Mr.
Возможны два случая:
Случай 1. Есть работа, которая в момент t прервалась на Ml (l ¤ r), а после продолжилась на Mk (k ¤ r).
Случай 2. После t работы перешли на MztM1; : : : ; Mru.
Тахонов Иван Иванович |
Параллельные машины. Модель. Сложность |
|
|
Описание модели |
Минимизация длины расписания |
|
Сложность задач |
||
Суммарное взвешенное время прохождения работ |
||
Неаппроксимируемость |
||
|
||
|
|
Случай 1. Среди работ Jj1 ; : : : Jjr , ïðåð. â t, есть хотя бы одна, которая после t завершается на одной из машин M1; : : : ; Mr.
Пусть A те из прерв. в t работ, которые затем заверш. на некоторой Mk (k ¤ r), причем, перед ними нет других финальных фрагментов работ из A (т.е., это работы, заверш. первыми среди тех, что попали на те же машины).
Очевидно, на каждой машине завершается не более одной работы из A. Можно полагать, что если Jjl P A выполнялась íà Ml, то завершается она на той же машине.
|
|
|
|
t |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
t |
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Ml |
|
Jjl |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Ml |
|
Jjl |
|
|
|
|
|
Jjl |
|
|
|
|
|
||
Mk |
|
|
|
|
|
|
|
Jjl |
|
|
|
|
|
|
|
Mk |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
Íà Mk è íà Ml в t прерывание, поэтому при перестановке ни одну работу дополнительно прерывать не придется.
Тахонов Иван Иванович |
Параллельные машины. Модель. Сложность |
|
|
Описание модели |
Минимизация длины расписания |
|
Сложность задач |
||
Суммарное взвешенное время прохождения работ |
||
Неаппроксимируемость |
||
|
||
|
|
Пусть Jjl P A выполняется на Ml â rq; ts и завершается в ru; u1s. Полагаем, что q ¥ t1 (если нет прерываем).
Преобразуем расписание в 1:
переместим предпоследний фраг. Jjl íà u t единиц позже (теперь работа Jjl содержит меньше прерываний),
фрагменты, вып. в rt; us, выполняем на u t раньше.
|
|
t′ |
|
q |
t |
|
|
|
u |
u′ |
|||||||||||||
σ |
Ml |
|
|
Jjl |
|
|
|
|
|
Jjl |
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
σ′ |
Ml |
|
|
|
|
|
|
|
|
|
|
Jjl |
|
|
|
|
|
|
|
|
|
||
Тахонов Иван Иванович |
Параллельные машины. Модель. Сложность |
|
|
Описание модели |
Минимизация длины расписания |
|
Сложность задач |
||
Суммарное взвешенное время прохождения работ |
||
Неаппроксимируемость |
||
|
||
|
|
|
|
t′ |
|
q |
t |
|
|
|
u |
u′ |
|||||||||||||
σ |
Ml |
|
|
Jjl |
|
|
|
|
|
Jjl |
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
σ′ |
Ml |
|
|
|
|
|
|
|
|
|
|
Jjl |
|
|
|
|
|
|
|
|
|
||
Заметим, что:
работы, фрагменты которых в выполнялись в rt; us, íå прерывались в t (Jjl первая из тех, что прерваны в t);
наиболее поздний момент их прерывания это t1, à 1 äî t1 совпадает с , следовательно, расписание 1 допустимо;
также, расписание 1 оптимально: времена завершения всех работ не возросли.
Так можно избавиться от всех работ, которые были прерваны в t и затем назначены на те же машины. Попадаем в Случай 2.
Тахонов Иван Иванович |
Параллельные машины. Модель. Сложность |
|
|