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]dp[i + 1][j] = \min \begin{cases} dp[i][j] + p_2[i + 1]\\ dp[i][j - p_1[i + 1]]\\ \end{cases} [/math]

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

Так же можно заметить, что во время каждой итерации алгоритма используется только два столбца массива [math] dp [/math]. Это позволяет уменьшить использование памяти до [math] O(\sum\limits_{i = 1}^{n} p_1[i])[/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(n, p1, p2)
     maxTime = 0
     for i = 0 .. n - 1
        maxTime += p1[i]
     dp[][] = INF
     dp[0][0] = 0
     for i = 0 .. n - 1
        for j = 0 .. maxTime
           if dp[i + 1][j + p1[i]] > dp[i][j]:
              dp[i + 1][j + p1[i]] = dp[i][j]
           if dp[i + 1][j] > dp[i][j] + p2[i]:
              dp[i + 1][j] = dp[i][j] + p2[i]
     answer = INF
     for j = 0 .. maxTime
        answer = min(answer, max(j, dp[n][j]))
     return answer

Время работы

Время работы [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.

См. также

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