R2Cmax

Эта статья находится в разработке!

[math]R2 \mid\mid C_{max} [/math]

Задача:

Дано два разных неоднородных станка, которые работают параллельно. Есть [math]n[/math] работ, время выполнения которых на первом и втором станке различное. Нужно минимизировать время завершения всех работ.

Сложность задачи

Задача [math]R2 \mid \mid C_{max}[/math] является [math]\mathrm{NP}[/math]-полной задачей.

Неэффективное решение

Переберём все битовые последовательности из [math]n[/math] элементов. Для каждой перестановки вычислим завершение последней работы. Работы будем выполнять следующим образом, если на [math]i[/math] -й позиции стоит [math]0[/math], то [math]i[/math] -ая работа будет выполняться на первом станке, иначе на втором. Среди всех перестановок выберем ту перестановку, у которой [math]C_{max}[/math] минимальный.

Время работы алгоритма [math]O(n \cdot 2^n)[/math]

Эффективное решение

Применим для решения данной задачи динамическое программирование.

Будем считать [math]dp[i][j][/math], в котором будем хранить минимально время выполнения работ на втором станке, где [math]i[/math] означает, что мы рассмотрели [math]i[/math] работ, а [math]j[/math] с каким временем выполнения работ на первом станке. Тогда [math]j[/math] не превосходит суммы выполнения работ на первом станке.

Изначальное значение [math]dp[0][0] = 0[/math], а всё остальную таблицу проинициализируем бесконечностью.

Допустим мы посчитали динамику для [math]i[/math] работ. Теперь надо пересчитать её для [math](i + 1)[/math]-ой работы. Переберём время выполнения работ на первом станке и посчитаем какое минимально время выполнения мы можем получить при на втором станке при фиксированном первом времени. Так как [math](i + 1)[/math]-ю работу мы можем выполнить либо на первом станке, либо на втором, то [math] dp[i + 1][j + p_1[i + 1]][/math] надо прорелаксировать значением [math]dp[i][j] [/math], что соответсвует выполнению работы на первом станке. А [math]dp[i + 1][j] [/math] релаксируем значением [math] dp[i][j]+p_2[i + 1][/math] (выполнение на втором станке).

Тогда ответом на задачу будет минимум среди всех максимумов из [math]j[/math] и [math]dp[n][j][/math].

Так же можно заметить, что во время каждой итерации алгоритма используется только два столбца массива [math] dp [/math]. Это позволяет уменьшить использование памяти до [math] \sum{p_{1}[i]}[/math].

Корректность

Пусть расписание, составленное этим алгоритмом [math]S[/math] не оптимальное. Пусть в конце работы алгоритма минимум достигается в [math]\max(time, d[n][time])[/math]. Рассмотрим оптимальное решение [math]O[/math].

Рассмотрим произвольную работу, выполненную на первом станке в оптимальном расписании, но на втором в расписании, составленном алгоритмом. Пусть у этой работы номер [math]i[/math]. Если её выполнить на первом станке, то время окончания всех работ будет [math]\max(time + p_{1}[i], d[n][time + p_{1}[i]])[/math]. Однако [math]\max(time, d[n][time]) \leqslant \max(time + p_{1}[i], d[n][time + p_{1}[i]])[/math]

Рассмотрим произвольную работу, выполненную в оптимальном расписании на втором станке, но на первом в расписании, составленном алгоритмом. Пусть номер этой работы [math]j[/math]. Если выполнять эту работу на втором станке, то время выполнения всех работ будет [math]\max(time - p_{1}[j], d[n][time - p_{1}[j]])[/math]. Но [math] \max(time, d[n][time]) \leqslant \max(time - p_{1}[j], d[n][time - p_{1}[j]]) [/math].

В итоге если превратить решение [math]S[/math] в решение [math]S'[/math] эквивалентное [math]O[/math], то ответ [math]S[/math] не будет превосходить ответ [math]S'[/math]. Тогда расписание [math]S[/math] оптимальное.

Псевдокод

  [math]maxTime = 0 [/math]
  for [math]i = 0 \dots n - 1[/math]
     [math]maxTime += p_1[i][/math]
  [math]dp[][] = INF[/math]
  [math]dp[0][0] = 0 [/math]
  for [math]i = 0 \dots n - 1 [/math]
     for [math]j = 0 \dots maxTime [/math]
        if [math] (dp[i + 1][j + p_{1}[i]] \gt  dp[i][j]) [/math] then
           [math] dp[i + 1][j + p_{1}[i]] = dp[i][j] [/math]
        if [math](dp[i + 1][j] \gt  dp[i][j] + p_{2}[i]) [/math] then
           [math] dp[i + 1][j] = dp[i][j] + p_{2}[i] [/math]
  [math]answer = INF[/math]
  for [math] j = 0 \dots maxTime [/math]
     [math]answer = \min (answer, \max(j, dp[n][j]))[/math]

Время работы

Время работы [math]O(n \cdot maxTime)[/math] — псевдополиномиальный алгоритм. Кроме того, если время выполнения работ, будет вещественные числа, то придется приводить их до целых, либо считать приблежённое значения.

Литература

J.K. Lenstra, A.H.G. Rinnooy Kan, and P. Brucker. Complexity of machine scheduling problems. Annals of Discrete Mathematics, 1:343–362, 1977.