Изменения

(Б) В расширенной сети существует поток от s до t со значением <tex>\sum\limits_{i=1}^n p_i</tex> |proof=(b) -> (a):Consider a flow with value <tex>sum_{i = 1}^n {p_i}</tex> in the expanded network. Denote by x_{iK} the total flow which goes from J_i to I_K. Then <tex>sum_{i = 1}^n sum_{K = 2}^r X_{iK} = sum_{i = 1}^n p_i</tex>. It is sufficient to show that for each subset <tex>A ⊆ {1, . . . , n}</tex> we have <tex>sum_{i∈A} x_{iK} \le T_Kh(A)</tex>. This means that condition (5.8) holds and the processing requirements <tex>x_{1K}, . . . , x_{nK}</tex> can be scheduled in <tex>I_K</tex> for <tex>K = 2, . . . , r</tex>. Consider in the expanded network the subnetwork induced by A and thecorresponding partial flow. The portion of this partial flow which goes through <tex>(K, j)</tex> is bounded by <tex>min{j(s_j − s_{j + 1})T_K, |A|(s_j − s_{j+1})TK_} = T_K(s_j − s_{j+1}) \dot min{j, |A|}</tex>. Thus, we have <tex>sum_{i∈A} x_{iK} \ge T_K sum_{j = 1}^m(s_j − s_{j+1}) min{j, |A|} = T_Kh(A)</tex>. (5.9)� That the equality in (5.9) holds can be seen as follows. If <tex>|A| \go > m</tex>, we have <tex>sum_{j = 1}^m min{j, |A|}(s_j - s_{j + 1}) = s_1 - s_2 + 2s_2 - 2s_3 + 3s_3 - 3s_4 + ... + ms_s - ms_{m+1} = S_m = h(A)</tex>. Otherwise <tex>sum_{j = 1} min{j, |A|} (s_j - s_{j + 1}) = s_1 - s_2 + 2s_2 - 2s_3 + 3s_3 - ... + (|A| - 1)s_{|A| - 1} - (|A| - 1)s_{|A|} + |A|(s_{|A|} - s_{|A| - 1} - ... - s_m + s_m - s_{m + 1}) = S_{|A|} = h(A)</tex>. (a) -> (b): Assume that a feasible schedule exists. For <tex>i = 1, ... , n </tex> and <tex>K = 2, ..., r</tex> let <tex>x_{iK}</tex> be the “amount of work” to be performed on job <tex>i</tex> in the interval <tex>I_K</tex> according to this feasible schedule. Then for all <tex>K = 2, ..., r</tex> and arbitrary sets <tex>A ⊆ {1, . . . , n} </tex>, the inequality <tex>sum_{i∈A} x_{iK} \le T_Kh(A)</tex> (5.10) holds. Furthermore, for <tex>i = 1, . . . , n</tex> we have <tex>p_i= sum_{K = 2}^r s_{iK}</tex>. It remainsto show that it is possible to send <tex>x_{iK}</tex> units of flow from <tex>J_i</tex> to <tex>I_K</tex> <tex>(i = 1, . . . , n; K = 2, . . . , r)</tex> in the expanded network. A sufficient condition for the existence of such a flow is that for arbitrary <tex>A ⊆ {1, . . . , n}</tex> and <tex>K = 2, . . . , r</tex> the value <tex>sum_{i∈A} x_{iK}</tex> is bounded by the value of a minimum cut in the partial network with sources <tex>J_i(i ∈ A)</tex> and sink <tex>I_K<tex>. However, this value is <tex>T_K sum_{j = 1}^m min {j, |A|}(s_j - s_{j+1})</tex> Using (5.10) and the right-hand side of (5.9), we get <tex>sum_{i∈A} x_{iK} \le T_Kh(A) = T_K sum_{j = 1}^m min{j, |A|}(s_j - s_{j+1})</tex> which is the desired inequality.