Изменения
Нет описания правки
Перед решением основной задачи рассмотрим более простые.
==Задача <tex>1 \mid r_i,p_i = 1 \mid \sum f_i</tex>==
<tex dpi = "200"> 1 \mid r_i,p_i = 1 \mid \sum f_i</tex>
{{Задача
Вес всех работ <tex>w_i \geqslant 0</tex>
Для всех функций <tex>f_1, f_2, \ldots, f_n</tex> выполняются следующие свойства:
<tex>f_j</tex> неубывающая функция для <tex>j = 1, 2, \ldots, n</tex>
<tex>f_i - f_j</tex> неубывающая функция для <tex>i, j = 1, 2, \ldots, n</tex> при <tex>i < j </tex>
<tex>\sum w_i C_i</tex> являются функцией <tex>f_j(C_j)</tex>, так что по факту решаем задачу <tex>1 \mid r_j,p_j = 1 \mid \sum w_i C_i </tex>
==Описание алгоритма задачи <tex>1 \mid r_j,p_j = 1 \mid \sum f_j</tex>==
<tex>w_1F_k'(s,e)</p_1 tex> это <tex>min(F_{k-1}(s,t_k)+F_{k-1}(t_k + p, e)+f_k(t_k + p) \geqslant w_2/p_2 mid t_k \in T, max(s, r_k) \geqslant leqslant t_k \ldots w_n/p_nleqslant e-p)</tex>
==Псевдокод задачи <tex>1 \mid r_j,p_j = 1 \mid \sum f_j</tex>==
'''for all''' <tex>s, e \in T \ with \ s \leqslant e</tex> '''do''' <tex> C_0 F_0(s,e) \leftarrow 0</tex> '''for''' <tex> i k \leftarrow 1</tex> '''to''' <tex>n</tex> '''do''' '''for all''' <tex>C_i s, e \in T \ with \ s \leqslant e</tex> '''do''' <tex> F_k(s,e) \leftarrow C_ \begin{cases} F_{k-1}(s,e) \ if \ r_k \notin [s - p,e);\\ F_k'(s,e) \ otherwise; \end{cases} </tex> '''Calculate''' <tex>F_n($$ \min_{i-=1} ^n (r_i) $$, max_{t \in T}(t+ p_ip) )</tex>
=Основная задача=
==Описание алгоритма основной задачи==
== Источники информации ==
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 19 - 20
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 38 - 39
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 84 - 85
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 101 - 102
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Теория расписаний]]
