1632
правки
Изменения
QSumCi
,rollbackEdits.php mass rollback
<includeonlytex dpi=200>[[Категория: В разработке]]Q\mid\mid\sum{C_i}</includeonlytex>
{{Задача|definition ==Постановка задачи==Есть несколько станков с разной скоростью выполнения работ и несколько работ с заданным временем выполнения.<br>Цель {{---}} составить такое расписание, чтобы суммарное время окончания всех работ было минимальным.}}== Решение ===== Алгоритм ===Пусть <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> составляем расписание.
==Алгоритм решения= Время работы ===Пусть Начальная сортировка работ и [[Двоичная куча#Построение кучи за O(n)|инициализация приоритетной очереди]] занимают <tex> i_1, i_2, ... i_r O(n\log{n} + m)</tex> последовательность работвремени. Затем происходит выбор минимальных коэффициентов, выполняемых на станке с номером посредством приоритетной очереди время работы составит <tex> j O(n\log{m})</tex>. Тогда вклад этих работ в целевую функцию будет равен Итого суммарное время работы <tex> p_O(n(\log{i1n}+\fraclog{r}{s_jm} ) + p_m)</tex>. == Источники информации ==* Peter Brucker Scheduling Algorithms {i2}\frac{r-1--}{s_j}+..Springer, 2006.+p_{ir}\frac{1---}{s_j} </tex>с. 133. Отсюда видно, что сумма оптимальна, когда последовательность <tex> p_{ij{---} </tex> не убывает.} ISBN 978-3-540-69515-8 [[Категория: Алгоритмы и структуры данных]][[Категория: Теория расписаний]]