Изменения

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

=== Препроцессинг ===Для начала, модифицируем времена появления работ. Если работа <tex> j </tex> зависит от <tex> i </tex>, то, очевидно, она не может быть начата раньше, чем закончится выполнение <tex> i </tex>, поэтому нужно заменить <tex> r_j </tex> на <tex> \max(r_j, r_i + p_i) </tex>. Алгоритм, делающий это, представлен ниже (работы рассматриваются в порядке [[Использование_обхода_в_глубину_для_топологической_сортировки|топологической сортировки]]):  Modify'''int[]''' modify('''int''' jobs[n]): rm = copy(r) '''for''' i u = 1 '''to''' n '''for''' j: ij (u, v) <tex> \in E </tex>E rrm[jv] = max(rrm[jv], rrm[iu] + p[iu]) '''return''' rm

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

=== Blocks Разбиение на блоки ===Здесь и далее считается, что работы отсортированы в порядке неубывания модифицированных <tex> r_i rm_i </tex>.

'''Структура блока''' '''struct''' Block '''int''' start Blocks<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{ 1 start}</tex> и <tex>\ldots n mathrm{time}</tex>. Используется для читаемости и уменьшения кода <tex>\mathrm{Decompose} </tex>. Можно воспринимать как макроподстановку. '''Алгоритм разбиения'''  '''Block[]''' blocks('''int''' p[n], '''int''' rm[n]): '''int''' j = 0 '''int''' t = 0<font color="darkgreen">// Переменная t указывает на время завершения последней работы </font> '''Block''' b[n]

'''if''' <tex> t < rrm[i] <font color="darkgreen">// Время появления очередной работы больше, чем время завершения последней </texfont> t = rrm[i] <font color="darkgreen">// работы в блоке, не можем начать её делать. Создаём новый блок </font>

Bb[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 b

Если алгоритм Blocks вызывается от пустого множествазначение <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): find '''int''' e = b.end <font color = "darkgreen"> // e — время завершения работ блока B<tex/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) G b.jobs.remove(l) '''Block[]''' g = Blocksblocks(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"> // Вставляем работу в расписание между блоками<tex/font> B \setminus schedule[b.start .. g[1].start - 1] = l <font color = "darkgreen"> /tex/ Нужно учесть пропуски перед первым и </font>) вставить schedule[g[g.size].end .. b.end - 1] = l в промежутки между блоками G, начиная с <texfont color = "darkgreen"> r_l // после последнего блоков соответственно</texfont> '''for''' B[j] b <tex>\in</tex> Gg ans = max(ans, Decomposedecompose(B[j]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 <tex>\langle</tex>'''int''', '''int[]'''<tex>\rangle</tex> makeSchedule('''int[]''' jobs): '''int'''[] schedule <font color="darkgreen">// Расписание работ</font> Modifyjobs = topSort(jobs) B '''int[]''' rm = modify(jobs) ''sort jobs by'' rm ''values'' '''Blocks[]''' b = blocks(<tex> \{1 \ldots n \} </tex>jobs.p, rm) '''int''' ans = <tex> -\infty </tex> '''for''' B[j] block <tex>\in</tex> Bb ans = max(ans, Decomposedecompose(B[j]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 \cfracdfrac{nk}{4}</tex>

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

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

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