R2Cmax

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

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

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

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

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

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

Переберём все битовые последовательности из [math]n[/math] элементов. Для каждой перестановки вычислим завершение последней работы. Работы будем выполнять следующим образом, если на [math]i[/math] -й позиции стоит 0, то [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-1[/math] работ. Теперь надо пересчитать её для [math]i[/math]-ой работы. Переберём время выполнения работ на первом станке и посчитаем какое минимально время выполнения мы можем получить при на втором станке при фиксированном первом времени. Так как [math]i[/math]-ю работу мы можем выполнить либо на первом станке, либо на втором, то [math]dp[i][j]= \min(dp[i-1][j-p_1[i]], dp[i-1][j]+p_2[i])[/math].

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

Псевдокод

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

Время работы

Время работы [math]O(n * 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.