32
правки
Изменения
м
{{Определение|id = def1|definition = Для любых <tex>t_u, t_v \in \Theta, u \leqslant v, </tex> и для любого <tex>k \in [1, n]:</tex>#положим <tex>U_k(t_u, t_v) = \{J_i \mid i < k \wedge t_u <= r_i < t_v\}</tex> <tex>-</tex> это множество работ, индекс которых меньше <tex>k</tex> и чьи <tex>r_i</tex> лежать в интервале <tex>[t_u, t_v);.</tex>#Также определим <tex>W_k(t_u, t_v, m)</tex> <tex>-</tex> как максимальный вес множества работ <tex>Z \subset U_k(t_u, t_v), |Z| = m</tex> такой, что <tex>m \in (1, \dots ,n)</tex> и расписание от <tex>Z</tex> разрешимо и заканчивается до <tex>t_v</tex>. Если такое <tex>Z</tex> существует, будем говорить, что <tex>Z</tex> реализует <tex>W_k(t_u, t_v, m)</tex>. Если же такого <tex>Z</tex> нет, то <tex>W_k(t_u, t_v, m) = - \infty.</tex>}} Будем основывать динамику на следующей лемме.
→Псевдокод: убрал фигурную скобку
=== Динамика ===
{{Лемма
'''else'''
<tex>W'_k = </tex> Подсчитать <tex>W'_k</tex> по формуле из леммы
<tex>W_k (t_u, t_v, m) = \max(W_{k - 1} (t_u, t_v, m), W'_k\})</tex>
'''return''' <tex>\max\limits_{i \in [1, \dots, n]}(W_n(\min\limits_{t \in \Theta} (t - p), \max\limits_{t \in \Theta} (t), i))</tex>
*[http://www.lix.polytechnique.fr/~baptiste/jsched98.pdf Philippe Baptiste <tex>-</tex> Polynomial Time Algorithms for Minimizing the Weighted Number of Late Jobs on a Single Machine with Equal Processing Times]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Теория расписаний]]
