QSumCi

[math]Q\mid\mid\sum{C_i}[/math]

Постановка задачи

Есть несколько станков с разной скоростью выполнения работ и несколько работ с заданным временем выполнения.

Цель — составить такое расписание, чтобы суммарное время окончания всех работ было минимальным.

Алгоритм решения

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

Теорема:

Приведенный алгоритм верен.

Доказательство:

[math]\triangleright[/math]

Докажем правильность выбора мест работ. Станок, на котором выполняется работа, и номер работы на этом станке с конца определяют коэффициент перед длительностью выполнения [math] p_i\frac{t}{s_j} [/math], тут [math] t[/math] — номер работы с конца, а [math]j[/math] — номер станка. Именно с таким коэффициентом работа войдет в целевую функцию. Мы выбираем минимальные [math]n[/math] коэффициентов, следовательно, взяв хотя бы один другой коэффициент, мы увеличим время работы. Докажем, что работы надо сопоставлять в порядке не убывания. Предположим, у нас есть коэффициенты [math] t_i [/math] и [math] t_j [/math], такие что [math] t_i \le t_j [/math] и работы [math] p_k \ge p_l [/math], и мы сопоставили [math] t_i [/math] с [math] p_l [/math], а [math]t_j[/math] с [math]p_k[/math]. Тогда, если мы поменяем работы местами, то значение целевой функции станет меньше на [math] p_k(t_j - t_i)+p_l(t_i-t_j) = (p_k - p_l)(t_j-t_i) \ge 0[/math]. Видно, что результат не ухудшится.

[math]\triangleleft[/math]

Время работы

Начальная сортировка работ занимается [math]O(n\log{n})[/math] времени. Затем происходит выбор минимальных коэффициентов, посредством приоритетной очереди время работы составит [math]O(n\log{m})[/math]. Итого суммарное время работы [math] O(n(\log{n}+\log{m}))[/math].

Литература

• Peter Brucker. «Scheduling Algorithms» — «Springer», 2006 г. — 133 стр. — ISBN 978-3-540-69515-8