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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
 
(не показано 27 промежуточных версий 2 участников)
Строка 1: Строка 1:
<tex dpi = "200" >1 \mid r_i, p_i = 1 \mid \sum f_i</tex>
+
<tex dpi = "200" >1 \mid\mid \sum w_i U_i</tex>
 +
{{Утверждение
 +
|id=krit_dol3
 +
|statement=
 +
Критерии Делоне для ребер и треугольников равносильны.
 +
|proof=
 +
[[Файл:dol3.png|400px|thumb|right|]]
 +
Из треугольника в ребра: если для каждого треугольника выполнен критерий, то для каждого ребра можно рассматривать плоскость при любом треугольнике при ребре.
 +
Обратно: Рассмотрим треугольник <tex>ABC</tex>, для каждого из ребра можно провести плоскость и они образуют трехмерный угол, снаружи которого нет точек. В пересечении угла и плосокости <tex>ABC</tex> образуется тетраэдр. Если в нем есть точки, то точки есть внутри треугольника, тогда это не триангуляция <tex>\implies</tex> точек в тетраэдре нет <tex>\implies</tex> плоскостью <tex>ABC</tex> можно отделить пространство с точками <tex>\implies</tex> выполняется глобальный критерий.
 +
}}
 +
Будем называть '''хорошими''' те рёбра, для которых выполняется локальный критерий Делоне.
 +
{{Лемма
 +
|about=4
 +
|id=fliplemmasphere
 +
|statement=
 +
Из двух рёбер, которые можно провести для пары треугольников, как минимум одно хорошее.
 +
|proof=
 +
}}
  
 +
{{nohate2}}
 +
{{wasted}}
 +
{{под кат
 +
|title = Заголовок блока
 +
|content = Содержимое
 +
|frame-style = border:1px solid Plum
 +
|title-style = color:black;background-color:lavender;font-weight:bold
 +
|content-style = color:black;background-color:ghostwhite;text-align:center
 +
|footer = См. [[другая статья|другую статью]]
 +
|footer-style = background-color:lightgray;text-align:right
 +
}}
 
{{Задача
 
{{Задача
|definition= <ol>
+
|definition= Есть один станок и <tex>n</tex> работ. Для каждой работы заданы время выполнения <tex> p_i,</tex> дедлаин <tex>d_i</tex> и стоимось выполнения этой работы <tex>w_i \geqslant 0</tex>.
<li>Имеется один станок.</li>
+
Необходим минимизировать <tex>\sum w_i U_i</tex>.
<li>Есть <tex>n</tex> работ, каждая из которых выполняется за единицу времени.</li>
 
<li> Каждая работа имеет своё время появления <tex>r_i</tex>. </li>
 
<li>Для каждой работы задана монотонно неубывающая функция <tex>f_i</tex>. </li>
 
</ol>
 
Необходимо минимизировать <tex> \sum f_i, </tex> где <tex>f_i</tex> {{---}} значение функции <tex>f_i</tex> в момент завершения выполнения задания с номером <tex>i</tex>.
 
 
}}
 
}}
  
==Решение за <tex> O(n^3) </tex>==
+
==Решение==
 +
Применим для решения данной задачи [[Динамическое программирование|динамическое программирование]].
 +
 
 +
Обозначим <tex>T = \sum\limits_{i=1}^n p_i</tex>.
 +
Для всех <tex>t = 0, 1, \ldots, T </tex> и <tex>j = 1, \ldots, n</tex> будем рассчитывать <tex>F_j(t)</tex> {{---}} значение целевой функции, при условии, что были рассмотрены первые <tex>j</tex> работ и общее время выполнения тех из них, что будут закончены вовремя, не превышает времени <tex>t</tex>.
 +
#Если <tex>0 \leqslant t \leqslant  d_j </tex> и работа <tex>j</tex> успевает выполниться вовремя в расписании, соответствующем <tex>F_j(t)</tex>, то <tex>F_j(t) = F_{j- 1}(t - p_j)</tex>, иначе <tex>F_j(t) = F_{j- 1}(t) + w_i</tex>.
 +
#Если <tex>t > d_j</tex>, то <tex>F_j(t) = F_{j}(d_j)</tex>, поскольку все работы с номерами <tex>j = 1, \ldots, j</tex>, законченные позже, чем  <tex> d_j \geqslant \ldots \geqslant d_1 </tex>,  будут выполнены с опозданием.
 +
 
 +
Отсюда, получим соотношение:
 +
<p>
 +
<tex>
 +
F_j(t) =
 +
\left \{\begin{array}{ll} \min(F_{j-1}(t-p_j), F_{j-1}(t) + w_j), &  0 \leqslant t \leqslant  d_j \\
 +
F_j(d_j), &  d_j < t < T
 +
\end{array} \right.
 +
</tex>
 +
</p>
 +
В качестве начальных условий следует взять <tex>F_j(t) = \infty </tex> при  <tex>t < 0, j = 0,\ldots, n </tex>  и  <tex>F_0(t) = 0 </tex>  при  <tex>t \geqslant 0 </tex>.
  
Эта задача может быть решена сведением к решению [[Венгерский алгоритм решения задачи о назначениях | задачи о назначениях]].
+
Ответом на задачу будет <tex>F_n(d_n)</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_j(t)</tex> для <tex>j = 0,\ldots, n </tex> и <tex>t = 0,\ldots, d_j </tex>. За <tex>p_{max}</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 = -p_{max}</tex> '''to''' <tex>-1</tex>
     <tex>t_i</tex> = <tex>\max(r_i, t_{i-1} + 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>
 +
     '''for''' <tex>t = 0</tex> '''to''' <tex>d_j</tex>
 +
      '''if''' <tex> F_{j-1}(t) + 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>
 +
 
 +
Время работы данного алгоритма {{---}} <tex>O(n \sum\limits_{i=1}^n p_i)</tex>.
  
 +
Для того, чтобы найти само расписание, по доказанной ниже лемме, нам достаточно найти множество работ, которые будут выполнены с опозданием. Это может быть сделано следующим способом:
 +
  t = d_n
 +
  L = \varnothing
 +
  '''for''' <tex>j = n</tex> '''downto''' <tex>1</tex>
 +
    <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>
 +
 +
==Доказательство корректности и оптимальности==
  
 
{{Лемма
 
{{Лемма
 
|id=lemma1
 
|id=lemma1
|statement= Существует оптимальное расписание <tex>S</tex> в котором все <tex>n</tex> задач распределены по всем временам <tex>t_i (i = 1\ldots n)</tex>, которые выбирает приведенный выше алгоритм.
+
|statement= Пусть все работы отсортированы в порядке неубывания дедлайнов <tex>d_i</tex>.
|proof= Предположим, что в некоторое оптимальное расписание <tex>S</tex> входят времена <tex> t_1 \ldots t_j, </tex> где <tex> j < n</tex> и из всех возможных оптимальных расписаний мы возьмем то, у которого <tex>j</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> {{---}} номера просроченных работ.
Из того, как в алгоритме выбирались значения для <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>.
+
|proof= Пусть у нас есть некоторое оптимальное раписание <tex>S</tex>. Получим необходимое нам расписание путем переставления некоторых работ.
 +
#Если работа с номером <tex> i</tex> выполнится  в <tex>S</tex> с опозданием, то переставим эту работу в конец. При этом, так как работа просрочна в оптимальном расписании <tex>S</tex>, при такой перестановке не произойдет увеличения целевой функции.  
 +
#Если работы с номерами <tex>i</tex> и <tex>j</tex> в расписании <tex>S</tex> выполняются вовремя, но при этом <tex>d_i < d_j </tex>, но <tex>j</tex> стоит в <tex>S</tex> раньше <tex>i</tex>. Тогда переставим работу с номером <tex>j</tex> так, чтобы она выполнялась после работы <tex>i</tex>. Таким образом, каждая из работ, находившихся в <tex>S</tex> между <tex>j</tex> и <tex>i</tex>, включая <tex>i</tex>, будет выполняться в новом расписании на <tex>p_j</tex> единиц времени раньше. Эта перестановка не повлияет на оптимальнось расписания:
 +
#*Ни одна из работ, котарая успевала выполниться в расписании <tex>S</tex>, не попадет в список просроченных работ при переставлении её на более раннее время.
 +
#*Число работ, не успевающих выполниться вовремя, не может уменьшится, иначе бы возникло противоречие в исходным выбором <tex>S</tex>, как оптимального решения.
 +
#*Поскольку <tex>d_i < d_j </tex> и работа <tex>i</tex> будет заканчиваться на <tex>p_j</tex> единиц времени раньше, то стоящая сразу послее нее работа <tex>j</tex> тоже будет успевать выполниться.
 
}}
 
}}
  
Заметим, что в полученном расписании будут интервалы в которые машина будет работать без остановки, и будут периоды простоя.
+
==См. также ==
 
+
* [[Классификация задач]]
Для того, чтобы найти это оптимальное расписание, сведем к задаче о назначения следующим образом:
+
* [[1ripipsumwu|<tex> 1 \mid r_i,p_i=p \mid \sum w_i U_i</tex>]]
 
+
* [[1pi1sumwu|<tex>1 \mid p_{i} = 1 \mid \sum w_{i}U_{i}</tex>]]
<tex>V_1=\left \{ 1,\ldots,n \right\}</tex>
+
* [[R2Cmax|<tex>R2 \mid \mid C_{max}</tex>]]
  
<tex>V_2=\left \{ t_1,\ldots,t_n \right\}</tex>
+
== Источники информации ==
 
+
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 26 - 28
 
 
<p>
 
<tex>
 
c_{ij} =
 
\left \{\begin{array}{ll} f_i(t_j + 1), &  r_i \le t_i \\
 
\infty, &  otherwise
 
\end{array} \right.
 
</tex>
 
</p>
 

Текущая версия на 23:21, 28 ноября 2016

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

Утверждение:
Критерии Делоне для ребер и треугольников равносильны.
[math]\triangleright[/math]
Dol3.png

Из треугольника в ребра: если для каждого треугольника выполнен критерий, то для каждого ребра можно рассматривать плоскость при любом треугольнике при ребре.

Обратно: Рассмотрим треугольник [math]ABC[/math], для каждого из ребра можно провести плоскость и они образуют трехмерный угол, снаружи которого нет точек. В пересечении угла и плосокости [math]ABC[/math] образуется тетраэдр. Если в нем есть точки, то точки есть внутри треугольника, тогда это не триангуляция [math]\implies[/math] точек в тетраэдре нет [math]\implies[/math] плоскостью [math]ABC[/math] можно отделить пространство с точками [math]\implies[/math] выполняется глобальный критерий.
[math]\triangleleft[/math]

Будем называть хорошими те рёбра, для которых выполняется локальный критерий Делоне.

Лемма (4):
Из двух рёбер, которые можно провести для пары треугольников, как минимум одно хорошее.
nothumb
НЯ!
Эта статья полна любви и обожания.
Возможно, стоит добавить ещё больше?
nothumb


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


Решение

Применим для решения данной задачи динамическое программирование.

Обозначим [math]T = \sum\limits_{i=1}^n p_i[/math]. Для всех [math]t = 0, 1, \ldots, T [/math] и [math]j = 1, \ldots, n[/math] будем рассчитывать [math]F_j(t)[/math] — значение целевой функции, при условии, что были рассмотрены первые [math]j[/math] работ и общее время выполнения тех из них, что будут закончены вовремя, не превышает времени [math]t[/math].

  1. Если [math]0 \leqslant t \leqslant d_j [/math] и работа [math]j[/math] успевает выполниться вовремя в расписании, соответствующем [math]F_j(t)[/math], то [math]F_j(t) = F_{j- 1}(t - p_j)[/math], иначе [math]F_j(t) = F_{j- 1}(t) + w_i[/math].
  2. Если [math]t \gt d_j[/math], то [math]F_j(t) = F_{j}(d_j)[/math], поскольку все работы с номерами [math]j = 1, \ldots, j[/math], законченные позже, чем [math] d_j \geqslant \ldots \geqslant d_1 [/math], будут выполнены с опозданием.

Отсюда, получим соотношение:

[math] F_j(t) = \left \{\begin{array}{ll} \min(F_{j-1}(t-p_j), F_{j-1}(t) + w_j), & 0 \leqslant t \leqslant d_j \\ F_j(d_j), & d_j \lt t \lt T \end{array} \right. [/math]

В качестве начальных условий следует взять [math]F_j(t) = \infty [/math] при [math]t \lt 0, j = 0,\ldots, n [/math] и [math]F_0(t) = 0 [/math] при [math]t \geqslant 0 [/math].

Ответом на задачу будет [math]F_n(d_n)[/math].

Приведенный ниже алгоритм вычисляет [math]F_j(t)[/math] для [math]j = 0,\ldots, n [/math] и [math]t = 0,\ldots, d_j [/math]. За [math]p_{max}[/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}(t) + 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]

Время работы данного алгоритма — [math]O(n \sum\limits_{i=1}^n p_i)[/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]

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

Лемма:
Пусть все работы отсортированы в порядке неубывания дедлайнов [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]

См. также

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

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