Вычисление нижней границы длин расписаний

Для графа строго частичного упорядочения $G$ приводятся нижние оценки $T_1\leqslant T_2\leqslant T_3\leqslant T_4$ длин $m$-процессорных расписаний в зависимости от степени конкретизации графа $G$. Лучшая оценка -$T_4$ получается в случае, если для $G$ известны разбиения множества его вершин на этажи сверху и снизу. Сложность получения оценки $T_4$ равна $O(n)$, где $n=|G|$.