Изменения

<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()=== Препроцессинг === 1 '''for''' Для начала, модифицируем времена появления работ. Если работа <tex> j </tex> зависит от <tex> i </tex> \in \{ 1 \ldots n \} , то, очевидно, она не может быть начата раньше, чем закончится выполнение <tex> i </tex> 2 '''for''' j: ij , поэтому нужно заменить <tex> \in E r_j </tex> 3 на <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

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

=== Разбиение на блоки ===Здесь и далее считается, что работы отсортированы в порядке неубывания модифицированных <tex> rm_i </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>. Можно воспринимать как макроподстановку. '''Алгоритм разбиения'''  '''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=Существует оптимальное расписание, такое, что все во все временные интервалы <tex> [s_j; e_j] </tex>, соответствующие блокам <tex> B_j </tex>, построенным алгоритмом <tex>\mathrm{Blocks}</tex>, станок работает без простоя.|proof=Возьмем произвольное оптимальное расписание <tex> S </tex>, в нем деление на блоки может также быть произвольным. Найдем первый такой временной интервал <tex> [s_j; e_j] </tex>, что в <tex> S </tex> есть период простоя внутри <tex> [s_j; e_j] </tex> (если таких периодов несколько, будем рассматривать первый из них). Обозначим его за <tex> [s; e] </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>\mathrm{Decompose}</tex> следующая: найдем работу <tex>i</tex>, которую выгодно выгоднее всего выполнить последней. Разобъем оставшееся множество работ на блоки, решим задачу для этих блоков рекурсивно и вставим <tex> i </tex> в промежутки между этими блокаминими, до них и после них, начиная с <tex> r_i rm_i </tex>. Псевдокод этого алгоритма представлен ниже. Алгоритм принимает множество блоков и изначально пустое расписание, при каждом вызове заполняет пробелы в расписании очередной работой и обновляет ответ. Возвращает оптимальное расписание и соответствующее значение <tex>f_{max}</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> 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>, следует, что порядок выполнения будет правильным. Также для корректности требуется, чтобы работы выполнялись не раньше, чем они появляются. Так как время выполнения работы определяется в строках 5-9 алгоритма, которые соответствуют этому требованию, то условие выполняется. Найдем теперь нижнюю оценку на <tex> f_{max} </tex>.Пусть <tex> f_{max}(J) </tex> — ответ для множества работ <tex> J </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> 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>. По псевдокоду алгоритма видно, что его ответ достигает этой нижней оценки.}}

Выполним <tex>\mathrm{Modify()}</tex>, после чего разобъем все множество работ на блоки и для каждого блока запустим <tex>\mathrm{Decompose}</tex>:  <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> 1 \mid prec, pmtn, r_i \mid f_{max} </tex>() 1 Modify() 2 B = Blocks(<tex> \{1 \ldots n \} </tex>) 3 ans = - <tex> \infty </tex> 4 for max\limits_{j} f_{max}(<tex> B_i \in </tex> BB_j): 5 ans = <tex> \max </tex> (ans, Decompose(<tex> B_i </tex>)) 6 return ansпоэтому расписание для всего множества работ, поделенного на блоки, также будет оптимальным и корректным.

Лемма: {{Теорема|statement=Время работы алгоритма MakeSchedule — <tex> O(n^2) </tex> операций.|proof=Обозначим за <tex> P(n) </tex> время работы , необходимое для выполнения алгоритма MakeSchedule на n работах. Очевидно, для корректно определенной функции P в силу структуры алгоритма должно выполняться неравенство: <tex> P(n) \geqslant сn + \sum\limits_{i = 1 }^{k} P(n_i) </tex> Здесь <tex> n_i </tex> - размер блока с номером <tex> i </tex>, построенного алгоритмом Blocks(). Заметим, что <tex> \sum\mid preclimits_{i = 1}^{k} n_i = n - 1</tex>. Если <tex> P(n) = an^2 </tex>, pmtn, r_i то имеем: <tex> an^2 \geqslant cn + a \sum\mid f_limits_{i = 1}^{maxk} n_i^2 </tex> —  Так как <tex> On^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> \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> Значит, при <tex> a \geqslant \dfrac{cn}{2} \cdot \dfrac{4}{nk} = \dfrac{2c}{k} </tex> требуемое неравенство будет выполняться. }} ==См. также==*[[Правило_Лаулера|Правило Лаулера]] ==Источники информации==* Peter Brucker. «Scheduling Algorithms» {{---}} «Springer», 2006 г. {{---}} 63-67 стр.{{---}} ISBN 978-3-540-69515-8 [[Категория: Алгоритмы и структуры данных]][[Категория: Теория расписаний]]