Изменения
Нет описания правки
'''if''' T1 < LAST(i)
t = LAST(i)
A(t) = <tex>O_{ij}</tex>(*)
'''else'''
t = T1;
'''if''' T2 < LAST(i)
t = LAST(i)
B(t) = <tex>O_{ij}</tex>(**)
'''else'''
t = T2;
==Доказательство==
Для доказательство того, что алгоритм решения задачи корректен, необходимо показать то, что он строит достижимое расписание. Это справедливо тогда и только тогда, когда до исполнения строчек (*) и (**) пусты A(t) и B(t) соответственно. Иначе две разные операции будут выполняться в один момент времени на одной машине. Для того, чтобы показать достижимость докажем лемму.
{{Лемма
|id=lemma6.12
|statement=Пусть <tex>Y = (A(t), B(t))</tex> — расписание, где <tex>B(t) = \emptyset</tex> <tex>(A(t) = \emptyset)</tex>. Тогда для каждого <tex>s > t</tex>, где <tex>B(s) = O_{ij}</tex> <tex>(A(s) = O_{ij})</tex> выполняется <tex>A(s -1) = O_{i, j - 1}</tex> <tex>(B(s - 1) = O_{i, j -1}))</tex>
}}
==Источники==
