355
правок
Изменения
Нет описания правки
==Постановка задачи==
<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$-ой работы, была минимальна.
</wikitex>
Пусть $N = \{1, \dots, n\}$ {{---}} множество работ, и $S \subseteq N$ {{---}} множество незашедуленных работ. Пусть также $p(S) = \sum_{j \in S}{p_j}$. Тогда правило Лаулера можно сформулировать следующим образом: взять работу $j \in S$, у которой нет детей в графе зависимостей и имеющую минимальное значение $f_j(p(S))$, и поставить ее на последнее место среди работы из $S$.
</wikitex>
===Реализация===
<wikitex>Пусть граф задан матрицей смежности $A = (a_{ij})$, где $a_{ij} = 1$ тогда, и только тогда, когда существует ребро $i \to j$. За $n(i)$ обозначим число детей вершины $i$, а $schedule$ - расписписание.
for i = 1 to n do
for j = 1 to n do
n(i) += A[i][j];
S = {1,...,n};
P = sum(p[i]);
for k = n downto 1 do
find job j in S with n[j] = 0 and minimal f[j](P)-value;
S = S \ {j};
n[i] = inf;
schedule[k] = j;
P -= p[j];
for i = 1 to n do
if A[i][j] = 1 then
n[i]--;
Сложность этого алгоритма $O(n^2)$.
</wikitex>
