317
правок
Изменения
Нет описания правки
Пусть работы заданы в порядке неубывания их дедлайнов, то есть <tex>d_1 \leqslant d_2 \leqslant \ldots \leqslant d_n</tex>. За <tex>k</tex> обозначим количество различных <tex>r_{i}</tex>. За <tex>W = \sum\limits_{j = 1}^{n} {w_j}</tex>
Назовем множество работ <tex>S</tex> '''выполнимым''' (англ. ''feasible''), если существует такое расписание для работ из <tex>S</tex>, что все работы будут выполнены без опозданий. Чтобы проверить, является ли множество работ выполнимым, воспользуемся упрощенной версией <tex>\mathrm{EDD }</tex> правила<ref>см. стр 70 в Брукере</ref> (<tex>\mathrm{EDD }</tex>{{---}} правило наименьшего срока (англ. ''earliest due date''):
:''Составим расписание работ таким образом, чтобы первой в расписании стояла работа с наименьшим значением <tex>r_{i}</tex>. В любой момент времени, когда появляется новая работа, либо заканчивает выполняться текущая, вставим в расписание работу с наименьшим оставшимся сроком.''
<tex>S</tex> выполнимо тогда и только тогда, когда все работы в <tex>\mathrm{EDD }</tex> расписании выполняются без опозданий. Это прямое следствие из уже теоремы 4.4 <ref>см. стр 70 в Брукере</ref>. Если в <tex>S</tex> содержится <tex>n</tex> работ, то построение <tex>\mathrm{EDD }</tex> расписание может быть выполнено за <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> в <tex>\mathrm{EDD }</tex> расписании. Оно состоит из периодов непрерывного выполнения работы, разделенных периодами бездействия, когда нет доступных работ для выполнения. Это означает, что <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>j</tex> начинается перед <tex>C(S \setminus \{j\})</tex>.
В этом случае существует простой в <tex>\mathrm{EDD }</tex> расписании для множества <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>.
