1632
правки
Изменения
м
rollbackEdits.php mass rollback
{{Задача
|definition=
Дано <tex>n </tex> работ и <tex>1 </tex> станок. Для каждой работы известны время появления <tex>r_i</tex>, вес <tex>w_i </tex> и дедлайн <tex>d_i</tex>. Время выполнения всех работ <tex>p_i </tex> равно <tex>p</tex>. Требуется выполнить все работы так, чтобы значение <tex>\sum({w_iC_i)}</tex>, где <tex>C_i </tex> — время окончания работы, было минимальным.
}}
{{Задача
|definition=
Дано <tex>n </tex> работ и <tex>1 </tex> станок. Для каждой работы известны время появления <tex>r_i</tex>, вес <tex>w_i</tex> и дедлайн <tex>d_i</tex>. Время выполнения всех работ <tex>p_i </tex> равно <tex>p</tex>. Требуется выполнить все работы так, чтобы значение <tex>\sum({T_i) }</tex> — суммарной медлительности работы(<tex>T_i = \max(C_i - d_i), 0)</tex>) — было минимальным.
}}
==Предисловие==
Аналогично задаче [[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>f_i</tex> удовлетворяла условиям неубывания;
for s, e <tex>\in</tex> T : s <tex>\leq</tex> e
<tex>F_0</tex>(s, e) = 0;
for k = 1..n
for s, e <tex>\in</tex> T : s <tex>\leq</tex> e
if <tex>r_k\notin [s - p, e)</tex>
<tex>F_k(s,e) = F_{k-1}(s,e)</tex>
else
<tex>F'_k(s,e) = F'(s,e)</tex>, где
<tex>F'_k(s,e) = \min(F_{k-1} (s, t_k) + F_{k-1} (t_k + p, e) + f_k(t_k + p) \mid t_k \in T, max(s, r_k) \leq t_k \leq e - p)</tex>
return <tex>F_n($$\min\limits_{i=1}^{n}r_i$$, max_{t \in T}t + p)</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>]]).
==Корректность алгоритма==
Ниже приведена теорема, показывающая, что возвращаемое алгоритмом значение <tex>F_k (s, e)</tex> равно <tex>F^*_k (s, e)</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=
Будем полагать, что равенство верно для <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>.
}}
==Другие задачи==
==См. также==
[[1ripipsumwu|<tex>1 | r_i, p_i = p | \sum{w_i U_i}</tex>]]
==Источники информации==
P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 98 - 104
