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

Материал из Викиконспекты
Перейти к: навигация, поиск
(добавлен заголовок в нотации Грэхема)
(не показано 8 промежуточных версий 1 участника)
Строка 1: Строка 1:
==Постановка задачи==
+
<tex dpi=200>1 \mid prec; r_i; p_i = 1 \mid L_{max}</tex>
Рассмотрим задачу:
+
 
<ol>
+
{{Задача
<li>Дано <tex>n</tex> работ и один станок.</li>
+
|definition = Дано <tex>n</tex> работ и один станок. Для каждой работы известно её время появления <tex>r_{i}</tex>. Время выполнения всех работ <tex>p_i</tex> равно <tex>1</tex>. Работа может начаться только после выполнения некоторых других работ, эта зависимость дана в виде ациклического графа. Необходимо составить такое расписание, чтобы значение <tex>L_{max} = \max\limits_{i=1..n} (C_i - d_i)</tex> было минимальным.
<li>Для каждой работы известно её время появления <tex>r_{i}</tex>. Время выполнения всех работ <tex>p_i</tex> равно <tex>1</tex>. Работа может начаться только после выполнения некоторых других работ, эта зависимость дана в виде ациклического графа.</li>
+
}}
</ol>
 
Необходимо составить такое расписание, чтобы значение <tex>L_{max} = max_{i=1}^n (C_i - d_i)</tex> было минимальным.
 
  
 
==Описание алгоритма==
 
==Описание алгоритма==
Строка 12: Строка 10:
 
<ol>
 
<ol>
 
<li> Выполнять работу <tex>k</tex> из множества невыполненных работ, у которой <tex>d_{k}</tex> минимально.</li>
 
<li> Выполнять работу <tex>k</tex> из множества невыполненных работ, у которой <tex>d_{k}</tex> минимально.</li>
<li> Увеличиваем <tex>time</tex> на один.</li>
+
<li> Увеличивать <tex>time</tex> на один.</li>
 
</ol>
 
</ol>
  
 
==Доказательство==
 
==Доказательство==
[[Файл:1precripi1Lmax.png|500px|thumb|right|Пояснение]]
 
 
Пусть существует оптимальное расписание <tex> S^* </tex>. В этом расписании работа выполняется тогда, когда она появилась, либо когда закончилась другая работа.
 
Пусть существует оптимальное расписание <tex> S^* </tex>. В этом расписании работа выполняется тогда, когда она появилась, либо когда закончилась другая работа.
Рассмотрим такое расписание <tex>S^*</tex>, которое как можно дольше совпадает с расписанием S, построенным алгоритмом. Пусть <tex> t~-</tex> первый момент времени, когда в расписании <tex>S</tex> начинает выполняться работа <tex>i</tex>, а в расписании <tex>S^*</tex> работа <tex>j</tex> (причем <tex> i \ne j </tex>). Мы знаем, что <tex> r_i, r_j \le t </tex>, а значит <tex> d_i \le d_j </tex> (поскольку при построении мы выбираем минимальное доступное <tex> d_k </tex>). Пусть <tex> i_1, i_2, ..., i_l~-</tex> все работы, которые  находятся в расписании <tex>S^*</tex> между работами <tex>j</tex> и <tex>i</tex>  и являются наследниками работы <tex>j</tex>. Кроме того, предположим, что эти работы упорядочены по времени начала выполнения. Теперь, если мы поставим работу <tex>i_l</tex> вместо <tex>i, i_{l-1}</tex> вместо <tex>i_{l}, ..., j</tex> вместо <tex>i_1, i</tex> вместо <tex>j</tex>, то мы снова получим возможное оптимальное расписание <tex> S' </tex>. так как <tex> d_i \le d_j \le d_v </tex>, где <tex> v \in {i_1, i_2, ... i_l} </tex>. Последнее неравенство имеет место быть, поскольку все работы <tex>i_v</tex> являются наследниками работы <tex>j</tex>.
+
Рассмотрим такое расписание <tex>S^*</tex>, которое как можно дольше совпадает с расписанием S, построенным алгоритмом. Пусть <tex> t~-</tex> первый момент времени, когда в расписании <tex>S</tex> начинает выполняться работа <tex>i</tex>, а в расписании <tex>S^*</tex> работа <tex>j</tex> (причем <tex> i \ne j </tex>). Мы знаем, что <tex> r_i, r_j \leqslant t </tex>, а значит <tex> d_i \leqslant d_j </tex> (поскольку при построении мы выбираем минимальное доступное <tex> d_k </tex>). Пусть <tex> i_1, i_2, \ldots, i_l~-</tex> все работы, которые  находятся в расписании <tex>S^*</tex> между работами <tex>j</tex> и <tex>i</tex>  и являются наследниками работы <tex>j</tex>. Кроме того, предположим, что эти работы упорядочены по времени начала выполнения. Теперь, если мы поставим работу <tex>i_l</tex> вместо <tex>i, i_{l-1}</tex> вместо <tex>i_{l}, \ldots, j</tex> вместо <tex>i_1, i</tex> вместо <tex>j</tex>, то мы снова получим возможное оптимальное расписание <tex> S' </tex>. так как <tex> d_i \leqslant d_j \leqslant d_v </tex>, где <tex> v \in {i_1, i_2, \ldots, i_l} </tex>. Последнее неравенство имеет место быть, поскольку все работы <tex>i_v</tex> являются наследниками работы <tex>j</tex>.
 +
 
 +
[[Файл:1precripi1Lmax.png|400px|thumb|center|Составление оптимального расписания <tex> S^* </tex>]]
 +
 
  
 +
==Источники информации==
 +
* [http://math.mit.edu/~goemans/18438/lec13.pdf Minmax criteria. A polynomial-time algorithm for jobs of equal length. 13 стр.]
 +
* [http://community.stern.nyu.edu/om/faculty/pinedo/scheduling/shakhlevich/handout04.pdf Basic Scheduling Algorithms for Single Machine Problems: Due-Date Scheduling]
  
[[Категория: Дискретная математика и алгоритмы]]
+
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Теория расписаний]]
 
[[Категория: Теория расписаний]]

Версия 21:48, 25 апреля 2016

[math]1 \mid prec; r_i; p_i = 1 \mid L_{max}[/math]


Задача:
Дано [math]n[/math] работ и один станок. Для каждой работы известно её время появления [math]r_{i}[/math]. Время выполнения всех работ [math]p_i[/math] равно [math]1[/math]. Работа может начаться только после выполнения некоторых других работ, эта зависимость дана в виде ациклического графа. Необходимо составить такое расписание, чтобы значение [math]L_{max} = \max\limits_{i=1..n} (C_i - d_i)[/math] было минимальным.


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

Пусть [math]time[/math] — текущий момент времени.
Для каждого очередного значения [math]time[/math], которое изменяется от [math]0[/math] до времени окончания последней работы, будем:

  1. Выполнять работу [math]k[/math] из множества невыполненных работ, у которой [math]d_{k}[/math] минимально.
  2. Увеличивать [math]time[/math] на один.

Доказательство

Пусть существует оптимальное расписание [math] S^* [/math]. В этом расписании работа выполняется тогда, когда она появилась, либо когда закончилась другая работа. Рассмотрим такое расписание [math]S^*[/math], которое как можно дольше совпадает с расписанием S, построенным алгоритмом. Пусть [math] t~-[/math] первый момент времени, когда в расписании [math]S[/math] начинает выполняться работа [math]i[/math], а в расписании [math]S^*[/math] работа [math]j[/math] (причем [math] i \ne j [/math]). Мы знаем, что [math] r_i, r_j \leqslant t [/math], а значит [math] d_i \leqslant d_j [/math] (поскольку при построении мы выбираем минимальное доступное [math] d_k [/math]). Пусть [math] i_1, i_2, \ldots, i_l~-[/math] все работы, которые находятся в расписании [math]S^*[/math] между работами [math]j[/math] и [math]i[/math] и являются наследниками работы [math]j[/math]. Кроме того, предположим, что эти работы упорядочены по времени начала выполнения. Теперь, если мы поставим работу [math]i_l[/math] вместо [math]i, i_{l-1}[/math] вместо [math]i_{l}, \ldots, j[/math] вместо [math]i_1, i[/math] вместо [math]j[/math], то мы снова получим возможное оптимальное расписание [math] S' [/math]. так как [math] d_i \leqslant d_j \leqslant d_v [/math], где [math] v \in {i_1, i_2, \ldots, i_l} [/math]. Последнее неравенство имеет место быть, поскольку все работы [math]i_v[/math] являются наследниками работы [math]j[/math].

Составление оптимального расписания [math] S^* [/math]


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