689
правок
Изменения
→Blocks: +доказательство
=== Blocks ===
Здесь и далее считается, что работы отсортированы в порядке неубывания модифицированных <tex> r_i </tex>.
Станок, выполняющий работы, выполняет работу в некоторые интервалы времени и простаивает в остальное время. Следующий алгоритм разбивает множество работ на блоки, внутри которых станок работает без простоя.
Blocks(<tex> \{ 1 \ldots n \} </tex>)
6 <tex> j \leftarrow j + 1 </tex>
7 <tex> B_j \leftarrow B_j \cup i </tex>
8 <tex> t \leftarrow t + p_i </tex> 9 return <tex> {B_1, \ldots, B_j} </tex> Определим время начала блока <tex> B_j </tex> t как <tex>s_j = \min\limits_{i \in B_j} r_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>, построенным алгоритмом Blocks, станок работает без простоя.|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>p_i , не имеет в графе зависимостей предков, завершаемых позже, чем в момент <tex> s </tex> и <tex> r_i \le s </tex>. Такая работа обязательно существует, иначе для множества работ, выполняемых позже, чем в момент <tex> s </tex>, было бы <tex> r = \min\limits{k \in T} r_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 ===
