189
правок
Изменения
→Алгоритм решения
[[Файл:Figure_5.9.b.png|500px|thumb|right|Рис. 2 - Расширение сети]]
Как в [[PpmtnriLmax|задаче ]] <tex>P \mid pmtn, r_i \mid L_{max}</tex> ([[PpmtnriLmax|ссылка]]) применим метод [[Вещественный_двоичный_поиск|двоичного поиска]] и сведем задачу к <tex> Q \mid pmtn, r_i, d_i \mid - </tex>. Для существования расписания с <tex> L_{max} \le L^* </tex> требуется, чтобы у работы с номером <tex> i </tex> выполнялось <tex> C_i - d_i \le L^* </tex>, что эквивалентно <tex> C_i \le d_i + L^* </tex>. Опишем алгоритм решения <tex> Q \mid pmtn, r_i, d_i \mid - </tex> при помощи сведения к задаче поиска [[Определение_сети,_потока|максимального потока]].
Пусть <tex> t_1 \le t_2 \le ... \le t_r </tex> {{---}} упорядоченная последовательность всех значений <tex>r_i</tex> и <tex>d_i + L^*</tex>.
Определим интервалы на исходной сети (Рис. 1) <tex> I_K := [t_{K-1}, t_K], \ T_K = t_K-t_{K-−1} </tex> для <tex> K = 2,..., r </tex>. Cчитаем, что станки занумерованы в порядке невозрастания скоростей <tex> s_1 \ge s_2 \ge . . . \ge s_m </tex> (также считаем <tex>s_{m+1} = 0</tex>).
