81
правка
Изменения
м
'''for''' j = schedule[g[i - 1].end '''to''' .. g[i].begin - 1 schedule[j] = l <font color = "darkgreen"> // Вставляем работу в расписание между блоками</font> schedule[b.begin to start .. g[1].begin start - 1] = l<font color = "darkgreen"> // Нужно учесть пропуски перед первым и </font> schedule[g[g.size].end to .. b.end - 1] = l<font color = "darkgreen"> // после последнего блоков соответственно</font>
→Декомпозиция
== Алгоритм ==
Работу будем обозначать просто ее номером <tex>(i)</tex>, при этом, номера работ могут меняться в зависимости от того, по какому параметру они отсортированы. Время появления работы — <tex> r[i]</tex>, время, требуемое для ее выполнения — <tex> p[i] </tex>. Множество ребер графа обозначается как <tex> E </tex>.
===Идея алгоритма===
Будем решать задачу рекурсивно. Разобьем множество работ на подмножества (блоки), внутри которых не будет перерыва между выполнением работ. После этого для каждого из блоков найдем работу, которую выгоднее всего выполнить последней, удалим работу из соответствующего блока и повторим разбиение на подблоки для оставшихся работ. Пустые промежутки между подблоками, полученными из данного блока, заполним выбранной работой. Повторим рекурсивно для каждого из полученных подблоков. Как будет показано далее, данный алгоритм строит корректное и оптимальное расписание. Можно заметить, что если на каждом этапе будет получаться всего один блок, алгоритм выродится в [[Правило_Лаулера|алгоритм Лаулера]].
=== Препроцессинг ===
Для начала, модифицируем времена появления работ. Если работа <tex> j </tex> зависит от <tex> i </tex>, то, очевидно, она не может быть начата раньше, чем закончится выполнение <tex> i </tex>, поэтому нужно заменить <tex> r_j </tex> на <tex> \max(r_j, r_i + p_i) </tex>. Алгоритм, делающий это, представлен ниже (работы рассматриваются в порядке [[Использование_обхода_в_глубину_для_топологической_сортировки|топологической сортировки]]):
'''voidint[]''' modify('''int''' jobs[n]): rm = copy(r)
'''for''' u = 1 '''to''' n
'''for''' (u, v) <tex> \in </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>, поэтому, при рассмотрении работ в порядке неубывания времен их появления, они также будут топологически отсортированы.
'''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 < rrm[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>.
=== Декомпозиция ===
Допустим, у нас есть блок работ, который можно выполнить без прерываний. Общая идея алгоритма <tex>\mathrm{Decompose}</tex> следующая: найдем работу <tex> i </tex>, которую выгоднее всего выполнить последней. Разобъем оставшееся множество работ на блоки, решим задачу для этих блоков рекурсивно и вставим <tex> i </tex> в промежутки между ними, до них и после них, начиная с <tex> 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(<tex> b \setminus l </tex>.jobs.p, b.jobs.rm)
'''for''' i = 2 '''to''' g.size
'''for''' b <tex>\in</tex> g
ans = max(ans, decompose(b, schedule).first)
=== Общий алгоритм ===
Выполним <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''' b[j] block <tex>\in</tex> b ans = max(ans, decompose(b[j]block,schedule).first)
'''return''' <tex>\langle</tex>ans, schedule<tex>\rangle</tex>
