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> j </tex> зависит от <tex> i </tex>, то, очевидно, она не может быть начата раньше, чем закончится выполнение <tex> i </tex>, поэтому нужно заменить <tex> r_j </tex> на <tex> \max(r_j, r_i + p_i) </tex>. Алгоритм, делающий это, представлен ниже (работы рассматриваются в порядке [[Использование_обхода_в_глубину_для_топологической_сортировки|топологической сортировки]]):
'''int[]''' modify('''int''' jobs[n]):
rm = copy(r)
'''for''' u = 1 '''to''' 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]
'''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>\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)
'''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>
