317
правок
Изменения
→Второй случай
В этом случае существует простой в 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>. Используя данную запись, количество времен доступнух для обработки работы <tex>j</tex> в интервале <tex>[r_j, r(S')]</tex> записывается формулой:<tex>(r(S') - r_j) - P_{j - 1}(r, r(S'), w - w_j - w(S'))</tex>. Количество готовности работы (какое количество уже сделано) <tex>j</tex> после времени:<tex>\max(0, p_j - (r(S') - r_j) + P_{j - 1}(r, r(S'), w - w_j - w(S'))</tex>. И время выполнения последней работы <tex>j</tex> из <tex>S</tex>:<tex>C_j(r,w) = \min\limits_{r', w'} \{ C_{j - 1}(r', w') + \max \{ 0, p_j - r' + r_j + P_{j - 1}(r, r', w - w_j - w' \} \}</tex>.
=== Конечная формула ===
