81
правка
Изменения
м
→Декомпозиция
'''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
schedule[g[i-1].end..g[i].begin - 1] = l <font color = "darkgreen">// Вставляем работу в расписание между блоками</font> schedule[b.start to .. 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)
