Участник:Dominica

[math]1 \mid r_i, p_i = 1 \mid \sum f_i[/math]

Задача:

Имеется один станок. Есть [math]n[/math] работ, каждая из которых выполняется за единицу времени. Каждая работа имеет своё время появления [math]r_i[/math]. Для каждой работы задана монотонно неубывающая функция [math]f_i[/math]. Необходимо минимизировать [math] \sum f_i, [/math] где [math]f_i[/math] — значение функции [math]f_i[/math] в момент завершения выполнения задания с номером [math]i[/math].

Решение за [math] O(n^3) [/math]

Эта задача может быть решена сведением к решению задачи о назначениях. А именно, покажем, что решение задачи состоит сопоставлении [math]n[/math] различным заданиям различных времен начала выполнения работы. Если сопоставляем работе [math]i[/math] время [math]t[/math], то вклад в целевую функцию будет [math] f_i(t + 1) [/math]. Далее будет показано, что при построении оптимального расписания нам нужно будет рассмотреть всего [math]n[/math] различных времен начала работ. Следовательно, подобная задача может быть решена за [math]O(n^3)[/math].

Поскольку [math]f_i[/math] — монотонно неубывающие функции, то это значит, что в оптимальном расписании работы должны начинать исполняться как можно раньше. Первые [math]n[/math] самых ранних для начала исполнения времен [math]t_i[/math] могут быть вычислены следующим алгоритмом, в котором мы предполагаем, что все работы отсортированы по неубыванию времени появления [math]r_i[/math]:

 [math]t_1[/math] = [math]r_1[/math]
 for [math] i \in \{ 2 \ldots n \} [/math]
   [math]t_i[/math] = [math]\max(r_i, t_{i-1} + 1)[/math]

Лемма:

Существует оптимальное расписание [math]S[/math] в котором все [math]n[/math] задач распределены по всем временам [math]t_i (i = 1\ldots n)[/math], которые выбирает приведенный выше алгоритм.

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

[math]\triangleright[/math]

Предположим, что в некоторое оптимальное расписание [math]S[/math] входят времена [math] t_1 \ldots t_j, [/math] где [math] j \lt n[/math] и максимально возможное для этого расписания. Из того, как в алгоритме выбирались значения для [math]t_i[/math] следует, что [math]t_{j + 1}[/math] — минимальное возможное время, большее [math]t_j,[/math] в которое вообще можно начать выполнять какое-нибудь задание.

[math]\triangleleft[/math]