Изменения

==Сложность задачи==Задача <tex>R2 \mid \mid C_{max}</tex> является <tex>\mathrm{NP}</tex>-полной задачей. Доказательство смотри в книге, указанной в источниках информации.

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

Применим для решения данной задачи [[Динамическое программирование|динамическое программирование]].

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

Так же можно заметить, что во время каждой итерации алгоритма используется только два столбца массива <tex> dp </tex>. Это позволяет уменьшить использование памяти до <tex dpi=130> O(\sum\limits_{p_i = 1}^{1n}p_1[i]})</tex>. ==Доказательство корректности алгоритма== {{Теорема|statement=Расписание, построенное данным алгоритмом, является корректным и оптимальным.|proof=Корректность расписания, составленного алгоритмом очевидна. Надо доказать его оптимальность.

<font color=green>//Функция принимает количество работ n, список времён выполнения работ на первом станке p1 и времён выполнения на втором станке p2.<texbr>maxTime = 0 //Функция возвращает минимальное время выполнения всех работ на двух станках.</texfont> '''function''' getCmax(n, p1, p2) maxTime = 0 '''for''' <tex>i = 0 \dots .. n - 1</tex> <tex> maxTime += p_1p1[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}p1[i]] > dp[i][j]) </tex> '''then''': <tex> dp[i + 1][j + p_{1}p1[i]] = dp[i][j] </tex> '''if''' <tex>(dp[i + 1][j] > dp[i][j] + p_{2}p2[i]) </tex> '''then''': <tex> dp[i + 1][j] = dp[i][j] + p_{2}p2[i] </tex> <tex> answer = INF</tex> for <tex> j = 0 \dots .. maxTime </tex> <tex> answer = \'''min '''(answer, \'''max'''(j, dp[n][j]))</tex> '''return''' answer

==ЛитератураИсточники информации==* J.K. Lenstra, A.H.G. Rinnooy Kan, and P. Brucker. Complexityof machine scheduling problems. Annals of Discrete Mathematics,1:343–362, 1977. ==См. также==* [[F2Cmax|<tex>F2\mid\mid C_{max}</tex>]]* [[O2Cmax|<tex>O2\mid\mid C_{max}</tex>]]