Участник:Qtr — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Описание)
м (Декомпозиция)
 
(не показано 67 промежуточных версий 2 участников)
Строка 1: Строка 1:
'''Алгоритм Джонсона''' (англ. ''Johnson's algorithm'') находит кратчайшие пути между всеми парами вершин во взвешенном ориентированном графе с любыми весами ребер, но не имеющем отрицательных циклов.
+
<tex dpi = "200"> 1 \mid prec,pmtn,r_i \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> j </tex> зависит от <tex> i </tex>, то, очевидно, она не может быть начата раньше, чем закончится выполнение <tex> i </tex>, поэтому нужно заменить <tex> r_j </tex> на <tex> \max(r_j, r_i + p_i) </tex>. Алгоритм, делающий это, представлен ниже (работы рассматриваются в порядке [[Использование_обхода_в_глубину_для_топологической_сортировки|топологической сортировки]]):
  
Алгоритм Джонсона позволяет найти кратчайшие пути между всеми парами вершин в течение времени <tex> O(V^2\log(V) + VE) </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
  
В этом алгоритме используется метод '''изменения веса''' (англ. ''reweighting''). Суть его заключается в том, что для заданного графа <tex> G </tex> строится новая весовая функция <tex> \omega_\varphi </tex>, неотрицательная для всех ребер графа <tex> G </tex> и сохраняющая кратчайшие пути. Такая весовая функция строится с помощью так называемой [[Амортизационный_анализ#.D0.9C.D0.B5.D1.82.D0.BE.D0.B4_.D0.BF.D0.BE.D1.82.D0.B5.D0.BD.D1.86.D0.B8.D0.B0.D0.BB.D0.BE.D0.B2|потенциальной]] функции.
+
После выполнения этого алгоритма для любых двух работ <tex> i, j </tex>, таких, что <tex> j </tex> зависит от <tex> i </tex>, выполняется <tex> rm[j] > rm[i] </tex>, поэтому, при рассмотрении работ в порядке неубывания времен их появления, они также будут топологически отсортированы.
  
Пусть <tex> \varphi : V \rightarrow \mathbb R </tex> — произвольное отображение из множества вершин в вещественные числа. Тогда новой весовой функцией будет <tex> \omega_\varphi(u, v) = \omega(u, v) + \varphi(u) - \varphi(v) </tex>.
+
=== Разбиение на блоки ===
 +
Здесь и далее считается, что работы отсортированы в порядке неубывания модифицированных <tex> rm_i </tex>.
  
Такая потенциальная функция строится при помощи добавлении фиктивной вершины в <tex> G </tex>, из которой проведены ребра нулевого веса во все остальные вершины и запуском [[Алгоритм Форда-Беллмана|алгоритма Форда-Беллмана]] из нее. На этом же этапе мы сможем обнаружить наличие отрицательного цикла в графе.
+
Станок, выполняющий работы, выполняет работу в некоторые интервалы времени и простаивает в остальное время. Следующий алгоритм разбивает множество работ на блоки, внутри которых станок работает без простоя.
  
Теперь, когда мы знаем, что веса всех ребер неотрицательны, и кратчайшие пути сохранятся, можно запустить [[Алгоритм Дейкстры|алгоритм Дейкстры]] из каждой вершины и таким образом найти кратчайшие расстояния между всеми парами вершин.
+
'''Структура блока'''
 +
  '''struct''' Block
 +
    '''int''' start  <font color = "darkgreen">// Время начала выполнения блока</font>
 +
    '''int''' time  <font color = "darkgreen">// Время, затрачиваемое на соответствующий блок</font>
 +
    '''int''' end  <font color = "darkgreen"> // Время конца выполнения блока </font>
 +
    '''int[]''' jobs <font color = "darkgreen">// Номера работ</font>
 +
    '''void''' add() <font color = "darkgreen">// Добавляет работу в конец jobs[] </font>
  
=== Сохранение кратчайших путей ===
+
Нетрудно заметить, что переменная <tex>\mathrm{end}</tex> получается из суммы <tex>\mathrm{start}</tex> и <tex>\mathrm{time}</tex>. Используется для читаемости и уменьшения кода <tex>\mathrm{Decompose}</tex>. Можно воспринимать как макроподстановку.
Утверждается, что если какой-то путь <tex> P </tex> был кратчайшим относительно весовой функции <tex> \omega </tex>, то он будет кратчайшим и относительно новой весовой функции <tex> \omega_\varphi </tex>.
+
 
 +
'''Алгоритм разбиения'''
 +
 
 +
  '''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>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>P,\; Q </tex> {{---}} два пути <tex> a \rightsquigarrow b\;</tex> и <tex>\omega(P) < \omega(Q).</tex> Тогда <tex>\forall \varphi: \; \omega_\varphi(P) < \omega_\varphi(Q)</tex>  
+
Существует оптимальное расписание, такое, что все во все временные интервалы <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>P: \;u_0 \rightarrow u_1 \rightarrow u_2 \rightarrow \ldots \rightarrow u_k </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> — неубывающая функция, то ответ останется оптимальным. Повторяя этот процесс, мы за конечное число шагов придем к оптимальному расписанию с требуемым свойством.
 +
}}
  
:Его вес с новой весовой функцией равен <tex>\omega_\varphi(P) = \omega_\varphi(u_0u_1) + \omega_\varphi(u_1u_2) + \ldots + \omega_\varphi(u_{k-1}u_k) </tex>.
+
=== Декомпозиция ===
 +
Допустим, у нас есть блок работ, который можно выполнить без прерываний. Общая идея алгоритма <tex>\mathrm{Decompose}</tex> следующая: найдем работу <tex> i </tex>, которую выгоднее всего выполнить последней. Разобъем оставшееся множество работ на блоки, решим задачу для этих блоков рекурсивно и вставим <tex> i </tex> в промежутки между ними, до них и после них, начиная с <tex> rm_i </tex>. Псевдокод этого алгоритма представлен ниже. Алгоритм принимает множество блоков и изначально пустое расписание, при каждом вызове заполняет пробелы в расписании очередной работой и обновляет ответ. Возвращает оптимальное расписание и соответствующее значение <tex>f_{max}</tex>.
  
:Вставим определение функции <tex> \omega_\varphi : \omega_\varphi(P) = \varphi(u_0) + \omega(u_0u_1) - \varphi(u_1) + \ldots + \varphi(u_{k-1}) + \omega(u_{k-1}u_k) - \varphi(u_k) </tex>
+
  '''<tex>\langle</tex>int, int[]<tex>\rangle</tex>''' decompose('''Block''' b, '''int[]''' schedule):
 +
    '''int''' e = b.end <font color = "darkgreen"> // e — время завершения работ блока B</font>
 +
    find l: f[l](e) = <tex> \min  \{f[j](e) \mid j \in B, \overline\exists\ k: jk \in E \} </tex>
 +
    '''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<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=
 +
Расписание для блока, построенное алгоритмом <tex>\mathrm{Decompose}</tex>, является корректным и оптимальным.
 +
|proof=
 +
Докажем сначала корректность.
  
:Заметим, что потенциалы все промежуточных вершин в пути сократятся. <tex> \omega_\varphi(P) = \varphi(u_0) + \omega(P) - \varphi(u_k)</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>, следует, что порядок выполнения будет правильным.
  
:По изначальному предположению: <tex>\omega(P) < \omega(Q)</tex>. С новой весовой функцией веса соответствующих путей будут:
+
Также для корректности требуется, чтобы работы выполнялись не раньше, чем они появляются. Так как время выполнения работы определяется в строках 5-9 алгоритма, которые соответствуют этому требованию, то условие выполняется.
  
:<tex>\omega_\varphi(P) = \varphi(a) + \omega(P) - \varphi(b)</tex>
+
Найдем теперь нижнюю оценку на <tex> f_{max} </tex>. Пусть <tex> f_{max}(J) </tex> — ответ для множества работ <tex> J </tex>.
  
:<tex>\omega_\varphi(Q) = \varphi(a) + \omega(Q) - \varphi(b)</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>\omega_\varphi(P) < \omega_\varphi(Q)</tex>
+
Также, так как в оптимальном решении какая-то работа без потомков обязательно заканчивается в блоке <tex> B </tex>, то <tex> f_{max}(J) \geqslant f_l(e) </tex>.
 +
 
 +
Отсюда следует <tex> f_{max}(J) \geqslant \max(f_l(e), \max\limits_{j \in J} f_{max}(J \setminus j)) </tex>. По псевдокоду алгоритма видно, что его ответ достигает этой нижней оценки.
 
}}
 
}}
  
=== Теорема о существовании потенциальной функции ===
+
=== Общий алгоритм ===
{{Теорема
 
|statement=  
 
  
В графе <tex>G</tex> нет отрицательных циклов <tex>\Leftrightarrow</tex> существует потенциальная функция <tex> \phi:\; \forall uv \in E\; \omega_\varphi(uv) \geqslant 0 </tex>
+
Выполним <tex>\mathrm{Modify}</tex>, после чего разобъем все множество работ на блоки и для каждого блока запустим <tex>\mathrm{Decompose}</tex>:
  
|proof=
+
  <tex>\langle</tex>'''int''', '''int[]'''<tex>\rangle</tex> makeSchedule('''int[]''' jobs):
 +
    '''int'''[] schedule <font color="darkgreen">// Расписание работ</font>
 +
    jobs = topSort(jobs)
 +
    '''int[]''' rm = modify(jobs)
 +
    ''sort jobs by'' rm ''values''
 +
    '''Blocks[]''' b = blocks(jobs.p, rm)
 +
    '''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>\Leftarrow </tex>: Рассмотрим произвольный <tex>C</tex> — цикл в графе <tex>G</tex>
+
Из доказанной ранее леммы следует, что <tex> f_{max}(\{ 1 \ldots n \}) = \max\limits_{j} f_{max}(B_j) </tex>, поэтому расписание для всего множества работ, поделенного на блоки, также будет оптимальным и корректным.
  
:По лемме, его вес равен <tex> \omega(C) = \omega_\varphi(C) - \varphi(u_0) - \varphi(u_0) = \omega_\varphi(C) \geqslant 0</tex>
+
== Время работы ==
 +
{{Теорема
 +
|statement=
 +
Время работы алгоритма MakeSchedule — <tex> O(n^2) </tex> операций.
 +
|proof=
 +
Обозначим за <tex> P(n) </tex> время, необходимое для выполнения алгоритма MakeSchedule на n работах. Очевидно, для корректно определенной функции P в силу структуры алгоритма должно выполняться неравенство:
  
<tex>\Rightarrow </tex>: Добавим фиктивную вершину <tex>s</tex> в граф, а также ребра <tex> s \to u </tex> весом <tex> 0 </tex> для всех <tex> u </tex>.
+
<tex> P(n) \geqslant сn + \sum\limits_{i = 1}^{k} P(n_i) </tex>
  
:Обозначим <tex>\delta(u,v)</tex> как минимальное расстояние между вершинами <tex>u,\; v</tex>, введем потенциальную функцию <tex> \phi </tex>
+
Здесь <tex> n_i </tex> - размер блока с номером <tex> i </tex>, построенного алгоритмом Blocks(). Заметим, что <tex> \sum\limits_{i = 1}^{k} n_i = n - 1</tex>.
  
: <tex>\phi(u) = \delta(s,u)</tex>
+
Если <tex> P(n) = an^2 </tex>, то имеем:
  
:Рассмотрим вес произвольного ребра <tex> uv \in E </tex>: <tex>\omega_\phi(uv) = \phi(u) + \omega(uv) - \phi(v) = \delta(s, u) + \omega(uv) - \delta(s, v)</tex>.
+
<tex> an^2 \geqslant cn + a \sum\limits_{i = 1}^{k} n_i^2 </tex>
  
:Поскольку <tex>\delta(s, u) + \omega(uv) </tex> {{---}} вес какого-то пути <tex> s \rightsquigarrow v </tex>, а <tex> \delta(s, v) </tex> {{---}} вес кратчайшего пути <tex> s \rightsquigarrow v</tex>, то <tex> \delta(s, u) + \omega(uv) \geqslant \delta(s, v) \Rightarrow \delta(s, u) + \omega(uv) - \delta(s, v) = \omega_\varphi(uv) \geqslant 0 </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 \geqslant cn </tex>
  
=== Псевдокод ===
+
Чтобы получить максимальную нижнюю оценку на <tex> a </tex>, оценим снизу <tex> \sum\limits_{i, j = 1}^{k} n_i n_j </tex>:
  
Предварительно построим граф  <tex>G' = (V',\;E')</tex>, где <tex>V' = V \cup \{s\}</tex>,  <tex>s \not\in V</tex>, а <tex>E' = E \cup \{(s,\;v): \omega(s, v) = 0,\ v \in V \}</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>
'''function''' Johnson(G): '''int[][]'''
 
    '''if''' BellmanFord<tex>(G',\;\omega,\;s)</tex> == ''false''
 
        print "Входной граф содержит цикл с отрицательным весом"
 
        '''return''' <tex>\varnothing</tex>
 
    '''else''' '''for''' <tex>v \in V'</tex>
 
        <tex>\varphi(v)</tex> = <tex>\delta(s,\;v)</tex> <font color = green>// <tex>\delta(s,\;v)</tex> вычислено алгоритмом Беллмана — Форда</font>
 
        '''for''' <tex>(u,\;v) \in E'</tex>
 
            <tex>\omega_\varphi(u,\;v)</tex> = <tex> \omega(u,\;v) + \varphi(u) - \varphi(v)</tex>
 
        '''for''' <tex>u \in V</tex>
 
            Dijkstra<tex>(G,\;\omega_\varphi,\;u)</tex>
 
            '''for''' <tex>v \in V</tex>
 
                <tex>d_{uv} \leftarrow \delta_\varphi(u,\;v) + \varphi(v) - \varphi(u)</tex>
 
        '''return''' <tex>d</tex>
 
  
Итого, в начале алгоритм Форда-Беллмана либо строит потенциальную функцию такую, что после перевзвешивания все веса ребер будут неотрицательны, либо выдает сообщение о том, что в графе присутствует отрицательный цикл.
+
Значит, при <tex> a \geqslant \dfrac{cn}{2} \cdot \dfrac{4}{nk} = \dfrac{2c}{k} </tex> требуемое неравенство будет выполняться.
  
Затем из каждой вершины запускается алгоритм Дейкстры для составления искомой матрицы. Так как все веса ребер теперь неотрицательны, алгоритм Дейкстры будет работать корректно. А поскольку перевзвешивание таково, что кратчайшие пути относительно обеих весовых функций совпадают, алгоритм Джонсона в итоге корректно найдет все кратчайшие пути между всеми парами вершин.
+
}}
 
 
== Сложность ==
 
Алгоритм Джонсона работает за <tex>O(VE + VD)</tex>, где <tex>O(D)</tex> — время работы [[Алгоритм Дейкстры| алгоритма Дейкстры]]. Если в алгоритме Дейкстры неубывающая очередь с приоритетами реализована в виде [[Фибоначчиевы кучи| фибоначчиевой кучи]], то время работы алгоритма Джонсона есть <tex>O(V^2\log V + V E)</tex>. В случае реализации очереди с приоритетами в виде двоичной кучи время работы равно <tex>O(V E \log V)</tex>.
 
  
== См. также ==
+
==См. также==
* [[Алгоритм Дейкстры]]
+
*[[Правило_Лаулера|Правило Лаулера]]
* [[Алгоритм Форда-Беллмана]]
 
* [[Алгоритм Флойда]]
 
  
== Источники информации ==
+
==Источники информации==
* ''Кормен Т., Лейзерсон Ч., Ривест Р.'' Алгоритмы: построение и анализ. 2-е изд. — М.: Издательский дом «Вильямс», 2007. — С. 1296.
+
* Peter Brucker. «Scheduling Algorithms» {{---}} «Springer», 2006 г. {{---}} 63-67 стр. {{---}} ISBN 978-3-540-69515-8
* [http://rain.ifmo.ru/cat/view.php/vis/graph-paths/johnson-2001 Визуализатор алгоритма]
 
  
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Кратчайшие пути в графах ]]
+
[[Категория: Теория расписаний]]

Текущая версия на 02:18, 5 июня 2016

[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