1ripmtnsumwu — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Первый случай)
м (Идея)
(не показано 40 промежуточных версий 1 участника)
Строка 3: Строка 3:
 
{{Задача
 
{{Задача
 
|definition=Дана задача на нахождение расписания:
 
|definition=Дана задача на нахождение расписания:
# У нас есть несколько работ, которе необходимо выполнит на одном станке.
+
# У нас есть несколько работ, которые необходимо выполнить на одном станке.
# У работ есть время появления <tex>r_i</tex>
+
# У работ есть время появления <tex>r_i</tex>.
 
# Работы разрешается прерывать в любой момент времени.
 
# Работы разрешается прерывать в любой момент времени.
 
# Все значения целочисленны, веса <tex>w_{i}</tex> положительны.
 
# Все значения целочисленны, веса <tex>w_{i}</tex> положительны.
Строка 13: Строка 13:
  
 
=== Идея ===
 
=== Идея ===
Пусть работы заданы в порядке неубывания их дедлайнов, то есть <tex>d_1 \leqslant d_2 \leqslant \ldots \leqslant d_n</tex>. За <tex>k</tex> обозначим количество различных <tex>r_{i}</tex>.
+
Пусть работы заданы в порядке неубывания их дедлайнов, то есть <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>, что все работы будут выполнены без опозданий. Чтобы проверить, является ли множество работ выполнимым, воспользуемся упрощенной версией EDD правила (см. стр 70 в Брукере):  
+
Назовем множество работ <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>r_{i}</tex>. В любой момент времени, когда появляется новая работа, либо заканчивает выполняться текущая, вставим в расписание работу с наименьшим оставшимся сроком.''
  
<tex>S</tex> выполнимо тогда и только тогда, когда все работы в EDD расписании выполняются без опозданий. Это прямое следствие из уже теоремы 4.4 (Брукер). Если в <tex>S</tex> содержится <tex>n</tex> работ, то построение EDD расписание может быть выполнено за <tex>O(n \log n)</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>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>r(S) =  \min\limits_{i \in S} r_{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>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>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>, если множеств, удовлетворяющих условиям, нет.
+
Введем величину <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>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, 0) = 0</tex> для всех <tex>r</tex>  
 
:<tex>C_{0}(r, w) = \infty</tex> для всех <tex>r</tex> и <tex>w > 0</tex>
 
:<tex>C_{0}(r, w) = \infty</tex> для всех <tex>r</tex> и <tex>w > 0</tex>
  
<tex>j</tex> не может содержаться в выполнимом множестве, если <tex>r(S) > r_{j}</tex>. Следовательно,  
+
<tex>j</tex> не может содержаться в выполнимом множестве, если <tex>r(S) > r_{j}</tex>. Следовательно,
 
:<p>
 
:<p>
 
<tex>C_{j}(r, w)  
 
<tex>C_{j}(r, w)  
\left \{\begin{array}{ll} = C_{j - 1}(r, w)  & \text{if } r > r_{j} \\
+
\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.  
 
\leqslant  C_{j - 1}(r, w), & \text{otherwise} \end{array} \right.  
 
</tex>
 
</tex>
Строка 43: Строка 45:
 
Отсюда следует, что нам нужно посчитать только такие значения <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>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>j</tex> начинается после <tex>C(S \setminus \{j\})</tex>.  
  
Рассмотрим два подслучая, для <tex>C(S \setminus \{j\}) \leqslant r_{j}</tex> и <tex>C(S \setminus \{j\}) > r_{j}</tex>.
+
Рассмотрим два подслучая:
# В первом случае <tex>C(S) = r_{j} + p_{j}</tex>
+
# <tex>C(S \setminus \{j\}) \leqslant r_{j}</tex> <br> В этом случае <tex>C(S) = r_{j} + p_{j}</tex>
# Во втором работы из <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(S \setminus \{j\}) > 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(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>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>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>.
  
 
=== Конечная формула ===
 
=== Конечная формула ===
 +
Собирая все написаное выше, приходим к рекуррентной формуле:
 +
:<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  \\
 +
\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'  \} \} \end{array} \right.
 +
</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>. Кроме того, в общем случае, заметим, что выполнятся
 +
:<tex>P_{j - 1}(r, r', w'') \leqslant P_{j - 1}(r^+, r', w'')</tex>.
 +
Где за <tex>r^+</tex> берется наименьшая дата появления, меньшая чем <tex>r</tex>, если такая существует.
 +
 +
Если <tex>r(S'') = r</tex>, то пусть <tex>S' \subseteq S''</tex> будет блоком <tex>S''</tex> таким, что <tex>r(S') = r</tex>. Можно предположить, что <tex>C(S') = C_{j - 1}(r, w(S'))</tex>. Следовательно, общее количество сделанной работы из <tex>S'</tex> в интервале <tex>[r_j, r']</tex> будет равно
 +
:<tex>\max \{ 0, C_{j - 1}(r, w(S')) - r_j \} </tex>.
 +
 +
Пусть <tex>r''</tex> будет наименьшей датой появления, меньшей или равной <tex>C_{j - 1}(r, w(S'))</tex>. Тогда общее количество сделанной работы в <tex>S'' \setminus S' </tex> в интервале <tex>[r_j, r']</tex> будет равно <tex>P_{j - 1}(r'', r', w'' - w(S'))</tex>. Следовательно, общее количество сделанной работы в <tex>S''</tex> в интервале <tex>[r_j, r']</tex> будет равно
 +
:<tex>\max \{ 0, C_{j - 1}(r, w(S')) - r_j\} + P_{j - 1}(r'', r', w'' - w(S'))</tex>.
 +
 +
Правая часть выражения должна быть минимальной для множеств <tex>S', S'' \setminus S'</tex> и <tex>r(S') = r, C(S') \leqslant r( S'' \setminus S') = r'', w(S') + w( S'' \setminus S') = w''</tex>. Собирая все вместе, получим формулу
 +
:<p>
 +
<tex>P_{j - 1}(r, r', w'') = \min
 +
\left \{\begin{array}{ll} P_{j - 1}(r^+, r', w'') \\
 +
\min\limits_{0 < w' \leqslant w''} \{ \max \{ 0, C_{j - 1}(r, w') - r_j \} + P_{j - 1}(r'', r', w'' - w')\} \end{array} \right.
 +
</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>w</tex> такого, что <tex>C_n(r_{\min},w)</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 />
  
 
==Источники информации==
 
==Источники информации==

Версия 22:35, 8 июня 2016

[math]1 \mid r_i, pmtn \mid \sum w_{i}U_{i}[/math]


Задача:
Дана задача на нахождение расписания:
  1. У нас есть несколько работ, которые необходимо выполнить на одном станке.
  2. У работ есть время появления [math]r_i[/math].
  3. Работы разрешается прерывать в любой момент времени.
  4. Все значения целочисленны, веса [math]w_{i}[/math] положительны.
Требуется выполнить все работы, чтобы значение [math]\sum w_i U_i[/math] (суммарный вес просроченных работ) было минимальным.


Описание алгоритма

Идея

Пусть работы заданы в порядке неубывания их дедлайнов, то есть [math]d_1 \leqslant d_2 \leqslant \ldots \leqslant d_n[/math]. За [math]k[/math] обозначим количество различных [math]r_{i}[/math]. За [math]W = \sum\limits_{j = 1}^{n} {w_j}[/math]

Назовем множество работ [math]S[/math] выполнимым (англ. feasible), если существует такое расписание для работ из [math]S[/math], что все работы будут выполнены без опозданий. Чтобы проверить, является ли множество работ выполнимым, воспользуемся упрощенной версией [math]\mathrm{EDD}[/math] правила [1] ([math]\mathrm{EDD}[/math] (earliest due date) правило — правило наименьшего срока):

Составим расписание работ таким образом, чтобы первой в расписании стояла работа с наименьшим значением [math]r_{i}[/math]. В любой момент времени, когда появляется новая работа, либо заканчивает выполняться текущая, вставим в расписание работу с наименьшим оставшимся сроком.

[math]S[/math] выполнимо тогда и только тогда, когда все работы в [math]\mathrm{EDD}[/math] расписании выполняются без опозданий. Это прямое следствие из теоремы 4.4 [2]. Если в [math]S[/math] содержится [math]n[/math] работ, то построение [math]\mathrm{EDD}[/math] расписание может быть выполнено за [math]O(n \log n)[/math] времени. Наша задача сводится к тому, чтобы найти выполнимое множество работ с максимальным суммарным весом.

Для данного непустого множества [math]S[/math] определим следующие величины:

  • [math]r(S) = \min\limits_{i \in S} r_{i} [/math]
  • [math]p(S) = \sum\limits_{i \in S} p_{i} [/math]
  • [math]w(S) = \sum\limits_{i \in S} w_{i}[/math]

Кроме того, обозначим за [math]C(S)[/math] время последней выполненной работы из [math]S[/math] в [math]\mathrm{EDD}[/math] расписании. Оно состоит из периодов непрерывного выполнения работы, разделенных периодами бездействия, когда нет доступных работ для выполнения. Это означает, что [math]S[/math] может быть разделено на множества [math]S_{1} \ldots S_{x}[/math], для которых выполняется [math]C(S_{i}) = r(S_{i}) + p(S_{i}) \lt r(S_{i + 1})[/math] для [math]i = 1 \ldots x - 1 [/math].

Выполнимое множество [math]S[/math] является блоком (англ. block), если работы из [math]S[/math] обрабатываются непрерывно с начала и до конца, и [math]S[/math] не может быть разделен на подмножества, расписания для которых не пересекаются, например, если [math]C(S) = r(S)+ p(S)[/math] и [math]S[/math] не является объединением [math]S_{1}[/math] и [math]S_{2}[/math] таких, что [math]C(S_{1}) \lt r(S_{2})[/math]. Решим задачу [math]1 \mid r_i, pmtn \mid \sum w_{i}U_{i}[/math] методами динамического программирования.

Введем величину [math]C_{i}(r, w) = \min \{C(S) \mid S \subseteq \{ 1 \ldots i \} [/math] — выполнимое, причём выполняется [math] r(S) \geqslant r \wedge w(S) \geqslant w \}[/math] и [math]C_{i}(r, w) = \infty[/math], если множеств, удовлетворяющих условиям, нет.

Максимальный вес выполнимого множества задается максимальным значением [math]w[/math] такого, что [math]C_{n}(r_{\min}, w)[/math] конечно, где [math]r_{\min} = \min\limits_{j = 1 \ldots n} r_{i}[/math]. Посчитаем значения [math]C_{j}(r, w)[/math] за [math]n[/math] итераций с начальными значениями:

[math]C_{0}(r, 0) = 0[/math] для всех [math]r[/math]
[math]C_{0}(r, w) = \infty[/math] для всех [math]r[/math] и [math]w \gt 0[/math]

[math]j[/math] не может содержаться в выполнимом множестве, если [math]r(S) \gt r_{j}[/math]. Следовательно,

[math]C_{j}(r, w) \left \{\begin{array}{ll} = C_{j - 1}(r, w), & \text{if } r \gt r_{j} \\ \leqslant C_{j - 1}(r, w), & \text{otherwise} \end{array} \right. [/math]

Отсюда следует, что нам нужно посчитать только такие значения [math]C_{j} (r, w)[/math] для которых [math]r \leqslant r_{j}[/math]. Пусть [math] S \subseteq \{ 1 \ldots j \} [/math] и [math]C_{j}(r, w) = C(S)[/math]. Если [math]j \notin S[/math], тогда [math]C_{j}(r, w) = C_{j - 1}(r, w)[/math]. Иначе рассмотрим два случая.

Разбор случаев

Первый случай

Работа [math]j[/math] начинается после [math]C(S \setminus \{j\})[/math].

Рассмотрим два подслучая:

  1. [math]C(S \setminus \{j\}) \leqslant r_{j}[/math]
    В этом случае [math]C(S) = r_{j} + p_{j}[/math]
  2. [math]C(S \setminus \{j\}) \gt r_{j}[/math]
    Работы из [math]C(S \setminus \{j\})[/math] обрабатываются непрерывно в интервале [math][r_{j}, C(S \setminus \{j\})][/math], потому что иначе [math]j[/math] начнет обрабатываться до [math]C(S \setminus \{j\})[/math].

Делаем вывод, что [math]C_{j} (r, w) = \max(r_{j} , C(S \setminus \{j\}) + p_{j}[/math]. Предположим, что [math]C(S \setminus \{j\})[/math] такое, что [math]C(S \setminus \{j\}) = C_{j - 1}(r, w - w_{j})[/math] и, если это не так, заменим [math]C(S \setminus \{j\})[/math] на выполнимое подмножество из [math]1 \ldots j - 1[/math] для которого это выполняется. Из этого следует, что

[math]C_{j}(r, w) = \max(r_{j} , C_{j - 1}(r, w − w_{j})) + p_{j}[/math].

Второй случай

Работа [math]j[/math] начинается перед [math]C(S \setminus \{j\})[/math].

В этом случае существует простой в [math]\mathrm{EDD}[/math] расписании для множества [math]C(S \setminus \{j\})[/math] после [math]r_{j}[/math]. Пусть [math]S'[/math] — последний блок в [math]C(S \setminus \{j\})[/math], то есть [math]r(S') = \max\{r(B) \mid B [/math] является блоком в [math] C(S \setminus \{j\}) \} [/math]. Тогда [math]r(S') \geqslant r_{j}[/math], в таком случае обязано выполняться равенство [math]C(S') = C_{j - 1}(r(S'), w(s'))[/math], иначе расписание для [math]S[/math] будет не оптимально.

Кроме того, мы можем предположить, что общее количество сделанной работы в [math](S \setminus \{j\}) \setminus S'[/math], лежащих в интервале [math][r_{j}, r(S')][/math], — минимально, учитвая выполнимые множества [math]S \subseteq \{1 \ldots j \}[/math] такие, что [math]r(S'') \geqslant r, C(S'') \leqslant r(S'), w(S'') \geqslant w - w_{j} - w(S')[/math].

Пусть [math]r, r'[/math] — даты появления [math]r \leqslant r_{j} \lt r[/math], и [math]w''[/math] — некоторое целочисленное значение [math]0 \leqslant w'' \lt W[/math]. За [math]P_{j - 1}(r, r', w'')[/math] возьмем минимальное число сделанной работы в итервале [math][r_{j}, r'][/math], учитвая выполнимые множества [math]S \subseteq \{1 \ldots j \}[/math] такие, что [math]r(S'') \geqslant r, C(S'') \leqslant r', w(S'') \geqslant w''[/math]. Если таких выполнимых множеств нет, то [math]P_{j - 1}(r, r', w'') = \infty[/math].

Используя данную запись, количество времен доступнух для обработки работы [math]j[/math] в интервале [math][r_j, r(S')][/math] записывается формулой

[math](r(S') - r_j) - P_{j - 1}(r, r(S'), w - w_j - w(S'))[/math].

Количество готовности работы (какое количество уже сделано) [math]j[/math] после времени

[math]\max(0, p_j - (r(S') - r_j) + P_{j - 1}(r, r(S'), w - w_j - w(S'))[/math].

И время выполнения последней работы [math]j[/math] из [math]S[/math]

[math]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' \} \}[/math].

Конечная формула

Собирая все написаное выше, приходим к рекуррентной формуле:

[math]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 \\ \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' \} \} \end{array} \right. [/math]

В этой формуле внутренняя минимизация берется по всем различным датам появления [math]r' \gt r_j[/math] таких, что [math]r' = r(S') \in \{ r1 \ldots r_{j - 1} \} [/math] и целочисленным значениям [math]w'[/math], [math]0 \leqslant w' \lt w - w_j[/math]. Важно, что формула корректна только в том случае, если правая часть не превышает [math]d_j[/math] и, если это не так, то [math] C_{j}(r, w) = \infty[/math].

Рассмотрим, как посчитать значения [math]P_{j - 1}(r, r', w'')[/math] для [math]r \leqslant r_j \lt r'[/math] и [math]0 \leqslant w'' \lt W[/math]. Если [math]w'' = 0[/math], то [math]P_{j - 1}(r, r', w'') = 0[/math]. Иначе значение [math]P_{j - 1}(r, r', w'')[/math] можно посчитать, используя непустое множество [math]S'' \subseteq \{ 1 \ldots j - 1\}[/math]. Если [math]r (S'') \gt r[/math], то[math]P_{j - 1}(r, r', w'') = P_{j - 1}(r(S''), r', w'')[/math]. Кроме того, в общем случае, заметим, что выполнятся

[math]P_{j - 1}(r, r', w'') \leqslant P_{j - 1}(r^+, r', w'')[/math].

Где за [math]r^+[/math] берется наименьшая дата появления, меньшая чем [math]r[/math], если такая существует.

Если [math]r(S'') = r[/math], то пусть [math]S' \subseteq S''[/math] будет блоком [math]S''[/math] таким, что [math]r(S') = r[/math]. Можно предположить, что [math]C(S') = C_{j - 1}(r, w(S'))[/math]. Следовательно, общее количество сделанной работы из [math]S'[/math] в интервале [math][r_j, r'][/math] будет равно

[math]\max \{ 0, C_{j - 1}(r, w(S')) - r_j \} [/math].

Пусть [math]r''[/math] будет наименьшей датой появления, меньшей или равной [math]C_{j - 1}(r, w(S'))[/math]. Тогда общее количество сделанной работы в [math]S'' \setminus S' [/math] в интервале [math][r_j, r'][/math] будет равно [math]P_{j - 1}(r'', r', w'' - w(S'))[/math]. Следовательно, общее количество сделанной работы в [math]S''[/math] в интервале [math][r_j, r'][/math] будет равно

[math]\max \{ 0, C_{j - 1}(r, w(S')) - r_j\} + P_{j - 1}(r'', r', w'' - w(S'))[/math].

Правая часть выражения должна быть минимальной для множеств [math]S', S'' \setminus S'[/math] и [math]r(S') = r, C(S') \leqslant r( S'' \setminus S') = r'', w(S') + w( S'' \setminus S') = w''[/math]. Собирая все вместе, получим формулу

[math]P_{j - 1}(r, r', w'') = \min \left \{\begin{array}{ll} P_{j - 1}(r^+, r', w'') \\ \min\limits_{0 \lt w' \leqslant w''} \{ \max \{ 0, C_{j - 1}(r, w') - r_j \} + P_{j - 1}(r'', r', w'' - w')\} \end{array} \right. [/math]

С начальными значениями:

[math]P_{j - 1}(r, r', 0) = 0[/math] для [math]j = 1 \ldots n[/math]
[math]P_{0}(r, r', w'') = \infty[/math] для [math]w'' \gt 0\ldots n[/math]

Максимальный вес вычислимого множества может быть посчитан с помощью нахождения максимального значения [math]w[/math] такого, что [math]C_n(r_{\min},w)[/math] — конечно.

Ассимптотика

На каждой из [math]n[/math] итераций для [math]j = 1 \ldots n [/math] существует [math]O(k^2W)[/math] вычислямых значений [math]P_{j - 1}(r, r', w'')[/math], по одному на каждую комбинацию из [math]r, r', w''[/math]. По представленной выше формуле, каждое значение [math]P_{j - 1}(r, r', w'')[/math] находится с помощью минимизации из [math]O(W)[/math] выборов [math]w' \lt w''[/math]. Следовательно, время, требуемое для вычисления значений [math]P_{j - 1}(r, r', w'')[/math], ограниченно [math]O(k^2W^2)[/math] на каждой итерации. Всего нам нужно посчитать [math]O(kW)[/math] значений [math]C_j(r,w)[/math], по одному на каждую комбинацию [math]r[/math] и [math]w[/math]. Из формулы, приведенной для вычисления [math]C_j(r,w)[/math], каждое значение [math]C_j(r,w)[/math] считается с помощью минимизации [math]O(kW)[/math] выборов [math]r', w'[/math]. Следовательно, время, требуемое для вычисления значений [math]C_j(r,w)[/math] на каждой итерации, ограниченно [math]O(k^2W^2)[/math]. Максимальный вес вычислимого множества может быть посчитан с помощью нахождения максимального значения [math]w[/math] такого, что [math]C_n(r_{\min},w)[/math] — конечно. Сделать это мы можем за [math]O(W)[/math]. Итоговая сложность составляет [math]O(nk^2W^2)[/math].

Чтобы создать вычислимое множество с максимальным весом, мы считаем характеристический вектор, учитывая значения [math]P_{j - 1}(r, r', w'')[/math] и [math]C_j(r,w)[/math]. Вычисляем веторы за [math]O(n^2k^2W)[/math], это значение меньше, чем [math]O(nk^2W^2)[/math].

Специальные случаи

Если времена появления и дедлайны идут в одинаковом порядке, то есть [math]r_1 \leqslant r_2 \leqslant \ldots \leqslant r_n[/math] и [math]d_1 \leqslant d_2 \leqslant \ldots \leqslant d_n[/math], то второй случай никогда не возникает. В этом случае, формула для вычисления [math]C_j(r,w)[/math] может быть упрощена:

[math]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. [/math]

Либо, если мы примем [math]C_{j}(w) = C_{j}(r_{\min}, w)[/math], то:

[math]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. [/math]

Отсюда следует, что мы делаем [math]O(nW)[/math] вычислений в этом случае, когда максимальный вес вычислимого множества [math]w[/math] такой, что [math]C_{n}(w)[/math] — конечно. В случае, если все веса одинаковы, но время уменьшается до [math]O(n^2)[/math].

Когда все времена появления работ равны нулю, рекурретная формула упрощается до

[math]C_j(w) = \min \{ C_{j - 1}(w), C_{j - 1}(w - w_{j}) + p_j\} [/math]

Отсюда следует альтернативное решение для задачи [math]1 \mid\mid \sum w_j U_j[/math], которое работает за [math]O(n\sum w_j)[/math].

См. также

Примечания

  1. Peter Brucker «Scheduling Algorithms», fifth edition, Springer — с. 70
  2. Peter Brucker «Scheduling Algorithms», fifth edition, Springer — с. 70

Источники информации

  • Peter Brucker «Scheduling Algorithms», fifth edition, Springer — с. 88-93 ISBN 978-3-540-69515-8