Изменения

Для решения применим правило '''SRPT-FM''' (Shortest Remaining Processing Time on Fastest Machine), которое предлагает класть работу с наименьшим оставшемся временем обработки на самый быстрый доступный станок. Отсортируем работы по времени обработки в невозрастающем порядке так, что <tex>p_1 \ge geqslant p_2 \ge ... geqslant \ldots \ge geqslant p_n</tex>. Отсортируем станки по скорости обработки в невозрастающем порядке, так чтобы <tex>v_1 \ge geqslant v_2 \ge ... geqslant \ldots \ge geqslant v_m</tex>. Далее назначаем <tex>n</tex>-ю работу на станок <tex>M_1</tex> (1-й по скорости станок) на время <tex>t_1 = \cfrac{p_n}{v_1}</tex>, то есть пока она полностью не выполнится. Теперь назначим <tex>n-1</tex> работу сначала станок <tex>M_2</tex> на время <tex>t_1</tex>, а затем на время от <tex>t_1</tex> до <tex>t_2 \ge geqslant t_1</tex> на станок <tex>M_1</tex>, пока она не завершится. С <tex>n-2</tex> работой поступаем аналогично, сначала она <tex>t_1</tex> времени выполняется на станке <tex>M_3</tex>, затем <tex>t_2 - t_1</tex> времени на станке <tex>M_2</tex>, и, начиная с <tex>t_2</tex> до <tex>t_3 \ge geqslant t_2</tex>, на станке <tex>M_1</tex>. Также поступаем со всеми оставшимися работами.

'''function''' scheduling(p: '''int'''[n], v: '''int'''[n]) -> '''(int, int, int)'''[m] '''int''' a = 0 p '''(int, int, int)'''[] ans <font color=green> // массив времен сюда будет записываться ответ</font> sort(p) <font color=green>// сортируем времена обработки работ отсортированный в невозрастающем порядке</font> sort(v[] ) <font color=green>// массив скоростей сортируем скорости обработки станков отсортированный в невозрастающем порядке</font> '''while''' p[1] > 0 Находим наибольший i такой, что p[i] > 0 '''int''' t = p[i] / v[1] '''for''' j = i '''down todownto''' k = max(1, i - m + 1) ans[1 + i - j].push(a, a + t, j) <font color=green>// Назначаем работу j на станок <tex>M_{1+i-j}</tex> на время от a до a + t</font> p[j] = p[j] - t * v[1 + i - j] a = a + t return ans

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

Существует оптимальное расписание, в котором <tex>C_j \le leqslant C_k</tex>, когда <tex>p_j \le leqslant p_k</tex>, для всех <tex>j</tex> и <tex>k</tex>.

Рассмотрим расписание <tex>S</tex>, где для некоторых <tex>j</tex> и <tex>k</tex> верно, что <tex>C_j > C_k</tex>, но <tex>p_j \le leqslant p_k</tex>. С помощью обмена частей обработки, полученной работами <tex>j</tex> и <tex>k</tex>, мы можем изменить расписание <tex>S</tex>, получив новое оптимальное расписание <tex>S'</tex>, где обработка работ <tex>j</tex> и <tex>k</tex> завершается во времена <tex>C'_j \le leqslant C_k</tex> и <tex>C'_k = C_j</tex> соответственно, при этом время завершения обработки остальных работ остается прежним. Тот факт, что в расписании <tex>S'</tex> работа <tex>j</tex> заканчивается раньше <tex>k</tex>, при этом не нарушая оптимальности расписания, свидетельствует о существовании расписания, описанного в условии леммы.

* Если <tex>p^+_j \le leqslant p^3_k</tex>, то расписание <tex>S'</tex> получается обменом обработки, полученной <tex>j</tex> после момента <tex>C_k</tex> с частью обработки, полученной <tex>k</tex> не одновременно с <tex>j</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 geqslant p^1_k</tex> и <tex>p_j \le leqslant p_k</tex>, то <tex>p^2_j + \tilde{p}^+_j \le leqslant p^2_k</tex>. Следовательно, существует такой <tex>\tilde{p}^{+,i}_j</tex>, что верно::<tex>\sum\limits_{i=1}^{T}{\tilde{p}^{+,i}_j} = \tilde{p}^+_j</tex>, <tex>p^{2,i}_j + \tilde{p}^{+,i}_j \le leqslant p^{2,i}_k</tex>, <tex>i = 1...\ldots T</tex><br>Для каждого <tex>i = 1...\ldots 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> интервалов нужно обменять:

Расписание, построенное по принципу '''SRPT-FM''', оптимальное для задачи <tex> Q \mid pmtn \mid \sum C_i </tex>.

Пусть у нас есть расписание, построенное по правилу '''SRPT-FM''', тогда <tex>C_{n} \le leqslant C_{n-1} \le ... leqslant \le ldots \leqslant C_{1}</tex>. Следовательно, верны следующие равенства:

:<tex>v_n \cdot C_n + v_{n-1} \cdot (C_{n-1} - C_n) + ... \ldots + v_1 \cdot (C_1 - C_2) = p_1</tex>

:<tex>v_n \cdot C_n + v_{n-1} \cdot C_{n-1} + ... \ldots + v_1 \cdot C_1 = p_n + p_{n-1} + ... \ldots + p_1</tex>Пусть <tex>S'</tex> оптимальное расписание, по предыдущей лемме верно, что <tex>C'_{n} \le leqslant C'_{n-1} \le ... leqslant \ldots \le leqslant C'_{1}</tex>. Самая короткая работа не может быть выполнена раньше, чем <tex>\cfrac{p_n}{v_1}</tex>. Таким образом <tex>C'_{n} \ge geqslant \cfrac{p_n}{v_1}</tex> или:<tex>v_1 \cdot C'_{n} \ge geqslant p_n</tex>

:<tex>v_2 \cdot C'_n + v_1 \cdot C'_{n-1} \ge geqslant p_n + p_{n-1}</tex>

:<tex>v_k \cdot C'_n + v_{k-1} \cdot C'_{n-1} + ... \ldots + v_1 \cdot C'_{n-k+1} \ge geqslant p_n + p_{n-1} + ... \ldots + p_{n-k+1}</tex>

:<tex>v_1 \cdot C'_{n} \ge geqslant v_1 \cdot C_n</tex>:<tex>v_2 \cdot C'_n + v_1 \cdot C'_{n-1} \ge geqslant 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 geqslant v_3 \cdot C_n + v_2 \cdot C_{n-1} + v_1 \cdot C_{n-2}</tex>

:<tex>v_n \cdot C'_n + v_{n-1} \cdot C'_{n-1} + ... \ldots + v_1 \cdot C'_1 \ge geqslant v_n \cdot C_n + v_{n-1} \cdot C_{n-1} + ... \ldots + v_1 \cdot C_1</tex>Если существует такой набор положительных чисел <tex>a_j</tex>, что умножение <tex>j</tex>-го неравенства на <tex>a_j</tex> и сложение всех неравенств будет давать неравенство <tex>\sum{C'_j} \ge geqslant \sum{C_j}</tex>, тогда теорема будет доказана. Можно показать, что <tex>a_j</tex> должны удовлетворять следующим равенствам:<tex>v_1 \cdot a_1 + v_2 \cdot a_2 + ... \ldots + v_n \cdot a_n = 1</tex>:<tex>v_1 \cdot a_2 + v_2 \cdot a_3 + ... \ldots + v_{n-1} \cdot a_n = 1</tex>

Так как <tex>v_1 \ge geqslant v_2 \ge ... geqslant \ge ldots \geqslant v_n</tex> такой набор <tex>a_j</tex> существует.

* [[QSumCi|<tex>Q\mid\mid\sum{C_i}</tex>]]

* [http://link.springer.com/chapter/10.1007%2F978-1-4614-2361-4_5 M.L. Pinedo "Parallel Machine Models (Deterministic)" {{---}} с.135-136] [[Категория: Дискретная математика Алгоритмы и алгоритмыструктуры данных]]