Изменения
→Доказательство
|id=lemma6.14
|statement=Если существует расписание без опозданий, то данный алгоритм построит расписание без опозданий.
|proof=Покажем, что если в расписании, построенном данным алгоритмом есть опоздание, то опоздание есть в каждом расписании. Если есть опоздание в <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 l(A(t)) </tex> <tex> for</tex> <tex> v = 1, . . . , t - 1</tex> и <tex> l(A(0)) \leq 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> A(t) </tex> является первой операцией для работы, так как если <tex> l(A(t)) < l(A(v)) </tex> при некоторых <tex>v = 0. . . , t - 1</tex>,то алгоритм должен запланировать <tex> A(t) </tex> перед <tex> A(v) </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,...,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)) \leq l(A(s)), v = r, . . . , s - 1</tex>. Если <tex> O_{i',j'-1} = B(s - 1) </tex>, тогда возьмем минимальное <tex> r \leq 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>, мы продолжаем таким же образом.
}}
|proof={{в разработке}}
}}
==См. также.==
* [[Классификация задач]]
