264
правки
Изменения
Новая страница: «<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>n</tex> различным заданиям различных времен начала выполнения работы. Если сопоставляем работе <tex>i</tex> время <tex>t</tex>, то вклад в целевую функцию будет <tex> f_i(t + 1) </tex>.
Далее будет показано, что при построении оптимального расписания нам нужно будет рассмотреть всего <tex>n</tex> различных времен начала работ. Следовательно, подобная задача может быть решена за <tex>O(n^3)</tex>.
Поскольку <tex>f_i</tex> {{---}} монотонно неубывающие функции, то это значит, что в оптимальном расписании работы должны начинать исполняться как можно раньше. Первые <tex>n</tex> самых ранних для начала исполнения времен <tex>t_i</tex> могут быть вычислены следующим алгоритмом :
отсортиртировать по неубыванию времена появления <tex>r_i</tex>
<tex>t_1</tex> = <tex>r_1</tex>
'''for''' <tex> i \in \{ 2 \ldots n \} </tex>
<tex>t_i</tex> = <tex>\max(r_i, t_{i-1} + 1)</tex>
Для того, чтобы найти оптимальное расписание, построим полный [[Основные_определения_теории_графов#Двудольный_граф |двудольный граф]], в котором будут доли <tex>V_1 = \left \{ 1,\ldots,n \right\} и V_2 = \left \{ t_1,\ldots,t_n \right\}</tex> и ребра <tex>c_{ij}</tex> между ними:
<p>
<tex>
c_{ij} =
\left \{\begin{array}{ll} f_i(t_j + 1), & r_i \leqslant t_i \\
\infty, & \mathrm{otherwise}
\end{array} \right.
</tex>
</p>
Решив задачу о назначениях для данного графа, получим оптимальное расписание.
==Доказательство корректности и оптимальности==
{{Лемма
|id=lemma1
|statement= Существует оптимальное расписание <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> будет максимально.
Из того, как в алгоритме выбирались значения для <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>.
}}
==См. также ==
* [[Классификация задач]]
* [[1precpmtnrifmax|<tex>1 \mid prec, pmtn, r_i \mid f_{\max}</tex>]]
== Источники информации ==
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 19 - 20
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Теория расписаний]]
Для каждой работы задана монотонно неубывающая функция <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>O(n^3)</tex>.
Поскольку <tex>f_i</tex> {{---}} монотонно неубывающие функции, то это значит, что в оптимальном расписании работы должны начинать исполняться как можно раньше. Первые <tex>n</tex> самых ранних для начала исполнения времен <tex>t_i</tex> могут быть вычислены следующим алгоритмом :
отсортиртировать по неубыванию времена появления <tex>r_i</tex>
<tex>t_1</tex> = <tex>r_1</tex>
'''for''' <tex> i \in \{ 2 \ldots n \} </tex>
<tex>t_i</tex> = <tex>\max(r_i, t_{i-1} + 1)</tex>
Для того, чтобы найти оптимальное расписание, построим полный [[Основные_определения_теории_графов#Двудольный_граф |двудольный граф]], в котором будут доли <tex>V_1 = \left \{ 1,\ldots,n \right\} и V_2 = \left \{ t_1,\ldots,t_n \right\}</tex> и ребра <tex>c_{ij}</tex> между ними:
<p>
<tex>
c_{ij} =
\left \{\begin{array}{ll} f_i(t_j + 1), & r_i \leqslant t_i \\
\infty, & \mathrm{otherwise}
\end{array} \right.
</tex>
</p>
Решив задачу о назначениях для данного графа, получим оптимальное расписание.
==Доказательство корректности и оптимальности==
{{Лемма
|id=lemma1
|statement= Существует оптимальное расписание <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> будет максимально.
Из того, как в алгоритме выбирались значения для <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>.
}}
==См. также ==
* [[Классификация задач]]
* [[1precpmtnrifmax|<tex>1 \mid prec, pmtn, r_i \mid f_{\max}</tex>]]
== Источники информации ==
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 19 - 20
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Теория расписаний]]
