Изменения

<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> (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'''int[]''' modify('''int''' jobs[n]): rm = copy(r) 1 '''for''' i <tex> \in \{ u = 1 \ldots '''to''' n \} </tex> 2 '''for''' j: ij (u, v) <tex> \in E </tex>E 3 <tex> r_j \leftarrow \ rm[v] = max(r_jrm[v], r_i rm[u] + p_ip[u]) </tex> '''return''' rm

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

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

'''Структура блока''' '''struct''' Block '''int''' start Blocks(<texfont color = "darkgreen"> \{ 1 \ldots n \} // Время начала выполнения блока</texfont>) 1 '''int''' time <texfont color = "darkgreen"> j \leftarrow 0 // Время, затрачиваемое на соответствующий блок</texfont> 2 '''int''' end <texfont color = "darkgreen"> t \leftarrow 0 // Время конца выполнения блока </texfont> 3 '''forint[]''' jobs <texfont color = "darkgreen"> i \in \{ 1 \ldots n \} // Номера работ</texfont> 4 '''ifvoid''' add() <font color = "darkgreen">// Добавляет работу в конец jobs[] </font> Нетрудно заметить, что переменная <tex> t < r_i \mathrm{end}</tex> 5 получается из суммы <tex> t \leftarrow r_i mathrm{start}</tex> 6 и <tex> j \leftarrow j + 1 mathrm{time}</tex> 7 . Используется для читаемости и уменьшения кода <tex> B_j \leftarrow B_j \cup i mathrm{Decompose}</tex>. Можно воспринимать как макроподстановку. '''Алгоритм разбиения'''  '''Block[]''' blocks('''int''' p[n], '''int''' rm[n]): '''int''' j = 0 8 '''int''' t = 0 <texfont color="darkgreen"> // Переменная t \leftarrow указывает на время завершения последней работы </font> '''Block''' b[n] '''for''' i = 1 '''to''' n '''if''' t + p_i < rm[i] <font color="darkgreen">// Время появления очередной работы больше, чем время завершения последней </texfont> t = rm[i] 9 return <texfont color="darkgreen"> {B_1// работы в блоке, \ldotsне можем начать её делать. Создаём новый блок </font> j = j + 1 b[j].start = rm[i] b[j].time = 0 b[j].add(i) <font color="darkgreen">// Добавляем к последнему блоку рассматриваемую работу, B_j} </texfont> b[j].time = b[j].time + p[i] <font color="darkgreen">// увеличиваем суммарное время внутри блока и текущее время</font> t = t + p[i] '''return''' 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\limitslimits_{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): 1 найти '''int''' e = b.end <font color = "darkgreen"> // e — время завершения работ блока B<tex/font> find l: f_lf[l](e) = <tex> \min \{f_jf[j](e) \mid j \in B, \overline\exists\ k: jk \in E \} </tex> 2 '''int''' ans <tex> \leftarrow f_l= f[l](e) </tex> 3 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>) 4 вставить schedule[g[g.size].end .. b.end - 1] = l в промежутки между блоками G, начиная с <texfont color = "darkgreen"> r_l // после последнего блоков соответственно</texfont> 5 '''for''' b <tex>B_j \in G </tex>:g 6 ans = max(ans, Decomposedecompose(b, schedule).first) '''return''' <tex> B_j \langle</tex>)) 7 return 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() 1 Modify() 2 B <tex> \leftarrow langle</tex> Blocks('''int''', '''int[]'''<tex> \{1 \ldots n \} rangle</tex>makeSchedule('''int[]''' jobs): 3 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> 4 '''for (''' block <tex> B_j \in B</tex>):b 5 ans = max(ans, Decomposedecompose(block,schedule).first) '''return''' <tex> B_j \langle</tex>)) 6 return 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 \fracdfrac{nk}{4}</tex>

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

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

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