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