Изменения

<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>dp\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>оптимальное.}}

<texfont color=green>// Функция принимает количество работ n, список времён выполнения работ на первом станке p1 и времён выполнения на втором станке p2.<br>maxTime \leftarrow 0 // Функция возвращает минимальное время выполнения всех работ на двух станках.</texfont> '''function''' getCmax(p1 : '''int'''[n], p2 : '''int'''[n]): '''int''' '''int''' maxTime = 0 '''for <tex>''' i = 0 .. n - 1 \dots n</tex> <tex> maxTime += p_1p1[i]</tex> <tex>dp '''int'''[][] dp fill(dp, <tex>\leftarrow INFinfty</tex>) <tex> dp[0][0] \leftarrow = 0 </tex> '''for <tex>''' i = 0 .. n - 1 \dots n</tex> '''for <tex>''' j = 0 \dots .. maxTime </tex> if <tex>(j - p_2[i] > 0) </tex> then <tex> dp[i+ 1][j] \leftarrow \= min (dp[i][j- p1[i + 1]], dp[i-1][j - p_1] + p2[i+ 1]) '''int''' answer = </tex> \infty</tex>dp[i][ '''for''' j] \leftarrow \= 0 .. maxTime answer = min (dp[i][answer, max(j], dp[i-1n][j] + p_2[i])</tex>) '''return''' answer==Время работы== Время работы <tex>answer O(n \leftarrow INFcdot maxTime)</tex>{{---}} псевдополиномиальный алгоритм. Кроме того, если время выполнения работ, будет вещественные числа, то придется приводить их до целых, либо считать приблежённое значения. ==См. также== for * [[F2Cmax|<tex> j = 0 F2\mid\dots maxTime mid C_{max}</tex>]] * [[O2Cmax|<tex>answer \leftarrow O2\min (answer, mid\mid C_{max(j, dp[n][j]))}</tex>]]

==Время работыПримечания==Время работы <texreferences/>O(n  ==Источники информации==* maxTime)</tex> {{---}} псевдополиномиальный алгоритмJ.K. Кроме тогоLenstra, если время выполнения работA.H.G. Rinnooy Kan, будет вещественные числаand P. Brucker. Complexity of machine scheduling problems. Annals of Discrete Mathematics, то придется приводить их до целыхстр. 358–360, либо считать приблежённое значения1977.

==Литература==J.K. Lenstra, A.H.G. Rinnooy Kan, and P. Brucker. Complexityof machine scheduling problems. Annals of Discrete Mathematics,[[Категория: Алгоритмы и структуры данных]]1[[Категория:343–362, 1977.Теория расписаний]]