25
правок
Изменения
м
1 '''for''' i <tex> \in \{ 1 \ldots n \} </tex> 2 '''for''' j: ij <tex> \in E </tex> 3 <tex> r_j \leftarrow \max(r_j, r_i + p_i) </tex>
1 <tex> j \leftarrow 0 </tex> 2 <tex> t \leftarrow 0 </tex> 3 '''for''' <tex> i \in \{ 1 \ldots n \} </tex> 4 '''if''' <tex> t < r_i </tex> 5 <tex> t \leftarrow r_i </tex> 6 <tex> j \leftarrow j + 1 </tex> 7 <tex> B_j \leftarrow B_j \cup i </tex> 8 <tex> t \leftarrow t + p_i </tex> 9 '''return''' <tex> {B_1, \ldots, B_j} </tex>
1 найти <tex> l: f_l(e) = \min \{f_j(e) \mid j \in B, \overline\exists\ k: jk \in E \} </tex> 2 ans <tex> \leftarrow f_l(e) </tex> 3 G <tex> \leftarrow </tex> Blocks(<tex> B \setminus l </tex>) 4 вставить l в промежутки между блоками G, начиная с <tex> r_l </tex> 5 '''for''' <tex>B_j \in G </tex>: 6 ans = max(ans, Decompose(<tex> B_j </tex>)) 7 '''return''' ans
1 Modify() 2 B <tex> \leftarrow </tex> Blocks(<tex> \{1 \ldots n \} </tex>) 3 ans <tex> \leftarrow </tex> <tex> -\infty </tex> 4 '''for''' (<tex> B_j \in B</tex>): 5 ans = max(ans, Decompose(<tex> B_j </tex>)) 6 '''return''' ans
Нет описания правки
Modify()
После выполнения этого алгоритма для любых двух работ <tex> i, j </tex>, таких, что <tex> j </tex> зависит от <tex> i </tex>, выполняется <tex> r_j > r_i </tex>, поэтому, при рассмотрении работ в порядке неубывания времен их появления, они также будут топологически отсортированы.
Blocks(<tex> \{ 1 \ldots n \} </tex>)
Если алгоритм Blocks вызывается от пустого множества, то считаем, что он возвращает также пустое множество.
Decompose(B)
{{Теорема
MakeSchedule()
Из доказанной ранее леммы следует, что <tex> f_{max}(\{ 1 \ldots n \}) = \max\limits_{j} f_{max}(B_j) </tex>, поэтому расписание для всего множества работ, поделенного на блоки, также будет оптимальным и корректным.
