книги из ГПНТБ / Приоритетные системы обслуживания

Тогда

на основании

(5.6)

выражение s — ^ П а £ ( 1 — ß ,

(s))

заменится

на 5.

Формула

(5.5)

после

произведенной

замены запишется

в виде

Г е - " Р 0

(x) [dx

+ 1

- ^ + ^-аклк(8))

7 e _ s x

х ) d x

+

=

[s + CTÄ - oknk (s)]-i [(Ä =

Г77).

(5.7)

Если в системе уравнений (5.7)

неизвестными

считать

выражения

j e~sx Р 0 (x) dx,

j P, (x) e~sx

dx и j e-S Ï

P;

(x) dx

(/ = 2, r),

оо

s Г e~sx

Р 0

(x) dx = — - —

{1 — e (s -|- а)} х

J

s + cT

о

X

II — e(s + a)cp(s +

o — on(s))

— [ 1 — e (s + er)] л

( s ) l - 1 ,

1

s+a

i

(5.8)

где

л (s) задается формулой (5.6).

14*

211

Кроме того,

р- = А Р « » - ^ і г 1 {

'

-

+

*'«»}"'•

1 = 1

(5.9)

Из уравнения (5.9) и системы уравнений

(5.7) шаг за

шагом

нахо­

дятся

00

j e - » P , ( x ) d x

(/ = 277).

о

Таким

образом,

(àk(s,

t)

определяется из системы

уравнений

(5.4),

(5.7) и

(5.8).

Е. Обозначим через wh(t)

возможное

время

ожидания

вызо­

вом приоритета к, поступившим в момент t

щ{а,Г)

= л и ? - и > * ( 0 .

*

(5.10)

Методом катастроф легко убедиться в справедливости

соотно­

шения

щ

(s,' t) = (ok (s +

afe_! — oft_! nk^i (s), t).

(5.11)

Из выражений

(5.4),

(5.6) и (5.11)

получаем

wk(s,

t)

= е^-в *+0 А(*+в й-і-( Т *.ія й-і")"'

x

X {1 - ( s + а ^ - а ц Я й - !

(s)) f Р 0 (ж) е - [ S - ° * +

W +

^

-

I

- W

A -

I

W * ^ -

ö

— {1 — ф (s + аА _! —

nk-i

(s))} X

X j

Pi

'(*)

e ~ l

$ ~ a k + a k ^ s + 0

k . i - a

k - i n k - i ^ x

dx

—

0

r

—

£

{1 — ßy (s +

0ft_i — аА _! лк-1

(s))}

X

/=fe+l

X J Pj (x) e -Ii -e *+e *Pft<'+o ft-i-0 *.i"ft.iW)]J t

.

(5.12)

о

Таким

образом,

Wk (s, f)

определяется

уравнением

(5.12),

где не­

известные Ро(х),

Pi(x),

Pj(x),

j = k+l,

r, k = l, r—1, задаются со­

отношениями (5.7), (5.8) и (5.6) соответственно.

Ж. Найдем стационарное

распределение

времени

ожидания

для вызова приоритета k.

Умножаем

обе

части

формулы (5.7) на s и при k = r устрем­

ляем s к нулю. При этом, так как существует

р0 =

lim

Р 0 (0,

то существует

р, =

lim Р, (t)

=

lim s

Г e~sx

Р, (x)

dx.

Для определения

pj ( / = 2 ,

г)

с

учетом

(5.13)

из (5.7)

при

sjO

получаем

Е

ß,-i Pi =

t

û

i ßyi

<* =

Ѵ ^ Т ) ,

(5-14)

/=ft+i

/=ft+i

откуда

Р,- = о,-

Из

(5.9) и (5.13)

вычисляется

р г

г

р, =

е (а) (

1 -

ß u )

{ і

: = а І ^ -

+ е И

Ф і } " ' •

( 5 - 1 5 >

І = І

В

(5.12) устремляем

t-*--\-oo

и применяем

правило

Лопиталя.

шд

(s,

0

= |pu -(s +

аА _,

— Ok-i

Jtft_i (s))

+

+

Px

[1 — ф (S-f-

0 * - l

—

Ofr-i

Яе_і (s))]

-f-

r

+

E

1 — ßj ( s , +

—

a é

-

i

(s))j) x

/•=*+!

X {s — aft

+ a f t ß Ä ( s +

0fe_i — afe-irefe-iCs))}-1.

(5.16)

Теперь,

подставляя

в

(5.16) значения

р0 , рг

и ру (/

= k + 1, г),

по­

лучаем

выражение

1 -

У

afin

1 — c(0)

+

ae(a)

ер, [ ( 1 - е

(a))

(s +

Ok-i — ok-\

ftk—i (s))

-!- a e (a)

[1 — cp (s -f- af e _i — ak~\

%k-\ (s))]]

V

a.

[1

—

ß3 (s

- f

aA _i

— Ok-i

nk-\(s))]

X

l = k+l

X

{s — ak

+

aft

ßÄ (s + af t _i — aA _i

я е _ і (s))}-

(5.17)

совпадающее

с вычисленным

ранее методом вложенных цепей.

Доказать,

что при выполнении условия стационарности

а А і Ф І ( 1 ) + •••

+ a , ß a < p ; ( l ) < l

справедливы формулы (5.17) и (5.6), если

ß(- (s) и afin заменить всюду HaO,(ß,(s))

и a£- ßa

( 1 ) , соответственно.

тетную систему

M r | G r | l

| o o с

ненадежным

в свободном состоянии

прибором, но предпочли

остановиться на

двухприоритетной

систе­

ме и получить

окончательный

результат,

а не рекуррентные

соот­

ношения. Ищем

нестационарную производящую функцию

числа

что в момент времени t уже время х как

обслуживается

вызов

приоритета і ( / = 1 , 2); в системе находятся

m вызовов приоритета

1 и п вызовов приоритета 2 (включается

и обслуживаемый

вызов);

Р3 (от, n, x, t)dx — вероятность того,

что в момент t уже время

вов приоритета 1 и п вызовов приоритета 2;

Ро(х, t)dx

— вероятность

того, что в

момент t уже время х

как прибор исправен, а система свободна от вызовов

з

р(т,

n, x, t) = £

Pi

(m,

n, x, t),

m + « > l ,

(6.1)

p1(0,0,x,t)

=

p2(0,0,x,t)

= 0,

(6.2)

со

P(zx ,

z2 , x, s) = j e - 5

'

2

P(m,n,x,t)zTz2dt

+

X

rt+m^l

со

- f f P0 (x, 0 e - s '^,

0 < z x

< 1, 0 < z 2 <

1, s > 0 ,

(6.3)

ô

Моменты

начала или окончания как обслуживании

вызовов,

Пусть каждый вызов

приоритета i ( і = 1 ,

2) является

красным

с вероятностью z* и синим

с дополнительной

вероятностью

1—Zi, и

строфы, поток которых является пуассоновый с параметром

s > 0 .

Тогда 2

P (т> п< х> О Z\

Z2 dx + Р 0

(x, t) dx — вероятность

то-

m+njîl

го, что в момент t в системе [были лишь

красные

вызовы, а с пос­

леднего 0-момента прошло время х.

Далее (6.3) можно

записать

в виде

оо

sP(z1 (

z2 , x,s)dx

=

{jP0 (x, 0 d t [ 1 - e - s < ] } d x +

oo

+ {j £

p ( m , « , x , O ^ d J 1 - e - ^ ] } d x .

Теперь sP(zu

z2,

x,

s)dx

можно интерпретировать как вероятность

того, что первая катастрофа

наступила в момент, когда все вызовы,

находящиеся

в

системе,

оказались

красными,

а с последнего

0-момента прошло время х.

В. Упрощение задачи. Рассмотрим

процесс

{m(t),n(t),

l{t),

o(t)},

где m(t) — число

вызовов приоритета / в системе в момент t,

n(t)

приоритета

2,

— время,

прошедшее с последнего 0-момента,

к

моменту

t, «г (^)

= {1, 2, 3,

4}

—

указывает, обслуживаются

ли

в

момент /

вызовы

приоритета

/

или

2, или происходит восстанов­

Пусть

sP(zi, z2,

x,

s)dx

— вероятность

наступления

первой

катастрофы

в первом периоде регенерации в момент, когда все вы­

зовы в системе оказались

красными,

а с последнего 0-момента

про­

шло время x.

Л е м м а

1. Верна

формула

где

Р(гѵ

гѵ

x,

s) =

[n(s)]-lP(zv

z,,

x, s),

(6.4)

ц (s) =

1 — e (s -;- a) ф (s -f- a — ал

(s)) — —-— [1 — e (s

-{- a)] л

(s),

s - j - a

1(6-5)

a = a1

+ a2 ,

a П(^) есть ф. p. периода

занятости

нашей

системы,

определяв'

мая из

функционального

уравнения

2

ал

(s) = 2 a<ß( (s

+ о — ал

(s)),

Re s >

0, | л (s) | < 1.

(6.6)

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

Представим

(6.4) в

виде

sP (2p

z2,

x,

s) dx =

sP(zv

z2 , x,

s) dx - f [1 — p (s)] sP (zv

z2 ,

x,

s)dx.

(6.7)

Теперь

доказательство

(6.7)

аналогично

приведенному

в § 3 гл. 5.

Г.

Обсуждение.

Из

пункта

А ясно,

что

задача

значительно

1-й цикл

\ 2-й цикл

k-іяый цикл

Рис.

8

1-й цикл

2-й цикл

k-тый цикл

Рис.

9

1-й цикл

2-й

цикл

k-тый

цикл

Рис.

10

Промежутки времени между последовательными поступления­

ми вызовов приоритета 2

на прибор

в периоде

занятости

назовем

вызова

приоритета 2, то он состоит только из циклов

(рис.

8).

б)

Период

занятости

может начаться с вызова

приоритета /

(рис. 9).

в)

Может

случиться,

что до поступления вызовов

прибор

Будем говорить, что рис. 8—10 соответствуют

периоды

занято­

сти типа

1—3.

syi(zu

z2,

Д. Еще одно упрощение задачи.

Обозначим

через

x, s)dx

(i= 1,2,3)

вероятность того,

что в периоде

занятости

типа

і первая

катастрофа

наступила

в

момент,

когда все

вызовы

в системе оказались

красными,

а с последнего

0-момента

прошло

время

x.

Следующая

лемма

позволяет

свести

изучение

процесса

к изучению его в периоде занятости.

Л е м м а

2.

Функция

P(zi,

z2,

x, s)

выражается

через

\i(zu

z2,

x, s)

(i—l,

2, 3),

причем

P (zlt

za ,

x, s) =

exp

{—(s-\-a)

x} [l — E (x)] +

e (s + a) y3 (zl t z2 , x, s) +

-I

- — [1 — e (s + o-)] Y2 (zl f z2 , x, s) +

s -j -

о

a *

[ 1 — e (s + a)] y±

(zx,

z2,

x, s).

(6.8)

s +

a

Формула

(6.8) получается по формуле полной

вероятности.

При

доказательстве ее следует обе части

(6.8) помножить

на

sdx.

Тогда первое слагаемое правой части

(6.8)

соответствует

случаю,

когда

в

периоде

регенерации

первая

катастрофа насту­

пила

в

момент

свободного

и исправного состояния

прибора,

вто­

четвертое — типа

1.

Е. Процесс

в

периоде

занятости.

1°. Пусть

в

момент

времени

/о = 0 начался

период

занятости

обслуживанием

вызовов

приорите­

та 1 (т. е. промежуток

времени

с момента

/о = 0 до

первого

момен­

та освобождения системы от вызовов приоритета 1), причем

в

начале этого периода было п(п^І)

вызов

приоритета

/

и не

было

вызовов приоритета

2.

Такой

период

назовем

/п-периодом.

Пусть nin(zu

z2,

0,

s)

—

сумма

вероятностей

того, что

внутри

/я-периода в моменты

окончания

обслуживания

некоторого

вызова

в

очереди

находятся

лишь красные

вызовы (приоритета

/

и

2),

а до этого момента не наступала

катастрофа;

smn(zu

z2,

x,

s)dx

—

вероятность

того, что

первая

катастрофа

в /я-периоде наступила в момент, когда все

вызовы

оказались

красными,

а с последнего 0-момента

прошло время

х.

Положим

a = s + a\

(1 — Zi)+a 2 (l — z 2 ) .

по

2°. Л е м м а

3.

nin(zu

z2,

x,

s)

и

ліп(ги

z2,

0,

s)

определяются

формулам

я in {zx,

z2 ,

0,

s)

--=

i

-

(п>1),

(6.9)

— «Г ßi

(°)

я І п

(zv

z2, x,

s) =

[ï —B1

(x)] exp {— ax}

• [ Я і ( в + а 2 ( 1 — z 8 ) ) J n

l - z p ß i

(a)

( я > 1 ) .

(6.10)

Здесь

ni(s)

—

преобразование

Лапласа—Стилтьеса

от ф.р.

перио­

да

занятости

системы

M | G111 оо с

интенсивностью

а\

поступаю­

щего

потока

и

ф.р.

Bi(t)

длительности

обслуживания

вызовов.

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

Представим

формулу

(6.10)

в

виде

5 Я і п ( z x ,

z2 ,

x,

s) — [I — Вг(x)]

exp

{— ax}zfsdx

+

+

Я і п

(zv

z2 ,

0, s) [1—j51 (x)]exp(—ax}sdx

(n >

1).

(6.11)

Тогда

в правой части (6.11) первое слагаемое есть вероят­

ность того,

что в /n-периоде первая катастрофа наступила при

Перейдем

к доказательству соотношения

(6.9). Запишем его

в виде

ящ (zv

2 а , 0, s) =

z » - ^ ! (а) + г~'яІп

(гѵ

za ,

0, s) ßL (а) —

- K (

S +

a 2 ( l - 2 2 ) ) ] «

( л > 1 ) ,

(6.12)

где 2 ^ ~ 1 ß 1 ( a )

— вероятность того,

что в

/n-периоде

в момент

окончания обслуживания

первого

вызова

в

системе

оказались

лишь красные

вызовы и до этого момента

не наступала катастро­

фа; г ~ І я І П ( 2 ' 1 ,

22 , 0, s ) ß x ( a )

— сумма вероятностей того, что внут­

ри -/«-периода

до момента

окончания

обслуживания

какого-либо

зались лишь

красные

вызовы, не считая следующего обслуживае­

мого вызова,

за

время обслуживания

которого

не

было ни

катастроф,

ни синих

вызовов.

Далее,

так как

первые

два слагаемых

правой

части

(6.12)

включают

в

себя

и

вероятность [яі(5 + а 2 ( 1 — z 2 ) ) ] n

того,

что

в /«-периоде не наступала

«катастрофа»

и

в момент

окончания

/л-периода

в системе

остались лишь красные

вызовы

приоритета 2

часть

(6.12)

такую возможность

исключает,

то ее надо

исключить

и из правой

части. Равенство (6.9)

доказано.

3°. Пусть в момент времени

/ = 0

началось

восстановление

прибора. Промежуток

времени от ^ = 0 до первого

момента,

когда

прибор исправен, а в системе нет вызовов приоритета

/,

назовем

/••-периодом.

через sF(z\, z2,

x, s)dx

в

Обозначим

вероятность

того,

что

/^-периоде

первая

катастрофа

наступила,

когда все

вызовы

в

системе оказались

красными,

а с последнего О-момента

прошло

время

x.

Л е м м а

4.

JIF(Z\,

Z 2 ,

X, S) находится

по

формуле

Лр

(2 р 2 2 ,

x, s) = ехр {— ах} {[1 — F (х)] +

- Ь [ 1 - В 1 ( х ) ] [ ф ( а ) - ф ( а ) ] } ,

(6.13)

где а

получается

из а при

замене

z\ на n\{s

+

a2{\—z2)).

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

лР (zx,

z2, x, s)

можно

выразить

через

Щп(г±,

2 2 , x,

s)

,ry

С Jb^e-bUß-is+aji-zMu^z

г X t S ) d F ( u y

(6.14)

J

n\

Помножим обе стороны

(6.14) на sdx.

Подставляем из (6.10)

значение

J i i n ( z i ,

z2, x, s) в

(6.14)

и пос­

ле простых преобразований получаем (6.13).

m

4°. Цикл, начавшийся при наличии

в

системе

вызовов

(приоритета

2),

назовем т-циклом.

Обозначим

через

snm s2

(zv z2 , x, s) dx

вероятность

того, что

первая катастрофа в m-цикле наступила,

когда все вызовы

оказа­

лись красными,

а с последнего 0-момента

прошло время х. Как

и в пункте В настоящего параграфа,

•nm B l (z1 , z2 , x, s)

выражается

через я і п ( г 1

г 2 2 ,

x, s),

и снова, используя

(8.10), выводим

Л е м м а

5.

nmBa

{zv г2 , x, s) = z™ exp {— ах} {1 — В2

(х) +

_

def

+

[1 -

В, (x)] zt

[ß2 (а) -

ß 2 (et)] = z?R (zl t z„ x, s).

(6.15)

5°. Промежуток занятости прибора, состоящий только из цик­

лов и начинающийся

с m вызовов приоритета 2, назовем

т-перио-

дом типа 1.

Найдем распределение Т(х) длительности одного

цикла. Ме­

тодом катастроф легко доказывается

равенство

t(s)

= p2(s + a1[l-n1(s)]).

(6.16)

Обозначим

через

пцт(г2,

0, s)

сумму

вероятностей

того, что

с начала

от-периода

типа

1 до окончания

фиксированного

цикла

внутри m-периода типа / не наступала

катастрофа, а все вызовы

приоритета 2 (других в такие моменты

не

бывает)

оказались

красными.

Если

наш процесс в m-периоде

типа

/

рассматривать

лишь

в моменты окончания циклов, то можно

считать,

что

изучается

начавшийся

с m вызовов период

занятости

системы

M} G111 оо

с интенсивностью а2 поступающего потока

и ф. р. Т(х)

длитель­

ности обслуживания

вызовов.

На основании леммы 3 пцт{г2,

0, s)

определяется

по формуле

(8.9), если шаг за шагом сделать следующие

замены:

z2 = 0, n = m, z1 = г2 , ах

= а2 , ß2 (s) =

t (s).

Окончательно выводим

Л е м м а

6.

" i i m ( 2 2 . 0 . s ) =

z?- 1 ß2

(<х)— [nls{s)]m

( m > l ) ,

(6.17)

2

1

_Л