40
правок
Изменения
м
Расширим эту Искомая сетьстроится с помощью расширения сети из задачи <tex>P \mid pmtn, r_i \mid L_{max}</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>.
Cчитаем, что станки занумерованы в порядке невозрастания скоростей <tex> s_1 \ge s_2 \ge . . . \ge s_m </tex> (считаем <tex>s_{m+1} = 0</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>).
Расширение сети показано на Рис. 2.
Расширенная подсеть строится путем добавления к вершинам <tex> I_K, J_{i_1}, J_{i_2}, . . . , J_{i_s} </tex> вершин <tex>(K, 1), (K, 2), . . . (K, m) </tex>. При <tex>j = 1,..., m </tex>, есть дуги от <tex>(K, j)</tex> до <tex>I_K</tex> с пропускной способностью <tex> j(s_j - s_{j+1}) T_K </tex> и для всех <tex>\nu = 1,. . . , s</tex> и <tex>j = 1,. . ., m</tex> существует дуга из <tex>J_{i_\nu}</tex> в <tex>(K, J)</tex> с пропускной способностью <tex> (s_j - s_{j+1}) T_K </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> (Рис. 1).
