Просмотр исходного текста страницы Участник:Dominica

<tex dpi = "200" >1 \mid\mid \sum w_i U_i</tex>

Для каждой работы заданы время выполнения <tex> p_i,</tex> дедлаин <tex>d_i</tex> и стоимось выполнения этой работы <tex>w_i \geqslant 0</tex>
Необходимо сотавить такое расписание, что  <tex>\sum w_i U_i</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>d_i</tex>
  <tex>t_1</tex> = <tex>r_1</tex>
  '''for''' <tex>t = -p_{max}</tex> '''to''' <tex>-1</tex>
    '''for''' <tex>j = 0</tex> '''to''' <tex>n</tex>
      F_j(t) = \infty
  '''for''' <tex>t = 0</tex> '''to''' <tex>T</tex>
    F_0(t) = 0
  '''for''' <tex>j = 1</tex> '''to''' <tex>n</tex>
  '''begin'''
    '''for''' <tex>t = 0</tex> '''to''' <tex>d_j</tex>
      '''if''' <tex> F_{j-1} + w_j  < F_{j-1}(t-p_j) </tex>   
         <tex> F_j(t) = F_{j-1}(t) + w_j </tex>
      '''else'''
        <tex>  F_j(t) = F_{j-1}(t-p_j) </tex>
    '''for''' <tex>t = d_j + 1</tex> '''to''' <tex>T</tex>
      <tex> F_j(t) = F_{j}(d_j) </tex>
  '''end'''

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

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

{{Лемма
|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