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].

Станок, выполняющий работы, выполняет работу в некоторые интервалы времени и простаивает в остальное время. Следующий алгоритм разбивает множество работ на блоки, внутри которых станок работает без простоя.

Blocks([math] \{ 1 \ldots n \} [/math])
1    [math] j \leftarrow 0 [/math]
2    [math] t \leftarrow 0 [/math]
3    for [math] i \in \{ 1 \ldots n \} [/math]
4      if [math] t \lt  r_i [/math]
5        [math] t \leftarrow r_i [/math]
6        [math] j \leftarrow j + 1 [/math]
7      [math] B_j \leftarrow B_j \cup i [/math]
8      [math] t \leftarrow t + p_i [/math]
9    return [math] {B_1, \ldots, B_j} [/math]

Если алгоритм Blocks вызывается от пустого множества, то считаем, что он возвращает также пустое множество.

Определим время начала блока [math] B_j [/math] как [math]s_j = \min\limits_{i \in B_j} r_i [/math], а время конца — как [math] e_j = s_j + \sum\limits_{i \in B_j} p_i [/math].

Лемма:

Существует оптимальное расписание, такое, что все во все временные интервалы [math] [s_j; e_j] [/math], соответствующие блокам [math] B_j [/math], построенным алгоритмом Blocks, станок работает без простоя.

Доказательство:

[math]\triangleright[/math]

Возьмем произвольное оптимальное расписание [math] S [/math], в нем деление на блоки может также быть произвольным. Найдем первый такой временной интервал [math] [s_j; e_j] [/math], что в [math] S [/math] есть период простоя внутри [math] [s_j; e_j] [/math] (если таких периодов несколько, будем рассматривать первый из них). Обозначим его за [math] [s; e] [/math]. Возьмем некоторую работу [math] i [/math], такую, что она начинается позже, чем в момент времени [math] s [/math], не имеет в графе зависимостей предков, завершаемых позже, чем в момент [math] s [/math] и [math] r_i \le s [/math]. Такая работа обязательно существует, иначе для множества работ, выполняемых позже, чем в момент [math] s [/math], было бы [math] r = \min\limits{k \in T} r_k \gt s [/math], и внутри блока [math] B_j [/math] был бы простой [math] [s_j; r] [/math], что невозможно по построению алгоритма Blocks. Очевидно, мы можем начать выполнять ее в момент времени [math] s [/math] и полностью, либо частично заполнить простой [math] [s; e] [/math]; так как [math] f_i [/math] — неубывающая функция, то ответ останется оптимальным. Повторяя этот процесс, мы за конечное число шагов придем к оптимальному расписанию с требуемым свойством.

[math]\triangleleft[/math]

Decompose

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

Decompose(B)
1    найти [math] l: f_l(e) = \min \{f_j(e) \mid j \in B, \overline\exists\ k: jk \in E \} [/math]
2    ans [math] \leftarrow f_l(e) [/math]
3    G [math] \leftarrow [/math] Blocks([math] B \setminus l [/math])
4    вставить l в промежутки между блоками G, начиная с [math] r_l [/math]
5    for [math]B_j \in G [/math]:
6      ans = max(ans, Decompose([math] B_j [/math]))
7    return ans

Теорема:

Расписание, построенное алгоритмом Decompose(), является корректным и оптимальным.

Доказательство:

[math]\triangleright[/math]

Докажем сначала корректность. Убедимся, что порядок выполнения работ, заданный графом зависимостей, не нарушается. Заметим, что в разбиении [math] B \setminus l [/math] на блоки существует не более одного блока [math] B_0 [/math], расположенного до момента времени [math] r_l [/math] — иначе после вставки [math] l [/math] в промежутки между блоками, [math] B [/math] выполнялся бы с прерываниями. Далее, заметим, что все интервалы времени, на которые назначается работа из блока [math] B_j [/math], находятся внутри интервала [math] [s_j; e_j] [/math]; это относится и к блоку [math] B_0 [/math]. Из этих двух наблюдений, а также того, что все работы со временами появления меньше, чем [math] r_l [/math], будут помещены в блок [math] B_0 [/math], следует, что порядок выполнения будет правильным. Также для корректности требуется, чтобы работы выполнялись не раньше, чем они появляются. Так как время выполнения работы определяется только в строке 4 алгоритма, которая соответствует этому требованию, то условие выполняется. Найдем теперь нижнюю оценку на [math] f_{max} [/math]. Пусть [math] f_{max}(J) [/math] — ответ для множества работ [math] J [/math]. Очевидно, для любой работы [math] j \in J [/math] выполняется [math] f_{max}(J) \ge f_{max}(J \setminus j) [/math], значит, [math] f_{max}(J) \ge \max\limits_{j \in J} f_{max}(J \setminus j) [/math]. Также, так как в оптимальном решении какая-то работа без потомков обязательно заканчивается в блоке [math] B [/math], то [math] f_{max}(J) \ge f_l(e) [/math]. Отсюда следует [math] f_{max}(J) \ge \max(f_l(e), \max\limits_{j \in J} f_{max}(J \setminus j)) [/math]. По псевдокоду алгоритма видно, что его ответ достигает этой нижней оценки.

[math]\triangleleft[/math]

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

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

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

Время работы

Теорема:

Время работы алгоритма MakeSchedule() — [math] O(n^2) [/math] операций.

Доказательство:

[math]\triangleright[/math]

Обозначим за [math] P(n) [/math] время, необходимое для выполнения алгоритма MakeSchedule() на n работах. Очевидно, для корректно определенной функции P в силу структуры алгоритма должно выполняться неравенство: [math] P(n) \ge сn + \sum\limits_{i = 1}^{k} P(n_i) [/math] Здесь [math] n_i [/math] - размер блока с номером [math] i [/math], построенного алгоритмом Blocks(). Заметим, что [math] \sum\limits_{i = 1}^{k} n_i = n - 1[/math]. Если [math] P(n) = an^2 [/math], то имеем: [math] an^2 \ge cn + a \sum\limits_{i = 1}^{k} n_i^2 [/math] Так как [math] n^2 \gt (n - 1)^2 = (\sum\limits_{i = 1}^{k} n_i)^2 = \sum\limits_{i = 1}^{k} n_i^2 + 2\sum\limits_{\substack{i, j = 1\\ i \ne j}}^{k} n_i n_j [/math], то можно переписать неравенство в следующем виде: [math] 2a \sum\limits_{\substack{i, j = 1\\ i \ne j}}^{k} n_i n_j \ge cn [/math] Чтобы получить максимальную нижнюю оценку на [math] a [/math], оценим снизу [math] \sum\limits_{i, j = 1}^{k} n_i n_j [/math]: Так как [math] \sum\limits_{\substack{i, j = 1\\ i \ne j}}^{k} n_i n_j \ge \sum\limits_{\substack{i, j = 1\\ i \ne j}}^{k} 1 \cdot n_j = \sum\limits_{j = 1}^{k} (k - 1) n_j = (k - 1) (n - 1) \ge \frac{nk}{4}[/math] Значит, при [math] a \ge \frac{c}{2} \frac{n}{\frac{nk}{4}} = \frac{2c}{k} [/math] требуемое неравенство будет выполняться.

[math]\triangleleft[/math]