Изменения
Нет описания правки
==Алгоритм решения==
[[Файл:Figure_5.2.png|400px|thumb|right|Рисунок Рис. 1]]
Применим бинарный поиск для общего решения задачи. Сведем задачу к поиску потока сети.
Также определим <tex> I_K := [t_{K-1}, t_K],\ T_K = t_K-t_{K-−1} </tex> для <tex> K = 2,..., r </tex>.
Далее мы расширяем сеть, показанную на рисунке 1 {{TODO | t = ДОБАВИТЬ_Рисунок 5.9: Расширение сети.}} следующим образом:
<tex>I_K</tex> - произвольный интервал узел на рисунке, обозначим через <tex> J_{i_1}, J_{i_2}, . . . , J_{i_s} </tex> набор предшественников узла <tex>I_K</tex>.
Тогда замененная нами подсеть определяется как <tex> I_K, J_{i_1}, J_{i_2}, . . . , J_{i_s} </tex>, которая показана на рисунке 5.9 (а), расширение сети показано на рисунке 5.9 (б).{{TODO | t = ДОБАВИТЬ_Рисунок 5.9: Расширение сети.}}
Cчитаем, что машины индексируются в порядке невозрастания скоростей <tex> s_1 \ge s_2 \ge . . . \ge s_m </tex>, кроме того <tex>s_{m+1} = 0</tex>.
Для каждого <tex>I_K</tex> у нас есть такие расширения. Кроме того, мы сохраняем дуги от <tex>s</tex> до <tex>J_i</tex> и мощностью <tex>p_i</tex> дуг из <tex>I_K</tex> в <tex>t</tex> мощностью <tex>S_mT_K</tex> (см. рисунок 5.2). Сеть построена таким образом, называется расширенной сетью.
{{TODOТеорема| t statement= Теоремы 5.9}} Следующие свойства эквивалентны:
(А) Существует допустимое расписание.
(Б) В расширенной сети существует поток от s до t со значением <tex>\sum\limits_{i=1}^{n} p_i</tex>
}}==Время работы==[[Файл:Figure_5.9.a.png|400px|thumb|right|Рис. 2.1]][[Файл:Figure_5.9.b.png|400px|thumb|right|Рис. 2.2]]
Из-за максимального потока в расширенной сети могут быть рассчитаны в <tex>O (m n^3)</tex> шагов, возможность проверки может быть сделано с такой же сложности.
Для решения задачи <tex>Q|pmtn; r_{i}|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>. //===================================================================================================================
Потому что (5.10) справедливо для всех К частичной работы с требования к обработке Xik могут быть запланированы в ИК с уровнем алгоритма.
