Участник:Dominica

[math]1 \mid\mid \sum w_i U_i[/math]

Для каждой работы заданы время выполнения [math] p_i,[/math] дедлаин [math]d_i[/math] и стоимось выполнения этой работы [math]w_i \geqslant 0[/math] Необходимо сотавить такое расписание, что [math]\sum w_i U_i[/math] будет минимальна.

Решение

Лемма:

Пусть все работы отсортированы в порядке неубывания дедлайнов [math]d_i[/math]. Тогда существует оптимальное расписание вида [math]i_1, i_2, \ldots, i_s, i_{s+1}, \ldots, i_n [/math], где [math]i_1 \lt i_2 \lt \ldots \lt i_s [/math] — номера работ, которые успеют выполниться вовремя, а [math]i_{s+1}, \ldots, i_n [/math] — номера просроченных работ.

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

[math]\triangleright[/math]

Это можно показать следующим образом

[math]\triangleleft[/math]

 отсортиртировать  работы по неубыванию времен дедлайнов [math]d_i[/math]
 [math]t_1[/math] = [math]r_1[/math]
 for [math] t \in \{ -p_{max} \ldots -1 \} [/math]
   for [math] j \in \{ 0 \ldots n \} [/math]
     F_j(t) = \infty
 for [math] t \in \{ 0 \ldots T \} [/math]
   F_0(t) = 0
 for [math] j \in \{ 0 \ldots n \} [/math]
   for [math] t \in \{ 0 \ldots d_j \} [/math]
     if [math] F_{j-1} + w_j  \lt  F_{j-1}(t-p_j) [/math] then    
        [math] F_j(t) = F_{j-1}(t) + w_j [/math]
     else
       [math]  F_j(t) = F_{j-1}(t-p_j) [/math]
   for [math] t \in \{ d_{j+1} \ldots T \} [/math]
     [math] F_j(t) = F_{j}(d_j) [/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]j[/math] будет максимально. Из того, как в алгоритме выбирались значения для [math]t_i[/math] следует, что [math]t_{j + 1}[/math] — минимальное возможное время, большее [math]t_j,[/math] в которое можно начать выполнять какое-нибудь из оставшихся заданий. Если во время [math]t_{j+1}[/math] в расписании [math]S[/math] не выполняется никакого задания, то какое-то задание, которое могло бы выполнится в момент времени [math]t_{j+1}[/math] выполняется в [math]S[/math] позднее. Значит оно может быть перемещено в нашем расписании [math]S[/math] на время [math]t_{j+1}[/math] без увеличения целевой функции. Таким образом, наше новое расписание тоже будет оптимальным. Получили противоречие с максимальностью [math]j[/math]. Значит из всех оптимальных расписаний нам подходят только те, в которых [math]j = n[/math].

[math]\triangleleft[/math]

См. также

• Классификация задач
• [math]1 \mid prec, pmtn, r_i \mid f_{\max}[/math]

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

• P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 19 - 20