419
правок
Изменения
→Решение
[[Файл:Figure_5.2.png|400px|thumb|right|Рис. 1 - Cеть]]
Сведем эту задачу к поиску максимального потока в сети, построенной указанным ниже образом.
Пусть <tex>t_1 < t_2 < \ldots < t_r</tex> - упорядоченная последовательность <tex>r_i</tex> и <tex>d_i</tex>. Определим интервалы <tex>I_K = [t_K; t_{K+1}]</tex> с длиной <tex>T_K = t_{K+1} - t_K</tex> для всех <tex>K = 1 \ldots r-1</tex>.
Работам <tex>J_i</tex> сопоставим свой тип вершин, а интервалам <tex>I_K</tex> свой. Добавим две фиктивные вершины <tex>s</tex> и <tex>t</tex>. Из вершины Вершина <tex>s</tex> в вершины соединена с работами идут направленные ребра вершинами <tex>J_i</tex> ребрами с пропускной способностью <tex>p_i</tex>, из вершин вершина <tex>t</tex> соединена с интервалами в вершину вершинами <tex>tI_K</tex> идут направленные ребра ребрами с пропускной способностью <tex>mT_K</tex>. Ребро между вершиной с работой <tex>J_i</tex> и вершиной с интервалом <tex>I_K</tex> существует, если <tex>r_i \le t_K, t_{K+1} \le d_i</tex>. Пропускная способность этого ребра - <tex>T_K</tex>. Нетрудно понять, что расписание существует, если максимальный поток через эту сеть равен <tex>\sum_{i=1}^n p_i</tex>. Если это так, то поток <tex>x_{iK}</tex> на дуге <tex>(J_i, I_K)</tex> соответствует тому, что работа <tex>J_i</tex> будет выполняться во временном интервале <tex>I_K</tex>, и будет справедливо следующее: # <tex>\sum_{K=1}^{r-1} x_{iK} = p_i, i = 1 \ldots n</tex># <tex>\sum_{i=1}^n x_{iK} \le mT_K, K = 1 \ldots r - 1</tex># <tex>x_{iK} \le T_K</tex> для всех ребер <tex>(J_i, I_K)</tex>
