Изменения

Перейти к: навигация, поиск

Правило Лаулера

36 байт убрано, 16:58, 9 мая 2012
Постановка задачи 1 \mid prec \mid f_{max}
==Постановка задачи <tex>1 \mid prec \mid f_{max}</tex>==
<wikitex>Рассмотрим задачу $1 \mid prec \mid f_{max}$. Дано $n$ работ, которые надо выполнить на одной машине, причем $i$-ая работа выполняется $p_i$ времени. Для каждой работы задана монотонно неубывающая функция $f_i$. Также между работами заданы отношения в виде ориентированного графа без циклов: если существует ребро $a \to b$, то работа $a$ должна завершиться раньше работы $b$. Необходимо построить такое расписание, чтобы величина $f_{max} = max^{n}_{j=1}{f_j(C_j)}$, где $C_j$ {{---}} время окончания выполнения $j$-ой работы, была минимальна.
355
правок

Навигация