Изменения

Сложность === Асимптотика ===Сначала мы сортируем работы и станки, что занимает <tex> \mathcal{O}(n\log{n})</tex> и <tex> \mathcal{O}(m\log{m})</tex>. Так как мы можем предположить, что количество станков меньше или равно колиеству работ <tex>m \le n</tex>, то в итоге сортировка займет <tex> \mathcal{O}(n\log{n})</tex>.Количество прерываний ограничено числом <tex>(m-1) \cdot n - (1 + 2 + ... + (m - 1)) = (m - 1) \cdot (n - \cfrac{m}{2})</tex>.Что в итоге даёт асимптотику алгоритма составляет <tex> \mathcal{O}(n\log{n} + mn)</tex>.

* Если <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>.

Без потери общности будем предполагать, что количество станков равно количеству работ <tex>m = n</tex>. Если <tex>m < n</tex>, то добавим <tex>n - m</tex> станков с нулевой скоростью обработки, если <tex>m > n</tex>, то удалим <tex>m - n</tex> самых медленных станков. Пусть у нас есть расписание, построенное по правилу '''SRPT-FM''', тогда <tex>C_{n} \le C_{n-1} \le ... \le C_{1}</tex>. Следовательно, верны следующие равенства::<tex>v_1 \cdot C_n = p_n</tex>:<tex>v_2 \cdot C_n + v_1 \cdot (C_{n-1} - C_n) = p_{n-1}</tex>:<tex>v_3 \cdot C_n + v_2 \cdot (C_{n-1} - C_n) + v_1 \cdot (C_{n-2} - C_{n-1}) = p_{n-2}</tex>:<tex>\vdots</tex>:<tex>v_n \cdot C_n + v_{n-1} \cdot (C_{n-1} - C_n) + ... + v_1 \cdot (C_1 - C_2) = p_1</tex>Проведем математические преобразования и получим следующие равенства::<tex>v_1 \cdot C_n = p_n</tex>:<tex>v_2 \cdot C_n + v_1 \cdot C_{n-1} = p_n + p_{n-1}</tex>:<tex>v_3 \cdot C_n + v_2 \cdot C_{n-1} + v_1 \cdot C_{n-2} = p_n + p_{n-1} + p_{n-2}</tex>:<tex>\vdots</tex>:<tex>v_n \cdot C_n + v_{n-1} \cdot C_{n-1} + ... + v_1 \cdot C_1 = p_n + p_{n-1} + ... + p_1</tex>Пусть <tex>S'</tex> оптимальное расписание, по предыдущей лемме верно, что <tex>C'_{n} \le C'_{n-1} \le ... \le C'_{1}</tex>. Самая короткая работа не может быть выполнена раньше, чем <tex>\cfrac{p_n}{v_1}</tex>. Таким образом <tex>C'_{n} \ge \cfrac{p_n}{v_1}</tex> или:<tex>v_1 \cdot C'_{n} \ge p_n</tex>Так как работы <tex>n</tex> и <tex>n-1</tex> выполнены к моменту <tex>C'_n</tex> и <tex>C'_{n-1}</tex> соответственно, то максимальное количество обработки, полученной этими работами составляет:<tex>(v_1 + v_2) \cdot C'_n + v_1 \cdot (C'_{n-1} - C'_n)</tex>Из чего следует, что:<tex>v_2 \cdot C'_n + v_1 \cdot C'_{n-1} \ge p_n + p_{n-1}</tex>Продолжая в том же духе можно показать, что:<tex>v_k \cdot C'_n + v_{k-1} \cdot C'_{n-1} + ... + v_1 \cdot C'_{n-k+1} \ge p_n + p_{n-1} + ... + p_{n-k+1}</tex>В разработкеитоге получаем следующие неравенства:<tex>v_1 \cdot C'_{n} \ge v_1 \cdot C_n</tex>:<tex>v_2 \cdot C'_n + v_1 \cdot C'_{n-1} \ge v_2 \cdot C_n + v_1 \cdot C_{n-1} </tex>:<tex>v_3 \cdot C'_n + v_2 \cdot C'_{n-1} + v_1 \cdot C'_{n-2} \ge v_3 \cdot C_n + v_2 \cdot C_{n-1} + v_1 \cdot C_{n-2}</tex>:<tex>\vdots</tex>:<tex>v_n \cdot C'_n + v_{n-1} \cdot C'_{n-1} + ... + v_1 \cdot C'_1 \ge v_n \cdot C_n + v_{n-1} \cdot C_{n-1} + ... + v_1 \cdot C_1</tex>Если существует такой набор положительных чисел <tex>a_j</tex>, что умножение <tex>j</tex>-го неравенства на <tex>a_j</tex> и сложение всех неравенств будет давать неравенство <tex>\sum{C'_j} \ge \sum{C_j}</tex>, тогда теорема будет доказана. Можно показать, что <tex>a_j</tex> должны удовлетворять следующим равенствам:<tex>v_1 \cdot a_1 + v_2 \cdot a_2 + ... + v_n \cdot a_n = 1</tex>:<tex>v_1 \cdot a_2 + v_2 \cdot a_3 + ... + v_{n-1} \cdot a_n = 1</tex>:<tex>\vdots</tex>:<tex>v_{1} \cdot a_n = 1</tex>Так как <tex>v_1 \ge v_2 \ge ... \ge v_n</tex> такой набор <tex>a_j</tex> существует.