Изменения

Сначала докажем лемму для <tex>e_i</tex>. Пусть <tex>t</tex> <tex>-</tex> минимальная временная точка такая, что между <tex>t</tex> и <tex>s_i</tex> станок не простаивает. По структуре расписания <tex>t = r_x</tex>. Работы, которые выполняются между <tex>s_i</tex> и <tex>e_i</tex>, не могут выполняться ни до <tex>s_i</tex>, ни после <tex>e_i</tex>, даже частично. Это следует из структуры алгоритма построения расписания <tex>- </tex> если работа <tex>J_u</tex> была прервана работой <tex>J_v</tex>, то после выполнения <tex>J_v</tex> мы снова вставляем в расписание <tex>J_u</tex>. Таким образом, <tex>e_i - s_i</tex> делится на <tex>p</tex>. Возможны следующие два случая:

Теперь докажем принадлежность <tex>s_i</tex> к <tex>\Theta</tex>. По структуре расписания <tex>s_i</tex> <tex> - </tex> это либо окончание предыдущей работы <tex>e_u</tex>, либо <tex>r_i</tex>. Таким образом, легко понять, что <tex>s_i \in \Theta</tex>.

|definition = <tex>\forall t_u, t_v \in \Theta, u <= \leqslant v, k \forall k = in [1, \dots ,n]:</tex>#<tex>U_k(t_u, t_v) = \{J_i \mid i < k \wedge t_u <= r_i < t_v\}</tex> <tex>-</tex> это множество работ, индекс которых меньше <tex>k</tex> и чьи <tex>r_i</tex> лежать в интервале <tex>[t_u, t_v);</tex>#<tex>W_k(t_u, t_v, m)</tex> <tex> - </tex> максимальный вес <tex>Z \subset U_k(t_u, t_v), |Z| = m</tex> такой, что <tex>m \in (1, \dots ,n)</tex> и расписание от <tex>Z</tex> разрешимо и заканчивается до <tex>t_v</tex>. Если такое <tex>Z</tex> существует, будем говорить, что <tex>Z</tex> реализует <tex>W_k(t_u, t_v, m)</tex>. Если же такого <tex>Z</tex> нет, то <tex>W_k(t_u, t_v, m) = - \infty.</tex>}}

<tex>\forall t_u, t_v \in \Theta, u <= \leqslant v, \forall k \in (1, \dots ,n), \forall m \in (1, \dots ,n):</tex>