689
правок
Изменения
Добавил Modify и общий алгоритм.
== Алгоритм ==
Работу будем обозначать просто ее номером (<tex> i </tex>), при этом, номера работ могут меняться в зависимости от того, по какому параметру они отсортированы. Время появления работы — <tex> r_i </tex>, время, требуемое для ее выполнения — <tex> p_i </tex>. Множество ребер графа обозначается как <tex> E </tex>.
=== Modify ===
Для начала, модифицируем времена появления работ. Если работа <tex> j </tex> зависит от <tex> i </tex>, то, очевидно, она не может быть начата раньше, чем закончится выполнение </tex> i </tex>, поэтому нужно заменить <tex> r_j </tex> на <tex> \max(r_j, r_i + p_i) </tex>. Алгоритм, делающий это, представлен ниже (работы рассматриваются в порядке топологической сортировки):
Modify()
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>
После выполнения этого алгоритма для любых двух работ <tex> i, j </tex>, таких, что <tex> j </tex> зависит от <tex> i </tex>, выполняется <tex> r_j > r_i </tex>, поэтому, при рассмотрении работ в порядке неубывания времен их появления, они также будут топологически отсортированы.
=== Blocks ===
Здесь и далее считается, что работы отсортированы в порядке неубывания модифицированных <tex> r_i </tex>.
=== Decompose ===
Идея следующая: допустим, у нас есть блок работ, который можно выполнить без прерываний. Найдем работу <tex>i</tex>, которую выгодно выполнить последней. Разобъем оставшееся множество работ на блоки, решим задачу для этих блоков рекурсивно и вставим <tex> i </tex> в промежутки между этими блоками, до них и после них, начиная с <tex> r_i </tex>.
=== Общий алгоритм ===
Выполним Modify(), после чего разобъем все множество работ на блоки и для каждого блока запустим '''Decompose'''():
<tex> 1 \mid prec, pmtn, r_i \mid f_{max} </tex>()
1 Modify()
2 B = '''Blocks(<tex> \{1 \ldots n \} </tex>)
3 ans = - <tex> \infty </tex>
4 for (<tex> B_i \in </tex> B):
5 ans = <tex> \max </tex> (ans, '''Decompose'''(<tex> B_i </tex>))
6 return ans
== Время работы ==
Лемма: время работы алгоритма <tex> 1 \mid prec, pmtn, r_i \mid f_{max} </tex> — <tex> O(n^2) </tex> операций.
