Изменения

Работу будем обозначать просто ее номером (<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'''void''' modify({1...n}) rm = 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])

После выполнения этого алгоритма для любых двух работ <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(<texfont color = "darkgreen">// Время начала выполнения блока</font> '''int''' time <font color = "darkgreen">// Время, затрачиваемое на соответствующий блок</font> '''int''' end <font color = "darkgreen"> // Время конца выполнения блока</font> '''int[]''' jobs <font color = "darkgreen">// Номера работ</font> \ '''Алгоритм разбиения'''  '''Block''' blocks({ 1 \ldots ...n \} </tex>) '''int''' j = 0 '''int''' t = 0 '''Block[]''' b

'''if''' <tex> t < r[i] </tex> t = rrm[i]

Bb[j].start = r[i] Bb[j].time = 0 Bb[j].add(i) Bb[j].time = Bb[j].time + p[i]

'''return''' B b

Если алгоритм <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 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>. Псевдокод этого алгоритма представлен ниже.

Decompose '''int''' decompose(B'''Block''' b) '''int''' e = Bb.end <font color = "darkgreen"> //e — время завершения работ блока B.</font> find <tex> 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 Block g = Blocksblocks(<tex> B b \setminus l </tex>) '''for''' i = 2 '''to''' Gb.size '''for''' j = Gg[i - 1].end '''to''' Gg[i].begin - 1 schedule[j] = l <font color = "darkgreen"> //Вставляем работу в расписании между блоками</font> schedule[Gg[Gg.size].end to Bb.end - 1] = l '''for''' Bb[j] <tex>\in</tex> Gg ans = max(ans, Decomposedecompose(Bb[j]))

Убедимся, что порядок выполнения работ, заданный графом зависимостей, не нарушается. Заметим, что в разбиении <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>, следует, что порядок выполнения будет правильным.

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

MakeSchedule ('''int''', '''int[]''') ModifymakeSchedule('''Job[]''' jobs) B '''int'''[] schedule <font color= Blocks(<tex"darkgreen"> \{1 \ldots n \} // Расписание работ</texfont> topSort(jobs) modify(jobs) b = blocks(jobs) '''int''' ans = <tex> -\infty </tex> '''for''' Bb[j] <tex>\in</tex> Bb ans = max(ans, Decomposedecompose(Bb[j])) '''return''' (ans, schedule)