Изменения

|definition=Задача <texwikitex> 1 Дано $n$ работ, которые надо выполнить на одной машине, причем $i$-ая работа выполняется $p_i$ времени. Для каждой работы задана монотонно неубывающая функция $f_i$. Работы можно прерывать, у каждой работы есть время появления $r_{i}$. Также между работами заданы отношения в виде ориентированного графа без циклов: если существует ребро $a \mid precto b$, pmtnто работа $a$ должна завершиться до начала выполнения работы $b$. Необходимо построить такое расписание, r_i \mid чтобы величина $f_{max} </tex> является обобщением [[Правило Лаулера|<tex>1 = \mid prec max\mid f_limits_{j=1..n}{f_j(C_j)}$, где $C_j$ {{max---}}время окончания выполнения $j$-ой работы, была минимальна.</texwikitex>]], но здесь у работ также есть времена появления, раньше которых их делать запрещено, и их можно прерывать.

Работу будем обозначать просто ее номером (<tex> (i )</tex>), при этом, номера работ могут меняться в зависимости от того, по какому параметру они отсортированы. Время появления работы — <tex> r_i r[i]</tex>, время, требуемое для ее выполнения — <tex> p_i 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''' Для начала, модифицируем времена появления работ. Если работа <tex> j </tex> зависит от <tex> i </tex> \in \{ 1 \ldots n \} , то, очевидно, она не может быть начата раньше, чем закончится выполнение <tex> i </tex> '''for''' j: ij , поэтому нужно заменить <tex> \in E r_j </tex> на <tex> r_j \leftarrow \max(r_j, r_i + p_i) </tex> . Алгоритм, делающий это, представлен ниже (работы рассматриваются в порядке [[Использование_обхода_в_глубину_для_топологической_сортировки|топологической сортировки]]):

После выполнения этого алгоритма для любых двух работ <tex> i, j </tex>, таких '''int[]''' modify('''int''' jobs[n]): rm = copy(r) '''for''' u = 1 '''to''' n '''for''' (u, что v) <tex> j \in </tex> зависит от <tex> i </tex>, выполняется <tex> r_j > r_i </tex>, поэтому, при рассмотрении работ в порядке неубывания времен их появленияE rm[v] = max(rm[v], они также будут топологически отсортированы.rm[u] + p[u]) '''return''' rm

После выполнения этого алгоритма для любых двух работ <tex> i, j </tex>, таких, что <tex> j </tex> зависит от <tex> i </tex>, выполняется <tex> rm[j] > rm[i] </tex>, поэтому, при рассмотрении работ в порядке неубывания времен их появления, они также будут топологически отсортированы. === Blocks Разбиение на блоки ===Здесь и далее считается, что работы отсортированы в порядке неубывания модифицированных <tex> r_i rm_i </tex>.

'''Структура блока''' '''struct''' Block '''int''' start Blocks(<texfont color = "darkgreen"> \{ 1 \ldots n \} // Время начала выполнения блока</texfont>) '''int''' time <texfont color = "darkgreen"> j \leftarrow 0 // Время, затрачиваемое на соответствующий блок</texfont> '''int''' end <texfont color = "darkgreen"> t \leftarrow 0 // Время конца выполнения блока </texfont> '''forint[]''' jobs <texfont color = "darkgreen"> i \in \{ 1 \ldots n \} // Номера работ</texfont> '''ifvoid''' add() <texfont color = "darkgreen"> t < r_i // Добавляет работу в конец jobs[] </texfont> Нетрудно заметить, что переменная <tex> t \leftarrow r_i mathrm{end}</tex> получается из суммы <tex> j \leftarrow j + 1 mathrm{start}</tex> и <tex> B_j \leftarrow B_j \cup i mathrm{time}</tex> . Используется для читаемости и уменьшения кода <tex> t \leftarrow t + p_i 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>n</tex> равно нулю, то считаем, что алгоритм <tex>\mathrm{Blocks}</tex> возвращает пустое множество. Определим время начала блока <tex> B_j </tex> как <tex>s_j = \min\limits_{i \in B_j} r_i rm_i </tex>, а время конца — как <tex> e_j = s_j + \sum\limits_{i \in B_j} p_i </tex>.

Существует оптимальное расписание, такое, что все во все временные интервалы <tex> [s_j; e_j] </tex>, соответствующие блокам <tex> B_j </tex>, построенным алгоритмом <tex>\mathrm{Blocks}</tex>, станок работает без простоя.

Возьмем некоторую работу <tex> i </tex>, такую, что она начинается позже, чем в момент времени <tex> s </tex>, не имеет в графе зависимостей предков, завершаемых позже, чем в момент <tex> s </tex> и <tex> r_i rm_i \le leqslant s </tex>. Такая работа обязательно существует, иначе для множества работ, выполняемых позже, чем в момент <tex> s </tex>, было бы <tex> r = \min\limits_{k \in T} r_k 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 Декомпозиция ===Допустим, у нас есть блок работ, который можно выполнить без прерываний. Общая идея алгоритма <tex>\mathrm{Decompose }</tex> следующая: найдем работу <tex> i </tex>, которую выгоднее всего выполнить последней. Разобъем оставшееся множество работ на блоки, решим задачу для этих блоков рекурсивно и вставим <tex> i </tex> в промежутки между ними, до них и после них, начиная с <tex> r_i rm_i </tex>. Псевдокод этого алгоритма представлен ниже. Алгоритм принимает множество блоков и изначально пустое расписание, при каждом вызове заполняет пробелы в расписании очередной работой и обновляет ответ. Возвращает оптимальное расписание и соответствующее значение <tex>f_{max}</tex>.

Decompose '''<tex>\langle</tex>int, int[]<tex>\rangle</tex>''' decompose(B'''Block''' b, '''int[]''' schedule): найти '''int''' e = b.end <texfont color = "darkgreen"> // e — время завершения работ блока B</font> find l: f_lf[l](e) = <tex> \min \{f_jf[j](e) \mid j \in B, \overline\exists\ k: jk \in E \} </tex> '''int''' ans <tex> \leftarrow f_l= f[l](e) </tex> G 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<texfont color = "darkgreen"> \leftarrow // Вставляем работу в расписание между блоками</texfont> Blocks( schedule[b.start .. g[1].start - 1] = l <texfont color = "darkgreen"> B \setminus l // Нужно учесть пропуски перед первым и </texfont>) вставить schedule[g[g.size].end .. b.end - 1] = l в промежутки между блоками G, начиная с <texfont color = "darkgreen"> r_l // после последнего блоков соответственно</texfont> '''for''' b <tex>B_j \in G </tex>:g ans = max(ans, Decomposedecompose(<tex> B_j </tex>b, schedule).first) '''return''' <tex>\langle</tex>ans, schedule<tex>\rangle</tex>

Расписание для блока, построенное алгоритмом <tex>\mathrm{Decompose}</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> r_l rm_l </tex>, будут помещены в блок <tex> B_0 </tex>, следует, что порядок выполнения будет правильным.

Также для корректности требуется, чтобы работы выполнялись не раньше, чем они появляются. Так как время выполнения работы определяется только в строке 4 строках 5-9 алгоритма, которая соответствует которые соответствуют этому требованию, то условие выполняется.

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

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

Отсюда следует <tex> f_{max}(J) \ge geqslant \max(f_l(e), \max\limits_{j \in J} f_{max}(J \setminus j)) </tex>. По псевдокоду алгоритма видно, что его ответ достигает этой нижней оценки.

Выполним <tex>\mathrm{Modify}</tex>, после чего разобъем все множество работ на блоки и для каждого блока запустим <tex>\mathrm{Decompose()}</tex>:

MakeSchedule() Modify() B <tex> \leftarrow langle</tex> Blocks('''int''', '''int[]'''<tex> \{1 \ldots n \} rangle</tex>makeSchedule('''int[]''' jobs): ans '''int'''[] schedule <texfont color="darkgreen"> \leftarrow // Расписание работ</texfont> 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> B_j \in B</tex>):b ans = max(ans, Decomposedecompose(<tex> B_j </tex>block,schedule).first) '''return''' <tex>\langle</tex>ans, schedule<tex>\rangle</tex>

<tex> P(n) \ge geqslant сn + \sum\limits_{i = 1}^{k} P(n_i) </tex>

<tex> an^2 \ge geqslant cn + a \sum\limits_{i = 1}^{k} n_i^2 </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 geqslant cn </tex>

<tex> \sum\limits_{\substack{i, j = 1\\ i \ne j}}^{k} n_i n_j \ge 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) \ge geqslant \dfrac{nk}{4}</tex>

Значит, при <tex> a \ge geqslant \dfrac{ccn}{2} \cdot \dfrac{n4}{\dfrac{nk}{4}} = \dfrac{2c}{k} </tex> требуемое неравенство будет выполняться.

==См. также==*[[Правило_Лаулера|Правило Лаулера]] ==Источникиинформации==* Peter Brucker. «Scheduling Algorithms» {{---}} «Springer», 2006 г. {{---}} 379 63-67 стр. {{---}} ISBN 978-3-540-69515-8

[[Категория: Дискретная математика Алгоритмы и алгоритмыструктуры данных]]