317
правок
Изменения
→Второй случай
=== Второй случай ===
Работа <tex>j</tex> начинается перед <tex>C(S \setminus \{j\})</tex>.
В этом случае существует простой в EDD расписании для множества <tex>C(S \setminus \{j\})</tex> после <tex>r_{j}</tex>. Пусть <tex>S'</tex> {{---}} последний блок в <tex>C(S \setminus \{j\})</tex>, то есть <tex>r(S') = \max\{r(B) \mid B </tex> является блоком в <tex> C(S \setminus \{j\}) \} </tex>. Тогда <tex>r(S') \geqslant r_{j}</tex>, в таком случае обязано выполняться равенство <tex>C(S') = C_{j - 1}(r(S'), w(s'))</tex>, иначе расписание для <tex>S</tex> будет не оптимально.
Кроме того, мы можем предположить, что общее количество сделанных работ в <tex>(S \setminus \{j\}) \setminus S'</tex>, лежащих в интервале <tex>[r_{j}, r(S')]</tex>, {{---}} минимально, учитвая выполнимые множества <tex>S \subseteq \{1 \ldots j \}</tex> такие, что <tex>r(S'') \geqslant r, C(S'') \leqslant r(S'), w(S'') \geqslant w - w_{j} - w(S')</tex>.
Пусть <tex>r, r'</tex> {{---}} даты появления <tex>r \leqslant r_{j} < r</tex>, и <tex>w''</tex> {{---}} некоторое целочисленное значение <tex>0 \leqslant w'' < W</tex>. За <tex>P_{j - 1}(r, r', w'')</tex> возьмем минимальное число выполненных работ в итервале <tex>[r_{j}, r']</tex>, учитвая выполнимые множества <tex>S \subseteq \{1 \ldots j \}</tex> такие, что <tex>r(S'') \geqslant r, C(S'') \leqslant r', w(S'') \geqslant w''</tex>. Если таких выполнимых множеств нет, то <tex>P_{j - 1}(r, r', w'') = \infty</tex>.
=== Конечная формула ===
