1rjpjpsumwjcjиsumtj

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

Задача:

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

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

Задача:

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

Предисловие

Аналогично задаче [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]\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[/math] [math]\notin[/math] [s - p, e)
           [math]F_k[/math](s,e) = [math]F_{k-1}[/math](s,e)
       else
           [math]F'_k[/math](s,e) = [math]F'[/math](s,e), где 
           [math]F'_k[/math](s,e) = min{[math]F_{k-1}[/math](s,t_k) + [math]F_{k-1}[/math](t_k + p, e) + [math]f_k[/math](t_k + p)| [math]t_k[/math] [math]\in[/math] T; max{s, [math]r_k[/math]} [math]\leq[/math] [math]t_k[/math] [math]\leq[/math] e - p};
   return [math]F_n($$\min_{i=1}^{n}r_i$$, max_{t \in T}t + p)[/math]