1632
правки
Изменения
м
<div style="background-color: #ABCDEF; font-size: 16px; font-weight: bold; color: #000000; text-align: center; padding: 4px; border-style: solid; border-width: 1px;">Эта статья находится в разработке!</div>
<includeonly>[[Категория: В разработке]]</includeonly>
==Сложность задачи==Задача <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>j</tex> и <tex>dp[n][j]</tex>.==Доказательство корректности алгоритма==
Так же можно заметить{{Теорема|statement=Расписание, построенное данным алгоритмом, что во время каждой итерации алгоритма используется только два столбца массива <tex> dp </tex>является корректным и оптимальным. Это позволяет уменьшить использование памяти до <tex dpi|proof=130> \sum{p_{1}[i]}</tex>Корректность расписания, составленного алгоритмом очевидна. Надо доказать его оптимальность.
==Корректность==Пусть расписание, составленное этим алгоритмом <tex>S</tex> не оптимальное. Пусть и в конце работы алгоритма минимум достигается в <tex>\max(time, d[n][time])</tex>. Рассмотрим оптимальное решение <tex>O</tex>.
<texfont color=green>// Функция принимает количество работ n, список времён выполнения работ на первом станке p1 и времён выполнения на втором станке p2.<br>// Функция возвращает минимальное время выполнения всех работ на двух станках.</font> '''function''' getCmax(p1 : '''int'''[n], p2 : '''int'''[n]): '''int''' '''int''' maxTime = 0 </tex> '''for''' <tex>i = 0 \dots .. n - 1</tex> <tex> maxTime += p_1p1[i]</tex> <tex>dp '''int'''[][] = INFdp fill(dp, </tex> \infty</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}[i]] > = min(dp[i][j]) </tex> '''then''' <tex> dp- p1[i + 1][j + p_{1}[i]] = , dp[i][j] </tex> '''if''' <tex>(dp+ p2[i + 1][j] > dp[i][j] + p_{2}[i]) </tex> '''thenint''' <tex> dp[i + 1][j] answer = dp[i][j] + p_{2}[i] </tex> <tex>answer = INF\infty</tex> '''for <tex> ''' j = 0 \dots .. maxTime </tex> <tex> answer = \min (answer, \max(j, dp[n][j]))</tex> '''return''' answer
rollbackEdits.php mass rollback
<tex dpi=200>R2 \mid\mid C_{max} </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[i][j]</tex>, в котором будем хранить минимально время выполнения работ на втором станке, где <tex>i</tex> означает, что мы рассмотрели <tex>i</tex> работ, а <tex>j</tex> {{---}} с каким временем выполнения работ на первом станке. Тогда <tex>j</tex> не превосходит суммы выполнения работ на первом станке. Назовем эту сумму <tex>maxTime</tex>.
Изначальное значение <tex>dp[0][0] = 0</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]+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>.
Рассмотрим произвольную работу, выполненную на первом станке в оптимальном расписании, но на втором в расписании, составленном алгоритмом. Пусть у этой работы номер <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>S</tex> в решение <tex>S'</tex> эквивалентное <tex>O</tex>, то ответ <tex>S</tex> не будет превосходить ответ <tex>S'</tex>. Тогда расписание <tex>S</tex> оптимальное.
}}
==Псевдокод==
==Время работы==
Время работы <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. Complexityof machine scheduling problems. Annals of Discrete Mathematics,1:343–362стр. 358–360, 1977.
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Теория расписаний]]
