1632
правки
Изменения
м
PROOFБудем полагать, что равенство верно для <tex>k - 1</tex> (очевидно, равенство выполнится при <tex>k = 0</tex>). Если <tex>r_k \notin [s - p, e)</tex>, тогда <tex>U_k(s - p, e) = U_{k - 1}(s - p, e)</tex> что подразумевается в равенстве. Теперь нужно показать, что а) <tex>F^{*}_k(s, e) \leq F^{'}_k(s, e)</tex>; б) <tex>F^{'}_k(s, e) \leq F^{*}_k(s, e)</tex> при <tex>r_k \in [s - p, e)</tex>. а) Полагаем, что <tex>F^{'}_k</tex> ограничена. Тогда существует <tex>t_k \in T</tex> такая, что <tex>max{s, t_k} \leq t_k \leq e - p</tex>, при которой <tex>F^*_k(s, e) = F_{k - 1}(s, t_k) + F_{k-1}(t_k + p, e) + f_k(t_k + p) = F^*_{k-1}(s, t_k) + F^*_k-1(t_k + p, e) + f_k(t_k + p) \geq F^*_k(s, e).</tex> б) Полагаем, что <tex>F^{*}_k</tex> ограничена. Среди всех оптимальных расписаний, возвращающих <tex>F^{*}_k(s, e)</tex> выберем оптимальное расписание <tex>S</tex>, соответствующий вектор времён окончания работ которого <tex>(C_{i_1}, C_{i_2}, ... , C_{i_l})</tex> минимален при условии, что <tex>i_1 \leq i_2 \leq \dots \leq i_l</tex> в лексикографическом порядке. Пусть <tex>t_k \in T</tex> — время начала работы <tex>k</tex> в расписании <tex>S</tex>. Тогда <tex>F^{*}_k(s, e) = \sum\limits_{j \in U_k(s - p, e)}{f_j(C_j)} = \sum\limits_{j \in U_k(s - p, t_k)}{f_j(C_j)} + \sum\limits_{j \in U_k(t_k, e)}{f_j(C_j)} + f_k(t_k + p) \geq F_{k-1}(s, t_k) + F_{k-1}(t_k + p, e) + f_k(t_k + p) \geq F^{'}_k(s, e).</tex> Чтобы проверить первое неравенство, нужно показать, что все работы <tex>U_{k-1}(s - p, t_k)</tex> записаны в <tex>S</tex> в пределах интервала <tex>[s, t_k]</tex>, а все работы <tex>U_{k-1}(t_k, e)</tex> — в пределах <tex>[t_k + p, e]</tex>. Докажем первое утверждение (второе доказывается аналогично). Полагаем, что существует работа <tex>j</tex> такая, что <tex> s - p \leq r_j \leq t_k</tex>, начинающаяся в расписании <tex>S</tex> позже, чем работа <tex>k (t_j > t_k)</tex>. Поменяв местами <tex>k</tex> и <tex>j</tex>, получим оптимальное расписание <tex>S'</tex> такое, что <tex>v = |S'| - |S| = f_j(t_k + p) + f_k(t_j + p) - f_j(t_j + p) - f_k(t_k + p) = (f_j - f_k)(t_k + p) - (f_j - f_k)(t_j + p)</tex>, где <tex>|S|</tex> — объективное значение расписания <tex>S.</tex> <tex>j < k</tex> подразумевает <tex>v \leq 0</tex>, так как <tex>f_j - f_k</tex> не убывает по условию. Таким образом, <tex>S'</tex> также является оптимальным, несмотря на то, что это противоречит лексикографической минимальности расписания <tex>S</tex>.
rollbackEdits.php mass rollback
==Предисловие==
Аналогично задаче [[1ripipsumwu|<tex>1 | r_i, p_i = p | \sum{w_i U_i}</tex>]], данные задачи решаются при помощи [[Динамическое программирование | динамического программирования]].
Вместо критериев оптимизации <tex>\sum{w_i C_i}</tex> и <tex>\sum{T_i}</tex> возьмём более общую для них функцию вида <tex>\sum{f_i(C_i)}</tex>, где функции <tex>f_1,...,f_n</tex> обладают следующими свойствами:
* <tex>f_i - f_j</tex> не убывает для всех <tex>i, j = 1,..., n</tex> при <tex>i < j</tex>.
Получим обобщенную задачу <tex>1 | r_i, p_i = p | \sum{f_i(C_i)}</tex>, для которой согласно [[1ripipsumwu#.D0.9F.D1.80.D0.B5.D0.B4.D0.B8.D1.81.D0.BB.D0.BE.D0.B2.D0.B8.D0.B5|лемме]] существует оптимальное расписание, в котором каждая работа начинается в момент времени из множества <tex>T = \{r_j + L_p | j = 1,...,n; l = 0,...,n - 1\}</tex>.
Функции <tex>\sum{w_i C_i}</tex> и <tex>\sum{T_i}</tex> удовлетворяют данным условиям, если отсортировать работы так, что <tex>w_1 \geq w_2 \geq ... \geq w_n</tex> и <tex>d_1 \leq d_2 \leq ... \leq d_n</tex>.
==Время работы==
Алгоритм работает за <tex>O(n \cdot n^2 \cdot n^2 \cdot n^2) = O(n^7)</tex> времени (см. время работы [[1ripipsumwu|<tex>1 | r_i, p_i = p | \sum{w_i U_i}</tex>]]).
==Корректность алгоритма==
{{Теорема
|statement=
Для любого <tex>k = 0, \dots, n</tex> и для любого <tex>s, e \in T \mid s \leqslant e</tex>, выполняетсяравенство: <tex>F_k (s, e) = F^*_k (s, e)</tex>.
|proof=
}}
==Другие задачи==
==См. также==
[[1ripipsumwu|<tex>1 | r_i, p_i = p | \sum{w_i U_i}</tex>]]
==Источники информации==
P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 98 - 104
