Изменения

Перейти к: навигация, поиск

PpmtnriLmax

76 байт добавлено, 18:34, 13 июня 2015
Нет описания правки
<tex dpi ==Постановка задачи=="200">P \mid pmtn, r_i \mid L_{max}</tex>
# {{Задача|definition = <ol><li>Имеется <tex>M</tex> однородных машин, работающих параллельно.</li># <li>Есть <tex>N</tex> работ, каждое имеет своё время появления <tex>r_i</tex> и время окончания <tex>d_i</tex>.</li># <li>Работа может быть прервана и продолжена позже.</li></ol>
Необходимо составить такое расписание, чтобы значение <tex>L_{max} = max_{i=1}^n (C_i - d_i)</tex> было минимальным.}}
== Решение ==
Т.к. сеть содержит <tex>O(N)</tex> элементов, значит максимальный поток в ней можно найти за <tex>O(n^3)</tex>. Кроме того, построение "окон" выполнения работ займет <tex>O(N^2)</tex>. Т.о. указанный выше алгоритм потребует <tex>O(N^3)</tex> операций.
Для решения данной задачи мы используем бинпоиск по <tex>L</tex> значениям, а значит, получаем алгоритм с <tex>\varepsilon</tex>-приближенной сложностью <tex>O (n^3(log(n) + log(1 / \varepsilon) + log(\max\limits_{j=1}^{..n} p_j)) </tex>, потому как <tex>L_{max}</tex>, ограничен <tex>n \max\limits_{j=1}^{..n}p_j</tex>
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Теория расписаний]]
Анонимный участник

Навигация