33
правки
Изменения
Нет описания правки
<includeonly>[[Категория: В разработке]]</includeonly><tex>Q\mid\mid\sum{C_i}</tex>{Задача|definition ==Постановка задачи==Есть несколько станков с разной скоростью выполнения работ и несколько работ с заданным временем выполнения. Цель {{---}} составить такое расписание, чтобы суммарное время окончания всех работ было минимальным.
Цель {{---}} составить такое расписание, чтобы суммарное время окончания всех работ было минимальным.}}
==Алгоритм решения==
Пусть <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> не убывает.
