Изменения

<includeonly>[[Категория: В разработке]]</includeonly><texdpi=200>Q\mid\mid\sum{C_i}</tex>==Постановка задачи==Есть несколько станков с разной скоростью выполнения работ и несколько работ с заданным временем выполнения.

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

# Докажем правильность выбора мест работ. Станок, на котором выполняется работа, и номер работы на этом станке с конца определяет определяют коэффициент перед длительностью выполнения <tex> p_i\fraccfrac{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 leqslant t_j </tex> и работы <tex> p_k \ge 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) \ge 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== Источники информации ==* Peter Brucker Scheduling Algorithms {n{---})</tex> времени} Springer, 2006. Затем происходит выбор минимальных коэффициентов, посредством приоритетной очереди время работы составит <tex>O(n\log{m{---}})</tex>с. 133. Итого суммарное время работы <tex> O(n(\log{n{---}+\log{m}))</tex>.ISBN 978-3-540-69515-8

==Литература==* Peter Brucker. «Scheduling Algorithms» {{---}} «Springer», 2006 г. {{---}} 133 стр. {{---}} ISBN 978-3-540-69515-8[[Категория: Дискретная математика Алгоритмы и алгоритмыструктуры данных]]