1632
правки
Изменения
м
rollbackEdits.php mass rollback
{{Лемма
|statement=
Существует оптимальное расписание, в котором время начала каждой работы <tex>t_j</tex> принадлежит множеству:
<tex>T=\{r_i + l \cdot p \mid i = 1, \dots, n; l = 0, \dots, n - 1\}</tex>
# <tex>\max \{W_{k - 1} (s, e), W'_k (s, e)\} \leqslant W^*_k (s, e)</tex>
#: Так как <tex>U_{k - 1} (s, e) \subseteq U_k (s, e)</tex>, то <tex>W_{k - 1} (s, e) = W^*_{k - 1} (s, e) \leqslant W^*_k (s, e)</tex>. Кроме того, если <tex>W'_k (s, e) > 0</tex>, то существует такое время <tex>s' \mid \max \{r_k, s + p\} \leqslant s' \leqslant \min \{d_k, e\} - p</tex>, что:
#:<tex>W'_k (s, e) = w_k + W_{k - 1} (s, s') + W_{k - 1} (s', e) = w_k + W^*_{k - 1} (s, s') + W^*_{k - 1} (s', e) \leqslant W^*_k (s, s'e)</tex>
#:
#: Неравенство выполняется, так как <tex>w_k + W^*_{k - 1} (s, s') + W^*_{k - 1} (s', e)</tex> - суммарный вес расписания, состоящего из:
== Прочие задачи ==
Идеи данного алгоритма могут быть использованы и для некоторых других задач. Ф. Баптист(''Philippe Baptiste''), его автор, показал, что задача <tex>1 \mid r_i; p_i = p; pmtn \mid \sum w_i U_i</tex> может быть решена за <tex>O(n^{10})</tex>.
== См. также ==
