1precpmtnrifmax

Постановка задачи

Задача [math] 1 \mid prec, pmtn, r_i \mid f_{max} [/math] является обобщением [math]1 \mid prec \mid f_{max}[/math], но здесь у работ также есть времена появления, раньше которых их делать запрещено, и их можно прерывать.

Алгоритм

Работу будем обозначать просто ее номером ([math] i [/math]), при этом, номера работ могут меняться в зависимости от того, по какому параметру они отсортированы. Время появления работы — [math] r_i [/math], время, требуемое для ее выполнения — [math] p_i [/math]. Множество ребер графа обозначается как [math] E [/math].

Modify

Для начала, модифицируем времена появления работ. Если работа [math] j [/math] зависит от [math] i [/math], то, очевидно, она не может быть начата раньше, чем закончится выполнение </tex> i </tex>, поэтому нужно заменить [math] r_j [/math] на [math] \max(r_j, r_i + p_i) [/math]. Алгоритм, делающий это, представлен ниже (работы рассматриваются в порядке топологической сортировки):

Modify()
1    for i [math] \in \{ 1 \ldots n \} [/math]
2      for j: ij [math] \in E [/math]
3        [math] r_j \leftarrow \max(r_j, r_i + p_i) [/math] 

После выполнения этого алгоритма для любых двух работ [math] i, j [/math], таких, что [math] j [/math] зависит от [math] i [/math], выполняется [math] r_j \gt r_i [/math], поэтому, при рассмотрении работ в порядке неубывания времен их появления, они также будут топологически отсортированы.

Blocks

Здесь и далее считается, что работы отсортированы в порядке неубывания модифицированных [math] r_i [/math].

Decompose

Идея следующая: допустим, у нас есть блок работ, который можно выполнить без прерываний. Найдем работу [math]i[/math], которую выгодно выполнить последней. Разобъем оставшееся множество работ на блоки, решим задачу для этих блоков рекурсивно и вставим [math] i [/math] в промежутки между этими блоками, до них и после них, начиная с [math] r_i [/math].

Общий алгоритм

Выполним Modify(), после чего разобъем все множество работ на блоки и для каждого блока запустим Decompose():

[math] 1 \mid prec, pmtn, r_i \mid f_{max} [/math]()
1    Modify()
2    B = Blocks([math] \{1 \ldots n \} [/math])
3    ans = - [math] \infty [/math]
4    for ([math] B_i \in [/math] B):
5      ans = [math] \max [/math] (ans, Decompose([math] B_i [/math]))
6    return ans

Время работы

Лемма: время работы алгоритма [math] 1 \mid prec, pmtn, r_i \mid f_{max} [/math] — [math] O(n^2) [/math] операций.