Изменения
Нет описания правки
|proof= Докажем по индукции по <tex>s</tex>, что если <tex>B(s) = O_{ij}</tex> и <tex>s > t</tex>, то <tex>A(s -1) = O_{i, j - 1}</tex>. Это, очевидно, верно при <tex>s = t+1</tex> так как если <tex>B(t+1) = O_{ij}</tex> и <tex>A(t)</tex> не соответствует работе <tex>i</tex>, то <tex>B(t) = \emptyset</tex> означает что операция <tex>O_{ij}</tex> должна быть запланирована в расписании ранее.
Предположим теперь что лемма верна для всех <tex>v</tex> при <tex>t < v < s</tex> и <tex>B(s) = O_{ij}</tex> . Выберем максимальное <tex>l</tex>, такое что <tex>t < l < s</tex> и <tex>B(l) = \emptyset</tex>. По предположению индукции, <tex>A(v- −1)</tex> и <tex>B(v)</tex> соответствуют одной и той же работе для <tex>v = l + 1,...\ldots,s —- 1</tex>. Пусть <tex>A(s - 1</tex>) не соответствует работе <tex>i</tex>. Тогда для каждого <tex> v \in\{l, l + 1, . . . \ldots , s - 1\}</tex> операция <tex>A(v)</tex> не соответствует работе <tex>i</tex>. Таким образом, <tex>O_{ij}</tex> может быть обработан в момент <tex>l</tex>, что противоречит тому, что <tex>Y</tex> является расписанием.
}}
Теперь положим <tex> A(t) = O_{ij}</tex> для какого-нибудь <tex> i</tex> и <tex> j > 1</tex>.
Получим <tex> O_{ij-1} = B(s) </tex> при <tex> s < t - 1</tex>,
так как из <tex> s = t - 1</tex> следует <tex> l(B(s)) = l(A(t)) - 1 < t = s + 1</tex>, а это противоречит минимальности <tex> t</tex>. Из этого следует, что <tex> l(A(v)) < l(A(t)) </tex> при <tex> v = s + 1,...\ldots,t - 1</tex>
так как в противном случае <tex> A(t) </tex> должно быть запланировано ранее. Также <tex> l(A(s)) < l(A(s + 1)) </tex> поскольку в противном случае <tex> A (s + 1) </tex> должно быть запланировано на время <tex> s</tex>, так как <tex> A (s + 1) </tex> и <tex> B(s) </tex> являются операциями различных задач. Для <tex> s = 0</tex> мы доказали (***). Иначе пусть <tex> A(s) = O_{i’,j’,} </tex>. Если <tex> A (s) </tex> — первая операция задачи, мы закончили. В противном случае, если
<tex> O_{i’,’j-1} = B(r) </tex> при <tex> r < s - 1</tex>,
<tex> l(A(v)) \leqslant l(A(s)), v = r, . . . , s - 1</tex>.
Если <tex> O_{i',j'-1} = B(s - 1) </tex>, тогда возьмем минимальное <tex> r \leqslant s - 1</tex> такое, что <tex> B(v) </tex> и <tex>A(v+1) </tex> являются последовательными операциями одной и той же задачи при <tex> v = r, ...\ldots,s - 1</tex>. <tex> A(s + 1) </tex> не соответствует задаче <tex> i</tex>, и мы снова имеем <tex> l(A(v)) < l(A(s + 1)), v = r,...\ldots,s</tex>.Если <tex> r = 0</tex>, мы закончили. Если <tex> r > 0</tex>, продолжаем таким же образом.
}}
