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]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]

PROOF

[math]\triangleleft[/math]

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

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