Изменения
→Алгоритм решения
|statement=Следующие свойства эквивалентны:
(Аa) Существует допустимое расписание.
(Бb) В расширенной сети существует поток от s до t со значением <tex>\sum\limits_{i=1}^n p_i</tex>
|proof=<tex>(b) -> \Rightarrow (a)</tex>:Consider a flow with value <tex>sum_\sum\limits_{i = 1}^n {p_i}</tex> in the expanded network. Denote by <tex>x_{iK} </tex> the total flow which goes from <tex>J_i </tex> to <tex>I_K</tex>. Then <tex>sum_\sum\limits_{i = 1}^n sum_\sum\limits_{K = 2}^r X_x_{iK} = sum_\sum\limits_{i = 1}^n p_i</tex>. It is sufficient to show that for each subset <tex>A ⊆ \subseteq \{1, . . . , n\}</tex> we have <tex>sum_\sum\limits_{i∈Ai \in 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 <tex>A </tex> 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 \} = T_K(s_j − s_{j+1}) \dot min\{j, |A|\}</tex>.
Thus, we have
<tex>sum_\sum\limits_{i∈Ai \in A} x_{iK} \ge T_K sum_\sum\limits_{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_\sum\limits_{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} = \ </tex><tex>S_m = h(A)</tex>.
Otherwise
<tex>sum_\sum\limits_{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>.
<tex>sum_{i∈A} (a) \Rightarrow (b)</tex>: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 \subseteq \{ 1, . . . , n \le T_Kh(A)}</tex> (5.10), the inequality
holds. Furthermore, for <tex>i = 1, . . . , n</tex> we have <tex>p_i = \sum\limits_{K = 2}^r s_{iK}</tex>. It remains to 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 \subseteq \{ 1, . . . , n \}</tex> and <tex>K = 2, . . . , r</tex> the value <tex>\sum\limits_{i \in A} x_{iK}</tex> is bounded by the value of a minimum cut in the partial network with sources <tex>J_i(i \in A)</tex> and sink <tex>I_K</tex>. However, this value is <tex>T_K sum_\sum\limits_{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_\sum\limits_{i∈Ai \in A} x_{iK} \le T_KhT_K h(A) = T_K sum_\sum\limits_{j = 1}^m \min\{j, |A|\}(s_j - s_{j+1})</tex>
which is the desired inequality.