Определение функции плотности загрузки и минимальной загрузки для ВС

Множество входных вершин графа G назы­вается минорантой графа G.

Множество выходных вершин графа G назы­вается мажорантой графа G.

Пусть А есть миноранта, В — мажоранта графа G, a p_j – j-го оператора. Тогда множество значений сроков окончания выпол­нения операторов определяется следующими неравенствами:

, если (1)

, если существует связь (2)

, если (3)

Множество значений, определяемых неравенствами (1) — (3), задает многоугольник М_Т в RS-мерном пространстве: . Тогда справедливо следующее определение:

Функция , где , называется плотностью загрузки ВС в точке  для значения .

Значение функции PZ в каждый момент времени формируется операторами множества ВНО, т. е. в каждый момент времени значе­ние функции PZ совпадает с числом одновременно выполняемых операторов.

Функция называется загрузкой отрезка для .

Функция Z определяет количество выполненных на этом отрез­ке операторов (с учетом частично выполненных операторов).

Функция называется минимальной загрузкой отрезка для .

Смысл этого определения заключается в том, что при решении задачи за время Т при любом планировании операторов на выпол­нение загрузка отрезка не может быть меньше вычи­сленной, согласно определению величины .