Изменения

Задача <tex>R2 \mid \mid C_{max}</tex> является [[Классы_NP_и_Σ₁#def1|<tex>\mathrm{NP}</tex>-полной задачей]]<ref> J.K. Lenstra, A.H.G. Rinnooy Kan, and P. Brucker. Complexity of machine scheduling problems. Доказательство смотри в книгеAnnals of Discrete Mathematics, 1:343–362, указанной в источниках информации1977.</ref>.

Будем считать массив <tex>dp[i][j]</tex>, в котором будем хранить минимально время выполнения работ на втором станке, где <tex>i</tex> означает, что мы рассмотрели <tex>i</tex> работ, а <tex>j</tex> {{---}} с каким временем выполнения работ на первом станке. Тогда <tex>j</tex> не превосходит суммы выполнения работ на первом станке. Назовем эту сумму <tex>maxTime</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- p_1[i + 1]] </tex>, что соответсвует выполнению работы на первом станке. А <tex>dp[i + 1][j] </tex> релаксируем , и значением <tex> dp[i][j]+p_2[i + 1]</tex> (выполнение на втором станке).

Так же <tex>dp[i + 1][j] = \min(dp[i][j] + p_2[i + 1], dp[i][j - p_1[i + 1]])</tex> Тогда ответом на задачу будет <tex>\min\limits_{j}(\max(j, dp[n][j]))</tex>. Другими словами мы перебираем время работы на первом станке и смотрим сколько ещё потребуется работать на втором станке. Время выполнения всех работ {{---}} это максимум из этих двух величин. И в конце из всех времен выбираем минимальное. Также можно заметить, что во время каждой итерации алгоритма используется только два столбца массива <tex> dp </tex>. Это позволяет уменьшить использование памяти с <tex>O(n \cdot maxTime)</tex> до <tex dpi=130> O(\sum\limits_{i = 1}^{n} p_1[i]maxTime)</tex>.

Пусть расписание, составленное этим алгоритмом <tex>S</tex> не оптимальное. Пусть и в конце работы алгоритма минимум достигается в <tex>\max(time, d[n][time])</tex>. Рассмотрим оптимальное решение <tex>O</tex>.

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