1632
правки
Изменения
м
rollbackEdits.php mass rollback
<tex dpi = "200" >1 \mid r_i, p_i = 1 \mid \sum f_i</tex>
Для каждой работы задана монотонно неубывающая функция <tex>f_i</tex>. Необходимо минимизировать <tex> \sum f_i, </tex> где каждая <tex>f_i</tex> считается на значении времени завершения выполнения задания с номером <tex>i</tex>.
==Решение==
А именно, покажем, что решение задачи состоит в сопоставлении <tex>n</tex> различным заданиям различных времен начала выполнения работы. Если сопоставляем работе <tex>i</tex> время <tex>t</tex>, то вклад в целевую функцию будет <tex> f_i(t + 1) </tex>.
Далее будет показано, что при построении оптимального расписания нам нужно будет рассмотреть всего <tex>n</tex> различных времен начала работ. Следовательно, подобная задача может быть решена за <tex>\mathcal{O}(n^3)</tex>.
Поскольку <tex>f_i</tex> {{---}} монотонно неубывающие функции, то это значит, что в оптимальном расписании работы должны начинать исполняться как можно раньше. Первые <tex>n</tex> самых ранних для начала исполнения времен <tex>t_i</tex> могут быть вычислены следующим алгоритмом :
{{Лемма
|id=lemma1
|statement= Существует Пусть значения <tex>t_i</tex> вычислены приведенным выше алгоритмом. Тогда существует оптимальное расписание <tex>S,</tex> в котором все <tex>n</tex> задач распределены по всем временам <tex>t_i (i = 1\ldots n).</tex>, которые выбирает приведенный выше алгоритм.|proof= Предположим, что в некоторое оптимальное расписание <tex>S</tex> входят времена <tex> t_1 \ldots t_j, </tex> где <tex> j < n,</tex> и из а вместо <tex>t_{j+1}</tex> времени используется какое-то другое. Из всех возможных таких оптимальных расписаний мы возьмем то, у которого <tex>j</tex> будет максимально.
Из того, как в алгоритме выбирались значения для <tex>t_i</tex> следует, что <tex>t_{j + 1}</tex> {{---}} минимальное возможное время, большее <tex>t_j,</tex> в которое можно начать выполнять какое-нибудь из оставшихся заданий. Если во время <tex>t_{j+1}</tex> в расписании <tex>S</tex> не выполняется никакого задания, то какое-то задание, которое могло бы выполнится в момент времени <tex>t_{j+1}</tex> выполняется в <tex>S</tex> позднее. Значит оно может быть перемещено в нашем расписании <tex>S</tex> на время <tex>t_{j+1}</tex> без увеличения целевой функции. Таким образом, наше новое расписание тоже будет оптимальным. Получили противоречие с максимальностью <tex>j</tex>. Значит из всех оптимальных расписаний нам подходят только те, в которых <tex>j = n</tex>.
}}
==Частный случай==
В случае, когда все времена появлений заданий различны, оптимальное решение может быть посчитано за <tex>\mathcal{O}(n\log n) </tex>.
Поскольку любое задание выполняется за единицу времени, а все функции <tex>f_i</tex> являются неубывающими, то будет достаточно отсортировать работы по возрастанию времен появления и выполнять каждую работу как только она появится. Поскольку все <tex>r_i</tex> различны, то промежутки выполнения работ не будут пересекаться {{---}} расписание будет корректным.
== Примеры ==
===Пример 1===
Даны четыре задания.
<tex>r_1 = 3, f_1 = 5t </tex>
<tex>r_2 = 2, f_2 = t^2 </tex>
<tex>r_3 = 4, f_3 = t + 4 </tex>
<tex>r_4 = 1, f_4 = 2^t </tex>
Отсортируем задания по неубыванию <tex>r_i</tex>, а дальше будем выполнять их по мере появления. В полученном расписании работы будут идти в порядке <tex>4, 2, 1, 3</tex> и давать в ответе <tex>2^{1 + 1} + (2 + 1)^2 + 5(3 + 1) + (4 + 1) + 4 = 42 </tex>, что является оптимальным результатом.
===Пример 2===
Пусть у нас есть три задания, и каждое из них имеет время появления <tex>r_i = 0.</tex>
Заданы функции <tex>f_i</tex>:
<tex>f_1(t) = t^2 </tex>
<tex>f_2(t) = t^3 </tex>
<tex>f_3(t) = 3 ^ t </tex>
Поступить как в предыдущем примере и просто отсортировать работы мы теперь не можем {{---}} не понятно, в каком порядке сортировать задания с одинаковым временем появления.
Тогда нужно по приведенному в начале алгоритму посчитать времена, когда мы можем начать выполнять задания. В результате получим: <tex>t_1 = 0, t_2 = 1, t_3 = 2</tex>.
Тогда, согласно алгоритму, задача сведется к следующей задаче о назначениях:
<tex>
\begin{tabular}{c||ccc}
$t_i$ $\backslash$ i & 1 & 2 & 3 \\
\hline
\hline
0 & 1 & $\mathbf{1}$ & 3 \\
1 & 4 & 8 & $\mathbf{9}$ \\
2 & $\mathbf{9}$ & 27 & 27\\
\hline
\end{tabular}
</tex>
В результате работы [[Венгерский алгоритм решения задачи о назначениях | Венгерского алгоритма]] будет выбран порядок работ <tex>2, 3, 1</tex>, что даст лучший результат {{---}} <tex>19</tex>.
На этом примере хорошо видно, что решение, выбирающие в каждый момент времени <tex>t_i</tex> несделанную работу с минимальным значением <tex>f_i(t_i + 1)</tex> будет давать плохой результат.
===Пример 3===
Пусть у нас есть четыре задания, определенные следующим образом:
<tex>r_1 = 0, f_1(t) = t^2 </tex>
<tex>r_2 = 0, f_2(t) = 2t </tex>
<tex>r_3 = 1, f_3(t) = 2 ^ t </tex>
<tex>r_4 = 5, f_3(t) = t + 2 </tex>
Работы уже отсортированы, поэтому посчитаем времена <tex>t_i</tex> для выполнения заданий. Получим: <tex>t_1 = 0, t_2 = 1, t_3 = 2, t_4 = 4</tex>.
Таблица, необходимая для решения задачи, будет построена так, что если работа с номером <tex>i</tex> ещё не доступна в момент времени <tex>t_j</tex>, то в соответствующей ячейке будет стоять <tex>\infty</tex>.
<tex>
\begin{tabular}{c||cccc}
$t_i$ $\backslash$ i & 1 & 2 & 3 & 4 \\
\hline
\hline
0 & $\mathbf{1}$ & 2 & $\infty$ & $\infty$ \\
1 & 4 & 4 & $\mathbf{4}$ & $\infty$ \\
2 & 9 & $\mathbf{6}$ & 8& $\infty$ \\
4 & 25 & 10 & 32 & $\mathbf{7}$ \\
\hline
\end{tabular}
</tex>
В результате будет выбран порядок работ <tex>1, 3, 2, 4</tex>, и все работы выполнятся за <tex>18</tex> единиц времени.
==См. также ==
* [[Классификация задач]]
* [[1precpmtnrifmax|<tex>1 \mid prec, pmtn, r_i \mid f_{\max}</tex>]]
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 19 - 20
[[Категория: Дискретная математика Алгоритмы и алгоритмыструктуры данных]]
[[Категория: Теория расписаний]]
