Изменения
Нет описания правки
Рассмотрим задачу <tex>1 \mid prec \mid f_{max}</tex>.
{{Задача
|definition = <wikitex>Дано $n$ работ, которые надо выполнить на одной машине, причем $i$-ая работа выполняется $p_i$ времени. Для каждой работы задана монотонно неубывающая функция $f_i$. Также между работами заданы отношения в виде ориентированного графа без циклов: если существует ребро $a \to b$, то работа $a$ должна завершиться до начала выполнения работы $b$. Необходимо построить такое расписание, чтобы величина $f_{max} = \max\limits_{j=1}^{..n}{f_j(C_j)}$, где $C_j$ {{---}} время окончания выполнения $j$-ой работы, была минимальна.</wikitex>
}}
<wikitex>Задача $1 \mid \mid f_{max}$ является частным случаем вышеописанной задачи. Здесь нет зависимостей между работами, то есть граф состоит из $n$ вершин и не содержит ребер. Очевидно, решив задачу в общем виде, мы также решим и эту.</wikitex>
find job j in S with N[j] == 0 and minimal f[j](P)-value
S = S \ {j}
N[ij] = <tex>\infty</tex>
schedule[k] = j
P -= p[j]
==Источники информации==
* Peter Brucker. «Scheduling Algorithms» {{---}} «Springer», 2006 г. {{---}} 62 -63 стр. {{---}} ISBN 978-3-540-69515-8
[[Категория:Алгоритмы и структуры данных]]
[[Категория: Теория расписаний]]
