QpmtnCmax

[math]Q \mid pmtn \mid C_{max}[/math]

Задача:

Дано несколько станков с разной скоростью выполнения работ, работающих параллельно. Работа может быть прервана в любой момент и продолжена позже на любой машине. Необходимо минимизировать время выполнения всех работ.

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

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

Пусть нам даны [math]n[/math] работ и [math]m[/math] станков. Перед выполнением алгоритма, упорядочим все работы по убыванию их времени выполнения:[math] p_1 \geqslant p_2 \geqslant p_3 \ldots \geqslant p_n[/math], а все машины в порядке убывания скоростей: [math] s_1 \geqslant s_2 \geqslant s_3 \ldots \geqslant s_m[/math]. Введем следующие обозначения:

[math] P_i = p_1 + \ldots + p_i[/math]

[math] S_j = s_1 + \ldots + s_j[/math]

[math]i = 1 \ldots n[/math], [math]j = 1 \ldots m[/math], [math] p_i [/math] — время выполнения [math]i[/math]-ой работы, [math] s_j[/math] — скорость работы [math] j [/math]-oй машины.

Необходимое условие для выполнения всех работ в интервале [math][0 \ldots T][/math]:

[math] P_n = p_1 + \ldots + p_n \leqslant s_1T + \ldots + s_mT = S_mT[/math] или [math]P_n/S_m \leqslant T[/math]

Кроме того, должно выполняться условие [math]P_j/S_j \leqslant T[/math] для всех [math] j = 1 \ldots m - 1 [/math], так как это нижняя оценка времени выполнения работ [math] J_1 \ldots J_j[/math]. Исходя из этого получаем нижнюю границу [math]C_{max}[/math] :

[math]C_{max} = \max \left \{\begin{array}{ll} \dfrac{P_n}{S_m} \\ \max\limits_{j=1 \ldots m-1} \dfrac{P_j}{S_j} \end{array} \right. [/math]

Перейдем к описанию алгоритма. Будем назвать [math]\mathrm{level}[/math]-ом работы [math] p_i(t) [/math] невыполненную часть работы [math] p_i [/math] в момент времени [math] t [/math]

Далее построим расписание, которое достигает нашей оценки [math]C_{max}[/math], с помощью [math]\mathrm{level}[/math]-алгоритма.

Псевдокод

Функция [math]\mathrm{level}[/math]:

  function level():
      int [math]t = 0 [/math]
      while [math]\exists p(t) \gt  0[/math]
         assign(t)
         int [math]t_1 = \min (s \mid s \gt  t [/math] and [math]p(s) = 0)[/math]
         int [math]t_2 = \min (s \mid s \gt  t[/math] and [math]\exists i[/math], [math]j : p_i(t) \gt  p_j(t)[/math] and [math]p_i(s) = p_j(s))[/math]
         [math]t = \min(t_1[/math], [math]t_2)[/math]   // поиск следующего момента времени, в который нужно будет перераспределить машины/работы 
      Построение расписания

Функция [math]\mathrm{assign}(t)[/math]:

  function assign ([math]t[/math] : int):
     [math]J = \{i \mid p_i(t) \gt  0\}[/math]   // множество работ с положительным level 
     [math]M = \{M_1 \ldots M_m\}[/math]   // множество всех станков 
     while [math]J \ne \varnothing[/math] or [math]M \ne \varnothing[/math]
        int [math]maxLevel = \max(p_i(t) \mid i \in J)[/math]   // максимальное значение level из J 
        int [math]count = J.getCount(maxLevel)[/math]   // количество работ с level = maxLevel 
        int [math]r = \min(|M|[/math], [math]count)[/math]
        [math]I \leftarrow \{r[/math] работ из [math]J \mid p(t) = maxLevel\}[/math]
        [math]M' \leftarrow \{r[/math] самых быстрых машин из [math]M\}[/math]
        Распределяем работы
        [math]J \leftarrow J \setminus I[/math]
        [math]M \leftarrow M \setminus M'[/math]

Асимптотика

[math]\mathrm{level}[/math]-алгоритм вызывает функцию [math]\mathrm{assign}(t) [/math] в самом худшем случае [math]O(n)[/math] раз. Функция [math]\mathrm{assign}(t) [/math] выполняется за [math]O(nm)[/math]. Итоговое время работы [math]O(n^2m)[/math].

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

Теорема:

Расписание, построенное данным алгоритмом, является корректным и оптимальным.

Доказательство:

[math]\triangleright[/math]

Так как нижняя граница [math]C_{max}[/math]: [math]C_{max} = \max \left \{\begin{array}{ll} \dfrac{P_n}{S_m} \\ \max\limits_{j=1 \ldots m-1} \dfrac{P_j}{S_j} \end{array} \right. [/math] то достаточно показать, что составленное расписание достигает этой оценки. Будем считать, что в начале алгоритма все работы упорядочены, как было сказано ранее: [math] p_1(0) \geqslant p_2(0) \geqslant \ldots \geqslant p_n(0) [/math]. Это утверждение не меняется на протяжении всего выполнения алгоритма, для любого момента времени. Получаем: [math] p_1(t) \geqslant p_2(t) \geqslant \ldots \geqslant p_n(t) [/math]. Докажем что алгоритм составляет расписание в соответствии с этим свойством. Чтобы доказать этот факт, будем считать что в любой момент времени [math]T[/math] нет простоев машин, когда есть хотя бы одна невыполненная работа. Получаем: [math] T(s_1 + \ldots + s_m) = p_1 + p_2 + \ldots + p_n [/math] или [math] T = {P_n \over S_m} [/math] Таким образом необходимая оценка достигается нашим алгоритмом. Допустим хотя бы одна машина простаивает, в момент когда есть невыполненные работы, получим следующее неравенство для времен окончания работ (обозначим далее как [math] f_i [/math]) на станках [math]M_1 \ldots M_m[/math], пронумерованных по убыванию скоростей: [math] f_1 \geqslant f_2 \geqslant \ldots \geqslant f_m [/math] Докажем написанное выше неравенство: Предположим, что [math] f_i \lt f_{i+1} [/math] для некоторого [math] 1 \leqslant i \leqslant m-1 [/math]. Тогда [math]\mathrm{level}[/math] последней работы, выполнявшейся на станке [math] M_i [/math] в момент времени [math] f_i - \varepsilon [/math] (где [math] \varepsilon \gt 0[/math] достаточно мал) меньше, чем [math]\mathrm{level}[/math] последней работы на станке [math] M_{i+1} [/math]. Пришли к противоречию, так как при распределении, работы с наибольшим [math]\mathrm{level}[/math] выставлялись на самые быстрые станки. Пусть [math] T [/math] = [math] f_1 = f_2 = f_3 = \ldots = f_j \gt f_{j+1}[/math] ,где [math] j \lt m [/math]. Чтобы работы завершились в момент времени [math] T [/math], необходимо начать их в момент времени 0, поскольку если это не выполняется, то у нас найдется работа [math] J_i [/math] , которая начинается позже [math] t = 0 [/math] и заканчивается в [math] T [/math]. Это означает, что в момент времени [math] 0 [/math] начинаются как минимум [math] m [/math] работ. Пусть первые [math] m [/math] работ стартовали вместе на всех машинах. Мы получаем [math] p_1(0) \geqslant p_2(0) \geqslant \ldots \geqslant p_m(0) \geqslant p_i(0) [/math], из чего следует, что [math] p_1(T - \varepsilon) \geqslant \ldots \geqslant p_m(T - \varepsilon) \geqslant p_i(T - \varepsilon) \gt 0 [/math] для любого [math] \varepsilon [/math], удовлетворяющего условию [math] 0 \leqslant \varepsilon \lt T - t [/math]. Таким образом, до момента времени [math] T [/math] нет простаивающих машин. Пришли к противоречию. Получаем [math] T = {P_j \over S_j} [/math].

[math]\triangleleft[/math]

Пример

Картинка к примеру

Пусть у нас есть [math]6[/math] работ и [math]3[/math] станка. Покажем работу алгоритма для данного случая.

В начальный момент времени начинаем обрабатывать работы с наибольшим временем выполнения [math]J_1[/math], [math]J_2[/math] и [math]J_3[/math] на станках [math]M_1[/math], [math]M_2[/math] и [math]M_3[/math] соответственно. В момент времени [math]T_1[/math] [math]\mathrm{level}[/math] [math]1[/math]-ой работы и [math]2[/math]-ой работы совпадает. С этого момента начинаем обрабатывать работы [math]J_1[/math] и [math]J_2[/math] синхронно на станках: [math]M_1[/math] и [math]M_2[/math]. В момент времени [math]T_2[/math] работа [math]J_3[/math] опускается до уровня работы [math]J_4[/math].Работы [math]J_3[/math] и [math]J_4[/math] выполняем одновременно на одном станке [math]M_3[/math]. В момент времени [math]T_3[/math] начинаем выполнять первые четыре работы на всех станках одновременно, далее просто добавятся работы [math]J_5[/math] и [math]J_6[/math], и все работы закончатся одновременно.

См. также

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

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

• Peter Brucker. «Scheduling Algorithms» — «Springer», 2006 г. — 124 — 129 стр. — ISBN 978-3-540-69515-8