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

Материал из Викиконспекты
Перейти к: навигация, поиск
(теперь правильно)
(не показано 15 промежуточных версий 4 участников)
Строка 1: Строка 1:
<includeonly>[[Категория: В разработке]]</includeonly>
+
<tex dpi=200>Q\mid\mid\sum{C_i}</tex>
<tex>Q\mid\mid\sum{C_i}</tex>
 
==Постановка задачи==
 
Есть несколько станков с разной скоростью выполнения работ и несколько работ с заданным временем выполнения.
 
  
Цель - составить такое расписание, чтобы суммарное время окончания всех работ было минимальным.
+
{{Задача
 
+
|definition = Есть несколько станков с разной скоростью выполнения работ и несколько работ с заданным временем выполнения.<br>Цель {{---}} составить такое расписание, чтобы суммарное время окончания всех работ было минимальным.}}
==Алгоритм решения==
+
== Решение ==
Пусть <tex> i_1, i_2, \cdots i_r </tex> последовательность работ, выполняемых на станке с номером <tex> j </tex>. Тогда вклад этих работ в целевую функцию будет равен <tex> p_{i1}\frac{r}{s_j} + p_{i2}\frac{r-1}{s_j}+ \cdots +p_{ir}\frac{1}{s_j} </tex>. Отсюда видно, что сумма оптимальна, когда последовательность <tex> p_{ij} </tex> не убывает.
+
=== Алгоритм ===
Теперь введем неубывающую последовательность <tex> t_1, t_2 ... t_n </tex>, которая состоит из <tex> n </tex> минимальных элементов из множества <tex> \{\frac{1}{s_1}, \frac{1}{s_2} \cdots \frac{1}{s_m}, \frac{2}{s_1}, \frac{2}{s_2} \cdots \frac{2}{s_m}, \frac{3}{s_1} \cdots \}</tex>. Тогда <tex> t_i</tex> показывает на каком станке и какой по счету с конца должна выполняться работа с номером <tex>i</tex> в отсортированном по длительности списке работ. Сопоставляя работы и <tex> t_i</tex> составляем расписание.
+
Пусть <tex> i_1, i_2, \ldots i_r </tex> последовательность работ, выполняемых на станке с номером <tex> j </tex>. Тогда вклад этих работ в целевую функцию будет равен <tex> p_{i1}\cfrac{r}{s_j} + p_{i2}\cfrac{r-1}{s_j} + \ldots + p_{ir}\cfrac{1}{s_j} </tex>. По [[Задача_о_минимуме/максимуме_скалярного_произведения|теореме о минимуме/максимуме скалярного произведения]] видно, что сумма оптимальна, когда последовательность <tex> p_{ij} </tex> не убывает.
 +
Теперь введем неубывающую последовательность <tex> t_1, t_2 \ldots t_n </tex>, которая состоит из <tex> n </tex> минимальных элементов из множества <tex> \left\{ \cfrac{1}{s_1}, \cfrac{1}{s_2} \ldots \cfrac{1}{s_m}, \cfrac{2}{s_1}, \cfrac{2}{s_2} \ldots \cfrac{2}{s_m}, \cfrac{3}{s_1} \ldots \right\}</tex> (для поиска <tex> t_1, t_2 \ldots t_n </tex> создадим [[Приоритетные очереди|приоритетную очередь]], положим в нее числа <tex> \cfrac{1}{s_1}, \cfrac{1}{s_2} \ldots \cfrac{1}{s_m}</tex> и будем последовательно извлекать <tex>n</tex> минимумов. После извлечения очередного минимума вида <tex>\cfrac{i}{s_j}</tex> добавим в очередь число <tex>\cfrac{i + 1}{s_j}</tex> и продолжим извлечение). Тогда <tex> t_i</tex> показывает на каком станке и какой по счету с конца должна выполняться работа с номером <tex>i</tex> в отсортированном по длительности списке работ. Сопоставляя работы и <tex> t_i</tex> составляем расписание.
  
 +
=== Корректность ===
 
{{Теорема
 
{{Теорема
 
|statement=
 
|statement=
 
Приведенный алгоритм верен.
 
Приведенный алгоритм верен.
 
|proof=  
 
|proof=  
# Докажем правильность выбора мест работ. Станок, на котором выполняется работа, и номер работы на этом станке с конца определяет коэффициент перед длительностью выполнения <tex> p_i\frac{t}{s_j} </tex>, тут <tex> t</tex> - номер работы с конца, а <tex>j</tex> - номер станка. Именно с таким коэффициентом работа войдет в целевую функцию. Мы выбираем минимальные <tex>n</tex> коэффициентов, следовательно, взяв хотя бы один другой коэффициент, мы увеличим время работы.
+
# Докажем правильность выбора мест работ. Станок, на котором выполняется работа, и номер работы на этом станке с конца определяют коэффициент перед длительностью выполнения <tex> p_i\cfrac{t}{s_j} </tex>, тут <tex> t</tex> {{---}} номер работы с конца, а <tex>j</tex> {{---}} номер станка. Именно с таким коэффициентом работа войдет в целевую функцию. Мы выбираем минимальные <tex>n</tex> коэффициентов, следовательно, взяв хотя бы один другой коэффициент, мы увеличим время работы.
# Докажем, что работы надо сопоставлять в порядке не убывания. Предположим у нас есть коэффициенты <tex> t_i </tex> и <tex> t_j </tex>, такие что <tex> t_i \le t_j </tex> и работы <tex> p_k \ge p_l </tex>, и мы сопоставили <tex> t_i </tex> с <tex> p_l </tex>, а <tex>t_j</tex> с <tex>p_k</tex>. Тогда, если мы поменяем работы местами, то значение целевой функции станет меньше на <tex> p_k(t_j - t_i)+p_l(t_i-t_j) = (p_k - p_l)(t_j-t_i) \ge 0</tex>. Видно, что результат не ухудшится.
+
# Докажем, что работы надо сопоставлять в порядке не убывания. Предположим, у нас есть коэффициенты <tex> t_i </tex> и <tex> t_j </tex>, такие что <tex> t_i \leqslant t_j </tex> и работы <tex> p_k \geqslant p_l </tex>, и мы сопоставили <tex> t_i </tex> с <tex> p_l </tex>, а <tex>t_j</tex> с <tex>p_k</tex>. Тогда, если мы поменяем работы местами, то значение целевой функции станет меньше на <tex> p_k(t_j - t_i)+p_l(t_i-t_j) = (p_k - p_l)(t_j-t_i) \geqslant 0</tex>. Видно, что результат не ухудшится.
 
}}
 
}}
  
==Время работы==
+
=== Время работы ===
 +
 
 +
Начальная сортировка работ и [[Двоичная куча#Построение кучи за O(n)|инициализация приоритетной очереди]] занимают <tex>O(n\log{n} + m)</tex> времени. Затем происходит выбор минимальных коэффициентов, посредством приоритетной очереди время работы составит <tex>O(n\log{m})</tex>. Итого суммарное время работы <tex> O(n(\log{n}+\log{m}) + m)</tex>.
  
Начальная сортировка работ занимается <tex>O(n\log{n})</tex> времени. Затем происходит выбор минимальных коэффициентов, посредством приоритетной очереди время работы составит <tex>O(n\log{m})</tex>. Итого суммарное время работы <tex> O(n(\log{n}+\log{m}))</tex>.
+
== Источники информации ==
 +
* Peter Brucker Scheduling Algorithms {{---}} Springer, 2006. {{---}} с. 133. {{---}} ISBN 978-3-540-69515-8
  
==Литература==
+
[[Категория: Алгоритмы и структуры данных]]
* Peter Brucker. «Scheduling Algorithms» {{---}} «Springer», 2006 г. {{---}} 133 стр. {{---}} ISBN 978-3-540-69515-8
 
[[Категория: Дискретная математика и алгоритмы]]
 
 
[[Категория: Теория расписаний]]
 
[[Категория: Теория расписаний]]

Версия 13:24, 10 июня 2016

[math]Q\mid\mid\sum{C_i}[/math]


Задача:
Есть несколько станков с разной скоростью выполнения работ и несколько работ с заданным временем выполнения.
Цель — составить такое расписание, чтобы суммарное время окончания всех работ было минимальным.

Решение

Алгоритм

Пусть [math] i_1, i_2, \ldots i_r [/math] последовательность работ, выполняемых на станке с номером [math] j [/math]. Тогда вклад этих работ в целевую функцию будет равен [math] p_{i1}\cfrac{r}{s_j} + p_{i2}\cfrac{r-1}{s_j} + \ldots + p_{ir}\cfrac{1}{s_j} [/math]. По теореме о минимуме/максимуме скалярного произведения видно, что сумма оптимальна, когда последовательность [math] p_{ij} [/math] не убывает. Теперь введем неубывающую последовательность [math] t_1, t_2 \ldots t_n [/math], которая состоит из [math] n [/math] минимальных элементов из множества [math] \left\{ \cfrac{1}{s_1}, \cfrac{1}{s_2} \ldots \cfrac{1}{s_m}, \cfrac{2}{s_1}, \cfrac{2}{s_2} \ldots \cfrac{2}{s_m}, \cfrac{3}{s_1} \ldots \right\}[/math] (для поиска [math] t_1, t_2 \ldots t_n [/math] создадим приоритетную очередь, положим в нее числа [math] \cfrac{1}{s_1}, \cfrac{1}{s_2} \ldots \cfrac{1}{s_m}[/math] и будем последовательно извлекать [math]n[/math] минимумов. После извлечения очередного минимума вида [math]\cfrac{i}{s_j}[/math] добавим в очередь число [math]\cfrac{i + 1}{s_j}[/math] и продолжим извлечение). Тогда [math] t_i[/math] показывает на каком станке и какой по счету с конца должна выполняться работа с номером [math]i[/math] в отсортированном по длительности списке работ. Сопоставляя работы и [math] t_i[/math] составляем расписание.

Корректность

Теорема:
Приведенный алгоритм верен.
Доказательство:
[math]\triangleright[/math]
  1. Докажем правильность выбора мест работ. Станок, на котором выполняется работа, и номер работы на этом станке с конца определяют коэффициент перед длительностью выполнения [math] p_i\cfrac{t}{s_j} [/math], тут [math] t[/math] — номер работы с конца, а [math]j[/math] — номер станка. Именно с таким коэффициентом работа войдет в целевую функцию. Мы выбираем минимальные [math]n[/math] коэффициентов, следовательно, взяв хотя бы один другой коэффициент, мы увеличим время работы.
  2. Докажем, что работы надо сопоставлять в порядке не убывания. Предположим, у нас есть коэффициенты [math] t_i [/math] и [math] t_j [/math], такие что [math] t_i \leqslant t_j [/math] и работы [math] p_k \geqslant p_l [/math], и мы сопоставили [math] t_i [/math] с [math] p_l [/math], а [math]t_j[/math] с [math]p_k[/math]. Тогда, если мы поменяем работы местами, то значение целевой функции станет меньше на [math] p_k(t_j - t_i)+p_l(t_i-t_j) = (p_k - p_l)(t_j-t_i) \geqslant 0[/math]. Видно, что результат не ухудшится.
[math]\triangleleft[/math]

Время работы

Начальная сортировка работ и инициализация приоритетной очереди занимают [math]O(n\log{n} + m)[/math] времени. Затем происходит выбор минимальных коэффициентов, посредством приоритетной очереди время работы составит [math]O(n\log{m})[/math]. Итого суммарное время работы [math] O(n(\log{n}+\log{m}) + m)[/math].

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

  • Peter Brucker Scheduling Algorithms — Springer, 2006. — с. 133. — ISBN 978-3-540-69515-8