- 9 -

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Покажем, что во втором случае оператор x _{i j l} включается в объединённый граф путём ввода одной дуги. Действительно, в этом случае нельзя уменьшить время начала выполнения оператора x _{i j l}, из-за увеличения числа процессоров, требуемых для решения системы независимых алгоритмов. Следовательно, существует хотя бы один оператор x _s, такой, что выполняется условие

(6) u _s = u _{i j l} - t _{i l}.

В этом случае, для включения оператора x _{i j l} в объединённый граф G*, достаточно введения дуги x _s -> x _{i j l}.

Если для оператора x _{i j l} выполняется условие (4) и не существует оператора x _s, удовлетворяющего условию (б), тогда для включения оператора x _{i j l} в объединённый граф может потребоваться ввод дополнительного оператора x _k.

Рассмотрим непустое множество А = { 0, u _p} для всех u _p}, удовлетворяющих условию

(7) u _p =< u _{i j l} - t _{i l}.

Обозначим максимальный элемент этого множества u _s. Если для u _s выполняется условие (6), введём дугу x _s -> x _{i j l}. В противном случае, введём дополнительный оператор x _k, начало выполнения которого соответствует моменту времени u _s, а окончание u _{i j l} - t _{i l}. Из выполнения условия (4) для оператора x _{i j l} вытекает выполнение условия (3) для оператора x _k. Если значение u _s отлично от нуля, то введём связи между операторами x _s -> x _k -> x _{i j l}, в противном случае - только связь x _k -> x _{i j l}.