1precpmtnrifmax — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Blocks)
м
Строка 9: Строка 9:
  
 
  Modify()
 
  Modify()
1    '''for''' i <tex> \in \{ 1 \ldots n \} </tex>
+
    '''for''' i <tex> \in \{ 1 \ldots n \} </tex>
2      '''for''' j: ij <tex> \in E </tex>
+
      '''for''' j: ij <tex> \in E </tex>
3        <tex> r_j \leftarrow \max(r_j, r_i + p_i) </tex>  
+
        <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>, поэтому, при рассмотрении работ в порядке неубывания времен их появления, они также будут топологически отсортированы.
 
После выполнения этого алгоритма для любых двух работ <tex> i, j </tex>, таких, что <tex> j </tex> зависит от <tex> i </tex>, выполняется <tex> r_j > r_i </tex>, поэтому, при рассмотрении работ в порядке неубывания времен их появления, они также будут топологически отсортированы.
Строка 21: Строка 21:
  
 
  Blocks(<tex> \{ 1 \ldots n \} </tex>)
 
  Blocks(<tex> \{ 1 \ldots n \} </tex>)
1    <tex> j \leftarrow 0 </tex>
+
    <tex> j \leftarrow 0 </tex>
2    <tex> t \leftarrow 0 </tex>
+
    <tex> t \leftarrow 0 </tex>
3    '''for''' <tex> i \in \{ 1 \ldots n \} </tex>
+
    '''for''' <tex> i \in \{ 1 \ldots n \} </tex>
4      '''if''' <tex> t < r_i </tex>
+
      '''if''' <tex> t < r_i </tex>
5        <tex> t \leftarrow r_i </tex>
+
        <tex> t \leftarrow r_i </tex>
6        <tex> j \leftarrow j + 1 </tex>
+
        <tex> j \leftarrow j + 1 </tex>
7      <tex> B_j \leftarrow B_j \cup i </tex>
+
      <tex> B_j \leftarrow B_j \cup i </tex>
8      <tex> t \leftarrow t + p_i </tex>
+
      <tex> t \leftarrow t + p_i </tex>
9    '''return''' <tex> {B_1, \ldots, B_j} </tex>
+
    '''return''' <tex> {B_1, \ldots, B_j} </tex>
  
 
Если алгоритм Blocks вызывается от пустого множества, то считаем, что он возвращает также пустое множество.
 
Если алгоритм Blocks вызывается от пустого множества, то считаем, что он возвращает также пустое множество.
Строка 48: Строка 48:
  
 
  Decompose(B)
 
  Decompose(B)
1    найти <tex> l: f_l(e) = \min \{f_j(e) \mid j \in B, \overline\exists\ k: jk \in E \} </tex>
+
    найти <tex> l: f_l(e) = \min \{f_j(e) \mid j \in B, \overline\exists\ k: jk \in E \} </tex>
2    ans <tex> \leftarrow f_l(e) </tex>
+
    ans <tex> \leftarrow f_l(e) </tex>
3    G <tex> \leftarrow </tex> Blocks(<tex> B \setminus l </tex>)
+
    G <tex> \leftarrow </tex> Blocks(<tex> B \setminus l </tex>)
4    вставить l в промежутки между блоками G, начиная с <tex> r_l </tex>
+
    вставить l в промежутки между блоками G, начиная с <tex> r_l </tex>
5    '''for''' <tex>B_j \in G </tex>:
+
    '''for''' <tex>B_j \in G </tex>:
6      ans = max(ans, Decompose(<tex> B_j </tex>))
+
      ans = max(ans, Decompose(<tex> B_j </tex>))
7    '''return''' ans
+
    '''return''' ans
 
   
 
   
 
{{Теорема
 
{{Теорема
Строка 80: Строка 80:
  
 
  MakeSchedule()
 
  MakeSchedule()
1    Modify()
+
    Modify()
2    B <tex> \leftarrow </tex> Blocks(<tex> \{1 \ldots n \} </tex>)
+
    B <tex> \leftarrow </tex> Blocks(<tex> \{1 \ldots n \} </tex>)
3    ans <tex> \leftarrow </tex> <tex> -\infty </tex>
+
    ans <tex> \leftarrow </tex> <tex> -\infty </tex>
4    '''for''' (<tex> B_j \in B</tex>):
+
    '''for''' (<tex> B_j \in B</tex>):
5      ans = max(ans, Decompose(<tex> B_j </tex>))
+
      ans = max(ans, Decompose(<tex> B_j </tex>))
6    '''return''' ans
+
    '''return''' ans
  
 
Из доказанной ранее леммы следует, что <tex> f_{max}(\{ 1 \ldots n \}) = \max\limits_{j} f_{max}(B_j) </tex>, поэтому расписание для всего множества работ, поделенного на блоки, также будет оптимальным и корректным.
 
Из доказанной ранее леммы следует, что <tex> f_{max}(\{ 1 \ldots n \}) = \max\limits_{j} f_{max}(B_j) </tex>, поэтому расписание для всего множества работ, поделенного на блоки, также будет оптимальным и корректным.

Версия 00:32, 10 июня 2015

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

Задача [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 [math] \in \{ 1 \ldots n \} [/math]
      for j: ij [math] \in E [/math]
        [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])
    [math] j \leftarrow 0 [/math]
    [math] t \leftarrow 0 [/math]
    for [math] i \in \{ 1 \ldots n \} [/math]
      if [math] t \lt  r_i [/math]
        [math] t \leftarrow r_i [/math]
        [math] j \leftarrow j + 1 [/math]
      [math] B_j \leftarrow B_j \cup i [/math]
      [math] t \leftarrow t + p_i [/math]
    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)
    найти [math] l: f_l(e) = \min \{f_j(e) \mid j \in B, \overline\exists\ k: jk \in E \} [/math]
    ans [math] \leftarrow f_l(e) [/math]
    G [math] \leftarrow [/math] Blocks([math] B \setminus l [/math])
    вставить l в промежутки между блоками G, начиная с [math] r_l [/math]
    for [math]B_j \in G [/math]:
      ans = max(ans, Decompose([math] B_j [/math]))
    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 [math] \leftarrow [/math] Blocks([math] \{1 \ldots n \} [/math])
    ans [math] \leftarrow [/math] [math] -\infty [/math]
    for ([math] B_j \in B[/math]):
      ans = max(ans, Decompose([math] B_j [/math]))
    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 \frac{nk}{4}[/math]

Значит, при [math] a \ge \frac{c}{2} \frac{n}{\frac{nk}{4}} = \frac{2c}{k} [/math] требуемое неравенство будет выполняться.
[math]\triangleleft[/math]

Источники

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