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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Решение)
(не показаны 3 промежуточные версии 2 участников)
Строка 4: Строка 4:
 
|definition = <ol>
 
|definition = <ol>
 
<li>Имеется <tex>M</tex> однородных машин, работающих параллельно.</li>
 
<li>Имеется <tex>M</tex> однородных машин, работающих параллельно.</li>
<li>Есть <tex>N</tex> работ, каждое имеет своё время появления <tex>r_i</tex> и время окончания <tex>d_i</tex>.</li>
+
<li>Есть <tex>n</tex> работ, каждое имеет своё время появления <tex>r_i</tex> и время окончания <tex>d_i</tex>.</li>
 
<li>Работа может быть прервана и продолжена позже.</li>
 
<li>Работа может быть прервана и продолжена позже.</li>
 
</ol>
 
</ol>
  
Необходимо составить такое расписание, чтобы значение <tex>L_{max} = \max\limits_{i=1..n} (C_i - d_i)</tex> было минимальным.}}
+
Необходимо составить такое расписание, чтобы значение <tex>L_{max} = \max\limits_{i=1\ldots n} (C_i - d_i)</tex> было минимальным.}}
  
 
== Решение ==
 
== Решение ==
  
[[Файл:Figure_5.2.png|400px|thumb|right|Рис. 1 - Cеть]]
+
[[Файл:Figure_5.2.png|400px|thumb|right|Рис. 1. Cеть]]
  
 
Сведем эту задачу к поиску максимального потока в сети, построенной указанным ниже образом.
 
Сведем эту задачу к поиску максимального потока в сети, построенной указанным ниже образом.
Строка 20: Строка 20:
 
Работам <tex>J_i</tex> сопоставим свой тип вершин, а интервалам <tex>I_K</tex> свой. Добавим две фиктивные вершины <tex>s</tex> и <tex>t</tex>. Вершина <tex>s</tex> соединена с вершинами <tex>J_i</tex> ребрами с пропускной способностью <tex>p_i</tex>, вершина <tex>t</tex> соединена с вершинами <tex>I_K</tex> ребрами с пропускной способностью <tex>mT_K</tex>. Ребро между вершиной <tex>J_i</tex> и вершиной <tex>I_K</tex> существует, если <tex>r_i \leqslant t_K, t_{K+1} \leqslant d_i</tex>. Пропускная способность этого ребра - <tex>T_K</tex>.
 
Работам <tex>J_i</tex> сопоставим свой тип вершин, а интервалам <tex>I_K</tex> свой. Добавим две фиктивные вершины <tex>s</tex> и <tex>t</tex>. Вершина <tex>s</tex> соединена с вершинами <tex>J_i</tex> ребрами с пропускной способностью <tex>p_i</tex>, вершина <tex>t</tex> соединена с вершинами <tex>I_K</tex> ребрами с пропускной способностью <tex>mT_K</tex>. Ребро между вершиной <tex>J_i</tex> и вершиной <tex>I_K</tex> существует, если <tex>r_i \leqslant t_K, t_{K+1} \leqslant d_i</tex>. Пропускная способность этого ребра - <tex>T_K</tex>.
  
Нетрудно понять, что расписание существует, если максимальный поток через эту сеть равен <tex>\sum_{i=1}^n p_i</tex>.
+
Нетрудно понять, что расписание существует, если максимальный поток через эту сеть равен <tex>\sum\limits_{i=1}^n p_i</tex>.
  
 
Если это так, то поток <tex>x_{iK}</tex> на дуге <tex>(J_i, I_K)</tex> соответствует тому, что работа <tex>J_i</tex> будет выполняться во временном интервале <tex>I_K</tex>, и будет справедливо следующее:
 
Если это так, то поток <tex>x_{iK}</tex> на дуге <tex>(J_i, I_K)</tex> соответствует тому, что работа <tex>J_i</tex> будет выполняться во временном интервале <tex>I_K</tex>, и будет справедливо следующее:
  
# <tex>\sum_{K=1}^{r-1} x_{iK} = p_i, i = 1 \ldots n</tex>
+
# <tex>\sum\limits_{K=1}^{r-1} x_{iK} = p_i, i = 1 \ldots n</tex>
# <tex>\sum_{i=1}^n x_{iK} \leqslant mT_K, K = 1 \ldots r - 1</tex>
+
# <tex>\sum\limits_{i=1}^n x_{iK} \leqslant mT_K, K = 1 \ldots r - 1</tex>
 
# <tex>x_{iK} \leqslant T_K</tex> для всех ребер <tex>(J_i, I_K)</tex>
 
# <tex>x_{iK} \leqslant T_K</tex> для всех ребер <tex>(J_i, I_K)</tex>
  
 
Исходя из этого, расписание строится выполнением работы <tex>J_{iK}</tex> с временем выполнения <tex>x_{iK} > 0</tex> в интервале <tex>I_K</tex>.
 
Исходя из этого, расписание строится выполнением работы <tex>J_{iK}</tex> с временем выполнения <tex>x_{iK} > 0</tex> в интервале <tex>I_K</tex>.
  
Т.к. сеть содержит <tex>O(N)</tex> элементов, значит максимальный поток в ней можно найти за <tex>O(n^3)</tex>. Кроме того, построение "окон" выполнения работ займет <tex>O(N^2)</tex>. Т.о. указанный выше алгоритм потребует <tex>O(N^3)</tex> операций.  
+
Т.к. сеть содержит <tex>O(n)</tex> элементов, значит максимальный поток в ней можно найти за <tex>O(n^3)</tex>. Кроме того, построение "окон" выполнения работ займет <tex>O(n^2)</tex>. Т.о. указанный выше алгоритм потребует <tex>O(n^3)</tex> операций.  
  
Для решения данной задачи мы используем бинпоиск по <tex>L</tex> значениям, а значит, получаем алгоритм с <tex>\varepsilon</tex>-приближенной  сложностью <tex>O (n^3(log(n) + log(1 / \varepsilon) + log(\max\limits_{j=1..n} (p_j))) </tex>, потому как <tex>L_{max}</tex>, ограничен <tex>n\max\limits_{j=1..n} (p_j)</tex>
+
Для решения данной задачи мы используем бинпоиск по <tex>L</tex> значениям, а значит, получаем алгоритм с <tex>\varepsilon</tex>-приближенной  сложностью <tex>O (n^3(\log(n) + \log(\cfrac{1}{\varepsilon}) + \log(\max\limits_{j=1 \ldots n} (p_j))) </tex>, потому как <tex>L_{max}</tex>, ограничен <tex>n\max\limits_{j=1 \ldots n} (p_j)</tex>
  
[[Категория: Дискретная математика и алгоритмы]]
+
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Теория расписаний]]
 
[[Категория: Теория расписаний]]

Версия 01:02, 14 июня 2015

[math]P \mid pmtn, r_i \mid L_{max}[/math]


Задача:
  1. Имеется [math]M[/math] однородных машин, работающих параллельно.
  2. Есть [math]n[/math] работ, каждое имеет своё время появления [math]r_i[/math] и время окончания [math]d_i[/math].
  3. Работа может быть прервана и продолжена позже.
Необходимо составить такое расписание, чтобы значение [math]L_{max} = \max\limits_{i=1\ldots n} (C_i - d_i)[/math] было минимальным.


Решение

Рис. 1. Cеть

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

Пусть [math]t_1 \lt t_2 \lt \ldots \lt t_r[/math] - упорядоченная последовательность [math]r_i[/math] и [math]d_i[/math]. Определим интервалы [math]I_K = [t_K; t_{K+1}][/math] с длиной [math]T_K = t_{K+1} - t_K[/math] для всех [math]K = 1 \ldots r-1[/math].

Работам [math]J_i[/math] сопоставим свой тип вершин, а интервалам [math]I_K[/math] свой. Добавим две фиктивные вершины [math]s[/math] и [math]t[/math]. Вершина [math]s[/math] соединена с вершинами [math]J_i[/math] ребрами с пропускной способностью [math]p_i[/math], вершина [math]t[/math] соединена с вершинами [math]I_K[/math] ребрами с пропускной способностью [math]mT_K[/math]. Ребро между вершиной [math]J_i[/math] и вершиной [math]I_K[/math] существует, если [math]r_i \leqslant t_K, t_{K+1} \leqslant d_i[/math]. Пропускная способность этого ребра - [math]T_K[/math].

Нетрудно понять, что расписание существует, если максимальный поток через эту сеть равен [math]\sum\limits_{i=1}^n p_i[/math].

Если это так, то поток [math]x_{iK}[/math] на дуге [math](J_i, I_K)[/math] соответствует тому, что работа [math]J_i[/math] будет выполняться во временном интервале [math]I_K[/math], и будет справедливо следующее:

  1. [math]\sum\limits_{K=1}^{r-1} x_{iK} = p_i, i = 1 \ldots n[/math]
  2. [math]\sum\limits_{i=1}^n x_{iK} \leqslant mT_K, K = 1 \ldots r - 1[/math]
  3. [math]x_{iK} \leqslant T_K[/math] для всех ребер [math](J_i, I_K)[/math]

Исходя из этого, расписание строится выполнением работы [math]J_{iK}[/math] с временем выполнения [math]x_{iK} \gt 0[/math] в интервале [math]I_K[/math].

Т.к. сеть содержит [math]O(n)[/math] элементов, значит максимальный поток в ней можно найти за [math]O(n^3)[/math]. Кроме того, построение "окон" выполнения работ займет [math]O(n^2)[/math]. Т.о. указанный выше алгоритм потребует [math]O(n^3)[/math] операций.

Для решения данной задачи мы используем бинпоиск по [math]L[/math] значениям, а значит, получаем алгоритм с [math]\varepsilon[/math]-приближенной сложностью [math]O (n^3(\log(n) + \log(\cfrac{1}{\varepsilon}) + \log(\max\limits_{j=1 \ldots n} (p_j))) [/math], потому как [math]L_{max}[/math], ограничен [math]n\max\limits_{j=1 \ldots n} (p_j)[/math]