Изменения

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

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

==Сложность задачи==Задача <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>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>maxTime</tex>.

Допустим мы посчитали динамику для <tex>i-1</tex> работ. Теперь надо пересчитать её для <tex>(i+ 1)</tex>-ой работы. Переберём время выполнения работ на первом станке и посчитаем какое минимально время выполнения мы можем получить при на втором станке при фиксированном времени на первом времени. Так как <tex>(i+ 1)</tex>-ю работу мы можем выполнить либо на первом станке, либо на втором, то <tex>dp[i+ 1][j]= \min(</tex> надо прорелаксировать значением <tex>dp[i-1][j-p_1[i+ 1]]</tex>, что соответсвует выполнению работы на первом станке, и значением <tex> dp[i-1][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> O(maxTime)</tex>. ==Доказательство корректности алгоритма== {{Теорема|statement=Расписание, построенное данным алгоритмом, является корректным и оптимальным.|proof=Корректность расписания, составленного алгоритмом очевидна. Надо доказать его оптимальность. Пусть расписание, составленное этим алгоритмом <tex>S</tex> не оптимальное и в конце работы алгоритма минимум среди достигается в <tex>\max(time, d[n][time])</tex>. Рассмотрим оптимальное решение <tex>O</tex>.  Рассмотрим произвольную работу, выполненную на первом станке в оптимальном расписании, но на втором в расписании, составленном алгоритмом. Пусть у этой работы номер <tex>i</tex>. Если её выполнить на первом станке, то время окончания всех максимумов из работ будет <tex>\max(time + p_{1}[i], d[n][time + p_{1}[i]])</tex>. Однако <tex>\max(time, d[n][time]) \leqslant \max(time + p_{1}[i], d[n][time + p_{1}[i]])</tex> Рассмотрим произвольную работу, выполненную в оптимальном расписании на втором станке, но на первом в расписании, составленном алгоритмом. Пусть номер этой работы <tex>j</tex>. Если выполнять эту работу на втором станке, то время выполнения всех работ будет <tex>\max(time - p_{1}[j], d[n][time - p_{1}[j]])</tex>. Но <tex>\max(time, d[n][time]) \leqslant \max(time - p_{1}[j], d[n][time - p_{1}[j]]) </tex>. В итоге если превратить решение <tex>S</tex> в решение <tex>S'</tex> эквивалентное <tex>O</tex>, то ответ <tex>S</tex> не будет превосходить ответ <tex>S'</tex>. Тогда расписание <tex>S</tex> оптимальное. }} ==Псевдокод== <font color=green>// Функция принимает количество работ n, список времён выполнения работ на первом станке p1 и времён выполнения на втором станке p2.<br>// Функция возвращает минимальное время выполнения всех работ на двух станках.</font> '''function''' getCmax(p1 : '''int'''[n], p2 : '''int'''[n]): '''int''' '''int''' maxTime = 0 '''for''' i = 0 .. n - 1 maxTime += p1[i] '''int'''[][] dp fill(dp, <tex>\infty</tex>) dp[0][0] = 0 '''for''' i = 0 .. n- 1 '''for''' j = 0 .. maxTime dp[i + 1][j] = min(dp[i][j - p1[i + 1]], dp[i][j]+ p2[i + 1]) '''int''' answer = <tex>\infty</tex> '''for''' j = 0 ..maxTime answer = min(answer, max(j, dp[n][j])) '''return''' answer==Время работы==Время работы <tex>O(n \cdot maxTime)</tex> {{---}} псевдополиномиальный алгоритм. Кроме того, если время выполнения работ, будет вещественные числа, то придется приводить их до целых, либо считать приблежённое значения. ==См. также==* [[F2Cmax|<tex>F2\mid\mid C_{max}</tex>]]* [[O2Cmax|<tex>O2\mid\mid C_{max}</tex>]] ==Примечания==<references/> ==Источники информации==* J.K. Lenstra, A.H.G. Rinnooy Kan, and P. Brucker. Complexity of machine scheduling problems. Annals of Discrete Mathematics, стр. 358–360, 1977. [[Категория: Алгоритмы и структуры данных]][[Категория: Теория расписаний]]