152
правки
Изменения
Новая страница: «<div style="background-color: #ABCDEF; font-size: 16px; font-weight: bold; color: #000000; text-align: center; padding: 4px; border-style: solid; border-width: 1p...»
<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>
==Эффективное решение==
Используем для решения данной задачи динамическое программирование.
<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>
==Эффективное решение==
Используем для решения данной задачи динамическое программирование.
