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]maxTime[/math].

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

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

Таким образом:

[math]dp[i + 1][j] = \min(dp[i][j] + p_2[i + 1], dp[i][j - p_1[i + 1]])[/math]

Тогда ответом на задачу будет [math]\min\limits_{j}(\max(j, dp[n][j]))[/math]. Другими словами мы перебираем время работы на первом станке и смотрим сколько ещё потребуется работать на втором станке. Время выполнения всех работ — это максимум из этих двух величин. И в конце из всех времен выбираем минимальное.

Также можно заметить, что во время каждой итерации алгоритма используется только два столбца массива [math] dp [/math]. Это позволяет уменьшить использование памяти с [math]O(n \cdot maxTime)[/math] до [math] O(maxTime)[/math].

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

Теорема:

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

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

[math]\triangleright[/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]\triangleleft[/math]

Псевдокод

// Функция принимает количество работ n, список времён выполнения работ на первом станке p1 и времён выполнения на втором станке p2.
// Функция возвращает минимальное время выполнения всех работ на двух станках.
function getCmax(p1 : int[n], p2 : int[n]): int
   int maxTime = 0
   for i = 0 .. n - 1
      maxTime += p1[i]
   int[][] dp
   fill(dp, [math]\infty[/math])
   dp[0][0] = 0
   for i = 0 .. n - 1
      for j = 0 .. maxTime
         dp[i + 1][j] = min(dp[i][j - p1[i + 1]], dp[i][j] + p2[i + 1])
   int answer = [math]\infty[/math]
   for j = 0 .. maxTime
      answer = min(answer, max(j, dp[n][j]))
   return answer

Время работы

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

См. также

• [math]F2\mid\mid C_{max}[/math]
• [math]O2\mid\mid C_{max}[/math]

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

• J.K. Lenstra, A.H.G. Rinnooy Kan, and P. Brucker. Complexity of machine scheduling problems. Annals of Discrete Mathematics, стр. 358–360, 1977.