Минимизация суммарного запаздывания выполнения заданий параллельными приборами (стр. 2 )

Теорема 3.7. Если в расписаниях s Î YP, s¢ ΠYP, построенных на заданном множестве заданий J, максимальное число запаздывающих заданий одинаково, то при RS(s)¹0 и RS(s¢)¹0 справедливо:

RS(s)–RS(s¢) = DS(s)–DS(s¢).

Доказательство. Пусть md = R0 и выполняется условие R1 ³ R2 ³ R3 ³ … ³ Rm:

R0 = + –=  –

– (s) + + =

= ++ RS(s) = const. (3.1)

Рассмотрим следующие случаи:

а) Р(s) = Р(s¢), справедливость теоремы очевидна в соответствии с (3.1);

б) Р(s) < Р(s¢), в этом случае задания j Î S(s), j = , k¢ < k, стали незапаздывающими, т. е. вошли в множество Р(s¢):

R0 = ++RS(s¢),

теорема справедлива согласно (3.1);

в) Р(s) > P(s²) DS(s) < DS(s²); в этом случае число запаздывающих заданий на приборах i = , k² < m увеличилось, так как часть заданий из множества P(s) стали запаздывающими:

R0(s) = –++ RS(s¢).

Теорема справедлива в соответствии с (3.1). Теорема доказана.

Теорема 3.8. Для любых двух расписаний s Î YP и s¢ Î YP справедливо следующее:

F(s) – F(s¢) = WS(s) – WS(s¢). (3.2)

Доказательство. Рассмотрим произвольное расписание s, построенное на заданном фиксированном множестве заданий J. Пусть в этом расписании P(s) = {1, 2, 3, ..., p – 1, p}.

Пронумеруем приборы таким образом, чтобы выполнялось условие

R1 ≥ R2 ≥ R3 ≥ … ≥ Rm.

Пусть для каждого прибора i число запаздывающих заданий равно L, а для прибора i =  равно L – 1.

Возможны следующие случаи построения новых расписаний s¢ Î YP, s² Î YP, s¢² Î YP на множестве заданий J:

а) Lmin = L – 1;

б) равномерное расписание;

в) Lmin = L – 2.

Рассмотрим случай (а). Запишем значение суммарного запаздывания: расписания s¢ Î YP (а):

F(s¢) = (lp+1 – R1) + (lp+1 – R1 + lp+1+m) + (lp+1 – R1 + lp+1+m + lp+1+2m) +

+ L + (lp+1 – R1 + lp+1+m + lp+1+2m + L + lp+1+(L–1)m) +

+ (lp+2 – R2) + (lp+2 – R2 + lp+2+m) + (lp+2 – R2 + lp+2+m + lp+2+2m) +

+ L + (lp+2 – R2 + lp+2+m + lp+2+2m + L + lp+2+(L–1)m) + L +

+ (lp+k – Rk) + (lp+k – Rk + lp+k+m) + (lp+k – Rk + lp+k+m + lp+k+km) + L +

+ (lp+k – Rk + lp+k+m + lp+k+km + L + lp+k+(L–1)m) + (lp+k+1 – Rk+1) +

+ (lp+k+1 – Rk+1 + lp+k+1+m) + (lp+k+1 – Rk+1 + lp+k+1+m + lp+k+1+2m) +

+ L + (lp+k+1 – Rk+1 + lp+k+1+m + lp+k+1+2m + L + lp+k+1+(L–2)m) + L +

+ (lp+m – Rm) + (lp+m – Rm + lp+2m) + (lp+m – Rm + lp+2m + lp+3m) + L +

+ (lp+m – Rm + lp+2m + lp+3m + L + lp+m+(L–2)m) =

= L · lp+1 + L · lp+2 + L + L · lp+k +

+ (L – 1) · lp+1+m + (L – 1) · lp+2+m + L + (L – 1) · lp+k+m +

+ (L – 2) · lp+1+2m + (L – 2) · lp+2+2m + L + (L – 2) · lp+k+2m + L +

+ lp+1+(L–1)m + lp+2+(L–1)m + L + lp+k+(L–1)m – L (R1 + R2 + L + Rk) +

+ (L – 1) lp+k+1 + (L – 1) lp+k+2 + L + (L – 1) lp+m +

+ (L – 2) lp+k+1+m + (L – 2) lp+k+2+m + L + (L – 2) lp+2m + L +

+ lp+k+1+(L–2)m + lp+k+2+(L–2)m + L + lp+(L–1)m –

– (L – 1)(Rk+1 + Rk+2 + L + Rm).

Обозначим

lp+r – Rr = Dr, r = ;

Dr = DS(s);

Rr = RS(s).

Суммарное опоздание F(s), соответствующее любому расписанию s Î YP и удовлетворяющее требованиям, сформулированным в первом случае, можно представить в виде

F(s) = L · DS(s) – (L – 1) · RS(s) +

+ (L – 1) · lp+1+m + (L – 1) · lp+2+m + L + (L – 1) · lp+k+m +

+ (L – 2) · lp+1+2m + (L – 2) · lp+2+2m + L + (L – 2) · lp+k+m + L +

+ lp+1+(L–1)m + lp+2+(L–1)m + L + lp+k+(L–1)m +

+ (L – 1) lp+k+1 + (L – 1) lp+k+2 + L + (L – 1) lp+m +

+ (L – 2) lp+k+1+m + (L – 2) lp+k+2+m + L + (L – 2) lp+2m + L +

+ lp+k+1+(L–2)m + lp+k+2+(L–2)m + L + lp+(L–1)m,

или F(s) = L · DS(s) – (L – 1) RS(s) + S(s), где величина S(s) является константой.

Рассмотрим два произвольных расписания s Î YP и s' Î YP, характеризующиеся соответственно F(s), RS(s), DS(s), F(s¢), RS(s¢), DS(s¢).

Пусть RS(s¢) = RS(s) – dR.

Тогда DS(s¢) = DS(s) – dR;

F(s) – F(s¢) = L DS(s) – (L – 1) RS(s) +  –

– L(DS(s) – dR) + (L – 1)(RS(s) – dR) –  = dR;

WS(s) = min(RS(s), DS(s)).

Тогда

WS(s) – WS(s¢) = min(RS(s), DS(s)) – min(RS(s¢), DS(s¢)).

Пусть min(RS(s), DS(s)) = RS(s).

Тогда min(RS(s¢), DS(s¢)) = RS(s) – dR.

WS(s) – WS(s¢) = RS(s) – RS(s) + dR = dR.

Рассуждения аналогичны при min(RS(s), DS(s)) = DS(s). Следовательно, для произвольных расписаний s Î YP (а¢), s¢ Î YP (а) справедливо

F(s) – F(s¢) = WS(s) – WS(s¢).

Рассмотрим равномерное расписание (б). Частным случаем равномерного расписания является расписание s² Î YP, полученное из расписания s Î YP (а) при DS(s) = 0. В этом случае число запаздывающих заданий на приборах равно L – 1. F(s) – F(s²) = WS(s) – WS(s²) = WS(s). Рассмотрим расписание s² Î YP с числом запаздывающих заданий на приборах, равным L. Это расписание получено из исходного расписания s Î YP, характеризующегося соответственно F(s), RS(s), DS(s), Lmax = L, DS(s) > RS(s). Найдем изменение суммарного запаздывания:

F(s) – F(s²) = L DS(s) – (L – 1) RS(s) + S(s) –

– L(DS(s) – RS(s) –  + (L – 1)(RS(s) – RS(s)) –   – S(s) =

= L DS(s) – LRS(s) + RS(s) + S(s) – L DS(s) + LRS(s) +