251
правка
Изменения
Нет описания правки
<includeonlytex dpi = "200">[[Категория: В разработке]]Q \mid pmtn, r_i \mid L_{max}</includeonlytex>{{Задача ==Постановка задачи=|definition=[[Файл:Figure_5.2.png|400px|thumb|right|Рис. 1 - Исходная сеть]] Рассмотрим задачу на нахождение расписания:
# У нас есть несколько станков, работающих параллельно. У станков могут быть разные скорости выполнения работ.
# Есть несколько заданий, каждое имеет своё время появления <tex>r_i</tex> и время окончания <tex>d_i</tex>.
# Работа может быть прервана в любой момент и продолжена позже на любой машине.
Требуется минимизировать максимальное опоздание <tex>L_{max} = \max\limits_i \{C_i - d_i\}</tex>
}}
[[Файл:Figure_5.9.b.png|500px|thumb|right|Рис. 2 - Расширение сети]]
}}
===Время работы===
Работа с максимальным потоком в расширенной сети занимает <tex>O (m n^3)</tex> шагов, проверка может быть сделана с такой же скоростью. Для решения <tex>Q \mid pmtn; r_{i} \mid L_{max}</tex> мы используем бинарный поиск, а значит, получаем алгоритм с <tex>\varepsilon</tex>-приближенной сложностью <tex>O (mn^3(\log(n) + \log(1 / \varepsilon) + \log(\max\limits_{i=1}^{n} p_i)) </tex>, потому как <tex>L_{max}</tex>, ограничен <tex>n \max\limits_{i=1}^{n}p_i</tex>, при <tex>s_1 = 1</tex>.
