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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «==Постановка задачи== Имеется N работ и M однородных машин.»)
 
Строка 1: Строка 1:
 
==Постановка задачи==
 
==Постановка задачи==
  
Имеется N работ и M однородных машин.
+
# Имеется <tex>M</tex> однородных машин, работающих параллельно.
 +
# Есть <tex>N</tex> работ, каждое имеет своё время появления <tex>r_i</tex> и время окончания <tex>d_i</tex>.
 +
# Работа может быть прервана и продолжена позже.
 +
 
 +
Необходимо составить такое расписание, чтобы значение <tex>L_{max} = max_{i=1}^n (C_i - d_i)</tex> было минимальным.
 +
 
 +
== Решение ==
 +
 
 +
Для начала научимся отвечать на следующий вопрос: пусть дано некоторое <tex>L</tex>, сможем ли мы составить расписание так, чтобы <tex>L_{max} \le L</tex> и <tex>\forall i : C_i \le d_i^L = L + d_i</tex>. Затем обратимся к проблеме нахождения такого расписания, что работа выполняется в интервале <tex>[r_i; d_i]</tex>.
 +
 
 +
Сведем эту задачу к поиску максимального потока в сети, построенной указанным ниже образом.
 +
 
 +
Пусть <tex>t_1 < t_2 < \ldots < t_r</tex> - упорядоченная последовательность <tex>r_i</tex> и <tex>d_i</tex>. Определим интервалы <tex>I_K = [t_K; t_{K+1}]</tex> с длиной <tex>T_K = t_{K+1} - t_K</tex> для всех <tex>K = 1 \ldots r-1</tex>.
 +
 
 +
Работам сопоставим свой тип вершин, а интервалам <tex>I_K</tex> свой. Добавим две фиктивные вершины <tex>s</tex> и <tex>t</tex>. Из вершины <tex>s</tex> в вершины с работами идут направленные ребра с пропускной способностью <tex>p_i</tex>, из вершин с интервалами в вершину <tex>t</tex> идут направленные ребра с пропускной способностью <tex>mT_K</tex>. Ребро между вершиной с работой и вершиной с интервалом существует, если <tex>r_i \le t_K, t_{K+1} \le d_i</tex>. Пропускная способность этого ребра - <tex>T_K</tex>.

Версия 17:39, 9 июня 2012

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

  1. Имеется [math]M[/math] однородных машин, работающих параллельно.
  2. Есть [math]N[/math] работ, каждое имеет своё время появления [math]r_i[/math] и время окончания [math]d_i[/math].
  3. Работа может быть прервана и продолжена позже.

Необходимо составить такое расписание, чтобы значение [math]L_{max} = max_{i=1}^n (C_i - d_i)[/math] было минимальным.

Решение

Для начала научимся отвечать на следующий вопрос: пусть дано некоторое [math]L[/math], сможем ли мы составить расписание так, чтобы [math]L_{max} \le L[/math] и [math]\forall i : C_i \le d_i^L = L + d_i[/math]. Затем обратимся к проблеме нахождения такого расписания, что работа выполняется в интервале [math][r_i; d_i][/math].

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

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