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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Алгоритм решения)
(Алгоритм решения)
Строка 3: Строка 3:
 
==Алгоритм решения==
 
==Алгоритм решения==
 
Пусть <tex> i_1, i_2, \cdots i_r </tex> последовательность работ, выполняемых на станке с номером <tex> j </tex>. Тогда вклад этих работ в целевую функцию будет равен <tex> p_{i1}\cfrac{r}{s_j} + p_{i2}\cfrac{r-1}{s_j} +  \cdots + p_{ir}\cfrac{1}{s_j} </tex>. [[Задача_о_минимуме/максимуме_скалярного_произведения|Отсюда]] видно, что сумма оптимальна, когда последовательность <tex> p_{ij} </tex> не возрастает.
 
Пусть <tex> i_1, i_2, \cdots i_r </tex> последовательность работ, выполняемых на станке с номером <tex> j </tex>. Тогда вклад этих работ в целевую функцию будет равен <tex> p_{i1}\cfrac{r}{s_j} + p_{i2}\cfrac{r-1}{s_j} +  \cdots + p_{ir}\cfrac{1}{s_j} </tex>. [[Задача_о_минимуме/максимуме_скалярного_произведения|Отсюда]] видно, что сумма оптимальна, когда последовательность <tex> p_{ij} </tex> не возрастает.
Теперь введем неубывающую последовательность <tex> t_1, t_2 ... t_n </tex>, которая состоит из <tex> n </tex> минимальных элементов из множества <tex> \{\cfrac{1}{s_1}, \cfrac{1}{s_2} \cdots \cfrac{1}{s_m}, \cfrac{2}{s_1}, \cfrac{2}{s_2} \cdots \cfrac{2}{s_m}, \cfrac{3}{s_1} \cdots \}</tex> (для поиска <tex> t_1, t_2 ... t_n </tex>, создадим приоритетную очередь, положим в нее числа <tex> \cfrac{1}{s_1}, \cfrac{1}{s_2} \cdots \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> составляем расписание.
+
Теперь введем неубывающую последовательность <tex> t_1, t_2 ... t_n </tex>, которая состоит из <tex> n </tex> минимальных элементов из множества <tex> \{\cfrac{1}{s_1}, \cfrac{1}{s_2} \cdots \cfrac{1}{s_m}, \cfrac{2}{s_1}, \cfrac{2}{s_2} \cdots \cfrac{2}{s_m}, \cfrac{3}{s_1} \cdots \}</tex> (для поиска <tex> t_1, t_2 ... t_n </tex> создадим приоритетную очередь, положим в нее числа <tex> \cfrac{1}{s_1}, \cfrac{1}{s_2} \cdots \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> составляем расписание.
  
 
{{Теорема
 
{{Теорема

Версия 01:46, 13 июня 2015

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

Алгоритм решения

Пусть [math] i_1, i_2, \cdots i_r [/math] последовательность работ, выполняемых на станке с номером [math] j [/math]. Тогда вклад этих работ в целевую функцию будет равен [math] p_{i1}\cfrac{r}{s_j} + p_{i2}\cfrac{r-1}{s_j} + \cdots + p_{ir}\cfrac{1}{s_j} [/math]. Отсюда видно, что сумма оптимальна, когда последовательность [math] p_{ij} [/math] не возрастает. Теперь введем неубывающую последовательность [math] t_1, t_2 ... t_n [/math], которая состоит из [math] n [/math] минимальных элементов из множества [math] \{\cfrac{1}{s_1}, \cfrac{1}{s_2} \cdots \cfrac{1}{s_m}, \cfrac{2}{s_1}, \cfrac{2}{s_2} \cdots \cfrac{2}{s_m}, \cfrac{3}{s_1} \cdots \}[/math] (для поиска [math] t_1, t_2 ... t_n [/math] создадим приоритетную очередь, положим в нее числа [math] \cfrac{1}{s_1}, \cfrac{1}{s_2} \cdots \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 \le t_j [/math] и работы [math] p_k \ge 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) \ge 0[/math]. Видно, что результат не ухудшится.
[math]\triangleleft[/math]

Время работы

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

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

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