Изменения

Перейти к: навигация, поиск

1ripippmtnsumwu

Нет изменений в размере, 20:47, 5 июня 2016
Динамика
*:# <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>.
32
правки

Навигация