QpmtnCmax

Постановка задачи

Есть несколько станков с разной скоростью выполнения работ. Работу на каждом из станков можно прервать и продолжить позже.

Цель - выполнить все как можно быстрее.

1. Найдем нижнюю границу времени выполнения.

2. Составим оптимальное расписание.

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

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

[math] P_i = p_1 + ... + p_i[/math]

[math] S_j = s_1 + ... + s_j[/math]

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

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

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

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

[math]C_{max}[/math] = [math]\max\{\max\limits_{j=1}^{m-1} {P_j \over S_j}, {P_n \over S_m}\}[/math]

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

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

[math]Level[/math] - алгоритм:

  [math]t \leftarrow 0 [/math]
  WHILE существуют работы с положительным [math]level[/math]
      Assign(t)
      [math]t1 \leftarrow \min (s \gt  t \mid s[/math] - время окончания какой-то работы [math] ) [/math]
      [math]t2 \leftarrow \min (s \gt  t \mid [/math] для некоторых работ [math]i, j : p_i(t) \gt  p_j(t)[/math] и [math]  p_i(s) = p_j(s))[/math]
      [math] t \leftarrow \min(t1,t2) [/math] //поиск следующего момента времени ,в который нужно будет перераспределить машины/работы
  Построение расписания

Функция [math]Assign(t)[/math]:

  [math]J [/math] - множество работ с положительным [math]level[/math]
  [math]M = \{M_1,...,M_m\}[/math] - множество всех станков
  WHILE множества [math]J[/math] и [math]M[/math] не пустые
     Найти множество работ [math]I \subset J[/math], [math]level[/math] которых максимален.
     [math]r \leftarrow min[/math](|[math]M[/math]|,|[math]I[/math]|)
     Назначаем работы из множества [math]I[/math] на [math]r[/math] самых быстрых машин из множества [math]M[/math]
     [math]J \leftarrow J[/math]\[math]I[/math]
     Удаляем из множества [math]M[/math] [math]r[/math] самых быстрых машин

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

Так как нижняя граница [math]C_{max}[/math]:

[math]C_{max}[/math] = [math]\max\{\max\limits_{j=1}^{m-1} {P_j \over S_j}, {P_n \over S_m}\}[/math]

то достаточно показать, что составленное расписание достигает этой оценки.

Будем считать, что в начале алгоритма все работы упорядочены, как было сказано ранее: [math] p_1(0) \ge p_2(0) \ge ... \ge p_n(0) [/math]. Это утверждение не меняется на протяжении всего выполнения алгоритма, для любого момента времени. Получаем: [math] p_1(t) \ge p_2(t) \ge ... \ge p_n(t) [/math]. Докажем что алгоритм составляет расписание в соответствии с этим свойством. Чтобы доказать этот факт, будем считать что в любой момент времени [math]T[/math] нет простоев машин, когда есть хотя бы одна невыполненная работа. Получаем:

[math] T(s_1 + ... + s_m) = p_1 + p_2 + ... + p_n [/math] или [math] T = {P_n \over S_m} [/math]

Таким образом необходимая оценка достигается нашим алгоритмом.

Допустим хотя бы одна машина простаивает, в момент когда есть невыполненные работы, получим следующее неравенство для времен окончания работ (обозначим далее как [math] f_i [/math]) на станках [math]M_1 ... M_m[/math]:

[math] f_1 \ge f_2 \ge ... \ge f_m [/math]

Докажем написанное выше неравенство:

Предположим, что [math] f_i \lt f_{i+1} [/math] для некоторого [math] 1 \le i \le m-1 [/math]. Тогда [math]Level[/math] последней работы, выполнявшейся на станке [math] M_i [/math] в момент времени [math] f_i - \varepsilon [/math] (где [math] \varepsilon \gt 0[/math] достаточно мал) меньше, чем [math]Level[/math] последней работы на станке [math] M_{i+1} [/math]. Пришли к противоречию.

Пусть [math] T [/math] = [math] f_1 = f_2 = f_3 = ... = 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) \ge p_2(0) \ge ... \ge p_m(0) \ge p_i(0) [/math], из чего следует, что [math] p_1(T - \varepsilon) \ge ... \ge p_m(T - \varepsilon) \ge p_i(T - \varepsilon) \gt 0 [/math] для любого [math] \varepsilon [/math], удовлетворяющего условию [math] 0 \le \varepsilon \lt T - t [/math]. Таким образом, до момента времени [math] T [/math] нет простаивающих машин. Пришли к противоречию. Получаем [math] T = {P_j \over S_j} [/math].

Пример

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

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

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

Время работы

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

Литература

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