Участник: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].

Препроцессинг

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

void modify({1...n})
    rm = r
    for u = 1 to n
      for (u, v) [math] \in [/math] E 
         rm[v] = max(rm[v], rm[u] + p[u]) 

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

Разбиение на блоки

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

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

Структура блока

 struct Block
    int start  // Время начала выполнения блока
    int time   // Время, затрачиваемое на соответствующий блок
    int end    // Время конца выполнения блока
    int[] jobs // Номера работ

Алгоритм разбиения

 Block blocks({1...n})
    int j = 0
    int t = 0
    Block[] b
    for i = 1 to n
      if  t < r[i] 
        t = rm[i] 
        j = j + 1 
        b[j].start = r[i]
        b[j].time = 0
      b[j].add(i)
      b[j].time = b[j].time + p[i]
      t = t + p[i] 
    return  b

Если алгоритм [math]\mathrm{Blocks}[/math] вызывается от пустого множества, то считаем, что он возвращает также пустое множество.

Определим время начала блока [math] B_j [/math] как [math]s_j = \min\limits_{i \in B_j} rm_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], построенным алгоритмом [math]\mathrm{Blocks}[/math], станок работает без простоя.

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

[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] rm_i \le s [/math]. Такая работа обязательно существует, иначе для множества работ, выполняемых позже, чем в момент [math] s [/math], было бы [math] r = \min\limits_{k \in T} rm_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]

Декомпозиция

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

 int decompose(Block b)
    int e = b.end  // e — время завершения работ блока B.
    find  l: f[l](e) = [math] \min  \{f[j](e) \mid j \in B, \overline\exists\ k: jk \in E \} [/math] 
    int ans = f[l](e) 
    Block g = blocks([math] b \setminus l [/math])
    for i = 2 to b.size
      for j =  g[i - 1].end to g[i].begin - 1     
        schedule[j] = l  // Вставляем работу в расписании между блоками
    schedule[g[g.size].end to b.end - 1] = l
    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] rm_l [/math], будут помещены в блок [math] B_0 [/math], следует, что порядок выполнения будет правильным. Также для корректности требуется, чтобы работы выполнялись не раньше, чем они появляются. Так как время выполнения работы определяется только в строках 5-8 алгоритма, которая соответствует этому требованию, то условие выполняется. Найдем теперь нижнюю оценку на [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]

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

Выполним [math]\mathrm{Modify}[/math], после чего разобъем все множество работ на блоки и для каждого блока запустим [math]\mathrm{Decompose}\gt [/math]:

 (int, int[]) makeSchedule(Job[] jobs)   
    int[] schedule // Расписание работ
    topSort(jobs)
    modify(jobs)
    b = blocks(jobs)
    int ans = [math] -\infty [/math]
    for b[j] [math]\in[/math] b
      ans = max(ans, decompose(b[j]))
    return (ans, schedule)

Из доказанной ранее леммы следует, что [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