317
правок
Изменения
→Идея
<tex>S</tex> выполнимо тогда и только тогда, когда все работы в EDD расписании выполняются без опозданий. Это прямое следствие из уже теоремы 4.4 (Брукер). Если в <tex>S</tex> содержится <tex>n</tex> работ, то построение EDD расписание может быть выполнено за <tex>O(n \log n)</tex> времени. Наша задача сводится к тому, чтобы найти выполнимое множество работ с максимальным суммарным весом.
Для данного непустого множества <tex>S</tex> определим следующие величины:
:<tex>r(S) = \min\limits_{i \in S} r_{i} ; p(S) = \sum\limits_{i \in S} p_{i}; w(S) = \sum\limits_{i \in S} w_{i}</tex>
Кроме того, обозначим за <tex>C(S)</tex> время последней выполненной работы из <tex>S</tex> в EDD расписании. Оно состоит из периодов непрерывного выполнения работы, разделенных периодами бездействия, когда нет доступных работ для выполнения. Это означает, что <tex>S</tex> может быть разделено на множества <tex>S_{1} \ldots S_{x}</tex>, для которых выполняется <tex>C(S_{i}) = r(S_{i}) + p(S_{i}) < r(S_{i + 1})</tex> для <tex>i = 1 \ldots x - 1 </tex>.
Выполнимое множество <tex>S</tex> является '''блоком''' (англ. ''block''), если работы из <tex>S</tex> обрабатываются непрерывно с начала и до конца, и <tex>S</tex> не может быть разделен на подмножества, расписания для которых не пересекаются, например, если <tex>C(S) = r(S)+ p(S)</tex> и <tex>S</tex> не является объединением <tex>S_{1}</tex> и <tex>S_{2}</tex> таких, что <tex>C(S_{1}) < r(S_{2})</tex>. Решим задачу <tex dpi>1 \mid r_i, pmtn \mid \sum w_{i}U_{i}</tex> методами динамического программирования.
Введем величину <tex>C_{i}(r, w) = \min \{C(S) \mid S \subseteq \{ 1 \ldots i \} </tex> {{---}} выполнимое<tex>; r(S) \geqslant r; w(S) \geqslant w \}</tex> и <tex>C_{i}(r, w) = \infty</tex>, если множеств, удовлетворяющих условиям, нет.
==Источники информации==
