Изменения

* Если <tex>p^+_j > p^3_k</tex>, то для начала обмениваем всю обработку <tex>p^3_k</tex> с частью <tex>p^+_j</tex>, чтобы получить новое расписаниирасписание, где <tex>C'_k = C_j</tex> и <tex>\tilde{p}^+_j = p^+_j - p^3_k</tex> обработки <tex>j</tex> после момента <tex>C_k</tex>. Пусть <tex>p^2_j</tex> и <tex>p^2_k</tex> представлены числом <tex>T</tex> непересекающихся временных интервалов длинной <tex>t_i</tex> с <tex>v^i_j</tex>, <tex>v^i_k</tex> {{---}} скоростями станков, обрабатывающих <tex>j</tex> и <tex>k</tex> в интервал <tex>i</tex> и <tex>p^{2,i}_j = v^i_j \cdot t_i</tex>, <tex>p^{2,i}_k = v^i_k \cdot t_i</tex> {{---}} количество обработки, полученной соответвующей соответствующей задачей за этот интервал. Так как <tex>p^1_j \ge p^1_k</tex> и <tex>p_j \le p_k</tex>, то <tex>p^2_j + \tilde{p}^+_j \le p^2_k</tex>. Следовательно , существует такой <tex>\tilde{p}^{+,i}_j</tex>, что верно:<br><tex>\sum\limits_{i=1}^{T}{\tilde{p}^{+,i}_j} = \tilde{p}^+_j</tex>, <tex>p^{2,i}_j + \tilde{p}^{+,i}_j \le p^{2,i}_k</tex>, <tex>i = 1...T</tex><br>Для каждого <tex>i = 1...T</tex> пусть <tex>t^i_j = \cfrac{\tilde{p}^{+,i}_j}{v^i_k - v^i_j}</tex>, <tex>t^i_k = t^i_j \cdot \cfrac{v^i_j}{v^i_k}</tex>. Чтобы получить расписание <tex>S'</tex> для каждого из <tex>T</tex> интервалов нужно обменять:<br> 1) обработку, полученную в начале интервала работой <tex>k</tex> на более быстром станке, с обработкой <tex>j</tex>, полученной на медленном станке, на интервалы <tex>t^i_k</tex> и <tex>t^i_j</tex> соответственно<br>2) обработку <tex>\tilde{p}^{+,i}_j</tex>, полученной <tex>j</tex> после момента <tex>C_k</tex>, с таким же количеством обработки, полученной работой <tex>k</tex> на более быстром станке в этот интервал сразу после момента <tex>t^i_k</tex>.