748
правок
Изменения
→Описание алгоритма
Рассмотрим работы в порядке не убывания дедлайнов: <tex>d_{1} \leqslant d_{2} \leqslant \ldots \leqslant d_{n}</tex>. Пусть мы нашли решение для работ <tex>1, 2, \ldots, i-1</tex>. Очевидно, что <tex>S \subseteq \{1, \ldots i-1\}</tex>.
Пусть <tex>h^S</tex> {{---}} вектор соответствующий множеству <tex>S</tex> из задачи [[Opij1di|<tex> O \mid p_{i,j} = 1, d_i \mid - </tex>]]. Тогда, для добавления работы <tex>i</tex> в множество <tex>S</tex> должно выполняться неравенство: <tex>m(d_i-m)-(km-\sum\limits_{j=1}^m {h^S(d_i-m+j)})+x(d_i) \geqslant m</tex>, где <tex>k=|S|</tex> и <tex>x(d_i)</tex> {{---}} номер периода количество периодов времени <tex>t</tex>, чтобы со свойствами: <tex>d_i-m+1 \leqslant t \leqslant d_i</tex> и <tex>h^S(t) < m</tex>. Чтобы проверить это неравенство, нам нужно <tex>m</tex> чисел <tex>h^S(t), t=d_i-m+1, \ldots, d_i</tex>.
Определим переменные:
