Изменения

*:Положим <tex>t_x</tex> и <tex>t_y</tex> временем начала выполнения и завершения работы <tex>J_k</tex> в расписании от <tex>Z</tex>. Благодаря предыдущей лемме, мы знаем, что <tex>t_x, t_y \in \Theta</tex>. Также выполняется условие <tex> \max(r_k, t_u) \leqslant t_x < t_y \leqslant \min(d_k, t_v).</tex> Пусть <tex>Z_1, Z_2, Z_3</tex> будут подмножествами <tex>Z/J_k</tex> такими, что все работы в <tex>Z_1, Z_2</tex> и <tex>Z_3</tex> имеют время появления <tex>r_i</tex> в границах <tex>[t_u,t_x)</tex>, <tex>[t_x, t_y)</tex> и <tex>[t_y,t_v)</tex> соответственно. По структуре расписания(работа <tex>J_k</tex> имеет максимальный дедлайн <tex>d_k</tex>) все работы в <tex>Z_1</tex> завершаться до <tex>t_x</tex>. Более того, все работы в <tex>Z_2</tex> начнут выполняться после <tex>t_x</tex> и завершаться до <tex>t_y</tex>, аналогично для <tex>Z_3</tex>. Также <tex>p \cdot (|Z_2| + 1) = t_y - t_x,</tex> так как <tex>J_k</tex> выполнялась в промежутке <tex>[t_x, t_y).</tex> При этом, <tex>|Z_1| + |Z_2| + |Z_3| = m - 1.</tex> Можно заметить, что вес <tex>Z_1</tex> не превосходит <tex>W_{k-1}(t_u, t_x, |Z_1|)</tex>, вес <tex>Z_2</tex> не превосходит <tex> W_{k-2}(t_x, t_y, |Z_2|)</tex> и вес <tex>Z_3</tex> не превосходит <tex> W_{k-1}(t_y, t_v, |Z_3|).</tex> Следовательно, <tex>W_k(t_u, t_v, m) = w_k + \sum\limits_{i = 1}^3weight(Z_i) \leqslant W'_k \leqslant \max(W_{k-1}(t_u, t_v, m), W'_k)</tex>, где <tex>wieghtweight(Z)</tex> <tex>-</tex> суммарный вес всех работ множества <tex>Z.</tex>

Исходя из двух неравенств доказанных выше, можно получить требуемое равенство <tex>W_k(t_u, t_v, m) = \max(W_{k-1}(t_u, t_v, m), W'_k).</tex> Лемма доказана.