Изменения

<tex dpi = "200">1 \mid r_jr_i, p_j p_i = p \mid \sum{w_j C_jw_i 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{w_iC_i}</tex>, где <tex>C_i</tex> — время окончания работы, было минимальным.}} <tex dpi = "200">1 \mid r_i, p_i = p \mid \sum{T_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</tex> не убывает для всех <tex>j = 1,...,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> удовлетворяют данным условиям, p_j если отсортировать работы так, что <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_{T_jk-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