QpmtnSumCi — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(теорема)
м (rollbackEdits.php mass rollback)
 
(не показано 5 промежуточных версий 2 участников)
Строка 7: Строка 7:
 
[[Файл:QpmtnSumCi example.png|320px|thumb|right|Пример работы алгоритма]]
 
[[Файл:QpmtnSumCi example.png|320px|thumb|right|Пример работы алгоритма]]
 
=== Идея ===
 
=== Идея ===
Для решения применим правило '''SRPT-FM''' (Shortest Remaining Processing Time on Fastest Machine), которое предлагает класть работу с наименьшим оставшемся временем обработки на самый быстрый доступный станок. Отсортируем работы по времени обработки в невозрастающем порядке так, что <tex>p_1 \ge p_2 \ge ... \ge p_n</tex>. Отсортируем станки по скорости обработки в невозрастающем порядке, так чтобы <tex>v_1 \ge v_2 \ge ... \ge 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 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 t_2</tex>, на станке <tex>M_1</tex>. Также поступаем со всеми оставшимися работами.
+
Для решения применим правило '''SRPT-FM''' (Shortest Remaining Processing Time on Fastest Machine), которое предлагает класть работу с наименьшим оставшемся временем обработки на самый быстрый доступный станок. Отсортируем работы по времени обработки в невозрастающем порядке так, что <tex>p_1 \geqslant p_2 \geqslant  \ldots  \geqslant p_n</tex>. Отсортируем станки по скорости обработки в невозрастающем порядке, так чтобы <tex>v_1 \geqslant v_2 \geqslant  \ldots  \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 \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 \geqslant t_2</tex>, на станке <tex>M_1</tex>. Также поступаем со всеми оставшимися работами.
  
 
=== Псевдокод ===
 
=== Псевдокод ===
  a = 0
+
Алгоритм принимает на вход два массива {{---}} массив с объемами работ и массив скоростей обработки станков, и возвращает вектор четвёрок, где первый элемент является номером станка, второй {{---}} номером работы, а два оставшихся время начала и окончания обработки этой работы на этом станке.
p[] // массив времен обработки работ отсортированный в невозрастающем порядке
+
  '''function''' scheduling(p: '''int'''[n], v: '''int'''[n]) -> '''vector<int, int, int, int>'''
v[] // массив скоростей обработки станков отсортированный в невозрастающем порядке
+
    '''int''' time = 0 <font color=green>// текущее время на всех станках</font>
'''while''' p[1] > 0
+
    '''vector<int, int, int, int>''' ans <font color=green> // вектор, куда будет записан ответ</font>
    Находим наибольший i такой, что p[i] > 0
+
    sort(p) <font color=green>// сортируем времена обработки работ в невозрастающем порядке</font>
    t = p[i] / v[1]
+
    sort(v) <font color=green>// сортируем скорости обработки станков в невозрастающем порядке</font>
    '''for''' j = i '''down to''' k = max(1, i - m + 1)
+
    '''while''' p[1] > 0
        Назначаем работу j на станок <tex>M_{1+i-j}</tex> на время от a до a + t
+
        Находим наибольший i такой, что p[i] > 0
        p[j] = p[j] - t * v[1 + i - j]
+
        '''int''' dt = p[i] / v[1] <font color=green>// время обработки самой короткой доступной задачи на самом быстром станке</font>
    a = a + t
+
        '''for''' j = i '''downto''' k = max(1, i - m + 1)
 +
            ans.push(1 + i - j, j, time, time + dt) <font color=green>// Назначаем на станок <tex>M_{1+i-j}</tex> работу j на время от time до time + dt</font>
 +
            p[j] = p[j] - dt * v[1 + i - j] <font color=green>// уменьшаем количество обработки, оставшейся для j-ой работы</font>
 +
        time = time + dt <font color=green>// обновляем текущее время</font>
 +
    '''return''' ans
  
 
=== Асимптотика ===
 
=== Асимптотика ===
Сначала мы сортируем работы и станки, что занимает <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> \mathcal{O}(n\log{n})</tex> и <tex> \mathcal{O}(m\log{m})</tex>. Так как при <tex>m \geqslant n</tex>, <tex>m - 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>(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> \mathcal{O}(n\log{n} + mn)</tex>.
  
 
== Доказательство корректности алгоритма ==
 
== Доказательство корректности алгоритма ==
 
{{Лемма
 
{{Лемма
 
|statement=
 
|statement=
Существует оптимальное расписание, в котором <tex>C_j \le C_k</tex>, когда <tex>p_j \le p_k</tex>, для всех <tex>j</tex> и <tex>k</tex>
+
Существует оптимальное расписание, в котором <tex>C_j \leqslant C_k</tex>, когда <tex>p_j \leqslant p_k</tex>, для всех <tex>j</tex> и <tex>k</tex>.
 
|proof=
 
|proof=
Рассмотрим расписание <tex>S</tex>, где для некоторых <tex>j</tex> и <tex>k</tex> верно, что <tex>C_j > C_k</tex>, но <tex>p_j \le 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 C_k</tex> и <tex>C'_k = C_j</tex> соответственно, при этом время завершения обработки остальных работ остается прежним. Тот факт, что в расписании <tex>S'</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 \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 \leqslant C_k</tex> и <tex>C'_k = C_j</tex> соответственно, при этом время завершения обработки остальных работ остается прежним. Тот факт, что в расписании <tex>S'</tex> работа <tex>j</tex> заканчивается раньше <tex>k</tex>, при этом не нарушая оптимальности расписания, свидетельствует о существовании расписания, описанного в условии леммы.
  
 
Для построения расписания <tex>S'</tex> из расписания <tex>S</tex> введем следующие обозначения:
 
Для построения расписания <tex>S'</tex> из расписания <tex>S</tex> введем следующие обозначения:
Строка 40: Строка 44:
  
 
Далее существуют два случая:
 
Далее существуют два случая:
* Если <tex>p^+_j \le p^3_k</tex>, то расписание <tex>S'</tex> получается обменом обработки, полученной <tex>j</tex> после момента <tex>C_k</tex> с частью обработки, полученной <tex>k</tex> не одновременно с <tex>j</tex>.
+
* Если <tex>p^+_j \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 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>, что верно:
+
* Если <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 \geqslant p^1_k</tex> и <tex>p_j \leqslant p_k</tex>, то <tex>p^2_j + \tilde{p}^+_j \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 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> интервалов нужно обменять:
+
:<tex>\sum\limits_{i=1}^{T}{\tilde{p}^{+,i}_j} = \tilde{p}^+_j</tex>,  <tex>p^{2,i}_j + \tilde{p}^{+,i}_j \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> интервалов нужно обменять:
 
:1) обработку, полученную в начале интервала работой <tex>k</tex> на более быстром станке, с обработкой <tex>j</tex>, полученной на медленном станке, на интервалы <tex>t^i_k</tex> и <tex>t^i_j</tex> соответственно
 
:1) обработку, полученную в начале интервала работой <tex>k</tex> на более быстром станке, с обработкой <tex>j</tex>, полученной на медленном станке, на интервалы <tex>t^i_k</tex> и <tex>t^i_j</tex> соответственно
 
:2) обработку <tex>\tilde{p}^{+,i}_j</tex>, полученной <tex>j</tex> после момента <tex>C_k</tex>, с таким же количеством обработки, полученной работой <tex>k</tex> на более быстром станке в этот интервал сразу после момента <tex>t^i_k</tex>.
 
:2) обработку <tex>\tilde{p}^{+,i}_j</tex>, полученной <tex>j</tex> после момента <tex>C_k</tex>, с таким же количеством обработки, полученной работой <tex>k</tex> на более быстром станке в этот интервал сразу после момента <tex>t^i_k</tex>.
Строка 49: Строка 53:
 
{{Теорема
 
{{Теорема
 
|statement=
 
|statement=
Расписание, построенное по принципу '''SRPT-FM''', оптимальное для задачи <tex> Q \mid pmtn \mid \sum C_i </tex>
+
Расписание, построенное по принципу '''SRPT-FM''', оптимальное для задачи <tex> Q \mid pmtn \mid \sum C_i </tex>.
 
|proof=
 
|proof=
 
Без потери общности будем предполагать, что количество станков равно количеству работ <tex>m = n</tex>. Если <tex>m < n</tex>, то добавим <tex>n - m</tex> станков с нулевой скоростью обработки, если <tex>m > n</tex>, то удалим <tex>m - n</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>. Следовательно, верны следующие равенства:
+
Пусть у нас есть расписание, построенное по правилу '''SRPT-FM''', тогда <tex>C_{n} \leqslant C_{n-1} \leqslant  \ldots  \leqslant C_{1}</tex>. Следовательно, верны следующие равенства:
 
:<tex>v_1 \cdot C_n = p_n</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_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>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>\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_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_1 \cdot C_n = p_n</tex>
 
:<tex>v_1 \cdot C_n = p_n</tex>
Строка 64: Строка 68:
 
:<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>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>\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>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 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>S'</tex> оптимальное расписание, по предыдущей лемме верно, что <tex>C'_{n} \leqslant C'_{n-1} \leqslant  \ldots  \leqslant C'_{1}</tex>. Самая короткая работа не может быть выполнена раньше, чем <tex>\cfrac{p_n}{v_1}</tex>. Таким образом <tex>C'_{n} \geqslant \cfrac{p_n}{v_1}</tex> или
:<tex>v_1 \cdot C'_{n} \ge p_n</tex>
+
:<tex>v_1 \cdot C'_{n} \geqslant p_n</tex>
 
Так как работы <tex>n</tex> и <tex>n-1</tex> выполнены к моменту <tex>C'_n</tex> и <tex>C'_{n-1}</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_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_2 \cdot C'_n + v_1 \cdot C'_{n-1} \geqslant 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_k \cdot C'_n + v_{k-1} \cdot C'_{n-1} + \ldots  + v_1 \cdot C'_{n-k+1} \geqslant p_n + p_{n-1} + \ldots  + p_{n-k+1}</tex>
 
В итоге получаем следующие неравенства
 
В итоге получаем следующие неравенства
:<tex>v_1 \cdot C'_{n} \ge v_1 \cdot C_n</tex>
+
:<tex>v_1 \cdot C'_{n} \geqslant 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_2 \cdot C'_n + v_1 \cdot C'_{n-1} \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 v_3 \cdot C_n + v_2 \cdot C_{n-1} + v_1 \cdot C_{n-2}</tex>
+
:<tex>v_3 \cdot C'_n + v_2 \cdot C'_{n-1} + v_1 \cdot C'_{n-2} \geqslant v_3 \cdot C_n + v_2 \cdot C_{n-1} + v_1 \cdot C_{n-2}</tex>
 
:<tex>\vdots</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>v_n \cdot C'_n + v_{n-1} \cdot C'_{n-1} + \ldots  + v_1 \cdot C'_1 \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 \sum{C_j}</tex>, тогда теорема будет доказана. Можно показать, что <tex>a_j</tex> должны удовлетворять следующим равенствам
+
Если существует такой набор положительных чисел <tex>a_j</tex>, что умножение <tex>j</tex>-го неравенства на <tex>a_j</tex> и сложение всех неравенств будет давать неравенство <tex>\sum{C'_j} \geqslant \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_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 + ... + v_{n-1} \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>\vdots</tex>
 
:<tex>\vdots</tex>
 
:<tex>v_{1} \cdot a_n = 1</tex>
 
:<tex>v_{1} \cdot a_n = 1</tex>
Так как <tex>v_1 \ge v_2 \ge ... \ge v_n</tex> такой набор <tex>a_j</tex> существует.
+
Так как <tex>v_1 \geqslant v_2 \geqslant  \ldots  \geqslant v_n</tex> такой набор <tex>a_j</tex> существует.
 
}}
 
}}
  
 
== См. также ==
 
== См. также ==
[[QSumCi|<tex>Q\mid\mid\sum{C_i}</tex>]]
+
* [[QSumCi|<tex>Q\mid\mid\sum{C_i}</tex>]]
  
 
== Источники информации ==
 
== Источники информации ==
 
* Peter Brucker «Scheduling Algorithms», fifth edition, Springer {{---}} с. 134-135 ISBN 978-3-540-69515-8
 
* Peter Brucker «Scheduling Algorithms», fifth edition, Springer {{---}} с. 134-135 ISBN 978-3-540-69515-8
 
* [http://www.semanticscholar.org/paper/Optimal-preemptive-scheduling-on-uniform-machines-Pandelis/819408316692bf5aa8ba80f1f6d6e7667863c33a/pdf Dimitrios G. Pandelis "Optimal preemptive scheduling on uniform machines with discounted flowtime objectives" {{---}} с. 631-632]
 
* [http://www.semanticscholar.org/paper/Optimal-preemptive-scheduling-on-uniform-machines-Pandelis/819408316692bf5aa8ba80f1f6d6e7667863c33a/pdf Dimitrios G. Pandelis "Optimal preemptive scheduling on uniform machines with discounted flowtime objectives" {{---}} с. 631-632]
* M.L. Pinedo "Parallel Machine Models (Deterministic)" {{---}} с.135-136
+
* [http://link.springer.com/chapter/10.1007%2F978-1-4614-2361-4_5 M.L. Pinedo "Parallel Machine Models (Deterministic)" {{---}} с.135-136]
[[Категория: Дискретная математика и алгоритмы]]
+
 
 +
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Теория расписаний]]
 
[[Категория: Теория расписаний]]

Текущая версия на 19:26, 4 сентября 2022

[math] Q \mid pmtn \mid \sum C_i [/math]

Задача:
Дано [math]m[/math] станков с разной скоростью выполнения работ [math]v_j[/math] и [math]n[/math] работ с заданным временем выполнения [math]p_i[/math]. Работы можно прерывать и продолжать их выполнение на другом станке. Необходимо построить такое расписание, чтобы суммарное время окончания всех работ было минимальным.

Описание алгоритма

Пример работы алгоритма

Идея

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

Псевдокод

Алгоритм принимает на вход два массива — массив с объемами работ и массив скоростей обработки станков, и возвращает вектор четвёрок, где первый элемент является номером станка, второй — номером работы, а два оставшихся время начала и окончания обработки этой работы на этом станке.

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

Асимптотика

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

Доказательство корректности алгоритма

Лемма:
Существует оптимальное расписание, в котором [math]C_j \leqslant C_k[/math], когда [math]p_j \leqslant p_k[/math], для всех [math]j[/math] и [math]k[/math].
Доказательство:
[math]\triangleright[/math]

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

Для построения расписания [math]S'[/math] из расписания [math]S[/math] введем следующие обозначения:

  • [math]p^1_j[/math], [math]p^1_k[/math] — количество обработки, полученной одновременно [math]j[/math] и [math]k[/math], когда работа [math]j[/math] была на более быстром станке или обе работы были на одинаковых станках.
  • [math]p^2_j[/math], [math]p^2_k[/math] — количество обработки, полученной одновременно [math]j[/math] и [math]k[/math], когда работа [math]k[/math] была на более быстром станке.
  • [math]p^3_j[/math], [math]p^3_k[/math] — количество обработки, полученной [math]j[/math] и [math]k[/math] до момента [math]C_k[/math] на непересекающихся участках времени.
  • [math]p^+_j[/math] — количество обработки, полученной [math]j[/math] после момента [math]C_k[/math].

Далее существуют два случая:

  • Если [math]p^+_j \leqslant p^3_k[/math], то расписание [math]S'[/math] получается обменом обработки, полученной [math]j[/math] после момента [math]C_k[/math] с частью обработки, полученной [math]k[/math] не одновременно с [math]j[/math].
  • Если [math]p^+_j \gt p^3_k[/math], то для начала обмениваем всю обработку [math]p^3_k[/math] с частью [math]p^+_j[/math], чтобы получить новое расписание, где [math]C'_k = C_j[/math] и [math]\tilde{p}^+_j = p^+_j - p^3_k[/math] обработки [math]j[/math] после момента [math]C_k[/math]. Пусть [math]p^2_j[/math] и [math]p^2_k[/math] представлены числом [math]T[/math] непересекающихся временных интервалов длинной [math]t_i[/math] с [math]v^i_j[/math], [math]v^i_k[/math] — скоростями станков, обрабатывающих [math]j[/math] и [math]k[/math] в интервал [math]i[/math] и [math]p^{2,i}_j = v^i_j \cdot t_i[/math], [math]p^{2,i}_k = v^i_k \cdot t_i[/math] — количество обработки, полученной соответствующей задачей за этот интервал. Так как [math]p^1_j \geqslant p^1_k[/math] и [math]p_j \leqslant p_k[/math], то [math]p^2_j + \tilde{p}^+_j \leqslant p^2_k[/math]. Следовательно, существует такой [math]\tilde{p}^{+,i}_j[/math], что верно:
[math]\sum\limits_{i=1}^{T}{\tilde{p}^{+,i}_j} = \tilde{p}^+_j[/math], [math]p^{2,i}_j + \tilde{p}^{+,i}_j \leqslant p^{2,i}_k[/math], [math]i = 1 \ldots T[/math]
Для каждого [math]i = 1 \ldots T[/math] пусть [math]t^i_j = \cfrac{\tilde{p}^{+,i}_j}{v^i_k - v^i_j}[/math], [math]t^i_k = t^i_j \cdot \cfrac{v^i_j}{v^i_k}[/math]. Чтобы получить расписание [math]S'[/math] для каждого из [math]T[/math] интервалов нужно обменять:
1) обработку, полученную в начале интервала работой [math]k[/math] на более быстром станке, с обработкой [math]j[/math], полученной на медленном станке, на интервалы [math]t^i_k[/math] и [math]t^i_j[/math] соответственно
2) обработку [math]\tilde{p}^{+,i}_j[/math], полученной [math]j[/math] после момента [math]C_k[/math], с таким же количеством обработки, полученной работой [math]k[/math] на более быстром станке в этот интервал сразу после момента [math]t^i_k[/math].
[math]\triangleleft[/math]
Теорема:
Расписание, построенное по принципу SRPT-FM, оптимальное для задачи [math] Q \mid pmtn \mid \sum C_i [/math].
Доказательство:
[math]\triangleright[/math]

Без потери общности будем предполагать, что количество станков равно количеству работ [math]m = n[/math]. Если [math]m \lt n[/math], то добавим [math]n - m[/math] станков с нулевой скоростью обработки, если [math]m \gt n[/math], то удалим [math]m - n[/math] самых медленных станков.

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

[math]v_1 \cdot C_n = p_n[/math]
[math]v_2 \cdot C_n + v_1 \cdot (C_{n-1} - C_n) = p_{n-1}[/math]
[math]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}[/math]
[math]\vdots[/math]
[math]v_n \cdot C_n + v_{n-1} \cdot (C_{n-1} - C_n) + \ldots + v_1 \cdot (C_1 - C_2) = p_1[/math]

Проведем математические преобразования и получим следующие равенства:

[math]v_1 \cdot C_n = p_n[/math]
[math]v_2 \cdot C_n + v_1 \cdot C_{n-1} = p_n + p_{n-1}[/math]
[math]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}[/math]
[math]\vdots[/math]
[math]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[/math]

Пусть [math]S'[/math] оптимальное расписание, по предыдущей лемме верно, что [math]C'_{n} \leqslant C'_{n-1} \leqslant \ldots \leqslant C'_{1}[/math]. Самая короткая работа не может быть выполнена раньше, чем [math]\cfrac{p_n}{v_1}[/math]. Таким образом [math]C'_{n} \geqslant \cfrac{p_n}{v_1}[/math] или

[math]v_1 \cdot C'_{n} \geqslant p_n[/math]

Так как работы [math]n[/math] и [math]n-1[/math] выполнены к моменту [math]C'_n[/math] и [math]C'_{n-1}[/math] соответственно, то максимальное количество обработки, полученной этими работами составляет

[math](v_1 + v_2) \cdot C'_n + v_1 \cdot (C'_{n-1} - C'_n)[/math]

Из чего следует, что

[math]v_2 \cdot C'_n + v_1 \cdot C'_{n-1} \geqslant p_n + p_{n-1}[/math]

Продолжая в том же духе можно показать, что

[math]v_k \cdot C'_n + v_{k-1} \cdot C'_{n-1} + \ldots + v_1 \cdot C'_{n-k+1} \geqslant p_n + p_{n-1} + \ldots + p_{n-k+1}[/math]

В итоге получаем следующие неравенства

[math]v_1 \cdot C'_{n} \geqslant v_1 \cdot C_n[/math]
[math]v_2 \cdot C'_n + v_1 \cdot C'_{n-1} \geqslant v_2 \cdot C_n + v_1 \cdot C_{n-1} [/math]
[math]v_3 \cdot C'_n + v_2 \cdot C'_{n-1} + v_1 \cdot C'_{n-2} \geqslant v_3 \cdot C_n + v_2 \cdot C_{n-1} + v_1 \cdot C_{n-2}[/math]
[math]\vdots[/math]
[math]v_n \cdot C'_n + v_{n-1} \cdot C'_{n-1} + \ldots + v_1 \cdot C'_1 \geqslant v_n \cdot C_n + v_{n-1} \cdot C_{n-1} + \ldots + v_1 \cdot C_1[/math]

Если существует такой набор положительных чисел [math]a_j[/math], что умножение [math]j[/math]-го неравенства на [math]a_j[/math] и сложение всех неравенств будет давать неравенство [math]\sum{C'_j} \geqslant \sum{C_j}[/math], тогда теорема будет доказана. Можно показать, что [math]a_j[/math] должны удовлетворять следующим равенствам

[math]v_1 \cdot a_1 + v_2 \cdot a_2 + \ldots + v_n \cdot a_n = 1[/math]
[math]v_1 \cdot a_2 + v_2 \cdot a_3 + \ldots + v_{n-1} \cdot a_n = 1[/math]
[math]\vdots[/math]
[math]v_{1} \cdot a_n = 1[/math]
Так как [math]v_1 \geqslant v_2 \geqslant \ldots \geqslant v_n[/math] такой набор [math]a_j[/math] существует.
[math]\triangleleft[/math]

См. также

Источники информации