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

Т е о р е м а

2. a) «(s ,

t) задается

системой

уравнений

оо

у

со (s, /)

г.

р 0

(t) -;- j

dß (у) j

e-<s+e-«t<s))ü,-*) Q ( X )

f) dx,

(9.8)

о

0

R e s > 0 , Q(x,

t) =

Q(l,x,

t),

где Q(\, X, t) и

P0(t)

определены

в

теореме

1;

б)

со* (s, ц) =

j e~^cö (s, t) dt

=

о

[ц - , a - а я

öx)]-i

\ 1 +

a

(

; -

^

-

1;

(9.9)

(.

1 -— p ([л)

ц, — s — a +

а я (s) J

б)

существует

lim цш' (s, ц) =

lim со (s,

^) =

со (s)

со (s) = (1 — ap\) +

^ 1 - " * ' »

,

(9.10)

s-+-a

— ait (s)

щих

параграфов)

будет

получено

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

ожида­

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

t.

А. Обозначим

через

w(t)

возможное

время ожидания,

начи­

нающееся с момента t, или более точно: длину промежутка

време­

ни, начинающегося

с момента

t

и

оканчивающегося

моментом,

когда

система

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

вызовов,

поступивших

в

систему

до момента t.

Положим

СО (s, t) =

Me-s a , W

и обозначим через Ро(0

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

t

система

свободна от вызовов. Предполагаем

ш ( 0 ) = 0 и a ß t < l .

Тогда

t

<ù(s,t) =

et»-e+"PW]< {1 — s [ e-[s-û+«Pfc)]ï p0(x)dx},

(10.1)

ô

oo

f e-S Ï P0 (x) dx =

[s +

a - o n f s ) ] - 1 ,

(10.2)

ô

я (s) - = ß (s + a — an (s)),

Re s >

0, | я (s) ] < 1.

(10.3)

Первое соотношение,

переписанное в виде

t

e -a[l-ß(S )]* =

e - s t щ ( S ) ^

. j . j p u до g-e[ i_p(g)]«_,) d Ц

e -

s

* j (

( 1 0 4 )

0

Вызов

будем

называть плохим,

если

во время

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

наступает

катастрофа.

Так

как вероятность

того,

что

за время

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

некоторого

вызова

наступит

катастрофа,

равна

1—ß(s), а поток вызовов — пуассоновый с параметром

а,

то поток

плохих

вызовов

— тоже

пуассоновый

с

параметром

а[\—ß(s)].

Наконец, пусть за время t в систему не поступали

плохие

вызовы

(вероятность e-a <l -ß(s »'). Для

этого

необходимо

и

достаточно,

чтобы

либо

катастрофа

не

наступила

ни

за

время t

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

е~яі),

ни за

промежуток

времени,

начинающийся

с момента

t и

оканчивающийся моментом, когда система освободится от

вызо­

вов, поступивших до t

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

со (s, / ) ) ,

либо

катастрофа

наступила до момента /, скажем, в некото­

рый момент x (вероятность d[l—е~ях]),

в

этот

момент

х

система

свободна

от вызовов

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

Ро(*))

и

за

оставшееся

время

t—x

в систему

не поступят

плохие

вызовы

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

e-a[l-fi(s)-](t-x)^

СО

Так как /' (s) = 1 — a

j ' e~sttdB

(t) >

1 — aß x > 0, где

b

/(s)

= s — a - j -

aß (s),

то

при s > 0

функция e x p { [ s — a n - a ß ( s ) ] ^ }

по t

возрастает

до

бес­

конечности при ^->-оо

(ибо / ( s ) > / ( 0 ) =

0

при s > 0).

Теперь,

так

как

при s >

0,

t

> 0 вероятность

со (s,

t)

ограничена

(единицей), то

из

соотношения

(10.1)

следует

00

f е-^-"1'

*

Р 0 (x) dx =

s-1.

(10.5)

Ô

Подставим

в

(10.5) вместо

s выражение s + a—an (s),

тогда,

учи­

тывая

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

уравнение

(2.1)

л (s) =

ß (s +

a — an (s)),

определяющее

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

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

распределе­

ния периода

занятости,

получаем

оо

j e~sx

Р 0 (x) dx — [s - f a — а я

(s)]~l,

о

б) при

a ß ! <

1

существуют

пределы

P (z) — lim Р„ (z),

W(t)

lim

V ( / ) - H m K „ ( 0 .

п-»оо

/г-»оо

где W (О и Ѵ (0 — несобственные ф. р.,

причем

=

(1 — aßi) (1 — z) ß (а — дг).

^ j

_ 4 j

ß (a — az) — z

P(z)

=

£

pkzk,

pk>0,

k>0;

P ( l )

= 1;

(11.5)

, ч

( 1 — a ß i ) s

/ s

( 1 — a ß J s ß C s )

n i

c\

e) при

a ß x <

1

+ -i jj5ï s r .

2 * P 4 - P - ( l ) = *

(11.7)

ASM

J] é » P

f c = P' (1) +

P" (1) =

a^+-j

a 2 ß 2

[ 1 +

7 3 ^ 7 ]

+

'

П /1

_ D \

1

A / 1

_ D 19

V

* /

2 ( 1 - a ^ ) '

6 ( 1 - a ^ )

'

4 ( 1 - a ß ^

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

В. Получение

основных формул

задачи.

Предположим, что каждый

вызов является

либо красным,

либо

си­

вызовов является

красным

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

z.

Вспоминая,

что

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

того, что

tt-ный

вызов, по­

кидая систему, оставляет в ней

k вызовов, имеем: Pknzh

— вероят­

ность того, что rt-ный вызов, покидая систему,

оставляет

в ней

лишь k

красных

вызовов;

Рп(г)

= ]Г Pknzk—

вероятность

того,

ft>0

что все вызовы, оставшиеся в

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

п-го

вызова,

красные;

оо

z* I -—- e~aidB

(t) —

вероятность

того,

что

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

о

в систему поступит лишь k красных

вызова

вызовов;

00

I

оо

Szk

e ~ a i d B

^ =

і"е ~ а < і ~ г ) і d B

w = ß ( ß — a z )

Ä>O

0

b

вероятность

того,

что за

время

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

вызова

в систему

не поступят

синие

вызовы.

вызовом и за время его обслуживания в систему

поступали лишь

красные

вызовы.

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

Теперь докажем формулу (11.1). Пусть вызов

покидая

прибор, оставил в системе разве лишь

красные вызовы

(вероятность zP„+i

(z) ) . Для этого необходимо и достаточно, чтобы

л-й вызов, покидая

прибор,

либо оставил систему не пустой, при этом оставшиеся вызовы

были красными (вероятность Pn(z)—Рп(0)),

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

пали

синие вызовы (вероятность ß(a—az)),

Р „ ( 0 ) ) ,

либо

оставил

систему свободной

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

следую­

щий

поступивший

в систему вызов оказался красным

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

z) и

за

время

его

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

поступали

лишь

красные

вызовы (вероятность ß(a—az)). Формула (11.1) доказана.

Наконец, так как

время пребывания вызова

в

системе скла­

пребывания на приборе,

а последние сл. в. независимы,

то

М « ) = M s ) ß ( s ) ,

т. е. верна формула (11.3).

(11.1) — 01-3)

При

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

предполагалось,

что

O s ^ z ^ l

и 5 > 0 . Так как Pn(z)

есть ряд по степеням

z

с неотри­

цательными коэффициентами, а функции

vn(s),

a)n (s),

ß(s)

анали-

тичны в

полуплоскости

Res>0,

то формулы

(11.1) — (П-З)

спра­

ведливы

и при | г | ^ 1 ,

Res>0.

Г. Условие существования стационарного распределения. Как

здесь, так и при изучении

существования

стационарного

распреде­

ных вероятностей {ац}>о,

имела стационарное распределение,

достаточно существования

е > 0 , натурального числа і0 и набора

неотрицательных чисел х0,

хи

Хч — таких, что

£ аИх.

<

xt

— 8 для

і >

і0 >

J ] atj*j

<

+

сю для

і <

і0 .

1>0

3*

35

дится

в состоянии k(k^O).

Обозначим

вероятность перехода

на­

шей цепи из состояния і в

состояние

/

за

один шаг

через

а,-3-.

Настоящая цепь Маркова:

1)

однородна,

так как

состояние системы на любом шаге не

зависит от

номера

шага, а

зависит лишь от состояния

системы

на предыдущем шаге;

2)

неприводима,

так

как:

при j^i

а)

из

состояния

t'(t'^O)

в состояние

/ ( / ^ 0 )

можно

попасть, например, через один шаг;

б)

из

состояния

і(і>0)

в состояние

/ ( / ^ 0 )

при t — / ^ І

мож­

но попасть, например, за і—/

шагов;

3)

непериодична,

так как, если в некоторое

состояние

можно

попасть из какого-то состояния за k шагов, то туда же

можно

попасть и за

k+l

шагов.

Рассмотрим

сл. в. х,

принимающую

значения х0, хіу

Х2... в

за­

висимости

от

того,

в каком

состоянии

находится система.

Тогда

£ aiixj

есть математическое ожидание сл. в. х после одного

шага,

если в начале этого шага система находилась в состоянии і.

Пусть a ß i < l . За

случайное число х

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

время,

необходимое для обслуживания вызовов, оставшихся

в

системе

после

окончания

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

некоторого

вызова;

x = xt- = ißi,

если число

оставшихся вызовов

равно

і

или система

находилась

в состоянии

г.

Тогда при

і > 0

£

aljXj

=

(i -

1 - j -

aß2 ) ß,

iß, — ß x ( l

— aß,) = xt

-

е..

Здесь

8 --r, ß t

(1 — aßx ) >

0; при i

0

£

ацхі

<

+ оо

живания

на

случай, когда обслуживающий прибор выходит из

строя, требуя

ремонта (восстановления). Действительно,

a priori.

очевидно,

что

существуют системы обслуживания, для

которых

но правил выхода прибора из строя.

Прежде

всего прибор может выходить из

строя либо

только

в свободном

состоянии

(когда

вызовов

в системе

нет), либо толь­

ко при обслуживании

вызовов,

либо и

в том

и в

другом

случае.

ния равна t, то и при новом поступлении на

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

вызова длительность обслуживания

должна

равняться t.

В настоящей главе результаты, полученные в главе 1, перено­

сятся на случай системы M | G | l | o o

с прибором, отказывающим

щего

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

ром

а > 0 . Вызов, заставший прибор

свободным,

немедленно

начи­

нает обслуживаться. В противном случае вызов

становится в оче­

редь. Допускается неограниченная

очередь. Длительность

обслу­

дился

от

вызовов

и за время t

вызовы

в

систему

не

поступали,

то

с

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

E(t)

прибор

выйдет

из строя

в

промежутке

[Т,

Т + t].

После выхода

прибора

из строя

начинается

его восста­

новление.

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

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

—

сл. в.

с

ф.р. F(x).

Длительности обслуживания вызовов, «жизни»

и

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

прибора — независимые сл. в.

А. Распределение я-периода. Обозначим

через П„(/)

ф.р.

«-периода занятости, a ïl(t),

как и ранее — ф . р . периода

заня­

тости системы M [ G | l | o o с

абсолютно надежным прибором. Ясно,

что порядок обслуживания

вызовов не влияет

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

я-периода. Пусть вызовы обслуживаются в инверсионном

поряд-

nnis)^[nis)y.

(2.1)

Б. Число вызовов, обслуженных за

«-период.

Пусть

—

вероятность того, что за «-период обслужено

& ( & ^ 1 )

вызовов.

Положим

Рп (г)

=

£

Pfzk-

(2.2)

Если каждый вызов считается красным

с

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

z,

незави­

симо

от

цвета

остальных

вызовов, то

pn(z)—вероятность

того,

что за «-период были обслужены

лишь

красные

вызовы,

а так

как «-период складывается из п независимых периодов

занятости,

то

Рп(г)--[Р(*)]П,

(2.3)

где piz)—вероятность

того, что

за

период занятости

M | G j l ( o c

с абсолютно надежным лрибором обслужены лишь красные

вызо­

вы. Величина р(г) определяется

в § 3 гл. 1.

Кроме того, имеет место соотношение

где

<p„(z, з)

= [ф(г,

s)f,

(2.4)

00

фя (z,

s) = J ег*ЧФп

(г,

t);

ф„ (z,

/)=-][] ф£я ) (t)

z\

a ФІ"' it)

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

того, что

за «-период обслужено k вызо­

вов и

все

они

красные;

n-период

длился

время,

не

превосходя­

щее t.

Здесь ф(г, s) определено в § 5 гл. 1.

В. Длина очереди в «-периоде. О-моментами называем

момен­

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

вызовов. Пусть

в

момент

іо = 0

начался

период

занятости

и

в

момент

t

он

еще

не

закон­

чился.

Обозначим

через

(х,

t) dx

вероятность

того, что в

момент

времени

t

в системе

находятся

kik^O)

вызовов,

а с

последнего

О-момента

прошло время

х.

Известно, что

я„ (z,

X, s) -

Y

] e

~ s t U ^

(*• 0

z 4

t '

оо

П„ (z, t) = £

П?» it)

=

£

Ç 2*ПІЛ )

ix, t) dx,

(2.5)

*5=1

0