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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Решение)
Строка 6: Строка 6:
 
==Решение==
 
==Решение==
  
Эта задача может быть решена сведением к решению [[Венгерский алгоритм решения задачи о назначениях | задачи о назначениях]].
+
{{Лемма
А именно, покажем, что решение задачи состоит в сопоставлении <tex>n</tex> различным заданиям различных времен начала выполнения работы. Если сопоставляем работе <tex>i</tex> время <tex>t</tex>, то вклад в целевую функцию будет <tex> f_i(t + 1) </tex>.
+
|id=lemma1
 +
|statement= Пусть все работы отсортированы в порядке неубывания дедлайнов <tex>d_i</tex>.
 +
Тогда существует оптимальное расписание вида <tex>i_1, i_2, \ldots, i_s, i_{s+1}, \ldots, i_n </tex>, где <tex>i_1 < i_2 < \ldots < i_s </tex> {{---}} номера работ, которые успеют выполниться вовремя, а  <tex>i_{s+1}, \ldots, i_n </tex> {{---}} номера просроченных работ.
 +
|proof= Это можно показать следующим образом
 +
}}
  
Далее будет показано, что при построении оптимального расписания нам нужно будет рассмотреть всего <tex>n</tex> различных времен начала работ. Следовательно, подобная задача может быть решена за <tex>O(n^3)</tex>.
 
  
Поскольку <tex>f_i</tex> {{---}} монотонно неубывающие функции, то это значит, что в оптимальном расписании работы должны начинать исполняться как можно раньше. Первые <tex>n</tex> самых ранних для начала исполнения времен <tex>t_i</tex> могут быть вычислены следующим алгоритмом :
 
  
   отсортиртировать по неубыванию времена появления <tex>r_i</tex>
+
 
 +
   отсортиртировать работы по неубыванию времен дедлайнов <tex>d_i</tex>
 
   <tex>t_1</tex> = <tex>r_1</tex>
 
   <tex>t_1</tex> = <tex>r_1</tex>
   '''for''' <tex> i \in \{ 2 \ldots n \} </tex>
+
   '''for''' <tex> t \in \{ -p_{max} \ldots -1 \} </tex>
     <tex>t_i</tex> = <tex>\max(r_i, t_{i-1} + 1)</tex>
+
     '''for''' <tex> j \in \{ 0 \ldots n \} </tex>
 
+
      F_j(t) = \infty
 
+
  '''for''' <tex> t \in \{ 0 \ldots T \} </tex>
Для того, чтобы найти оптимальное расписание, построим полный [[Основные_определения_теории_графов#Двудольный_граф |двудольный граф]], в котором будут доли <tex>V_1 = \left \{ 1,\ldots,n \right\} и  V_2 = \left \{ t_1,\ldots,t_n \right\}</tex> и ребра <tex>c_{ij}</tex> между ними:
+
    F_0(t) = 0
<p>
+
  '''for''' <tex> j \in \{ 0 \ldots n \} </tex>
<tex>
+
    '''for''' <tex> t \in \{ 0 \ldots d_j \} </tex>
c_{ij} =
+
      '''if''' <tex> F_{j-1} + w_j  < F_{j-1}(t-p_j) </tex> '''then'''   
\left \{\begin{array}{ll} f_i(t_j + 1), &  r_i \leqslant  t_i \\
+
        <tex> F_j(t) = F_{j-1}(t) + w_j </tex>
\infty, & \mathrm{otherwise}
+
      '''else'''
\end{array} \right.
+
        <tex> F_j(t) = F_{j-1}(t-p_j) </tex>
</tex>
+
    '''for''' <tex> t \in \{ d_{j+1} \ldots T \} </tex>
</p>
+
      <tex> F_j(t) = F_{j}(d_j) </tex>
 
 
Решив задачу о назначениях для данного графа, получим оптимальное расписание.
 
  
 
==Доказательство корректности и оптимальности==
 
==Доказательство корректности и оптимальности==

Версия 00:46, 4 июня 2016

[math]1 \mid\mid \sum w_i U_i[/math]

Для каждой работы заданы время выполнения [math] p_i,[/math] дедлаин [math]d_i[/math] и стоимось выполнения этой работы [math]w_i \geqslant 0[/math] Необходимо сотавить такое расписание, что [math]\sum w_i U_i[/math] будет минимальна.

Решение

Лемма:
Пусть все работы отсортированы в порядке неубывания дедлайнов [math]d_i[/math]. Тогда существует оптимальное расписание вида [math]i_1, i_2, \ldots, i_s, i_{s+1}, \ldots, i_n [/math], где [math]i_1 \lt i_2 \lt \ldots \lt i_s [/math] — номера работ, которые успеют выполниться вовремя, а [math]i_{s+1}, \ldots, i_n [/math] — номера просроченных работ.
Доказательство:
[math]\triangleright[/math]
Это можно показать следующим образом
[math]\triangleleft[/math]



 отсортиртировать  работы по неубыванию времен дедлайнов [math]d_i[/math]
 [math]t_1[/math] = [math]r_1[/math]
 for [math] t \in \{ -p_{max} \ldots -1 \} [/math]
   for [math] j \in \{ 0 \ldots n \} [/math]
     F_j(t) = \infty
 for [math] t \in \{ 0 \ldots T \} [/math]
   F_0(t) = 0
 for [math] j \in \{ 0 \ldots n \} [/math]
   for [math] t \in \{ 0 \ldots d_j \} [/math]
     if [math] F_{j-1} + w_j  \lt  F_{j-1}(t-p_j) [/math] then    
        [math] F_j(t) = F_{j-1}(t) + w_j [/math]
     else
       [math]  F_j(t) = F_{j-1}(t-p_j) [/math]
   for [math] t \in \{ d_{j+1} \ldots T \} [/math]
     [math] F_j(t) = F_{j}(d_j) [/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, стр. 19 - 20