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

Материал из Викиконспекты
Перейти к: навигация, поиск
(pre-alpha-0.01 version)
 
(Добавил Modify и общий алгоритм.)
Строка 1: Строка 1:
Данная задача является обобщением [[Правило Лаулера|<tex>1 \mid prec \mid f_{max}</tex>]] и также использует правило Лаулера для построения оптимального расписания.
+
== Постановка задачи ==
 +
Задача <tex> 1 \mid prec, pmtn, r_i \mid f_{max} </tex> является обобщением [[Правило Лаулера|<tex>1 \mid prec \mid f_{max}</tex>]], но здесь у работ также есть времена появления, раньше которых их делать запрещено, и их можно прерывать.
  
 
== Алгоритм ==
 
== Алгоритм ==
 +
Работу будем обозначать просто ее номером (<tex> i </tex>), при этом, номера работ могут меняться в зависимости от того, по какому параметру они отсортированы. Время появления работы — <tex> r_i </tex>, время, требуемое для ее выполнения — <tex> p_i </tex>. Множество ребер графа обозначается как <tex> E </tex>.
 +
 +
=== Modify ===
 +
Для начала, модифицируем времена появления работ. Если работа <tex> j </tex> зависит от <tex> i </tex>, то, очевидно, она не может быть начата раньше, чем закончится выполнение </tex> i </tex>, поэтому нужно заменить <tex> r_j </tex> на <tex> \max(r_j, r_i + p_i) </tex>. Алгоритм, делающий это, представлен ниже (работы рассматриваются в порядке топологической сортировки):
 +
 +
Modify()
 +
1    '''for''' i <tex> \in \{ 1 \ldots n \} </tex>
 +
2      '''for''' j: ij <tex> \in E </tex>
 +
3        <tex> r_j \leftarrow \max(r_j, r_i + p_i) </tex>
 +
 +
После выполнения этого алгоритма для любых двух работ <tex> i, j </tex>, таких, что <tex> j </tex> зависит от <tex> i </tex>, выполняется <tex> r_j > r_i </tex>, поэтому, при рассмотрении работ в порядке неубывания времен их появления, они также будут топологически отсортированы.
 +
 +
=== Blocks ===
 +
Здесь и далее считается, что работы отсортированы в порядке неубывания модифицированных <tex> r_i </tex>.
 +
 +
=== Decompose ===
 
Идея следующая: допустим, у нас есть блок работ, который можно выполнить без прерываний. Найдем работу <tex>i</tex>, которую выгодно выполнить последней. Разобъем оставшееся множество работ на блоки, решим задачу для этих блоков рекурсивно и вставим <tex> i </tex> в промежутки между этими блоками, до них и после них, начиная с <tex> r_i </tex>.
 
Идея следующая: допустим, у нас есть блок работ, который можно выполнить без прерываний. Найдем работу <tex>i</tex>, которую выгодно выполнить последней. Разобъем оставшееся множество работ на блоки, решим задачу для этих блоков рекурсивно и вставим <tex> i </tex> в промежутки между этими блоками, до них и после них, начиная с <tex> r_i </tex>.
 +
 +
=== Общий алгоритм ===
 +
 +
Выполним Modify(), после чего разобъем все множество работ на блоки и для каждого блока запустим '''Decompose'''():
 +
 +
<tex> 1 \mid prec, pmtn, r_i \mid f_{max} </tex>()
 +
1    Modify()
 +
2    B = '''Blocks(<tex> \{1 \ldots n \} </tex>)
 +
3    ans = - <tex> \infty </tex>
 +
4    for (<tex> B_i \in </tex> B):
 +
5      ans = <tex> \max </tex> (ans, '''Decompose'''(<tex> B_i </tex>))
 +
6    return ans
 +
 +
== Время работы ==
 +
Лемма: время работы алгоритма <tex> 1 \mid prec, pmtn, r_i \mid f_{max} </tex> — <tex> O(n^2) </tex> операций.

Версия 18:10, 3 июня 2012

Постановка задачи

Задача [math] 1 \mid prec, pmtn, r_i \mid f_{max} [/math] является обобщением [math]1 \mid prec \mid f_{max}[/math], но здесь у работ также есть времена появления, раньше которых их делать запрещено, и их можно прерывать.

Алгоритм

Работу будем обозначать просто ее номером ([math] i [/math]), при этом, номера работ могут меняться в зависимости от того, по какому параметру они отсортированы. Время появления работы — [math] r_i [/math], время, требуемое для ее выполнения — [math] p_i [/math]. Множество ребер графа обозначается как [math] E [/math].

Modify

Для начала, модифицируем времена появления работ. Если работа [math] j [/math] зависит от [math] i [/math], то, очевидно, она не может быть начата раньше, чем закончится выполнение </tex> i </tex>, поэтому нужно заменить [math] r_j [/math] на [math] \max(r_j, r_i + p_i) [/math]. Алгоритм, делающий это, представлен ниже (работы рассматриваются в порядке топологической сортировки):

Modify()
1    for i [math] \in \{ 1 \ldots n \} [/math]
2      for j: ij [math] \in E [/math]
3        [math] r_j \leftarrow \max(r_j, r_i + p_i) [/math] 

После выполнения этого алгоритма для любых двух работ [math] i, j [/math], таких, что [math] j [/math] зависит от [math] i [/math], выполняется [math] r_j \gt r_i [/math], поэтому, при рассмотрении работ в порядке неубывания времен их появления, они также будут топологически отсортированы.

Blocks

Здесь и далее считается, что работы отсортированы в порядке неубывания модифицированных [math] r_i [/math].

Decompose

Идея следующая: допустим, у нас есть блок работ, который можно выполнить без прерываний. Найдем работу [math]i[/math], которую выгодно выполнить последней. Разобъем оставшееся множество работ на блоки, решим задачу для этих блоков рекурсивно и вставим [math] i [/math] в промежутки между этими блоками, до них и после них, начиная с [math] r_i [/math].

Общий алгоритм

Выполним Modify(), после чего разобъем все множество работ на блоки и для каждого блока запустим Decompose():

[math] 1 \mid prec, pmtn, r_i \mid f_{max} [/math]()
1    Modify()
2    B = Blocks([math] \{1 \ldots n \} [/math])
3    ans = - [math] \infty [/math]
4    for ([math] B_i \in [/math] B):
5      ans = [math] \max [/math] (ans, Decompose([math] B_i [/math]))
6    return ans

Время работы

Лемма: время работы алгоритма [math] 1 \mid prec, pmtn, r_i \mid f_{max} [/math][math] O(n^2) [/math] операций.