Участник:Qtr

[math] 1 \mid prec,pmtn,r_i \mid f_{max}[/math]

Задача:

<wikitex>Дано $n$ работ, которые надо выполнить на одной машине, причем $i$-ая работа выполняется $p_i$ времени. Для каждой работы задана монотонно неубывающая функция $f_i$. Работы можно прерывать, у каждой работы есть время появления $r_{i}$. Также между работами заданы отношения в виде ориентированного графа без циклов: если существует ребро $a \to b$, то работа $a$ должна завершиться до начала выполнения работы $b$. Необходимо построить такое расписание, чтобы величина $f_{max} = \max\limits_{j=1..n}{f_j(C_j)}$, где $C_j$ — время окончания выполнения $j$-ой работы, была минимальна.</wikitex>

Задача [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], то, очевидно, она не может быть начата раньше, чем закончится выполнение [math] i [/math], поэтому нужно заменить [math] r_j [/math] на [math] \max(r_j, r_i + p_i) [/math]. Алгоритм, делающий это, представлен ниже (работы рассматриваются в порядке топологической сортировки):

Modify()
    for i = 1 to n
      for j: ij [math] \in E [/math]
         r[j] = max(r[j], r[i] + p[i]) 

После выполнения этого алгоритма для любых двух работ [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])
    j = 0
    t = 0
    for i = 1 to n
      if [math] t \lt  r[i] [/math]
        t = r[i] 
        j = j + 1 
      B[j].add(i)
      t = t + p[i] 
    return  B 

Если алгоритм 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)
    find [math] l: f[l](e) = \min \{f[j](e) \mid j \in B, \overline\exists\ k: jk \in E \} [/math]
    ans = f[l](e) 
    G = Blocks([math] B \setminus l [/math])
    вставить l в промежутки между блоками G, начиная с [math] r_l [/math]
    for B[j] [math]\in[/math] G
      ans = max(ans, Decompose(B[j]))
    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()
    Modify()
    B  =  Blocks([math] \{1 \ldots n \} [/math])
    ans = [math] -\infty [/math]
    for B[j] [math]\in[/math] B
      ans = max(ans, Decompose(B[j]))
    return ans

Из доказанной ранее леммы следует, что [math] f_{max}(\{ 1 \ldots n \}) = \max\limits_{j} f_{max}(B_j) [/math], поэтому расписание для всего множества работ, поделенного на блоки, также будет оптимальным и корректным.

Время работы

Теорема:

Время работы алгоритма 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 \cfrac{nk}{4}[/math] Значит, при [math] a \ge \cfrac{cn}{2} \cfrac{4}{nk} = \cfrac{2c}{k} [/math] требуемое неравенство будет выполняться.

[math]\triangleleft[/math]

Источники

• Peter Brucker. «Scheduling Algorithms» — «Springer», 2006 г. — 379 стр. — ISBN 978-3-540-69515-8