1rjpjpsumwjcjиsumtj

[math]1 \mid r_i, p_i = p \mid \sum{w_i C_i}[/math]

Задача:

Дано [math]n[/math] работ и [math]1[/math] станок. Для каждой работы известны время появления [math]r_i[/math], вес [math]w_i[/math] и дедлайн [math]d_i[/math]. Время выполнения всех работ [math]p_i[/math] равно [math]p[/math]. Требуется выполнить все работы так, чтобы значение [math]\sum{w_iC_i}[/math], где [math]C_i[/math] — время окончания работы, было минимальным.

[math]1 \mid r_i, p_i = p \mid \sum{T_i}[/math]

Задача:

Дано [math]n[/math] работ и [math]1[/math] станок. Для каждой работы известны время появления [math]r_i[/math], вес [math]w_i[/math] и дедлайн [math]d_i[/math]. Время выполнения всех работ [math]p_i[/math] равно [math]p[/math]. Требуется выполнить все работы так, чтобы значение [math]\sum{T_i}[/math] — суммарной медлительности работы ([math]T_i = \max(C_i - d_i, 0)[/math]) — было минимальным.

Предисловие

Аналогично задаче [math]1 | r_i, p_i = p | \sum{w_i U_i}[/math], данные задачи решаются при помощи динамического программирования.

Вместо критериев оптимизации [math]\sum{w_i C_i}[/math] и [math]\sum{T_i}[/math] возьмём более общую для них функцию вида [math]\sum{f_i(C_i)}[/math], где функции [math]f_1,...,f_n[/math] обладают следующими свойствами:

• [math]f_i[/math] не убывает для всех [math]j = 1,...,n[/math];

• [math]f_i - f_j[/math] не убывает для всех [math]i, j = 1,..., n[/math] при [math]i \lt j[/math].

Получим обобщенную задачу [math]1 | r_i, p_i = p | \sum{f_i(C_i)}[/math], для которой согласно лемме существует оптимальное расписание, в котором каждая работа начинается в момент времени из множества [math]T = \{r_j + L_p | j = 1,...,n; l = 0,...,n - 1\}[/math].

Функции [math]\sum{w_i C_i}[/math] и [math]\sum{T_i}[/math] удовлетворяют данным условиям, если отсортировать работы так, что [math]w_1 \geq w_2 \geq ... \geq w_n[/math] и [math]d_1 \leq d_2 \leq ... \leq d_n[/math].

Алгоритм

   Отсортировать работы так, чтобы [math]f_i[/math] удовлетворяла условиям неубывания;
   for s, e [math]\in[/math] T : s [math]\leq[/math] e
       [math]F_0[/math](s, e) = 0;
   for k = 1..n 
   for s, e [math]\in[/math] T : s [math]\leq[/math] e
       if [math]r_k\notin [s - p, e)[/math]
           [math]F_k(s,e) = F_{k-1}(s,e)[/math]
       else
           [math]F'_k(s,e) = F'(s,e)[/math], где 
           [math]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)[/math]
   return [math]F_n($$\min\limits_{i=1}^{n}r_i$$,  max_{t \in T}t + p)[/math]

Время работы

Алгоритм работает за [math]O(n \cdot n^2 \cdot n^2 \cdot n^2) = O(n^7)[/math] времени (см. время работы [math]1 | r_i, p_i = p | \sum{w_i U_i}[/math]).

Корректность алгоритма

Ниже приведена теорема, показывающая, что возвращаемое алгоритмом значение [math]F_k (s, e)[/math] равно [math]F^*_k (s, e)[/math].

Теорема:

Для любого [math]k = 0, \dots, n[/math] и для любого [math]s, e \in T \mid s \leqslant e[/math], выполняется равенство: [math]F_k (s, e) = F^*_k (s, e)[/math].

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

[math]\triangleright[/math]

Будем полагать, что равенство верно для [math]k - 1[/math] (очевидно, равенство выполнится при [math]k = 0[/math]). Если [math]r_k \notin [s - p, e)[/math], тогда [math]U_k(s - p, e) = U_{k - 1}(s - p, e)[/math] что подразумевается в равенстве. Теперь нужно показать, что а) [math]F^{*}_k(s, e) \leq F^{'}_k(s, e)[/math]; б) [math]F^{'}_k(s, e) \leq F^{*}_k(s, e)[/math] при [math]r_k \in [s - p, e)[/math]. а) Полагаем, что [math]F^{'}_k[/math] ограничена. Тогда существует [math]t_k \in T[/math] такая, что [math]max{s, t_k} \leq t_k \leq e - p[/math], при которой [math]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).[/math] б) Полагаем, что [math]F^{*}_k[/math] ограничена. Среди всех оптимальных расписаний, возвращающих [math]F^{*}_k(s, e)[/math] выберем оптимальное расписание [math]S[/math], соответствующий вектор времён окончания работ которого [math](C_{i_1}, C_{i_2}, ... , C_{i_l})[/math] минимален при условии, что [math]i_1 \leq i_2 \leq \dots \leq i_l[/math] в лексикографическом порядке. Пусть [math]t_k \in T[/math] — время начала работы [math]k[/math] в расписании [math]S[/math]. Тогда [math]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).[/math] Чтобы проверить первое неравенство, нужно показать, что все работы [math]U_{k-1}(s - p, t_k)[/math] записаны в [math]S[/math] в пределах интервала [math][s, t_k][/math], а все работы [math]U_{k-1}(t_k, e)[/math] — в пределах [math][t_k + p, e][/math]. Докажем первое утверждение (второе доказывается аналогично). Полагаем, что существует работа [math]j[/math] такая, что [math] s - p \leq r_j \leq t_k[/math], начинающаяся в расписании [math]S[/math] позже, чем работа [math]k (t_j \gt t_k)[/math]. Поменяв местами [math]k[/math] и [math]j[/math], получим оптимальное расписание [math]S'[/math] такое, что [math]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)[/math], где [math]|S|[/math] — объективное значение расписания [math]S.[/math] [math]j \lt k[/math] подразумевает [math]v \leq 0[/math], так как [math]f_j - f_k[/math] не убывает по условию. Таким образом, [math]S'[/math] также является оптимальным, несмотря на то, что это противоречит лексикографической минимальности расписания [math]S[/math].

[math]\triangleleft[/math]

См. также

[math]1 | r_i, p_i = p | \sum{w_i U_i}[/math]

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

P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 98 - 104