QSumCi

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

Задача:

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

Решение

Алгоритм

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

Корректность

Теорема:

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

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

[math]\triangleright[/math]

Докажем правильность выбора мест работ. Станок, на котором выполняется работа, и номер работы на этом станке с конца определяют коэффициент перед длительностью выполнения [math] p_i\cfrac{t}{s_j} [/math], тут [math] t[/math] — номер работы с конца, а [math]j[/math] — номер станка. Именно с таким коэффициентом работа войдет в целевую функцию. Мы выбираем минимальные [math]n[/math] коэффициентов, следовательно, взяв хотя бы один другой коэффициент, мы увеличим время работы. Докажем, что работы надо сопоставлять в порядке не убывания. Предположим, у нас есть коэффициенты [math] t_i [/math] и [math] t_j [/math], такие что [math] t_i \leqslant t_j [/math] и работы [math] p_k \geqslant 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) \geqslant 0[/math]. Видно, что результат не ухудшится.

[math]\triangleleft[/math]

Время работы

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

Источники информации

• Peter Brucker Scheduling Algorithms — Springer, 2006. — с. 133. — ISBN 978-3-540-69515-8