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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 16 промежуточных версий 3 участников)
Строка 1: Строка 1:
 
<tex dpi = "200" >1 \mid r_i, p_i = 1 \mid \sum f_i</tex>
 
<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>f_i</tex>. Необходимо минимизировать <tex> \sum f_i,</tex> где каждая <tex>f_i</tex> считается на значении времени завершения выполнения задания с номером <tex>i</tex>.
  
 
==Решение==
 
==Решение==
Строка 8: Строка 8:
 
А именно, покажем, что решение задачи состоит в сопоставлении <tex>n</tex> различным заданиям различных времен начала выполнения работы. Если сопоставляем работе <tex>i</tex> время <tex>t</tex>, то вклад в целевую функцию будет <tex> f_i(t + 1) </tex>.
 
А именно, покажем, что решение задачи состоит в сопоставлении <tex>n</tex> различным заданиям различных времен начала выполнения работы. Если сопоставляем работе <tex>i</tex> время <tex>t</tex>, то вклад в целевую функцию будет <tex> f_i(t + 1) </tex>.
  
Далее будет показано, что при построении оптимального расписания нам нужно будет рассмотреть всего <tex>n</tex> различных времен начала работ. Следовательно, подобная задача может быть решена за <tex>O(n^3)</tex>.
+
Далее будет показано, что при построении оптимального расписания нам нужно будет рассмотреть всего <tex>n</tex> различных времен начала работ. Следовательно, подобная задача может быть решена за <tex>\mathcal{O}(n^3)</tex>.
  
 
Поскольку <tex>f_i</tex> {{---}} монотонно неубывающие функции, то это значит, что в оптимальном расписании работы должны начинать исполняться как можно раньше. Первые <tex>n</tex> самых ранних для начала исполнения времен <tex>t_i</tex> могут быть вычислены следующим алгоритмом :  
 
Поскольку <tex>f_i</tex> {{---}} монотонно неубывающие функции, то это значит, что в оптимальном расписании работы должны начинать исполняться как можно раньше. Первые <tex>n</tex> самых ранних для начала исполнения времен <tex>t_i</tex> могут быть вычислены следующим алгоритмом :  
Строка 34: Строка 34:
 
{{Лемма
 
{{Лемма
 
|id=lemma1
 
|id=lemma1
|statement= Существует оптимальное расписание <tex>S</tex> в котором все <tex>n</tex> задач распределены по всем временам <tex>t_i (i = 1\ldots n)</tex>, которые выбирает приведенный выше алгоритм.
+
|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>j</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>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>]]
 
* [[1precpmtnrifmax|<tex>1 \mid prec, pmtn, r_i \mid f_{\max}</tex>]]
Строка 45: Строка 128:
 
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 19 - 20
 
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 19 - 20
  
[[Категория: Дискретная математика и алгоритмы]]
+
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Теория расписаний]]
 
[[Категория: Теория расписаний]]

Текущая версия на 19:42, 4 сентября 2022

[math]1 \mid r_i, p_i = 1 \mid \sum f_i[/math]

Для каждой работы задана монотонно неубывающая функция [math]f_i[/math]. Необходимо минимизировать [math] \sum f_i,[/math] где каждая [math]f_i[/math] считается на значении времени завершения выполнения задания с номером [math]i[/math].

Решение

Эта задача может быть решена сведением к решению задачи о назначениях. А именно, покажем, что решение задачи состоит в сопоставлении [math]n[/math] различным заданиям различных времен начала выполнения работы. Если сопоставляем работе [math]i[/math] время [math]t[/math], то вклад в целевую функцию будет [math] f_i(t + 1) [/math].

Далее будет показано, что при построении оптимального расписания нам нужно будет рассмотреть всего [math]n[/math] различных времен начала работ. Следовательно, подобная задача может быть решена за [math]\mathcal{O}(n^3)[/math].

Поскольку [math]f_i[/math] — монотонно неубывающие функции, то это значит, что в оптимальном расписании работы должны начинать исполняться как можно раньше. Первые [math]n[/math] самых ранних для начала исполнения времен [math]t_i[/math] могут быть вычислены следующим алгоритмом :

 отсортиртировать по неубыванию времена появления [math]r_i[/math]
 [math]t_1[/math] = [math]r_1[/math]
 for [math] i \in \{ 2 \ldots n \} [/math]
   [math]t_i[/math] = [math]\max(r_i, t_{i-1} + 1)[/math]


Для того, чтобы найти оптимальное расписание, построим полный двудольный граф, в котором будут доли [math]V_1 = \left \{ 1,\ldots,n \right\} и V_2 = \left \{ t_1,\ldots,t_n \right\}[/math] и ребра [math]c_{ij}[/math] между ними:

[math] c_{ij} = \left \{\begin{array}{ll} f_i(t_j + 1), & r_i \leqslant t_i \\ \infty, & \mathrm{otherwise} \end{array} \right. [/math]

Решив задачу о назначениях для данного графа, получим оптимальное расписание.

Доказательство корректности и оптимальности

Лемма:
Пусть значения [math]t_i[/math] вычислены приведенным выше алгоритмом. Тогда существует оптимальное расписание [math]S,[/math] в котором все [math]n[/math] задач распределены по всем временам [math]t_i (i = 1\ldots n).[/math]
Доказательство:
[math]\triangleright[/math]

Предположим, что в некоторое оптимальное расписание [math]S[/math] входят времена [math] t_1 \ldots t_j, [/math] где [math] j \lt n,[/math] а вместо [math]t_{j+1}[/math] времени используется какое-то другое. Из всех возможных таких оптимальных расписаний мы возьмем то, у которого [math]j[/math] будет максимально.

Из того, как в алгоритме выбирались значения для [math]t_i[/math] следует, что [math]t_{j + 1}[/math] — минимальное возможное время, большее [math]t_j,[/math] в которое можно начать выполнять какое-нибудь из оставшихся заданий. Если во время [math]t_{j+1}[/math] в расписании [math]S[/math] не выполняется никакого задания, то какое-то задание, которое могло бы выполнится в момент времени [math]t_{j+1}[/math] выполняется в [math]S[/math] позднее. Значит оно может быть перемещено в нашем расписании [math]S[/math] на время [math]t_{j+1}[/math] без увеличения целевой функции. Таким образом, наше новое расписание тоже будет оптимальным. Получили противоречие с максимальностью [math]j[/math]. Значит из всех оптимальных расписаний нам подходят только те, в которых [math]j = n[/math].
[math]\triangleleft[/math]

Частный случай

В случае, когда все времена появлений заданий различны, оптимальное решение может быть посчитано за [math]\mathcal{O}(n\log n) [/math].

Поскольку любое задание выполняется за единицу времени, а все функции [math]f_i[/math] являются неубывающими, то будет достаточно отсортировать работы по возрастанию времен появления и выполнять каждую работу как только она появится. Поскольку все [math]r_i[/math] различны, то промежутки выполнения работ не будут пересекаться — расписание будет корректным.

Примеры

Пример 1

Даны четыре задания.

[math]r_1 = 3, f_1 = 5t [/math]

[math]r_2 = 2, f_2 = t^2 [/math]

[math]r_3 = 4, f_3 = t + 4 [/math]

[math]r_4 = 1, f_4 = 2^t [/math]

Отсортируем задания по неубыванию [math]r_i[/math], а дальше будем выполнять их по мере появления. В полученном расписании работы будут идти в порядке [math]4, 2, 1, 3[/math] и давать в ответе [math]2^{1 + 1} + (2 + 1)^2 + 5(3 + 1) + (4 + 1) + 4 = 42 [/math], что является оптимальным результатом.

Пример 2

Пусть у нас есть три задания, и каждое из них имеет время появления [math]r_i = 0.[/math]

Заданы функции [math]f_i[/math]:

[math]f_1(t) = t^2 [/math]

[math]f_2(t) = t^3 [/math]

[math]f_3(t) = 3 ^ t [/math]

Поступить как в предыдущем примере и просто отсортировать работы мы теперь не можем — не понятно, в каком порядке сортировать задания с одинаковым временем появления.

Тогда нужно по приведенному в начале алгоритму посчитать времена, когда мы можем начать выполнять задания. В результате получим: [math]t_1 = 0, t_2 = 1, t_3 = 2[/math]. Тогда, согласно алгоритму, задача сведется к следующей задаче о назначениях:

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

В результате работы Венгерского алгоритма будет выбран порядок работ [math]2, 3, 1[/math], что даст лучший результат — [math]19[/math].

На этом примере хорошо видно, что решение, выбирающие в каждый момент времени [math]t_i[/math] несделанную работу с минимальным значением [math]f_i(t_i + 1)[/math] будет давать плохой результат.

Пример 3

Пусть у нас есть четыре задания, определенные следующим образом:

[math]r_1 = 0, f_1(t) = t^2 [/math]

[math]r_2 = 0, f_2(t) = 2t [/math]

[math]r_3 = 1, f_3(t) = 2 ^ t [/math]

[math]r_4 = 5, f_3(t) = t + 2 [/math]

Работы уже отсортированы, поэтому посчитаем времена [math]t_i[/math] для выполнения заданий. Получим: [math]t_1 = 0, t_2 = 1, t_3 = 2, t_4 = 4[/math].

Таблица, необходимая для решения задачи, будет построена так, что если работа с номером [math]i[/math] ещё не доступна в момент времени [math]t_j[/math], то в соответствующей ячейке будет стоять [math]\infty[/math].

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


В результате будет выбран порядок работ [math]1, 3, 2, 4[/math], и все работы выполнятся за [math]18[/math] единиц времени.

См. также

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

  • P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 19 - 20