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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
м (rollbackEdits.php mass rollback)
 
(не показаны 3 промежуточные версии 3 участников)
Строка 2: Строка 2:
  
 
{{Задача
 
{{Задача
|definition=Задача <tex> 1 \mid prec, pmtn, r_i \mid f_{max} </tex> является обобщением [[Правило Лаулера|<tex>1 \mid prec \mid f_{max}</tex>]], но здесь у работ также есть времена появления, раньше которых их делать запрещено, и их можно прерывать.
+
|definition = <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>
 
}}
 
}}
 +
 +
Задача <tex> 1 \mid prec, pmtn, r_i \mid f_{max} </tex> является обобщением [[Правило Лаулера|<tex>1 \mid prec \mid f_{max}</tex>]], но здесь у работ также есть времена появления, раньше которых их делать запрещено, и их можно прерывать.
  
 
== Алгоритм ==
 
== Алгоритм ==
Работу будем обозначать просто ее номером (<tex> i </tex>), при этом, номера работ могут меняться в зависимости от того, по какому параметру они отсортированы. Время появления работы — <tex> r_i </tex>, время, требуемое для ее выполнения — <tex> p_i </tex>. Множество ребер графа обозначается как <tex> E </tex>.
+
Работу будем обозначать просто ее номером <tex>(i)</tex>, при этом, номера работ могут меняться в зависимости от того, по какому параметру они отсортированы. Время появления работы — <tex> r[i]</tex>, время, требуемое для ее выполнения — <tex> p[i] </tex>. Множество ребер графа обозначается как <tex> E </tex>.
  
=== Modify ===
+
===Идея алгоритма===
Для начала, модифицируем времена появления работ. Если работа <tex> j </tex> зависит от <tex> i </tex>, то, очевидно, она не может быть начата раньше, чем закончится выполнение <tex> i </tex>, поэтому нужно заменить <tex> r_j </tex> на <tex> \max(r_j, r_i + p_i) </tex>. Алгоритм, делающий это, представлен ниже (работы рассматриваются в порядке топологической сортировки):
+
Будем решать задачу рекурсивно. Разобьем множество работ на подмножества (блоки), внутри которых не будет перерыва между выполнением работ. После этого для каждого из блоков найдем работу, которую выгоднее всего выполнить последней, удалим работу из соответствующего блока и повторим разбиение на подблоки для оставшихся работ. Пустые промежутки между подблоками, полученными из данного блока, заполним выбранной работой. Повторим рекурсивно для каждого из полученных подблоков. Как будет показано далее, данный алгоритм строит корректное и оптимальное расписание. Можно заметить, что если на каждом этапе будет получаться всего один блок, алгоритм выродится в [[Правило_Лаулера|алгоритм Лаулера]].
  
Modify()
+
=== Препроцессинг ===
    '''for''' i <tex> \in \{ 1 \ldots n \} </tex>
+
Для начала, модифицируем времена появления работ. Если работа <tex> j </tex> зависит от <tex> i </tex>, то, очевидно, она не может быть начата раньше, чем закончится выполнение <tex> i </tex>, поэтому нужно заменить <tex> r_j </tex> на <tex> \max(r_j, r_i + p_i) </tex>. Алгоритм, делающий это, представлен ниже (работы рассматриваются в порядке [[Использование_обхода_в_глубину_для_топологической_сортировки|топологической сортировки]]):
      '''for''' j: ij <tex> \in E </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>, поэтому, при рассмотрении работ в порядке неубывания времен их появления, они также будут топологически отсортированы.
+
'''int[]''' modify('''int''' jobs[n]):
 +
    rm = copy(r)
 +
    '''for''' u = 1 '''to''' n
 +
      '''for''' (u, v) <tex> \in </tex> E
 +
          rm[v] = max(rm[v], rm[u] + p[u])
 +
    '''return''' rm
  
=== Blocks ===
+
После выполнения этого алгоритма для любых двух работ <tex> i, j </tex>, таких, что <tex> j </tex> зависит от <tex> i </tex>, выполняется <tex> rm[j] > rm[i] </tex>, поэтому, при рассмотрении работ в порядке неубывания времен их появления, они также будут топологически отсортированы.
Здесь и далее считается, что работы отсортированы в порядке неубывания модифицированных <tex> r_i </tex>.
+
 
 +
=== Разбиение на блоки ===
 +
Здесь и далее считается, что работы отсортированы в порядке неубывания модифицированных <tex> rm_i </tex>.
  
 
Станок, выполняющий работы, выполняет работу в некоторые интервалы времени и простаивает в остальное время. Следующий алгоритм разбивает множество работ на блоки, внутри которых станок работает без простоя.
 
Станок, выполняющий работы, выполняет работу в некоторые интервалы времени и простаивает в остальное время. Следующий алгоритм разбивает множество работ на блоки, внутри которых станок работает без простоя.
  
  Blocks(<tex> \{ 1 \ldots n \} </tex>)
+
'''Структура блока'''
     <tex> j \leftarrow 0 </tex>
+
  '''struct''' Block
     <tex> t \leftarrow 0 </tex>
+
    '''int''' start <font color = "darkgreen">// Время начала выполнения блока</font>
     '''for''' <tex> i \in \{ 1 \ldots n \} </tex>
+
     '''int''' time  <font color = "darkgreen">// Время, затрачиваемое на соответствующий блок</font>
      '''if''' <tex> t < r_i </tex>
+
     '''int''' end  <font color = "darkgreen"> // Время конца выполнения блока </font>
        <tex> t \leftarrow r_i </tex>
+
     '''int[]''' jobs <font color = "darkgreen">// Номера работ</font>
        <tex> j \leftarrow j + 1 </tex>
+
    '''void''' add() <font color = "darkgreen">// Добавляет работу в конец jobs[] </font>
      <tex> B_j \leftarrow B_j \cup i </tex>
+
 
      <tex> t \leftarrow t + p_i </tex>
+
Нетрудно заметить, что переменная <tex>\mathrm{end}</tex> получается из суммы <tex>\mathrm{start}</tex> и <tex>\mathrm{time}</tex>. Используется для читаемости и уменьшения кода <tex>\mathrm{Decompose}</tex>. Можно воспринимать как макроподстановку.
    '''return''' <tex> {B_1, \ldots, B_j} </tex>
+
 
 +
'''Алгоритм разбиения'''
  
Если алгоритм Blocks вызывается от пустого множества, то считаем, что он возвращает также пустое множество.
+
  '''Block[]''' blocks('''int''' p[n], '''int''' rm[n]):
 +
    '''int''' j = 0
 +
    '''int''' t = 0 <font color="darkgreen">// Переменная t указывает на время завершения последней работы </font>
 +
    '''Block''' b[n]
 +
    '''for''' i = 1 '''to''' n
 +
      '''if''' t < rm[i] <font color="darkgreen">// Время появления очередной работы больше, чем время завершения последней </font>
 +
        t = rm[i]  <font color="darkgreen">// работы в блоке, не можем начать её делать. Создаём новый блок </font>
 +
        j = j + 1
 +
        b[j].start = rm[i]
 +
        b[j].time = 0
 +
      b[j].add(i)                  <font color="darkgreen">// Добавляем к последнему блоку рассматриваемую работу, </font>
 +
      b[j].time = b[j].time + p[i] <font color="darkgreen">// увеличиваем суммарное время внутри блока и текущее время</font>
 +
      t = t + p[i]
 +
    '''return''' b
  
Определим время начала блока <tex> B_j </tex> как <tex>s_j = \min\limits_{i \in B_j} r_i </tex>, а время конца — как <tex> e_j = s_j + \sum\limits_{i \in B_j} p_i </tex>.
+
Если значение <tex>n</tex> равно нулю, то считаем, что алгоритм <tex>\mathrm{Blocks}</tex> возвращает пустое множество.
 +
 
 +
Определим время начала блока <tex> B_j </tex> как <tex>s_j = \min\limits_{i \in B_j} rm_i </tex>, а время конца — как <tex> e_j = s_j + \sum\limits_{i \in B_j} p_i </tex>.
  
 
{{Лемма
 
{{Лемма
 
|statement=
 
|statement=
Существует оптимальное расписание, такое, что все во все временные интервалы <tex> [s_j; e_j] </tex>, соответствующие блокам <tex> B_j </tex>, построенным алгоритмом Blocks, станок работает без простоя.
+
Существует оптимальное расписание, такое, что все во все временные интервалы <tex> [s_j; e_j] </tex>, соответствующие блокам <tex> B_j </tex>, построенным алгоритмом <tex>\mathrm{Blocks}</tex>, станок работает без простоя.
 
|proof=
 
|proof=
 
Возьмем произвольное оптимальное расписание <tex> S </tex>, в нем деление на блоки может также быть произвольным. Найдем первый такой временной интервал <tex> [s_j; e_j] </tex>, что в <tex> S </tex> есть период простоя внутри <tex> [s_j; e_j] </tex> (если таких периодов несколько, будем рассматривать первый из них). Обозначим его за <tex> [s; e] </tex>.  
 
Возьмем произвольное оптимальное расписание <tex> S </tex>, в нем деление на блоки может также быть произвольным. Найдем первый такой временной интервал <tex> [s_j; e_j] </tex>, что в <tex> S </tex> есть период простоя внутри <tex> [s_j; e_j] </tex> (если таких периодов несколько, будем рассматривать первый из них). Обозначим его за <tex> [s; e] </tex>.  
  
Возьмем некоторую работу <tex> i </tex>, такую, что она начинается позже, чем в момент времени <tex> s </tex>, не имеет в графе зависимостей предков, завершаемых позже, чем в момент <tex> s </tex> и <tex> r_i \le s </tex>. Такая работа обязательно существует, иначе для множества работ, выполняемых позже, чем в момент <tex> s </tex>, было бы <tex> r = \min\limits_{k \in T} r_k > s </tex>, и внутри блока <tex> B_j </tex> был бы простой <tex> [s_j; r] </tex>, что невозможно по построению алгоритма Blocks. Очевидно, мы можем начать выполнять ее в момент времени <tex> s </tex> и полностью, либо частично заполнить простой <tex> [s; e] </tex>; так как <tex> f_i </tex> — неубывающая функция, то ответ останется оптимальным. Повторяя этот процесс, мы за конечное число шагов придем к оптимальному расписанию с требуемым свойством.
+
Возьмем некоторую работу <tex> i </tex>, такую, что она начинается позже, чем в момент времени <tex> s </tex>, не имеет в графе зависимостей предков, завершаемых позже, чем в момент <tex> s </tex> и <tex> rm_i \leqslant s </tex>. Такая работа обязательно существует, иначе для множества работ, выполняемых позже, чем в момент <tex> s </tex>, было бы <tex> r = \min\limits_{k \in T} rm_k > s </tex>, и внутри блока <tex> B_j </tex> был бы простой <tex> [s_j; r] </tex>, что невозможно по построению алгоритма Blocks. Очевидно, мы можем начать выполнять ее в момент времени <tex> s </tex> и полностью, либо частично заполнить простой <tex> [s; e] </tex>; так как <tex> f_i </tex> — неубывающая функция, то ответ останется оптимальным. Повторяя этот процесс, мы за конечное число шагов придем к оптимальному расписанию с требуемым свойством.
 
}}
 
}}
  
=== Decompose ===
+
=== Декомпозиция ===
Допустим, у нас есть блок работ, который можно выполнить без прерываний. Общая идея алгоритма Decompose следующая: найдем работу <tex> i </tex>, которую выгоднее всего выполнить последней. Разобъем оставшееся множество работ на блоки, решим задачу для этих блоков рекурсивно и вставим <tex> i </tex> в промежутки между ними, до них и после них, начиная с <tex> r_i </tex>. Псевдокод этого алгоритма представлен ниже.
+
Допустим, у нас есть блок работ, который можно выполнить без прерываний. Общая идея алгоритма <tex>\mathrm{Decompose}</tex> следующая: найдем работу <tex> i </tex>, которую выгоднее всего выполнить последней. Разобъем оставшееся множество работ на блоки, решим задачу для этих блоков рекурсивно и вставим <tex> i </tex> в промежутки между ними, до них и после них, начиная с <tex> rm_i </tex>. Псевдокод этого алгоритма представлен ниже. Алгоритм принимает множество блоков и изначально пустое расписание, при каждом вызове заполняет пробелы в расписании очередной работой и обновляет ответ. Возвращает оптимальное расписание и соответствующее значение <tex>f_{max}</tex>.
  
Decompose(B)
+
  '''<tex>\langle</tex>int, int[]<tex>\rangle</tex>''' decompose('''Block''' b, '''int[]''' schedule):
     найти <tex> l: f_l(e) = \min \{f_j(e) \mid j \in B, \overline\exists\ k: jk \in E \} </tex>
+
     '''int''' e = b.end <font color = "darkgreen"> // e — время завершения работ блока B</font>
     ans <tex> \leftarrow f_l(e) </tex>
+
    find l: f[l](e) = <tex> \min \{f[j](e) \mid j \in B, \overline\exists\ k: jk \in E \} </tex>  
     G <tex> \leftarrow </tex> Blocks(<tex> B \setminus l </tex>)
+
     '''int''' ans = f[l](e)  
     вставить l в промежутки между блоками G, начиная с <tex> r_l </tex>
+
     b.jobs.remove(l)
     '''for''' <tex>B_j \in G </tex>:
+
    '''Block[]''' g = blocks(b.jobs.p, b.jobs.rm)
       ans = max(ans, Decompose(<tex> B_j </tex>))
+
    '''for''' i = 2 '''to''' g.size
     '''return''' ans
+
      schedule[g[i-1].end .. g[i].begin - 1] = l<font color = "darkgreen"> // Вставляем работу в расписание между блоками</font>
 +
    schedule[b.start .. g[1].start - 1] = l <font color = "darkgreen">   // Нужно учесть пропуски перед первым и </font>
 +
     schedule[g[g.size].end .. b.end - 1] = l <font color = "darkgreen"> // после последнего блоков соответственно</font>
 +
     '''for''' b <tex>\in</tex> g
 +
       ans = max(ans, decompose(b, schedule).first)
 +
     '''return''' <tex>\langle</tex>ans, schedule<tex>\rangle</tex>
 
   
 
   
 
{{Теорема
 
{{Теорема
 
|statement=
 
|statement=
Расписание для блока, построенное алгоритмом Decompose, является корректным и оптимальным.
+
Расписание для блока, построенное алгоритмом <tex>\mathrm{Decompose}</tex>, является корректным и оптимальным.
 
|proof=
 
|proof=
 
Докажем сначала корректность.
 
Докажем сначала корректность.
  
Убедимся, что порядок выполнения работ, заданный графом зависимостей, не нарушается. Заметим, что в разбиении <tex> B \setminus l </tex> на блоки существует не более одного блока <tex> B_0 </tex>, расположенного до момента времени <tex> r_l </tex> — иначе после вставки <tex> l </tex> в промежутки между блоками, <tex> B </tex> выполнялся бы с прерываниями. Далее, заметим, что все интервалы времени, на которые назначается работа из блока <tex> B_j </tex>, находятся внутри интервала <tex> [s_j; e_j] </tex>; это относится и к блоку <tex> B_0 </tex>. Из этих двух наблюдений, а также того, что все работы со временами появления меньше, чем <tex> r_l </tex>, будут помещены в блок <tex> B_0 </tex>, следует, что порядок выполнения будет правильным.
+
Убедимся, что порядок выполнения работ, заданный графом зависимостей, не нарушается. Заметим, что в разбиении <tex> B \setminus l </tex> на блоки существует не более одного блока <tex> B_0 </tex>, расположенного до момента времени <tex> r_l </tex> — иначе после вставки <tex> l </tex> в промежутки между блоками, <tex> B </tex> выполнялся бы с прерываниями. Далее, заметим, что все интервалы времени, на которые назначается работа из блока <tex> B_j </tex>, находятся внутри интервала <tex> [s_j; e_j] </tex>; это относится и к блоку <tex> B_0 </tex>. Из этих двух наблюдений, а также того, что все работы со временами появления меньше, чем <tex> rm_l </tex>, будут помещены в блок <tex> B_0 </tex>, следует, что порядок выполнения будет правильным.
  
Также для корректности требуется, чтобы работы выполнялись не раньше, чем они появляются. Так как время выполнения работы определяется только в строке 4 алгоритма, которая соответствует этому требованию, то условие выполняется.
+
Также для корректности требуется, чтобы работы выполнялись не раньше, чем они появляются. Так как время выполнения работы определяется в строках 5-9 алгоритма, которые соответствуют этому требованию, то условие выполняется.
  
 
Найдем теперь нижнюю оценку на <tex> f_{max} </tex>. Пусть <tex> f_{max}(J) </tex> — ответ для множества работ <tex> J </tex>.
 
Найдем теперь нижнюю оценку на <tex> f_{max} </tex>. Пусть <tex> f_{max}(J) </tex> — ответ для множества работ <tex> J </tex>.
  
Очевидно, для любой работы <tex> j \in J </tex> выполняется <tex> f_{max}(J) \ge f_{max}(J \setminus j) </tex>, значит, <tex> f_{max}(J) \ge \max\limits_{j \in J} f_{max}(J \setminus j) </tex>.
+
Очевидно, для любой работы <tex> j \in J </tex> выполняется <tex> f_{max}(J) \geqslant f_{max}(J \setminus j) </tex>, значит, <tex> f_{max}(J) \geqslant \max\limits_{j \in J} f_{max}(J \setminus j) </tex>.
  
Также, так как в оптимальном решении какая-то работа без потомков обязательно заканчивается в блоке <tex> B </tex>, то <tex> f_{max}(J) \ge f_l(e) </tex>.
+
Также, так как в оптимальном решении какая-то работа без потомков обязательно заканчивается в блоке <tex> B </tex>, то <tex> f_{max}(J) \geqslant f_l(e) </tex>.
  
Отсюда следует <tex> f_{max}(J) \ge \max(f_l(e), \max\limits_{j \in J} f_{max}(J \setminus j)) </tex>. По псевдокоду алгоритма видно, что его ответ достигает этой нижней оценки.
+
Отсюда следует <tex> f_{max}(J) \geqslant \max(f_l(e), \max\limits_{j \in J} f_{max}(J \setminus j)) </tex>. По псевдокоду алгоритма видно, что его ответ достигает этой нижней оценки.
 
}}
 
}}
  
 
=== Общий алгоритм ===
 
=== Общий алгоритм ===
  
Выполним Modify, после чего разобъем все множество работ на блоки и для каждого блока запустим Decompose():
+
Выполним <tex>\mathrm{Modify}</tex>, после чего разобъем все множество работ на блоки и для каждого блока запустим <tex>\mathrm{Decompose}</tex>:
  
MakeSchedule()
+
  <tex>\langle</tex>'''int''', '''int[]'''<tex>\rangle</tex> makeSchedule('''int[]''' jobs):
    Modify()
+
     '''int'''[] schedule <font color="darkgreen">// Расписание работ</font>
    B <tex> \leftarrow </tex> Blocks(<tex> \{1 \ldots n \} </tex>)
+
    jobs = topSort(jobs)
     ans <tex> \leftarrow </tex> <tex> -\infty </tex>
+
    '''int[]''' rm = modify(jobs)
     '''for''' (<tex> B_j \in B</tex>):
+
    ''sort jobs by'' rm ''values''
       ans = max(ans, Decompose(<tex> B_j </tex>))
+
    '''Blocks[]''' b = blocks(jobs.p, rm)
     '''return''' ans
+
    '''int''' ans = <tex> -\infty </tex>
 +
     '''for''' block <tex>\in</tex> b
 +
       ans = max(ans, decompose(block,schedule).first)
 +
     '''return''' <tex>\langle</tex>ans, schedule<tex>\rangle</tex>
  
 
Из доказанной ранее леммы следует, что <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>, поэтому расписание для всего множества работ, поделенного на блоки, также будет оптимальным и корректным.
Строка 99: Строка 130:
 
Обозначим за <tex> P(n) </tex> время, необходимое для выполнения алгоритма MakeSchedule на n работах. Очевидно, для корректно определенной функции P в силу структуры алгоритма должно выполняться неравенство:
 
Обозначим за <tex> P(n) </tex> время, необходимое для выполнения алгоритма MakeSchedule на n работах. Очевидно, для корректно определенной функции P в силу структуры алгоритма должно выполняться неравенство:
  
<tex> P(n) \ge сn + \sum\limits_{i = 1}^{k} P(n_i) </tex>
+
<tex> P(n) \geqslant сn + \sum\limits_{i = 1}^{k} P(n_i) </tex>
  
 
Здесь <tex> n_i </tex> - размер блока с номером <tex> i </tex>, построенного алгоритмом Blocks(). Заметим, что <tex> \sum\limits_{i = 1}^{k} n_i = n - 1</tex>.
 
Здесь <tex> n_i </tex> - размер блока с номером <tex> i </tex>, построенного алгоритмом Blocks(). Заметим, что <tex> \sum\limits_{i = 1}^{k} n_i = n - 1</tex>.
Строка 105: Строка 136:
 
Если <tex> P(n) = an^2 </tex>, то имеем:
 
Если <tex> P(n) = an^2 </tex>, то имеем:
  
<tex> an^2 \ge cn + a \sum\limits_{i = 1}^{k} n_i^2 </tex>
+
<tex> an^2 \geqslant cn + a \sum\limits_{i = 1}^{k} n_i^2 </tex>
  
Так как <tex> n^2 > (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 </tex>, то можно переписать неравенство в следующем виде:
+
Так как <tex> n^2 > (n - 1)^2 = \Big(\sum\limits_{i = 1}^{k} n_i\Big)^2 = \sum\limits_{i = 1}^{k} n_i^2 + 2\sum\limits_{\substack{i, j = 1\\ i \ne j}}^{k} n_i n_j </tex>, то можно переписать неравенство в следующем виде:
  
<tex> 2a \sum\limits_{\substack{i, j = 1\\ i \ne j}}^{k} n_i n_j \ge cn </tex>
+
<tex> 2a \sum\limits_{\substack{i, j = 1\\ i \ne j}}^{k} n_i n_j \geqslant cn </tex>
  
 
Чтобы получить максимальную нижнюю оценку на <tex> a </tex>, оценим снизу <tex> \sum\limits_{i, j = 1}^{k} n_i n_j </tex>:
 
Чтобы получить максимальную нижнюю оценку на <tex> a </tex>, оценим снизу <tex> \sum\limits_{i, j = 1}^{k} n_i n_j </tex>:
  
<tex> \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}</tex>
+
<tex> \sum\limits_{\substack{i, j = 1\\ i \ne j}}^{k} n_i n_j \geqslant \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) \geqslant \dfrac{nk}{4}</tex>
  
Значит, при <tex> a \ge \frac{c}{2} \frac{n}{\frac{nk}{4}} = \frac{2c}{k} </tex> требуемое неравенство будет выполняться.
+
Значит, при <tex> a \geqslant \dfrac{cn}{2} \cdot \dfrac{4}{nk} = \dfrac{2c}{k} </tex> требуемое неравенство будет выполняться.
  
 
}}
 
}}
  
==Источники==
+
==См. также==
* Peter Brucker. «Scheduling Algorithms» {{---}} «Springer», 2006 г. {{---}} 379 стр. {{---}} ISBN 978-3-540-69515-8
+
*[[Правило_Лаулера|Правило Лаулера]]
 +
 
 +
==Источники информации==
 +
* Peter Brucker. «Scheduling Algorithms» {{---}} «Springer», 2006 г. {{---}} 63-67 стр. {{---}} ISBN 978-3-540-69515-8
  
[[Категория: Дискретная математика и алгоритмы]]
+
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Теория расписаний]]
 
[[Категория: Теория расписаний]]

Текущая версия на 19:10, 4 сентября 2022

[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]. Алгоритм, делающий это, представлен ниже (работы рассматриваются в порядке топологической сортировки):

int[] modify(int jobs[n]):
    rm = copy(r)
    for u = 1 to n
      for (u, v) [math] \in [/math] E 
         rm[v] = max(rm[v], rm[u] + p[u]) 
    return rm

После выполнения этого алгоритма для любых двух работ [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 // Номера работ
    void add() // Добавляет работу в конец jobs[] 

Нетрудно заметить, что переменная [math]\mathrm{end}[/math] получается из суммы [math]\mathrm{start}[/math] и [math]\mathrm{time}[/math]. Используется для читаемости и уменьшения кода [math]\mathrm{Decompose}[/math]. Можно воспринимать как макроподстановку.

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

 Block[] blocks(int p[n], int rm[n]):
    int j = 0
    int t = 0 // Переменная t указывает на время завершения последней работы 
    Block b[n]
    for i = 1 to n
      if t < rm[i] // Время появления очередной работы больше, чем время завершения последней 
        t = rm[i]  // работы в блоке, не можем начать её делать. Создаём новый блок 
        j = j + 1 
        b[j].start = rm[i]
        b[j].time = 0
      b[j].add(i)                  // Добавляем к последнему блоку рассматриваемую работу, 
      b[j].time = b[j].time + p[i] // увеличиваем суммарное время внутри блока и текущее время
      t = t + p[i] 
    return b

Если значение [math]n[/math] равно нулю, то считаем, что алгоритм [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 \leqslant 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]. Псевдокод этого алгоритма представлен ниже. Алгоритм принимает множество блоков и изначально пустое расписание, при каждом вызове заполняет пробелы в расписании очередной работой и обновляет ответ. Возвращает оптимальное расписание и соответствующее значение [math]f_{max}[/math].

  [math]\langle[/math]int, int[][math]\rangle[/math] decompose(Block b, int[] schedule):
    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) 
    b.jobs.remove(l)
    Block[] g = blocks(b.jobs.p, b.jobs.rm)
    for i = 2 to g.size
      schedule[g[i-1].end .. g[i].begin - 1] = l // Вставляем работу в расписание между блоками
    schedule[b.start .. g[1].start - 1] = l    // Нужно учесть пропуски перед первым и 
    schedule[g[g.size].end .. b.end - 1] = l   // после последнего блоков соответственно
    for b [math]\in[/math] g
      ans = max(ans, decompose(b, schedule).first)
    return [math]\langle[/math]ans, schedule[math]\rangle[/math]

Теорема:
Расписание для блока, построенное алгоритмом [math]\mathrm{Decompose}[/math], является корректным и оптимальным.
Доказательство:
[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-9 алгоритма, которые соответствуют этому требованию, то условие выполняется.

Найдем теперь нижнюю оценку на [math] f_{max} [/math]. Пусть [math] f_{max}(J) [/math] — ответ для множества работ [math] J [/math].

Очевидно, для любой работы [math] j \in J [/math] выполняется [math] f_{max}(J) \geqslant f_{max}(J \setminus j) [/math], значит, [math] f_{max}(J) \geqslant \max\limits_{j \in J} f_{max}(J \setminus j) [/math].

Также, так как в оптимальном решении какая-то работа без потомков обязательно заканчивается в блоке [math] B [/math], то [math] f_{max}(J) \geqslant f_l(e) [/math].

Отсюда следует [math] f_{max}(J) \geqslant \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}[/math]:

 [math]\langle[/math]int, int[][math]\rangle[/math] makeSchedule(int[] jobs):
    int[] schedule // Расписание работ
    jobs = topSort(jobs)
    int[] rm = modify(jobs)
    sort jobs by rm values
    Blocks[] b = blocks(jobs.p, rm)
    int ans = [math] -\infty [/math]
    for block [math]\in[/math] b
      ans = max(ans, decompose(block,schedule).first)
    return [math]\langle[/math]ans, schedule[math]\rangle[/math]

Из доказанной ранее леммы следует, что [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) \geqslant с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 \geqslant cn + a \sum\limits_{i = 1}^{k} n_i^2 [/math]

Так как [math] n^2 \gt (n - 1)^2 = \Big(\sum\limits_{i = 1}^{k} n_i\Big)^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 \geqslant 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 \geqslant \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) \geqslant \dfrac{nk}{4}[/math]

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

См. также

Источники информации

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