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

+ L – L – S(s) = RS(s).

Поскольку RS(s) < DS(s), справедливо

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

Минимальное число запаздывающих заданий на приборах равно L – 2 (случай (в)).

Сравним два произвольных расписания s Î YP, s¢² Î YP. Расписание s¢² отличается от расписания s тем, что часть заданий j Î Sj(s) стали незапаздывающими.

Пусть P(s) = {1, 2, …, | P |};

P(s¢²) = {1, 2, …, | P |, | P | + 1, …, | P | + k, …, | P | + k + f};

DS(s) = Di; RS(s) = Ri.

Замечание 3.1. Для произвольных расписаний s1 Î YP, s2 Î YP справедливо: совокупность запаздывающих заданий, назначенных на один прибор для выполнения, одинакова для всех расписаний, за исключением заданий, которые в результате перестановок стали незапаздывающими.

Лемма 3.1. Для расписаний s Î YP (случай (в)) справедливо:

RS(s) > DS(s), DS(s¢²) > RS(s¢²).

Доказательство.

Ri(s) ≥ lj + lj,

но RS(s) – DS(s) = Ri(s) – lj. Следовательно, RS(s) > DS(s).

Пусть P(s¢²) = p + k + f; f ≥ 1. Теперь сопоставим DS(s¢²) и RS(s¢²).

Число приборов с большим количеством запаздывающих заданий в расписании s¢² равно m – f. Для того чтобы RS(s¢²) ≥ DS(s¢²), необходимо выполнение

Ri(s¢²) ≥ lj,

но

= – .

Согласно утверждению 3.1,

Ri(s¢²) ≤ lj 

Следовательно,

lj – lj ≥lj;

lj ≥ lj +lj;

lj ≥lj.

Приходим к противоречию. Следовательно, RS(s¢²) < DS(s¢²).

Сравним F(s) и F(s¢²) 

F(s) – F(s¢²) = L· lp+1 + (L – 1) · lp+m+1 + (L – 2) · lp+2m+1 + L + lp+1+(L–1)m +

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

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

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

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

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

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

– L(R1 + R2 + L + Rk) – (L – 1)(Rk+1 + Rk+2 + L + Rm) –

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

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

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

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

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

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

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

+ (L – 1)(R¢²1 + R¢²2 + L + R¢²m–f) + (L – 2)(R¢²m–f+1 + R¢²m–f+2 + L + R¢²m) =

= L· lp+1 + L· lp+2 + L + L· lp+k + (L – 1) · lp+k+1 + L + (L – 1) · lp+k+f –

– L(R1 + R2 + L + Rk) – (L – 1)(Rk+1 + Rk+2 + L + Rm) +

+ (L – 1)(R¢²1 + R¢²2 + L + R¢²m–f) – (L – 2)(R¢²m–f+1 + R¢²m–f+2 + L + R¢²m) =

= L· lp+1 + L· lp+2 + L + L· lp+k + (L – 1) · lp+k+1 + L + (L – 1) · lp+k+f –

– (L – 1)(R1 + R2 + L + Rm) – (R1 + R2 + L + Rk) +

+ (L – 1)(R¢²1 + R¢²2 + L + R¢²m) – (L – 2)(R¢²m–f+1 + R¢²m–f+2 + L + R¢²m) =

= L· lp+1 + L· lp+2 + L + L· lp+k + (L – 1) · lp+k+1 + L + (L – 1) · lp+k+f –

– (L – 1)(R1 + R2 + L + Rm) + (L – 1)(R1 + R2 + L + Rm) –

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

– (R¢²m–f+1 + R¢²m–f+2 + L + R¢²m) – (R1 + R2 + L + Rk) =

= lp+1 + lp+2 + L + lp+k – (R1 + R2 + L + Rk) – (R¢²m–f+1 + R¢²m–f+2 + L + R¢²m) =

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

В соответствии с леммой 3.1,

RS(s) > DS(s), RS(s¢²) < DS(s¢²).

Следовательно,

F(s) – F(s¢²) = DS(s) – RS(s¢²) = WS(s) – WS(s¢²).

Теорема доказана.

Теорема 3.9. Если в расписании s Î YP выполняется WS(s) = min{RS(s), DS(s)} = 0, то расписание s оптимально.

Доказательство. Рассмотрим некоторое расписание s Î YP, для которого выполняется

R1(s) ³ R2(s) ³ L ³ Rm(s);

∆S(s) = ∆i; RS(s) = Ri.

1. Пусть выполняется равенство

WS(s) = ∆S(s) = 0.

В этом случае

z(s) = ∆i(s) = ∆i = 0.

Согласно следствию теоремы 3.5, расписание s оптимально.

2. Пусть выполняется WS(s) = RS(s) = 0.

2.1. Максимальное количество запаздывающих заданий на приборах больше единицы.

В общем случае справедливо

Ri > 0, "i =, l £ k.

Тогда

z(s) = ∆i(s) = ∆i(s) = 0.

Следовательно, расписание s оптимально.

2.2. Максимальное количество запаздывающих заданий на приборах в расписании s равно единице.

Согласно условию теоремы 3.9, RS(s) = 0. Перейдем от расписания s к расписанию s¢, для которого RS(s¢) > 0. Согласно теоремы 3.7 выполняется равенство

DS(s¢) – DS(s) = RS(s¢) – R S(s)

и, в соответствии с (3.2), F(s¢) > F(s).

Следовательно, расписание s оптимально. Теорема доказана.

Величина WS(s) = min{RS(s), DS(s)} является основной характеристикой расписания s Î YP, где DS(s) показывает, насколько можно теоретически уменьшить значение функционала F(s), чтобы получить оптимальное расписание. Суммарный резерв RS(s) показывает, какие резервы существуют для получения оптимального расписания.