Изменения
Нет описания правки
<includeonly>[[Категория: В разработке]]</includeonly>
<tex dpi=200>R2 \mid\mid C_{max} </tex> {{Задача|definition=Постановка задачи==Дано два разных неоднородных станка, которые работают параллельно. Есть <tex>n</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[0][0] = 0</tex>, а всё остальную таблицу проинициализируем бесконечностью.
Допустим мы посчитали динамику для <tex>i-1</tex> работ. Теперь надо пересчитать её для <tex>(i+ 1)</tex>-ой работы. Переберём время выполнения работ на первом станке и посчитаем какое минимально время выполнения мы можем получить при на втором станке при фиксированном первом времени. Так как <tex>(i+ 1)</tex>-ю работу мы можем выполнить либо на первом станке, либо на втором, то <tex>dp[i+ 1][j+ p_1[i + 1]= \min(]</tex> надо прорелаксировать значением <tex>dp[i-1][j-p_1] </tex>, что соответсвует выполнению работы на первом станке. А <tex>dp[i+ 1][j], </tex> релаксируем значением <tex> dp[i-1][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 \leftarrow = 0 </tex> '''for ''' <tex>i = 1 0 \dots n- 1</tex>
<tex>maxTime += p_1[i]</tex>
<tex>dp[][] \leftarrow = INF</tex> <tex>dp[0][0] \leftarrow = 0 </tex> '''for ''' <tex>i = 1 0 \dots n- 1 </tex> '''for ''' <tex>j = 0 \dots maxTime </tex> '''if ''' <tex>(dp[i + 1][j - p_2+ p_{1}[i]] > 0dp[i][j]) </tex> '''then''' <tex>dp[i+ 1][j] \leftarrow \min (dp+ p_{1}[i][j], = dp[i-1][j - p_1[i]) </tex> '''if''' <tex>(dp[i+ 1][j] \leftarrow \min (> dp[i][j], + p_{2}[i]) </tex> '''then''' <tex> dp[i-+ 1][j] = dp[i][j] + p_2p_{2}[i])</tex> <tex>answer \leftarrow = INF</tex>
for <tex> j = 0 \dots maxTime </tex>
<tex>answer \leftarrow = \min (answer, \max(j, dp[n][j]))</tex>
==Время работы==
of machine scheduling problems. Annals of Discrete Mathematics,
1:343–362, 1977.
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Теория расписаний]]
