Изменения

Пусть <tex> i_1, i_2, ... \cdots i_r </tex> последовательность работ, выполняемых на станке с номером <tex> j </tex>. Тогда вклад этих работ в целевую функцию будет равен <tex> p_{i1}\frac{r}{s_j} + p_{i2}\frac{r-1}{s_j}+...\cdots +p_{ir}\frac{1}{s_j} </tex>. Отсюда видно, что сумма оптимальна, когда последовательность <tex> p_{ij} </tex> не убывает.Теперь введем неубывающую последовательность <tex> t_1, t_2 ... t_n </tex>, которая состоит из <tex> n </tex> маленьких минимальных элементов из множества <tex> \{\frac{1}{s_1}, \frac{1}{s_2} ... \cdots \frac{1}{s_m}, \frac{2}{s_1}, \frac{2}{s_2} ... \cdots \frac{2}{s_m}, \frac{3}{s_1} ... \cdots \}</tex>. Если Тогда <tex> t_i = \frac{k}{s_j} </tex>, то показывает на каком станке и какой по счету с конца должна выполняться работа с номером <tex>i</tex> в отсортированном по длительности списке работ. Сопоставляя работы и <tex> jt_i</tex>-том станкесоставляем расписание.

{{Теорема|statement==Псевдокод=Приведенный алгоритм верен.|proof= for # Докажем правильность выбора мест работ. Станок, на котором выполняется работа, и номер работы на этом станке с конца определяет коэффициент перед длительностью выполнения <tex> p_i\frac{t}{s_j} </tex>, тут <tex> t</tex> - номер работы с конца, а <tex>j</tex> = 1 to - номер станка. Именно с таким коэффициентом работа войдет в целевую функцию. Мы выбираем минимальные <tex>mn</tex> doкоэффициентов, следовательно, взяв хотя бы один другой коэффициент, мы увеличим время работы. # Докажем, что работы надо сопоставлять в порядке не убывания. Предположим у нас есть коэффициенты <tex> t_i </tex> и <tex>t_j </tex>, такие что <tex> t_i \Pi_j = {\o} le t_j </tex> и работы <tex>w_j = p_k \frac{1}{s_j}ge p_l </tex> for , и мы сопоставили <tex>it_i </tex> = 1 to с <tex>np_l </tex> do Find the largest index , а <tex> j t_j</tex> of с <tex>w_jp_k</tex> . Тогда, если мы поменяем работы местами, то значение целевой функции станет меньше на <tex> p_k(t_j - t_i)+p_l(t_i-t_j) = (p_k - p_l)(t_j-t_i) \ge 0</tex>\min\limits_{l=1. Видно, что результат не ухудшится.}^{m} ==Время работы== Начальная сортировка работ занимается <tex>O(n\log{w_ln})</tex>; времени. Затем происходит выбор минимальных коэффициентов, посредством приоритетной очереди время работы составит <tex>O(n\Pi_j = i \cup \Pi_j log{m})</tex> . Итого суммарное время работы <tex>w_j = w_j + O(n(\fraclog{1n}+\log{s_jm} ))</tex>.