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].