Pintreepi1Lmax — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «<tex dpi = "200">P \mid Intree, p_{i} = 1 \mid L_{max}</tex> {{Задача |definition=Рассмотрим задачу на нахождение распис...»)
 
(Описание алгоритма)
Строка 22: Строка 22:
 
=== Первый шаг ===
 
=== Первый шаг ===
 
Алгоритм изменения сроков:
 
Алгоритм изменения сроков:
  deque = {i <tex>\mid</tex> i является листом}
+
  deque = i <tex>\mid</tex> i является листом
  while (deque not empty)
+
  while deque not empty
 
     i = stack.remove_first()
 
     i = stack.remove_first()
     for (j <tex>\mid</tex> j является предком i):
+
     for j <tex>\mid</tex> j является предком i
         <tex>d_{j} := min(d_{j}, d_{i} - 1)</tex>
+
         <tex>d_{j} = \min(d_{j}, d_{i} - 1)</tex>
 
         stack.add_last(j)
 
         stack.add_last(j)
 
      
 
      
Строка 33: Строка 33:
 
Работа с новым сроком <tex>{d'_i}</tex> в расписании не имеет опозданий тогда и только тогда, когда она не имела опозданий с оригинальным сроком <tex>{d_i}</tex>.
 
Работа с новым сроком <tex>{d'_i}</tex> в расписании не имеет опозданий тогда и только тогда, когда она не имела опозданий с оригинальным сроком <tex>{d_i}</tex>.
 
|proof=
 
|proof=
В одну сторону утверждение очевидно: т.к. <tex>{d'_i} \leq {d_i}</tex>, значит, если опозданий не было со значениями <tex>{d'_i}</tex>, их не будет и со значениями <tex>{d_i}</tex>.
+
В одну сторону утверждение очевидно: т.к. <tex>{d'_i} \leqslant {d_i}</tex>, значит, если опозданий не было со значениями <tex>{d'_i}</tex>, их не будет и со значениями <tex>{d_i}</tex>.
Докажем лемму в другую сторону: пусть у нас были сроки <tex>{d_i}</tex> и мы их заменили на <tex>{d'_i}</tex> в соответствии с приведенным алгоритмом. Пронумеруем вершины от <tex>1</tex> до <tex>n</tex> в соответствии с '''обратным''' порядком обхода в алгоритме изменения сроков. В соответствии с расписанием, время, когда деталь закончит обрабатываться на станке <tex>{C_i}</tex> удовлетворяет неравенству <tex>{C_i} \leq {d_i}</tex> для всех <tex>{C_1} \dots {C_n}</tex>. Тогда мы имеем  <tex>{C_n} \leq {d_n} = {d'_n}</tex>. Если для какого-то <tex>1 < r \leq n</tex> мы имеем <tex>{C_n} \leq {d'_n}</tex> для <tex>i = r \dots n </tex> и существует работа <tex>j</tex> из этого промежутка, что вершина с номером <tex>r - 1</tex> является ее родителем, тогда <tex>C_{r-1} \leq \min(d_{r-1},d'_{j}-1) = d'_{r-1}</tex>
+
Докажем лемму в другую сторону: пусть у нас были сроки <tex>{d_i}</tex> и мы их заменили на <tex>{d'_i}</tex> в соответствии с приведенным алгоритмом. Пронумеруем вершины от <tex>1</tex> до <tex>n</tex> в соответствии с '''обратным''' порядком обхода в алгоритме изменения сроков. В соответствии с расписанием, время, когда деталь закончит обрабатываться на станке <tex>{C_i}</tex> удовлетворяет неравенству <tex>{C_i} \leqslant {d_i}</tex> для всех <tex>{C_1} \dots {C_n}</tex>. Тогда мы имеем  <tex>{C_n} \leqslant {d_n} = {d'_n}</tex>. Если для какого-то <tex>1 < r \leqslant n</tex> мы имеем <tex>{C_n} \leqslant {d'_n}</tex> для <tex>i = r \dots n </tex> и существует работа <tex>j</tex> из этого промежутка, что вершина с номером <tex>r - 1</tex> является ее родителем, тогда <tex>C_{r-1} \leqslant \min(d_{r-1},d'_{j}-1) = d'_{r-1}</tex>
 
}}
 
}}
  
 
=== Второй шаг ===
 
=== Второй шаг ===
На втором этапе алгоритма работы сортируются в неубывающем порядке их дедлайнов. Предполагается, что работы занумерованы в соответствии с предыдущим пунктом, т.е. <tex>d_{i} \leq d_{j}</tex>, если <tex>i \leq j</tex>.
+
На втором этапе алгоритма работы сортируются в неубывающем порядке их дедлайнов. Предполагается, что работы занумерованы в соответствии с предыдущим пунктом, т.е. <tex>d_{i} \leqslant d_{j}</tex>, если <tex>i \leqslant j</tex>.
  
 
В переменной <tex>F</tex> хранится время, когда станок освободится.
 
В переменной <tex>F</tex> хранится время, когда станок освободится.
Строка 49: Строка 49:
  
 
  F = 0
 
  F = 0
  for (i = 1..n)
+
  for i = 1 .. n
 
     r[i] = 0
 
     r[i] = 0
  for (t = 0..n)
+
  for t = 0 .. n
 
     c[t] = 0
 
     c[t] = 0
  for (i = 1..n)
+
  for i = 1 .. n
 
     t = max(r[i], F)
 
     t = max(r[i], F)
 
     x[i] = t
 
     x[i] = t
 
     c[t] = c[t] + 1
 
     c[t] = c[t] + 1
     if (n[t] == m)
+
     if n[t] == m
        F = t + 1
+
      F = t + 1
 
     j = s[i]
 
     j = s[i]
 
     r[j] = max (r[j], t + 1)
 
     r[j] = max (r[j], t + 1)
  
Расписание, сгенерированное этим алгоритмом имеет важное свойство: число заданий в очереди в любой момент времени <tex>t</tex> меньше, чем в момент <tex>t + 1</tex>. Действительно, пусть во время <tex>t</tex> мы выполняем <tex>k</tex> работ, и хотя бы <tex>k + 1 \leq m</tex> работ готовы к выполению в момент времени <tex>t + 1</tex>. Но т.к. <tex>k + 1 \leq m</tex>, значит каждой из работ предшествовала как минимум одна, поскольку у всех вершин, кроме корней, есть как минимум один предок. Значит, в момент времени <tex>t</tex> исполнялось не менее <tex>k + 1</tex> работ, противоречие.
+
Расписание, сгенерированное этим алгоритмом имеет важное свойство: число заданий в очереди в любой момент времени <tex>t</tex> меньше, чем в момент <tex>t + 1</tex>. Действительно, пусть во время <tex>t</tex> мы выполняем <tex>k</tex> работ, и хотя бы <tex>k + 1 \leqslant m</tex> работ готовы к выполению в момент времени <tex>t + 1</tex>. Но т.к. <tex>k + 1 \leqslant m</tex>, значит каждой из работ предшествовала как минимум одна, поскольку у всех вершин, кроме корней, есть как минимум один предок. Значит, в момент времени <tex>t</tex> исполнялось не менее <tex>k + 1</tex> работ, противоречие.
  
 
{{Лемма
 
{{Лемма
Строка 68: Строка 68:
 
Если существует такое расписание, в котором ни одна из работ не будет выполнена с опозданием, то тогда это свойство сохранится в построенном данным алгоритмом расписании
 
Если существует такое расписание, в котором ни одна из работ не будет выполнена с опозданием, то тогда это свойство сохранится в построенном данным алгоритмом расписании
 
|proof=
 
|proof=
Предположим, что существует работа из <tex>x_{1} \dots x_{n}</tex> расписания, построенного алгоритмом. В таком случае существует работа, которая опоздала по отношению к измененным срокам. Возьмем наименьшее <tex>i</tex> такое, что <tex>x(i) + 1 > d'_{i}</tex>. Пусть <tex>t < d'_{i}</tex> {{---}} наибольшее из удовлетворяющих условию <tex>j < m \mid x(j) = t, d'_{j} \leq d'_{i}</tex>
+
Предположим, что существует работа из <tex>x_{1} \dots x_{n}</tex> расписания, построенного алгоритмом. В таком случае существует работа, которая опоздала по отношению к измененным срокам. Возьмем наименьшее <tex>i</tex> такое, что <tex>x(i) + 1 > d'_{i}</tex>. Пусть <tex>t < d'_{i}</tex> {{---}} наибольшее из удовлетворяющих условию <tex>j < m \mid x(j) = t, d'_{j} \leqslant d'_{i}</tex>
Такое <tex>t</tex> существует, потому что иначе <tex>m \cdot d'_{i}</tex> работ <tex>j</tex> с <tex>d'_{j} \leq d'_{i}</tex> находятся в очереди до <tex>d'_{i}</tex>. Работа <tex>i</tex> к ним не принадлежит, поскольку <tex>x(i) + 1 > d'_{i}</tex>, а значит, что <tex>m \cdot d'_{i} + 1</tex> должны быть в очереди в момент времени <tex>0 \dots d'_{i}</tex> и ни одна работа не должна опаздывать. Противоречие.
+
Такое <tex>t</tex> существует, потому что иначе <tex>m \cdot d'_{i}</tex> работ <tex>j</tex> с <tex>d'_{j} \leqslant d'_{i}</tex> находятся в очереди до <tex>d'_{i}</tex>. Работа <tex>i</tex> к ним не принадлежит, поскольку <tex>x(i) + 1 > d'_{i}</tex>, а значит, что <tex>m \cdot d'_{i} + 1</tex> должны быть в очереди в момент времени <tex>0 \dots d'_{i}</tex> и ни одна работа не должна опаздывать. Противоречие.
Любая работа <tex>j</tex> с <tex>d'_{j} \leq d'_{i} </tex> и <tex> x(j) > t </tex> должна иметь предка, начавшего работать в момент времени <tex>t</tex>. Теперь рассмотрим два случая:
+
Любая работа <tex>j</tex> с <tex>d'_{j} \leqslant d'_{i} </tex> и <tex> x(j) > t </tex> должна иметь предка, начавшего работать в момент времени <tex>t</tex>. Теперь рассмотрим два случая:
  
 
'''Первый случай.''' <tex>t = d'_{i} - 1</tex>.
 
'''Первый случай.''' <tex>t = d'_{i} - 1</tex>.
  
Мы имеем <tex>x(i)>d'_{i}-1 = t</tex>. Таким образом, предок <tex>k</tex> работы <tex>i</tex> должен начать работать во время <tex>t</tex> и закончить в <tex>d'_{i}</tex>. Но т.к. <tex>d'_{k} \leq d'_{i} - 1 < d'_{i} = x(k) + 1</tex>, работа <tex>k</tex> так же опоздает, однако <tex>i</tex> было выбрано минимальным. Противоречие.
+
Мы имеем <tex>x(i)>d'_{i}-1 = t</tex>. Таким образом, предок <tex>k</tex> работы <tex>i</tex> должен начать работать во время <tex>t</tex> и закончить в <tex>d'_{i}</tex>. Но т.к. <tex>d'_{k} \leqslant d'_{i} - 1 < d'_{i} = x(k) + 1</tex>, работа <tex>k</tex> так же опоздает, однако <tex>i</tex> было выбрано минимальным. Противоречие.
  
 
'''Второй случай.''' <tex>t < d'_{i} - 1</tex>.
 
'''Второй случай.''' <tex>t < d'_{i} - 1</tex>.
  
В этом случае <tex>m</tex> работ <tex>j</tex> таких, что <tex>d'_{j} \leq d'_{i}</tex> начнут работать в момент времени <tex>t + 1</tex>, каждая из которых имеет как минимум работающего в <tex>t</tex> предка. По структуре дерева все эти предки различны, кроме того, если <tex>k</tex> {{---}} такой предок <tex>j</tex>, тогда <tex>d'_{k} \leq d'_{j} - 1 < d'_{j} \leq d'_{i}</tex>, что противоречит выбору <tex>t</tex>  
+
В этом случае <tex>m</tex> работ <tex>j</tex> таких, что <tex>d'_{j} \leqslant d'_{i}</tex> начнут работать в момент времени <tex>t + 1</tex>, каждая из которых имеет как минимум работающего в <tex>t</tex> предка. По структуре дерева все эти предки различны, кроме того, если <tex>k</tex> {{---}} такой предок <tex>j</tex>, тогда <tex>d'_{k} \leqslant d'_{j} - 1 < d'_{j} \leqslant d'_{i}</tex>, что противоречит выбору <tex>t</tex>  
 
}}
 
}}
  
Строка 85: Строка 85:
 
Данный алгоритм корректно решает задачу <tex>P \mid Tree, p_{i} = 1 \mid L_{max}</tex>
 
Данный алгоритм корректно решает задачу <tex>P \mid Tree, p_{i} = 1 \mid L_{max}</tex>
 
|proof=
 
|proof=
Пусть <tex>L'_{max}</tex> {{---}} оптимальное значение. В таком случае, существует расписание, удовлетворяющее <tex>\max\limits_i \{C_i - d_i\} \leq L'_{max}</tex>, что эквивалетно выражению <tex>C_{i} \leq d_{i} + L'_{max}</tex> для <tex>i = 1 \dots n </tex>. По первой лемме расписание <tex>S</tex>, построенное для сдвинутых дат <tex>d_{i} + L'_{max}</tex> удовлетворяет данным выражениям. Таким образом, оно оптимально. Нетрудно заметить, что <tex>S</tex> идентично расписанию, построенному алгоритмом, т.к. <tex>(d_{i}+L'_{max})' = d'_{i} + L'_{max} </tex> для <tex>i = 1 \dots n </tex>
+
Пусть <tex>L'_{max}</tex> {{---}} оптимальное значение. В таком случае, существует расписание, удовлетворяющее <tex>\max\limits_i \{C_i - d_i\} \leqslant L'_{max}</tex>, что эквивалетно выражению <tex>C_{i} \leqslant d_{i} + L'_{max}</tex> для <tex>i = 1 \dots n </tex>. По первой лемме расписание <tex>S</tex>, построенное для сдвинутых дат <tex>d_{i} + L'_{max}</tex> удовлетворяет данным выражениям. Таким образом, оно оптимально. Нетрудно заметить, что <tex>S</tex> идентично расписанию, построенному алгоритмом, т.к. <tex>(d_{i}+L'_{max})' = d'_{i} + L'_{max} </tex> для <tex>i = 1 \dots n </tex>
 
}}
 
}}
 
  
 
==Источники информации==
 
==Источники информации==

Версия 13:37, 15 мая 2016

[math]P \mid Intree, p_{i} = 1 \mid L_{max}[/math]


Задача:
Рассмотрим задачу на нахождение расписания:
  1. У нас есть несколько станков, работающих параллельно. У станков могут быть разные скорости выполнения работ.
  2. Есть несколько заданий, каждое из которых имеет определенный порядок, который указан в направленном из корней в лист intree-дереве
  3. Любая работа на любом станке выполняется единицу времени.
Требуется минимизировать максимальное опоздание [math]L_{max} = \max\limits_i \{C_i - d_i\}[/math]


Описание алгоритма

Пример Intree-дерева

Идея

Все вершины хранятся в дереве (англ. Intree), которое имеет несколько корней и один лист.

Работы хранятся в дереве, состоящем из [math]n[/math] вершин с фиктивной нулевой работой, которая является родителем тех вершин, у которых изначально его не было. В intree-дереве у одной вершины может быть два и более родителей. Решение задачи состоит из двух шагов: на первом шаге мы меняем сроки выполнения работ в соответствии с их очередностью.

На первом шаге изменения сроков состоит в следующем: для всех [math]i, j[/math] таких, что существует ребро из [math]i[/math] в [math]j[/math] будем менять [math]{d_i}[/math] на [math]\min ({d_i}, {d_j} - 1) [/math]. На втором шаге работы расставляются в неубывающем порядке сроков.

Первый шаг

Алгоритм изменения сроков:

deque = i [math]\mid[/math] i является листом
while deque not empty
    i = stack.remove_first()
    for j [math]\mid[/math] j является предком i
        [math]d_{j} = \min(d_{j}, d_{i} - 1)[/math]
        stack.add_last(j)
   
Лемма:
Работа с новым сроком [math]{d'_i}[/math] в расписании не имеет опозданий тогда и только тогда, когда она не имела опозданий с оригинальным сроком [math]{d_i}[/math].
Доказательство:
[math]\triangleright[/math]

В одну сторону утверждение очевидно: т.к. [math]{d'_i} \leqslant {d_i}[/math], значит, если опозданий не было со значениями [math]{d'_i}[/math], их не будет и со значениями [math]{d_i}[/math].

Докажем лемму в другую сторону: пусть у нас были сроки [math]{d_i}[/math] и мы их заменили на [math]{d'_i}[/math] в соответствии с приведенным алгоритмом. Пронумеруем вершины от [math]1[/math] до [math]n[/math] в соответствии с обратным порядком обхода в алгоритме изменения сроков. В соответствии с расписанием, время, когда деталь закончит обрабатываться на станке [math]{C_i}[/math] удовлетворяет неравенству [math]{C_i} \leqslant {d_i}[/math] для всех [math]{C_1} \dots {C_n}[/math]. Тогда мы имеем [math]{C_n} \leqslant {d_n} = {d'_n}[/math]. Если для какого-то [math]1 \lt r \leqslant n[/math] мы имеем [math]{C_n} \leqslant {d'_n}[/math] для [math]i = r \dots n [/math] и существует работа [math]j[/math] из этого промежутка, что вершина с номером [math]r - 1[/math] является ее родителем, тогда [math]C_{r-1} \leqslant \min(d_{r-1},d'_{j}-1) = d'_{r-1}[/math]
[math]\triangleleft[/math]

Второй шаг

На втором этапе алгоритма работы сортируются в неубывающем порядке их дедлайнов. Предполагается, что работы занумерованы в соответствии с предыдущим пунктом, т.е. [math]d_{i} \leqslant d_{j}[/math], если [math]i \leqslant j[/math].

В переменной [math]F[/math] хранится время, когда станок освободится.

В массиве [math]r[/math] хранится информация о максимальном времени завершении обработки родителя.

Массив [math]c[/math] хранит информацию о количестве работ, готовых к исполнению (находящихся в очереди) в момент времени [math]t[/math].

Массив [math]x[/math] хранит информацию о начале выполнения работы [math]i[/math].

F = 0
for i = 1 .. n
   r[i] = 0
for t = 0 .. n
   c[t] = 0
for i = 1 .. n
   t = max(r[i], F)
   x[i] = t
   c[t] = c[t] + 1
   if n[t] == m
      F = t + 1
   j = s[i]
   r[j] = max (r[j], t + 1)

Расписание, сгенерированное этим алгоритмом имеет важное свойство: число заданий в очереди в любой момент времени [math]t[/math] меньше, чем в момент [math]t + 1[/math]. Действительно, пусть во время [math]t[/math] мы выполняем [math]k[/math] работ, и хотя бы [math]k + 1 \leqslant m[/math] работ готовы к выполению в момент времени [math]t + 1[/math]. Но т.к. [math]k + 1 \leqslant m[/math], значит каждой из работ предшествовала как минимум одна, поскольку у всех вершин, кроме корней, есть как минимум один предок. Значит, в момент времени [math]t[/math] исполнялось не менее [math]k + 1[/math] работ, противоречие.

Лемма:
Если существует такое расписание, в котором ни одна из работ не будет выполнена с опозданием, то тогда это свойство сохранится в построенном данным алгоритмом расписании
Доказательство:
[math]\triangleright[/math]

Предположим, что существует работа из [math]x_{1} \dots x_{n}[/math] расписания, построенного алгоритмом. В таком случае существует работа, которая опоздала по отношению к измененным срокам. Возьмем наименьшее [math]i[/math] такое, что [math]x(i) + 1 \gt d'_{i}[/math]. Пусть [math]t \lt d'_{i}[/math] — наибольшее из удовлетворяющих условию [math]j \lt m \mid x(j) = t, d'_{j} \leqslant d'_{i}[/math] Такое [math]t[/math] существует, потому что иначе [math]m \cdot d'_{i}[/math] работ [math]j[/math] с [math]d'_{j} \leqslant d'_{i}[/math] находятся в очереди до [math]d'_{i}[/math]. Работа [math]i[/math] к ним не принадлежит, поскольку [math]x(i) + 1 \gt d'_{i}[/math], а значит, что [math]m \cdot d'_{i} + 1[/math] должны быть в очереди в момент времени [math]0 \dots d'_{i}[/math] и ни одна работа не должна опаздывать. Противоречие. Любая работа [math]j[/math] с [math]d'_{j} \leqslant d'_{i} [/math] и [math] x(j) \gt t [/math] должна иметь предка, начавшего работать в момент времени [math]t[/math]. Теперь рассмотрим два случая:

Первый случай. [math]t = d'_{i} - 1[/math].

Мы имеем [math]x(i)\gt d'_{i}-1 = t[/math]. Таким образом, предок [math]k[/math] работы [math]i[/math] должен начать работать во время [math]t[/math] и закончить в [math]d'_{i}[/math]. Но т.к. [math]d'_{k} \leqslant d'_{i} - 1 \lt d'_{i} = x(k) + 1[/math], работа [math]k[/math] так же опоздает, однако [math]i[/math] было выбрано минимальным. Противоречие.

Второй случай. [math]t \lt d'_{i} - 1[/math].

В этом случае [math]m[/math] работ [math]j[/math] таких, что [math]d'_{j} \leqslant d'_{i}[/math] начнут работать в момент времени [math]t + 1[/math], каждая из которых имеет как минимум работающего в [math]t[/math] предка. По структуре дерева все эти предки различны, кроме того, если [math]k[/math] — такой предок [math]j[/math], тогда [math]d'_{k} \leqslant d'_{j} - 1 \lt d'_{j} \leqslant d'_{i}[/math], что противоречит выбору [math]t[/math]
[math]\triangleleft[/math]
Теорема:
Данный алгоритм корректно решает задачу [math]P \mid Tree, p_{i} = 1 \mid L_{max}[/math]
Доказательство:
[math]\triangleright[/math]
Пусть [math]L'_{max}[/math] — оптимальное значение. В таком случае, существует расписание, удовлетворяющее [math]\max\limits_i \{C_i - d_i\} \leqslant L'_{max}[/math], что эквивалетно выражению [math]C_{i} \leqslant d_{i} + L'_{max}[/math] для [math]i = 1 \dots n [/math]. По первой лемме расписание [math]S[/math], построенное для сдвинутых дат [math]d_{i} + L'_{max}[/math] удовлетворяет данным выражениям. Таким образом, оно оптимально. Нетрудно заметить, что [math]S[/math] идентично расписанию, построенному алгоритмом, т.к. [math](d_{i}+L'_{max})' = d'_{i} + L'_{max} [/math] для [math]i = 1 \dots n [/math]
[math]\triangleleft[/math]

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

  • Peter Brucker «Scheduling Algorithms», fifth edition, Springer — с. 151-156 ISBN 978-3-540-69515-8