R2Cmax

2016-05-22T01:03:16Z

5.18.60.212:

<div style="background-color: #ABCDEF; font-size: 16px; font-weight: bold; color: #000000; text-align: center; padding: 4px; border-style: solid; border-width: 1px;">Эта статья находится в разработке!</div>
<includeonly>[[Категория: В разработке]]</includeonly>

<tex dpi=200>R2 \mid\mid C_{max} </tex>

{{Задача
|definition=Дано два разных неоднородных станка, которые работают параллельно. Есть <tex>n</tex> работ, время выполнения которых на первом
и втором станке различное. Нужно минимизировать время завершения всех работ.}}

==Сложность задачи==
Задача <tex>R2 \mid \mid C_{max}</tex> является <tex>\mathrm{NP}</tex>-полной задачей.

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

Время работы алгоритма <tex>O(n \cdot 2^n)</tex>

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

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

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

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

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

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

==Псевдокод==
<tex>maxTime = 0 </tex>
'''for''' <tex>i = 0 \dots n - 1</tex>
<tex>maxTime += p_1[i]</tex>
<tex>dp[][] = INF</tex>
<tex>dp[0][0] = 0 </tex>
'''for''' <tex>i = 0 \dots n - 1 </tex>
'''for''' <tex>j = 0 \dots maxTime </tex>
'''if''' <tex> (dp[i + 1][j + p_{1}[i]] > dp[i][j]) </tex> '''then'''
<tex> dp[i + 1][j + p_{1}[i]] = dp[i][j] </tex>
'''if''' <tex>(dp[i + 1][j] > dp[i][j] + p_{2}[i]) </tex> '''then'''
<tex> dp[i + 1][j] = dp[i][j] + p_{2}[i] </tex>
<tex>answer = INF</tex>
for <tex> j = 0 \dots maxTime </tex>
<tex>answer = \min (answer, \max(j, dp[n][j]))</tex>

==Время работы==
Время работы <tex>O(n \cdot maxTime)</tex> {{---}} псевдополиномиальный алгоритм. Кроме того, если время выполнения работ, будет вещественные числа, то придется приводить их до целых, либо считать приблежённое значения.

==Литература==
J.K. Lenstra, A.H.G. Rinnooy Kan, and P. Brucker. Complexity
of machine scheduling problems. Annals of Discrete Mathematics,
1:343–362, 1977.

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Теория расписаний]]

Викиконспекты - Вклад участника [ru]

R2Cmax