32
правки
Изменения
→Динамика
<tex>\forall t_u, t_v \in \Theta, u <= v, \forall k \in (1, \dots ,n), \forall m \in (1, \dots ,n):</tex>
* <tex>r_k \notin [t_u, t_v) \Rightarrow W_k(t_u, t_v, m) = W_{k-1}(t_u, t_v, m);</tex>
* Иначе <tex>W_k(t_u, t_v, m) = \max(W_{k-1}(t_u, t_v, m), W'_k)</tex>, где <tex>W'_k = w_k + \max(W_{k-1}(t_u, t_x, m_1) + W_{k-1}(t_x, t_y, m_2) + W_{k-1}(t_y, t_v, m_3))</tex>.
|proof=
Если <tex>r_k \notin [t_u, t_v)</tex>, то работа <tex>J_k</tex> не может быть поставлена ни в какой <tex>Z</tex> такой, что <tex>JPS</tex> от <tex>Z</tex> разрешимо и <tex>Z \subset U_k(t_u, t_v)</tex>. Тогда, очевидно, что <tex>W_k(t_u, t_v, m) = W_{k-1}(t_u, t_v, m);</tex>
Теперь рассмотрим случай, когда <tex>r_k \in [t_u, t_v)</tex>. Сначала докажем, что <tex>W_k(t_u, t_v, m) \geqslant \max(W_{k-1}(t_u, t_v, m), W'_k)</tex>.
* <tex>W_{k-1}(t_u, t_v, m) > W'_k</tex>
*:Так как <tex>U_{k-1}(t_u, t_v) \subseteq U_k(t_u, t_v)</tex>, то <tex>W_{k-1}(t_u, t_v, m) \leqslant W_k(t_u, t_v, m)</tex>.
* <tex> W_{k-1}(t_u, t_v, m) < W'_k</tex>
*:Пусть существуют такие <tex>t_x, t_y \in \Theta</tex> и три числа <tex>m_1,m_2,m_3</tex>, такие что
*:# <tex> \max(r_k, t_u) \leqslant t_x < t_y \leqslant \min(d_k, t_v)</tex>,
*:# <tex> m_1 + m_2 + m_3 = m - 1</tex>,
*:# <tex> p \cdot (m_2 + 1) = t_y - t_x</tex>,
*: Очевидно, что <tex>U_{k-1}(t_u, t_x), U_{k-1}(t_x, t_y)</tex> и <tex>U_{k-1}(t_y, t_v)</tex> не пересекаются. Следовательно, <tex>JPS</tex> подмножеств, которые реализуют <tex>W_{k-1}(t_u, t_x, m_1), W_{k-1}(t_x, t_y, m_2)</tex> и <tex>W_{k-1}(t_y, t_v, m_3)</tex>, поставленные друг за другом дадут правильное расписание для <tex>m-1</tex> работ взятых из <tex>U_{k-1}(t_u, t_v)</tex>. Более того, у нас достаточно места чтобы вставить работу <tex>J_k</tex> в промежуток между <tex>t_x</tex> и <tex>t_y</tex>. Это возможно, так как <tex>p \cdot (m_2 + 1) = t_y - t_x</tex> и ровно <tex>m_2</tex> работ распределено для <tex>U_{k-1}(t_x, t_y)</tex>. Таким образом <tex>W'_k \leqslant W_k(t_u, t_v, m)</tex>.
}}
