2.2.Параллельные машины.Полиномиально разрешимые задачи

Algorithm 1 (Решения задачи P |prmp|Cmax)

Положить i 1, t 0. for j : 1 Ñ n do

назначить Jj íà Mi â t, t : t pj,

¡

if t C then i : i 1,

назначить остаток Jj íà Mi

Теорема 1

Алгоритм 1 строит оптимальное решение задачи P |prmp|Cmax с трудоемкостью Opnq.

Машины с различной производительностью

Задача Q|prmp|Cmax как задача лин. прог.:

$Cmax Ñ min;

txu

Полагаем, n%¥ m. Упорядочим машины и работы: s1 ¥ s2 ¥ ¥ sm è p1 ¥ p2 ¥ ¥ pn:

Оценим C

max.

C одной стороны, для любого допустимого расписания:

С другой стороны: рассм. пример Ik с первыми (длинными) k ¤ m работами и первыми (быстрыми) k ¤ m машинами.

Построим расписание длины

C.

Èäåÿ:

1В каждый момент времени назначаем недовыполненные работы на машины так, чтобы работа с самым длиннымостатком выполнялась на самой быстрой машине.

2Если имеется несколько работ с одинаковым остаткомразмазываем их равномерно между несколькими машинами.

3 Приводим расписание к допустимому виду.

Введем функции pjptq кол.-во единиц Jj не обработанных к t.

Algorithm 2 (Level-Algorithm äëÿ Q|prmp|Cmax)

1:Положить t 0. pjptq : pj äëÿ âñåõ j.

2:Положить J 1 tJj : pjptq ¡ 0u, M1 M

3:if J 1 H then GOTO 13

4:else

5:while J 1 H and M1 H do

6:найти J 2 J 1 работы с наибольшим pjptq;

7:r : mint|J 2|; |M1|u;

8: назначить J 2 на r самых быстрых из M1 (одновр.);

9:удалить из J 1 назначенные работы;

10:удалить из M1 занятые машины.

s ¡ t : в s заверш. одна из работ 11: Положить t : min " или в s у некот. работ выравн. pjpsq *

12: GOTO 2.

13: Привести расписание к допустимому виду.

Пример

m 4, s p7; 6; 5; 4q

n 5, p p20; 19; 10; 6; 2q

Теорема 2

Алгоритм 2 строит решение Q|prmp|Cmax ñ òðóä. Opmn2q.

Доказательство. Заметим, что расписание , где в rt1; t2s J1; : : : ; Jk вып. одновр. на M1; : : : ; Mr, всегда можно преобр. к допуст. виду. Разобьем rt1; t2s на k интервалов один. длины и назначим работы:

Íà M1: J1 Ñ J2 Ñ : : : Jk,

Íà M2: J2 Ñ J3 Ñ : : : Jk Ñ J1,

... и так далее с циклическим сдвигом.

Т.к. по построению k ¥ r, фрагменты каждой работы вып. на всех машинах в различных интервалах. Кроме того, в новом расписании

все работы проводят на каждой машине одно и то же время, заверш. те же доли работ, что и в исходном недопустимом расп.,

некоторые из фрагментов работ завершаются в t2.

То есть, получено допустимое расписание той же длины.

Таким образом, алгоритм корректен.

Исходное блочное расписании:

содержит не более n блоков, строится за Opn2q.

в каждом блоке ¤ n работ, вып. ¤ m машинах. Следовательно, допуст. расп. строится за Opmn2q.

Покажем, что алг. строит расп. длины

C (то есть, опт.). Обозначим fi время освобождения Mi (i ¤ m). Очевидно,

Cmax f1 ¥ f2 ¥ ¥ fm:

Случай 1. Все машины освобождаются одновременно: fi Cmax @i

Случай 2. f1 f2 fk ¡ fk 1 для некоторого k Заметим, что p1ptq ¥ p2ptq ¥ ¥ pnptq äëÿ âñåõ t P r0; Cmaxs.

Пусть в Cmax íà Mk заверш. Jj (возможно, в блоке). Тогда D" ¡ 0:

p1pfk "q ¥ p2pfk "q ¥ ¥ pjpfk "q ¡ 0:

Т.о., все предш. работы также заверш. в fk Cmax íà M1; : : : ; Mk.

Кроме того, в fk 1 ìàø. Mk 1 свободна, хотя есть незав. работы. Следовательно, этих работ k. Т.е., последними заверш. J1; : : : ; Jk.

Эти работы вып. на M1; : : : ; Mk с t 0, других работ на машинах не было (иначе они тоже заверш. бы в fk).

Замечание 1

Алгоритм 2 c трудоемкостью Opmn2q строит расписание, в котором до n2pm 1q прерываний.

Gonzalez, Sahni предложили алгоритм трудоемкости

Opn m ln nq с не более, чем 2pm 1q прерываниями.

[Gonzalez T., Sahni S. Preemptive Scheduling of Uniform Processor Systems // J. of the Association for Computing Machinery, Vol.25, No.1, 1978]