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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Решение)
(Доказательство корректности и оптимальности)
Строка 48: Строка 48:
  
 
==Доказательство корректности и оптимальности==
 
==Доказательство корректности и оптимальности==
 
{{Лемма
 
|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>.
 
}}
 
  
 
==См. также ==
 
==См. также ==

Версия 06:55, 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]S[/math]. Получим необходимое нам расписание путем переставления некоторых работ.

  1. Если работа с номером [math] i[/math] выполнится в [math]S[/math] с опозданием, то переставим эту работу в конец. При этом, так как работа просрочна в оптимальном расписании [math]S[/math], при такой перестановке не произойдет увеличения целевой функции.
  2. Если работы с номерами [math]i[/math] и [math]j[/math] в расписании [math]S[/math] выполняются вовремя, но при этом [math]d_i \lt d_j [/math], но [math]j[/math] стоит в [math]S[/math] раньше [math]i[/math]. Тогда переставим работу с номером [math]j[/math] так, чтобы она выполнялась после работы [math]i[/math]. Таким образом, каждая из работ, находившихся в [math]S[/math] между [math]j[/math] и [math]i[/math], включая [math]i[/math], будет выполняться в новом расписании на [math]p_j[/math] единиц времени раньше. Эта перестановка не повлияет на оптимальнось расписания:
    • Ни одна из работ, котарая успевала выполниться в расписании [math]S[/math], не попадет в список просроченных работ при переставлении её на более раннее время.
    • Число работ, не успевающих выполниться вовремя, не может уменьшится, иначе бы возникло противоречие в исходным выбором [math]S[/math], как оптимального решения.
    • Поскольку [math]d_i \lt d_j [/math] и работа [math]i[/math] будет заканчиваться на [math]p_j[/math] единиц времени раньше, то стоящая сразу послее нее работа [math]j[/math] тоже будет успевать выполниться.
[math]\triangleleft[/math]



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


 t = d_n
 L = \varnothing
 for [math]j = n[/math] downto [math]1[/math]
   [math]t = \min(t, d_j)[/math]
   if [math] F_j(t) = F_{j-1}(t) + w_j [/math] 
     [math] L = L \cup \{j\} [/math] </tex>
   else
     [math] t = t - p_j [/math]

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

См. также

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

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