Изменения
→Доказательство
Если есть опоздание в <tex> Y = (A(t), B(t)) </tex>, то существует операция <tex> A(t) </tex> или <tex> B(t) </tex> с <tex> l(A(t)) < t + 1</tex> или <tex> l(B(t)) < t + 1</tex>. Например, это неравенство верно для последней операции в конце работы. Выберем минимальное <tex> t</tex> с этим свойством и предположим, что <tex> l(A(t)) < t + 1</tex>.
Тогда мы докажем, что
<tex> l(A(v)) \leq leqslant l(A(t)) </tex> <tex> for</tex> <tex> v = 1, . . . , t - 1</tex> и <tex> l(A(0)) \leq leqslant l(A(t)) </tex> <tex> if </tex> <tex> A(0) \neq \emptyset</tex>.
(***)
Таким образом, в каждом расписании должно существовать, по крайней мере, одно опоздание, т.к. если <tex> A(0)\neq \emptyset</tex> то <tex> l(A(v)) < t + 1</tex> при <tex> v = 0, . . . , t</tex> и мы должны запланировать <tex> t + 1 </tex> операций во временном интервале <tex> [0, t] </tex>, что невозможно. Если же <tex> A(0) = \emptyset </tex>, то все задачи начинаются на машине <tex> B </tex> и <tex> t</tex> операций должны обрабатываться в интервале времени <tex> [1, t] </tex>, что тоже не возможно.
мы снова имеем
<tex> l(A(v)) \leq leqslant l(A(s)), v = r, . . . , s - 1</tex>.
Если <tex> O_{i',j'-1} = B(s - 1) </tex>, тогда возьмем минимальное <tex> r \leq leqslant s - 1</tex> такое, что <tex> B(v) </tex> и <tex>A(v+1) </tex> являются последовательными операциями одной и той же задачи при <tex> v = r, ...,s - 1</tex>. <tex> A(s + 1) </tex> не соответствует задаче <tex> i</tex>, и мы снова имеем <tex> l(A(v)) < l(A(s + 1)), v = r,...,s</tex>.Если <tex> r = 0</tex>, мы закончили. Если <tex> r > 0</tex>, продолжаем таким же образом.
}}
