Изменения

Перейти к: навигация, поиск

1ripmtnsumwu

2355 байт добавлено, 22:35, 8 июня 2016
м
Идея
{{Задача
|definition=Дана задача на нахождение расписания:
# У нас есть несколько работ, которе которые необходимо выполнит выполнить на одном станке.# У работ есть время появления <tex>r_i</tex>.
# Работы разрешается прерывать в любой момент времени.
# Все значения целочисленны, веса <tex>w_{i}</tex> положительны.
=== Идея ===
Пусть работы заданы в порядке неубывания их дедлайнов, то есть <tex>d_1 \leqslant d_2 \leqslant \ldots \leqslant d_n</tex>. За <tex>k</tex> обозначим количество различных <tex>r_{i}</tex>. За <tex>W = \sum^{n}_\limits_{j=1}^{n} {w_j}</tex>
Назовем множество работ <tex>S</tex> '''выполнимым''' (англ. ''feasible''), если существует такое расписание для работ из <tex>S</tex>, что все работы будут выполнены без опозданий. Чтобы проверить, является ли множество работ выполнимым, воспользуемся упрощенной версией <tex>\mathrm{EDD }</tex> правила (см<ref>Peter Brucker «Scheduling Algorithms», fifth edition, Springer — с. стр 70 в Брукере</ref> (<tex>\mathrm{EDD}</tex> (''earliest due date'') правило {{---}} правило наименьшего срока):
:''Составим расписание работ таким образом, чтобы первой в расписании стояла работа с наименьшим значением <tex>r_{i}</tex>. В любой момент времени, когда появляется новая работа, либо заканчивает выполняться текущая, вставим в расписание работу с наименьшим оставшимся сроком.''
<tex>S</tex> выполнимо тогда и только тогда, когда все работы в <tex>\mathrm{EDD }</tex> расписании выполняются без опозданий. Это прямое следствие из уже теоремы 4.4 (Брукер)<ref>Peter Brucker «Scheduling Algorithms», fifth edition, Springer — с. 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} ; </tex>* <tex>p(S) = \sum\limits_{i \in S} p_{i}; </tex>* <tex>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>C_{i}(r, w) = \min \{C(S) \mid S \subseteq \{ 1 \ldots i \} </tex> {{---}} выполнимое, причём выполняется <tex>; r(S) \geqslant r; \wedge w(S) \geqslant w \}</tex> и <tex>C_{i}(r, w) = \infty</tex>, если множеств, удовлетворяющих условиям, нет.
Максимальный вес выполнимого множества задается максимальным значением <tex>w</tex> такого, что <tex>C_{n}(r_{\min}, w)</tex> конечно, где <tex>r_{\min} = \min\limits_{j = 1 \ldots n} r_{i}</tex>. Посчитаем значения <tex>C_{j}(r, w)</tex> за <tex>n</tex> итераций с начальными значениями:
:<tex>C_{0}(r, 0) = 0</tex> для всех <tex>r</tex>
:<tex>C_{0}(r, w) = \infty</tex> для всех <tex>r</tex> и <tex>w > 0</tex>
<tex>j</tex> не может содержаться в выполнимом множестве, если <tex>r(S) > r_{j}</tex>. Следовательно,
:<p>
<tex>C_{j}(r, w)
\left \{\begin{array}{ll} = C_{j - 1}(r, w) , & \text{if } r > r_{j} \\
\leqslant C_{j - 1}(r, w), & \text{otherwise} \end{array} \right.
</tex>
Отсюда следует, что нам нужно посчитать только такие значения <tex>C_{j} (r, w)</tex> для которых <tex>r \leqslant r_{j}</tex>. Пусть <tex> S \subseteq \{ 1 \ldots j \} </tex> и <tex>C_{j}(r, w) = C(S)</tex>. Если <tex>j \notin S</tex>, тогда <tex>C_{j}(r, w) = C_{j - 1}(r, w)</tex>. Иначе рассмотрим два случая.
=== Разбор случаев === ==== Первый случай ====
Работа <tex>j</tex> начинается после <tex>C(S \setminus \{j\})</tex>.
Рассмотрим два подслучая, для : # <tex>C(S \setminus \{j\}) \leqslant r_{j}</tex> и <br> В этом случае <tex>C(S \setminus \) = r_{j\}) > r_+ p_{j}</tex>.# В первом случае <tex>C(S) = r_\setminus \{j\} + p_) > r_{j}</tex># Во втором работы <br>Работы из <tex>C(S \setminus \{j\})</tex> обрабатываются непрерывно в интервале <tex>[r_{j}, C(S \setminus \{j\})]</tex>, потому что иначе <tex>j</tex> начнет обрабатываться до <tex>C(S \setminus \{j\})</tex>.
Делаем вывод, что <tex>C_{j} (r, w) = \max(r_{j} , C(S \setminus \{j\}) + p_{j}</tex>. Предположим, что <tex>C(S \setminus \{j\})</tex> такое, что <tex>C(S \setminus \{j\}) = C_{j - 1}(r, w - w_{j})</tex> и, если это не так, заменим <tex>C(S \setminus \{j\})</tex> на выполнимое подмножество из <tex>1 \ldots j - 1</tex> для которого это выполняется. Из этого следует, что
:<tex>C_{j}(r, w) = \max(r_{j} , C_{j - 1}(r, w − w_{j})) + p_{j}</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>.
:<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>.
=== Конечная формула ===
Собирая все написаное выше, приходим к рекуррентной формуле:
:<p>
В этой формуле внутренняя минимизация берется по всем различным датам появления <tex>r' > r_j</tex> таких, что <tex>r' = r(S') \in \{ r1 \ldots r_{j - 1} \} </tex> и целочисленным значениям <tex>w'</tex>, <tex>0 \leqslant w' < w - w_j</tex>. Важно, что формула корректна только в том случае, если правая часть не превышает <tex>d_j</tex> и, если это не так, то <tex> C_{j}(r, w) = \infty</tex>.
 
=== Конечная формула ===
Рассмотрим, как посчитать значения <tex>P_{j - 1}(r, r', w'')</tex> для <tex>r \leqslant r_j < r'</tex> и <tex>0 \leqslant w'' < W</tex>. Если <tex>w'' = 0</tex>, то <tex>P_{j - 1}(r, r', w'') = 0</tex>. Иначе значение <tex>P_{j - 1}(r, r', w'')</tex> можно посчитать, используя непустое множество <tex>S'' \subseteq \{ 1 \ldots j - 1\}</tex>. Если <tex>r (S'') > r</tex>, то<tex>P_{j - 1}(r, r', w'') = P_{j - 1}(r(S''), r', w'')</tex>. Кроме того, в общем случае, заметим, что выполнятся
</p>
С начальными значениями:
: <tex>P_{j - 1}(r, r', 0) = 0</tex> для <tex>j = 1 \ldots n</tex>
: <tex>P_{0}(r, r', w'') = \infty</tex> для <tex>w'' > 0\ldots n</tex>
=== Ассимптотика ===
На каждой из <tex>n</tex> итераций для <tex>j = 1 \ldots n </tex> существует <tex>O(k^2W)</tex> вычислямых значений <tex>P_{j - 1}(r, r', w'')</tex>, по одному на каждую комбинацию из <tex>r, r', w''</tex>. По представленной выше формуле, каждое значение <tex>P_{j - 1}(r, r', w'')</tex> находится с помощью минимизации из <tex>O(W)</tex> выборов <tex>w' < w''</tex>. Следовательно, время, требуемое для вычисления значений <tex>P_{j - 1}(r, r', w'')</tex>, ограниченно <tex>O(k^2W^2)</tex> на каждой итерации. Всего нам нужно посчитать <tex>O(kW)</tex> значений <tex>C_j(r,w)</tex>, по одному на каждую комбинацию <tex>r</tex> и <tex>w</tex>. Из формулы, приведенной для второго случаявычисления <tex>C_j(r,w)</tex>, каждое значение <tex>C_j(r,w)</tex> считается с помощью минимизации <tex>O(kW)</tex> выборов <tex>r', w'</tex>. Следовательно, время, требуемое для вычисления значений <tex>C_j(r,w)</tex> на каждой итерации, ограниченно <tex>O(k^2W^2)</tex>. Максимальный вес вычислимого множества может быть посчитан с помощью нахождения максимального значения <tex>w</tex> такого, что <tex>C_n(r_{\min},w)</tex> {{---}} конечно. Сделать это мы можем за <tex>O(W)</tex>. Итоговая сложность составляет <tex>O(nk^2W^2)</tex>.
Чтобы создать вычислимое множество с максимальным весом, мы считаем характеристический вектор, учитывая значения <tex>P_{j - 1}(r, r', w'')</tex> и <tex>C_j(r,w)</tex>. Вычисляем веторы за <tex>O(n^2k^2W)</tex>, это значение меньше, чем <tex>O(nk^2W^2)</tex>.
=== Специальные случаи ===
Если времена появления и дедлайны идут в одинаковом порядке, то есть <tex>r_1 \leqslant r_2 \leqslant \ldots \leqslant r_n</tex> и <tex>d_1 \leqslant d_2 \leqslant \ldots \leqslant d_n</tex>, то второй случай никогда не возникает. В этом случае, формула для вычисления <tex>C_j(r,w)</tex> может быть упрощена:
:<p>
<tex>C_{j}(r, w) = \min
\left \{\begin{array}{ll} C_{j - 1}(r, w) \\
\max \{r_j, C_{j - 1}(r, w - w_j) \} + p_j \end{array} \right.
</tex>
</p>
Либо, если мы примем <tex>C_{j}(w) = C_{j}(r_{\min}, w)</tex>, то:
:<p>
<tex>C_{j}(w) = \min
\left \{\begin{array}{ll} C_{j - 1}(w) \\
\max \{r_j, C_{j - 1}(w - w_j) \} + p_j \end{array} \right.
</tex>
</p>
 
Отсюда следует, что мы делаем <tex>O(nW)</tex> вычислений в этом случае, когда максимальный вес вычислимого множества <tex>w</tex> такой, что <tex>C_{n}(w)</tex> {{---}} конечно. В случае, если все веса одинаковы, но время уменьшается до <tex>O(n^2)</tex>.
 
Когда все времена появления работ равны нулю, рекурретная формула упрощается до
:<tex>C_j(w) = \min \{ C_{j - 1}(w), C_{j - 1}(w - w_{j}) + p_j\} </tex>
 
Отсюда следует альтернативное решение для задачи [[1sumwu|<tex>1 \mid\mid \sum w_j U_j</tex>]], которое работает за <tex>O(n\sum w_j)</tex>.
 
==См. также==
*[[1precpmtnrifmax|<tex>1 \mid prec,pmtn,r_i \mid f_{max}</tex>]]
*[[1sumwu| <tex>1 \mid\mid \sum w_i U_i</tex>]]
 
==Примечания==
 
<references />
==Источники информации==

Навигация