Викиконспекты - Вклад участника [ru]

1precpmtnrifmax

2012-06-04T13:47:13Z

217.66.152.156: /* Modify */

== Постановка задачи ==
Задача <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>.

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

Blocks(<tex> \{ 1 \ldots n \} </tex>)
1 <tex> j \leftarrow 0 </tex>
2 <tex> t \leftarrow 0 </tex>
3 '''for''' <tex> i \in \{ 1 \ldots n \} </tex>
4 '''if''' <tex> t < r_i </tex>
5 <tex> t \leftarrow r_i </tex>
6 <tex> j \leftarrow j + 1 </tex>
7 <tex> B_j \leftarrow B_j \cup i </tex>
8 <tex> t \leftarrow t + p_i </tex>
9 return <tex> {B_1, \ldots, B_j} </tex>

Если алгоритм Blocks вызывается от пустого множества, то считаем, что он возвращает также пустое множество.

Определим время начала блока <tex> B_j </tex> как <tex>s_j = \min\limits_{i \in B_j} r_i </tex>, а время конца — как <tex> e_j = s_j + \sum\limits_{i \in B_j} p_i </tex>.

{{Лемма
|statement=
Существует оптимальное расписание, такое, что все во все временные интервалы <tex> [s_j; e_j] </tex>, соответствующие блокам <tex> B_j </tex>, построенным алгоритмом Blocks, станок работает без простоя.
|proof=
Возьмем произвольное оптимальное расписание <tex> S </tex>, в нем деление на блоки может также быть произвольным. Найдем первый такой временной интервал <tex> [s_j; e_j] </tex>, что в <tex> S </tex> есть период простоя внутри <tex> [s_j; e_j] </tex> (если таких периодов несколько, будем рассматривать первый из них). Обозначим его за <tex> [s; e] </tex>.

Возьмем некоторую работу <tex> i </tex>, такую, что она начинается позже, чем в момент времени <tex> s </tex>, не имеет в графе зависимостей предков, завершаемых позже, чем в момент <tex> s </tex> и <tex> r_i \le s </tex>. Такая работа обязательно существует, иначе для множества работ, выполняемых позже, чем в момент <tex> s </tex>, было бы <tex> r = \min\limits{k \in T} r_k > s </tex>, и внутри блока <tex> B_j </tex> был бы простой <tex> [s_j; r] </tex>, что невозможно по построению алгоритма Blocks. Очевидно, мы можем начать выполнять ее в момент времени <tex> s </tex> и полностью, либо частично заполнить простой <tex> [s; e] </tex>; так как <tex> f_i </tex> — неубывающая функция, то ответ останется оптимальным. Повторяя этот процесс, мы за конечное число шагов придем к оптимальному расписанию с требуемым свойством.
}}

=== Decompose ===
Допустим, у нас есть блок работ, который можно выполнить без прерываний. Общая идея алгоритма Decompose следующая: найдем работу <tex> i </tex>, которую выгоднее всего выполнить последней. Разобъем оставшееся множество работ на блоки, решим задачу для этих блоков рекурсивно и вставим <tex> i </tex> в промежутки между ними, до них и после них, начиная с <tex> r_i </tex>. Псевдокод этого алгоритма представлен ниже.

Decompose(B)
1 найти <tex> l: f_l(e) = \min \{f_j(e) \mid j \in B, \overline\exists\ k: jk \in E \} </tex>
2 ans <tex> \leftarrow f_l(e) </tex>
3 G <tex> \leftarrow </tex> Blocks(<tex> B \setminus l </tex>)
4 вставить l в промежутки между блоками G, начиная с <tex> r_l </tex>
5 '''for''' <tex>B_j \in G </tex>:
6 ans = max(ans, Decompose(<tex> B_j </tex>))
7 return ans

{{Теорема
|statement=
Расписание для блока, построенное алгоритмом Decompose, является корректным и оптимальным.
|proof=
Докажем сначала корректность.

Убедимся, что порядок выполнения работ, заданный графом зависимостей, не нарушается. Заметим, что в разбиении <tex> B \setminus l </tex> на блоки существует не более одного блока <tex> B_0 </tex>, расположенного до момента времени <tex> r_l </tex> — иначе после вставки <tex> l </tex> в промежутки между блоками, <tex> B </tex> выполнялся бы с прерываниями. Далее, заметим, что все интервалы времени, на которые назначается работа из блока <tex> B_j </tex>, находятся внутри интервала <tex> [s_j; e_j] </tex>; это относится и к блоку <tex> B_0 </tex>. Из этих двух наблюдений, а также того, что все работы со временами появления меньше, чем <tex> r_l </tex>, будут помещены в блок <tex> B_0 </tex>, следует, что порядок выполнения будет правильным.

Также для корректности требуется, чтобы работы выполнялись не раньше, чем они появляются. Так как время выполнения работы определяется только в строке 4 алгоритма, которая соответствует этому требованию, то условие выполняется.

Найдем теперь нижнюю оценку на <tex> f_{max} </tex>. Пусть <tex> f_{max}(J) </tex> — ответ для множества работ <tex> J </tex>.

Очевидно, для любой работы <tex> j \in J </tex> выполняется <tex> f_{max}(J) \ge f_{max}(J \setminus j) </tex>, значит, <tex> f_{max}(J) \ge \max\limits_{j \in J} f_{max}(J \setminus j) </tex>.

Также, так как в оптимальном решении какая-то работа без потомков обязательно заканчивается в блоке <tex> B </tex>, то <tex> f_{max}(J) \ge f_l(e) </tex>.

Отсюда следует <tex> f_{max}(J) \ge \max(f_l(e), \max\limits_{j \in J} f_{max}(J \setminus j)) </tex>. По псевдокоду алгоритма видно, что его ответ достигает этой нижней оценки.
}}

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

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

MakeSchedule()
1 Modify()
2 B <tex> \leftarrow </tex> Blocks(<tex> \{1 \ldots n \} </tex>)
3 ans <tex> \leftarrow </tex> <tex> -\infty </tex>
4 for (<tex> B_j \in B</tex>):
5 ans = max(ans, Decompose(<tex> B_j </tex>))
6 return ans

Из доказанной ранее леммы следует, что <tex> f_{max}(\{ 1 \ldots n \}) = \max\limits_{j} f_{max}(B_j) </tex>, поэтому расписание для всего множества работ, поделенного на блоки, также будет оптимальным и корректным.

== Время работы ==
{{Теорема
|statement=
Время работы алгоритма MakeSchedule — <tex> O(n^2) </tex> операций.
|proof=
Обозначим за <tex> P(n) </tex> время, необходимое для выполнения алгоритма MakeSchedule на n работах. Очевидно, для корректно определенной функции P в силу структуры алгоритма должно выполняться неравенство:

<tex> P(n) \ge сn + \sum\limits_{i = 1}^{k} P(n_i) </tex>

Здесь <tex> n_i </tex> - размер блока с номером <tex> i </tex>, построенного алгоритмом Blocks(). Заметим, что <tex> \sum\limits_{i = 1}^{k} n_i = n - 1</tex>.

Если <tex> P(n) = an^2 </tex>, то имеем:

<tex> an^2 \ge cn + a \sum\limits_{i = 1}^{k} n_i^2 </tex>

Так как <tex> n^2 > (n - 1)^2 = (\sum\limits_{i = 1}^{k} n_i)^2 = \sum\limits_{i = 1}^{k} n_i^2 + 2\sum\limits_{\substack{i, j = 1\\ i \ne j}}^{k} n_i n_j </tex>, то можно переписать неравенство в следующем виде:

<tex> 2a \sum\limits_{\substack{i, j = 1\\ i \ne j}}^{k} n_i n_j \ge cn </tex>

Чтобы получить максимальную нижнюю оценку на <tex> a </tex>, оценим снизу <tex> \sum\limits_{i, j = 1}^{k} n_i n_j </tex>:

<tex> \sum\limits_{\substack{i, j = 1\\ i \ne j}}^{k} n_i n_j \ge \sum\limits_{\substack{i, j = 1\\ i \ne j}}^{k} 1 \cdot n_j = \sum\limits_{j = 1}^{k} (k - 1) n_j = (k - 1) (n - 1) \ge \frac{nk}{4}</tex>

Значит, при <tex> a \ge \frac{c}{2} \frac{n}{\frac{nk}{4}} = \frac{2c}{k} </tex> требуемое неравенство будет выполняться.

}}

==Источники==
* Peter Brucker. «Scheduling Algorithms» {{---}} «Springer», 2006 г. {{---}} 379 стр. {{---}} ISBN 978-3-540-69515-8

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Теория расписаний]]

QpmtnriLmax

2012-06-04T13:25:59Z

217.66.152.156:

<includeonly>[[Категория: В разработке]]</includeonly>

[[Файл:Figure_5.2.png|400px|thumb|right|Рис. 1 - Исходная сеть]]

==Постановка задачи==
Рассмотрим еще одну задачу на нахождение расписания:

# Каждое задание имеет своё времени выпуска <tex>r_i</tex>.
# Срок завершения(дедлайн) <tex>d_i</tex>.

Требуется минимизировать опоздание <tex>L_i = C_i - d_i</tex>

==Алгоритм решения==
[[Файл:Figure_5.9.a.png|200px|thumb|right|Рис. 2.1 - Заменённая подсеть]]

Применим бинарный поиск. Таким образом сведем задачу к поиску потока сети.

Пусть <tex> t_1 < t_2 <...< t_r </tex> упорядоченная последовательности всех значений <tex>r_i</tex> и <tex>d_i</tex>.
Определим <tex> I_K := [t_{K-1}, t_K], \ T_K = t_K-t_{K-−1} </tex> для <tex> K = 2,..., r </tex>.

Расширим сеть, показанную на Рис. 1 следующим образом:

<tex>I_K</tex> - произвольный интервал-узел. Обозначим через <tex> J_{i_1}, J_{i_2}, . . . , J_{i_s} </tex> набор предшественников узла <tex>I_K</tex>, тогда замененная нами подсеть(Рис. 2.1) определяется как <tex> I_K, J_{i_1}, J_{i_2}, . . . , J_{i_s} </tex>. Расширение сети показано на Рис. 2.2.

Cчитаем, что станки индексируются в порядке невозрастания скоростей <tex> s_1 \ge s_2 \ge . . . \ge s_m </tex>, кроме того <tex>s_{m+1} = 0</tex>.

Расширенная подсеть строится путем добавления к вершинам <tex> I_K, J_{i_1}, J_{i_2}, . . . , J_{i_s} </tex> вершин <tex>(K, 1), (K, 2), . . . (K, m) </tex>. При <tex>j = 1,..., m </tex>, есть дуги от <tex>(K, j)</tex> до <tex>I_K</tex> с емкостью <tex> j(s_j - s_{j+1}) T_K </tex> и для всех <tex>ν = 1,. . . , s</tex> и <tex>j = 1,. . ., m</tex> существует дуга из <tex>J_{i_ν}</tex> в <tex>(K, J)</tex> с емкостью <tex> (s_j - s_{j+1}) T_K </tex>.

Для каждого <tex>I_K</tex> у нас есть такие расширения. Кроме того, мы сохраняем дуги из <tex>s</tex> в <tex>J_i</tex> емкостью <tex>p_i</tex> и дуги из <tex>I_K</tex> в <tex>t</tex> емкостью <tex>S_mT_K</tex> (Рис. 1).

{{Теорема
|statement=Следующие свойства эквивалентны:

(А) Существует допустимое расписание.

(Б) В расширенной сети существует поток от s до t со значением <tex>\sum\limits_{i=1}^{n} p_i</tex>
}}
[[Файл:Figure_5.9.b.png|500px|thumb|right|Рис. 2.2 - Расширение сети]]

==Время работы==

Работа с максимальным потоком в расширенной сети занимает <tex>O (m n^3)</tex> шагов, проверка может быть сделана с такой же скоростью. Для решения <tex>Q|pmtn; r_{i}|L_{max}</tex> мы используем бинарный поиск, получается алгоритм со сложностью <tex>O (mn^3(log(n) + log (\max\limits_{i=1}^{n} p_i)) </tex>, потому как <tex>L_{max}</tex>, ограничен <tex>n \max\limits_{i=1}^{n}p_i</tex>, при <tex>s_1 = 1</tex>.

<tex>Q | pmtn; ri | Cmax</tex> представляет собой частный случай <tex>Q | pmtn; ri | Lmax</tex>, и может быть решена более эффективно. Labetoulle, Lawler, Lenstra, и Rinnooy Kan разработали алгоритм работающий за <tex> O(n log(n) + mn) </tex> специально для этого случая.
{{Утверждение
|statement= Задача <tex>Q | pmtn | Lmax</tex> может быть решена за <tex> O(n log(n) + mn) </tex> шагов.
|proof=
Решение <tex>Q | pmtn; ri | Cmax</tex> эквивалентно нахождению наименьшего <tex>T \ge 0</tex>, такого, что задача с допустимым временным интервалом <tex>[r_i, T] (i = 1, . . . , n)</tex> имеет решение.

С другой стороны, решение <tex>Q | pmtn | Lmax</tex> эквивалентно нахождению такого наименьшего <tex>T \ge 0</tex>, такого, что задача с временным интервалом <tex>[0, d_i + T]</tex> или <tex>[−T, d_i]</tex> имеет решение.
}}
Таким образом, задачи <tex>Q | pmtn; ri | Cmax</tex> и <tex>Q | pmtn | Lmax</tex> симметричны.

==Источники==
* Peter Brucker. «Scheduling Algorithms» {{---}} «Springer», 2006 г. {{---}} 379 стр. {{---}} ISBN 978-3-540-69515-8

[[Категория: Теория расписаний]]