Участник:Dominica — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 11: Строка 11:
 
}}
 
}}
  
==Решение за <tex> O(n^3) </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>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>f_i</tex> {{---}} монотонно неубывающие функции, то это значит, что в оптимальном расписании работы должны начинать исполняться как можно раньше. Первые <tex>n</tex> самых ранних для начала исполнения времен <tex>t_i</tex> могут быть вычислены следующим алгоритмом, в котором мы предполагаем, что все работы отсортированы по неубыванию времени появления <tex>r_i</tex>:
Строка 23: Строка 25:
  
  
{{Лемма
+
Для того, чтобы найти оптимальное расписание, построим полный двудольный граф, в котором будут доли <tex>V_1, V_2</tex> и ребра <tex>c_{ij}</tex> между ними:
|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>.
 
}}
 
 
 
Заметим, что в полученном расписании будут интервалы в которые машина будет работать без остановки, и будут периоды простоя.
 
 
 
Для того, чтобы найти это оптимальное расписание, сведем к задаче о назначения следующим образом:
 
  
 
<tex>V_1=\left \{ 1,\ldots,n \right\}</tex>
 
<tex>V_1=\left \{ 1,\ldots,n \right\}</tex>
Строка 47: Строка 40:
 
</tex>
 
</tex>
 
</p>
 
</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>.
 +
}}
 +
 +
== Источники информации ==
 +
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 73 - 78
 +
 +
[[Категория: Дискретная математика и алгоритмы]]
 +
[[Категория: Теория расписаний]]

Версия 04:11, 4 мая 2016

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


Задача:
  1. Имеется один станок.
  2. Есть [math]n[/math] работ, каждая из которых выполняется за единицу времени.
  3. Каждая работа имеет своё время появления [math]r_i[/math].
  4. Для каждой работы задана монотонно неубывающая функция [math]f_i[/math].
Необходимо минимизировать [math] \sum f_i, [/math] где [math]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]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, V_2[/math] и ребра [math]c_{ij}[/math] между ними:

[math]V_1=\left \{ 1,\ldots,n \right\}[/math]

[math]V_2=\left \{ t_1,\ldots,t_n \right\}[/math]


[math] c_{ij} = \left \{\begin{array}{ll} f_i(t_j + 1), & r_i \le t_i \\ \infty, & otherwise \end{array} \right. [/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]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]

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

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