Изменения

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