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

Справедливо следующее утверждение.

Утверждение 3.3. Пусть s Î YP, тогда если z(s) = 0, то WS(s) = 0.

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

D1(s) £ D2(s) £ L £ Dm(s).

В этом расписании

z(s) = Di(s) = 0

в следующих случаях:

а) равномерного расписания, так как c(s) = 0;

б) при RS(s) = 0;

в) если Di(s) = 0; "I = .

Но при выполнении указанных условий имеем

WS(s) = min{DS(s), RS(s)} = 0.

Утверждение доказано.

Обозначим s* – оптимальное расписание выполнения множества заданий J. Справедлива следующая теорема.

Теорема 3.10. Для расписания s Î YP справедливо следующее соотношение:

F(s) – F(s*) ≤ WS(s).

Доказательство. Назовем теоретически оптимальным расписание с z() = 0. Пусть для множества заданий J существует теоретически оптимальное расписание  Î YP. В этом случае, в соответствии с утверждением 3.3,  = 0. Следовательно,

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

Пусть для множества заданий J существует теоретически оптимальное расписание  Î YPS \ YP. В этом случае F() = F(). Следовательно, также справедливо

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

Допустим теперь, что для рассматриваемого множества заданий J существует оптимальное расписание s*, для которого z(s*) ≠ 0. Для любого расписания s при z(s) > 0, согласно определению z(s), справедливо

z(s) = DS(s).

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

z(s*) = DS(s); F(s) – F(s*) ≤ WS(s).

В общем случае, в соответствии с теоремой 3.5, F(s) – F(s*) ≤ z(s), и следовательно, F(s) – F(s*) ≤ WS(s). Таким образом, для расписаний s Î YP величина WS(s) является оценкой отклонения значения суммарного запаздывания оптимального расписания.

Утверждение 3.4. Для расписаний s Î YP; WS(s) ≤ z(s).

Как было показано выше, при выполнении z(s) = 0 выполняется равенство WS(s) = 0, а при z(s) > 0 справедливо z(s) = DS(s). Следовательно, для любого расписания

s Î YP; WS(s) ≤ z(s).

Пусть IR(s) – множество номеров приборов расписания s, на которых запаздывает меньшее число заданий; ID(s) – множество номеров приборов расписания s, на которых запаздывает большее число заданий.

Введем новый класс Y(sр) Î YPS, который состоит из произвольных расписаний s, полученных в результате направленных последовательных перестановок, выполненных в произвольном порядке и уменьшающих DS(s), и, следовательно, RS(s). Эти перестановки последовательно выполняются с некоторого расписания s Î YP и осуществляются посредством переноса незапаздывающих заданий между приборами ID и IR в текущем расписании sk. При этом порядок выполнения работ на приборах, кроме указанных выше, не изменяется. В результате проведенной перестановки в полученном расписании sk+1 может измениться количество запаздывающих заданий только на одном из приборов из множества ID(sk) с номером i1 и на одном приборе из множества IR(sk) с номером i2. Перестановка является запрещенной, если в расписании sk+1 количество заданий на приборе i2 больше количества заданий на приборе i1.

Докажем следующую теорему.

Теорема 3.11. Для любого расписания s Î Y(sP) справедлива оценка отклонения показателя качества от оптимального значения:

F(s) – F(s*) ≤ WS(s).

Доказательство. На первом шаге указанные перестановки выполняются в s1 Î YP для двух произвольных приборов из рассматриваемого расписания s1 Î YP.

Справедливость теоремы 3.11 основана на теоремах 3.7 и 3.8. Для доказательства теоремы в общем случае рассмотрим два произвольных расписания: s¢ Î Y(sP), s² Î Y(sP). Эти расписания отличаются от расписаний s Î YP тем, что в множество P могут входить задания, для которых ljÎP > ljÎQ.

При построении расписания s² Î Y(sP) посредством направленных перестановок в расписании s¢ Î Y(sP) мы приходим к расписанию одного из та­ких видов: а) Lmax(s²) = Lmax(s¢); б) равномерному расписанию.

Следовательно, нетрудно показать, что теорема 3.7, доказанная для расписаний s Î YP, справедлива также и для расписаний s Î Y(sP).

Запишем изменение значения суммарного запаздывания для расписаний s¢ Î Y(sP) и s² Î Y(sP):

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

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

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

F(s¢) – F(s²) = WS(s¢) – WS(s²) и F(s) – F(s*) ≤ WS(s).

Следствие. Для расписаний s Î Y(sP) справедливы теоремы 3.9, 3.10 и утверждение 3.4.

Таким образом, в расписаниях s Î Y(sP) изменение значения функционала так же, как и в расписаниях s Î YP, определяется величинами DS(s), RS(s).

Теорема 3.12. Если в расписании s Î Y(sP) WS(s) = min {RS(s), DS(s)} достигает наименьшего значения, то расписание s оптимально.

В следующих утверждениях, доказательство которых очевидно, сформулированы свойства, характеризующие задания j Î S  U Q в расписаниях s Î Y(sP).

Утверждение 3.5. Пусть , – множества запаздывающих заданий на приборах k и l соответственно. В расписаниях, полученных в результате перестановки множеств запаздывающих заданий между приборами, то есть при выполнении , , отклонение показателя качества от оптимального расписания определяется функцией WS(s) = min{RS(s), DS(s)}.

Пусть на приборах k, l, r в расписании s задания j Î S U Q пронумерованы следующим образом:

jk, jk+m, jk+2m, ..., jl, jl+m, jl+2m, ..., jr, jr+m, jr+2m, ... .

Определение 3.2. Задания jk, jl, jr, или jk+m, jl+m, jr+m, … или jk+2m, jl+2m, jr+2m,… назовем запаздывающими заданиями одного уровня.

Утверждение 3.6. На приборах с одинаковым числом запаздывающих заданий задания одного уровня можно менять местами. При таких перестановках значение функционала (показателя качества) не изменяется.

Утверждение 3.7. От расписания s Î Y(sP) всегда можно перейти к расписанию s Î YPS с тем же значением показателя качества посредством перестановки запаздывающих заданий одного уровня.

На основании доказанных выше теорем и утверждений построена вычислительная схема поиска оптимального расписания, в которой можно выделить пять этапов.

Этап I. Построение исходного расписания s0 Î YP. Если WS(s0) = 0, то расписание оптимально, конец. Иначе: 1) если RS(s0) ³ DS(s0), переходим к выполнению этапа II; 2) если RS(s0) < DS(s0), переходим к выполнению этапа III.

Этап II. Построение равномерного расписания s Î Y(sP) с числом запаздывающих заданий на каждом приборе i, равном L(s) = L(s0) – 1, где L(s0) – максимальное число запаздывающих заданий на одном приборе в расписании s0. Если такое расписание найдено, то оно оптимально, конец. Иначе идем на выполнение этапа IV.

Этап III. Построение равномерного расписания s Î Y(sP) с числом запаздывающих заданий на каждом приборе, равным

L(s) = L(s0).

Этап IV. Построение расписания s Î Y(sP), для которого WS(s) < WS(s0). Если WS(s) = 0, то расписание оптимально, конец; иначе идем на выполнение этапа V.

Этап V. Построение расписания s Î YPS, для которого W(s) < W(s0). Конец.

Обозначим через W(s) оценку отклонения расписания s от оптимального.

Для реализации указанных этапов в приведенном ниже алгоритме применяются следующие типы перестановок.

Перестановка 1P-0P-∆. С прибора h Î I∆(s) перемещается задание j на прибор r Î IR(s). Задание j удовлетворяет условиям lj ³ ∆h(s), lj £ Rr(s).

Перестановка 1P-1P-∆. Меняются местами задание j ¢ с прибора h Î I∆(s) и задание j ² с прибора r Î IR(s). Задания j ¢, j ² такие, что выполняются условия

lj¢ – lj² ³ ∆h(s); lj¢ – lj² £ Rr(s).

Приведенные выше перестановки используются при построении равномерного расписания s Î Y(sP) на этапе II. После каждой из перестановок получаем расписание s¢, для которого справедливо

I∆(s¢) = I(s) \ { h }; | P(s¢) | = | P(s) | + 1;

∆S(s¢) = ∆S(s) – ∆h(s);

F(s¢) = F(s) – ∆h.

Следующие две перестановки используются на этапе III.

Перестановка 1P-0P-R∆. С прибора h Î I∆(s) перемещается задание j на прибор r Î IR(s). Задание j удовлетворяет условиям

lj < ∆h(s); lj > Rr(s).

Перестановка 1P-1P-R∆. Меняются местами задания j ¢ с прибора h Î I∆(s) и задание j ² с прибора r Î IR(s). Задания j ¢, j ² такие, что выполняются условия

lj¢ – lj² < ∆h(s); lj¢ – lj² > Rr(s).

После каждой перестановки получаем

I∆(s¢) = I∆(s) U r; | P(s¢) | = | P(s) | – 1;

∆S(s¢) = ∆S(s) – Rr;

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

Следующие две перестановки используются на этапе IV.

Перестановка 1P-0P-R. С прибора h Î I∆(s) на прибор r Î IR(s) перемещается задание j такое, что

lj £ ∆h(s),

lj £ Rr(s). (3.3)

В результате этой перестановки получаем расписание s¢ такое, что I∆(s¢) = I∆(s) \ { h }, если в (3.3) выполняется строгое равенство, и I∆(s¢) = I∆(s) – в противном случае; RS(s¢) = RS(s) – lj; F(s¢) = F(s) – lj.

Перестановка 1P-1P-R. Меняются местами задания j ¢ с прибора h Î I∆(s) и задание j ² с прибора r Î IR(s). Задания j ¢, j ² удовлетворяют следующим условиям:

lj¢ – lj² £ ∆h(s); (3.4)

lj¢ – lj² £ Rr(s).

В результате перестановки получаем расписание s¢ такое, что

I∆(s¢) = I∆(s) \ { h }, если в (3.4) выполняется строгое равенство, и I∆(s¢) = I∆(s) – в противном случае; RS(s¢) = RS(s) – (lj¢ – lj²); F(s¢) = F(s) – (lj¢ – lj²).

В следующих трех перестановках, используемых для получения расписания s Î YPS, на этапе V участвуют задания, принадлежащие двум множествам: P(s) и S(s). Их целью является уменьшение величины W(s).