R2Cmax

2012-06-16T22:33:40Z

83.149.2.238: /* Эффективное решение */

<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>n</tex> работ, время выполнения которых на первом
и втором станке различное. Нужно минимизировать время завершения всех работ.

==Сложность задачи==
Задача <tex>R2 \mid \mid C_{max}</tex> является <tex>\mathrm{NP}</tex>-полной задачей.

==Неэффективное решение==
Переберём все битовые последовательности из <tex>n</tex> элементов. Для каждой перестановки вычислим завершение последней работы. Работы будем выполнять следующим образом, если на <tex>i</tex> -й позиции стоит 0, то <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>dp[0][0] = 0</tex>.

Викиконспекты - Вклад участника [ru]

R2Cmax