close

Вход

Забыли?

вход по аккаунту

?

Математическая модель замкнутой одноканальной системы массового обслуживания.

код для вставкиСкачать
УДК 519.872
Р. Ф. Гильмутдинов, А. П. Кирпичников
МАТЕМАТИЧЕСКАЯ МОДЕЛЬ ЗАМКНУТОЙ ОДНОКАНАЛЬНОЙ СИСТЕМЫ
МАССОВОГО ОБСЛУЖИВАНИЯ
Ключевые слова: Система массового обслуживания, поток требований, очередь, обслуживающее устройство.
Представлена математическая модель одноканальной системы массового обслуживания замкнутого типа.
Проведена подробная математическая формализация модели и впервые вычислены вторые моменты всех
важнейших числовых характеристик систем массового обслуживания этого типа.
Keywords: queuing system, flow of requirements, queue, serving device.
The mathematical model of single-channel system of mass service of the closed type is presented. A detailed mathematical formalization of the model is held; for the first time the second moments of all the important numerical characteristics of queuing system of this type are calculated.
В открытых системах массового обслуживания
(СМО) все заявки приходят откуда-то извне, и при
этом интенсивность потока поступающих в систему
потока заявок не зависит от состояния самой системы.
Тем самым считается, что источник заявок располагает
неограниченным числом требований. В этом случае
поступающий в систему пуассоновский поток заявок
характеризуется как процесс, не зависимый от выходящего из системы потока обслуженных заявок. Системы массового обслуживания такого рода называют
разомкнутыми (или открытыми), считается, что их
питает источник заявок, располагающий бесконечным
числом требований [1 - 6].
Рассмотрим теперь тот случай, когда узел обслуживания предназначен для обслуживания конечного (обычно постоянного) числа циркулирующих в системе заявок. В этом случае, как только требования обслуживаются, они возвращаются обратно в источник.
Задачи такого рода особенно часто встречаются при
эксплуатации машин и механизмов (или комплексного
оборудования), которые могут выходить из строя, но
восстанавливаются после ремонта. Требования, покидающие систему, при этом возвращаются обратно в
источник заявок, где они пребывают в течение некоторого случайного промежутка времени, а затем вновь
поступают в систему. Такого рода системы называются
замкнутыми системами массового обслуживания.
Еще одним примером такого рода систем является так называемая сеть массового обслуживания.
Источник сети при этом рассматривается как система,
в свою очередь, нагружаемая выходами самой сети
массового обслуживания. В более общем случае требование последовательно проходит через несколько систем, и тогда мы имеем сеть, структура которой определяется правилами циркуляции требований в различных
системах массового обслуживания (такая сеть, конечно, может быть как замкнутой, так и разомкнутой).
В сущности, любая СМО, конечно, имеет дело
только с ограниченным числом заявок, но весьма часто
число их так велико, что на практике влиянием эффектов, связанных с конечностью числа требований, на
функционирование системы можно пренебречь. Например, поток вызовов на АТС крупного города исходит, в сущности, от ограниченного числа абонентов, но
189
это число так велико, что практически его можно
считать бесконечным.
Рассмотрим тот случай, когда входящий в
систему пуассоновский поток требований создается
конечной группой ее возможных клиентов. Систему
будем считать состоящей из очереди и одного обслуживающего прибора. Пусть структура системы
такова, что всего имеется N >1 заявок (требований),
циркулирующих в системе, но при этом каждое требование может либо реально находиться в системе
(в очереди или под обслуживанием), либо вне системы (фактически пребывая в источнике), чтобы
через некоторое время вновь в неё вернуться. Все
заявки поступают в систему и обслуживаются прибором независимо друг от друга. Ясно при этом, что
если в системе находится k требований (очередь
плюс прибор обслуживания), то в числе поступающих в систему (в источнике требований) будет находиться N  k заявок.
Пусть интервал времени, через которое каждое требование после его обслуживания и повторного пребывания в источнике заявок, вновь поступает в систему, есть некоторая случайная величина.
Будем считать, что эта случайная величина распределена по показательному (экспоненциальному)
закону, со средним значением, равным t ср . Или, что
то-же самое, t ср - это среднее время нахождения
одного требования в источнике заявок от окончания
обслуживания и до его возвращения обратно в систему. В этом случае физический смысл интенсивности   1 t ср , очевидно, заключается в том, что она
определяет среднее число возвращений в единицу
времени, своего рода частоту возвращений, одной
заявки после обслуживания обратно в систему. И
тогда, в свою очередь, общая интенсивность поступающего в систему потока требований равна
 N  k  , где k – номер состояния системы, то есть
число заявок, реально в ней находящихся, как в очереди, так и под обслуживанием. Граф такой системы
изображен на рис. 1. В рамках символики Кендалла
такого рода системы массового обслуживания обозначают аббревиатурой М/М/1//N, в которой по-
следний символ означает полное (предельное) число
заявок в системе.
N
 N 1  


 N  2 
3

2



Рис. 1 - Граф состояний и переходов замкнутой одноканальной системы массового обслуживания
Заметим, что в строгом смысле замкнутые системы массового обслуживания являются саморегулируемыми. В самом деле, если такая система перегружена, вследствие чего в ней образовалась большая
очередь ждущих обслуживания заявок, то интенсивность поступающего в систему потока дополнительных требований падает, что предотвращает дальнейший перегруз системы. Говоря другими словами, замкнутые СМО – это СМО с обратной связью.
Применяя общие формулы расчета вероятностей стационарных состояний [4] для процесса гибели
и размножения, изображенного на графе состояний
(рис. 1), имеем
p1 
N!
N  1!
 p0 ; p2 
N!
N  2!
 2 p0 ; p 3 
N!
N  3!
3 p0
N k  N
в правой части формулы (2) относятся к
соответствующим вероятностям каждого из состояний системы в целом. Например, если поступившая
в систему заявка застала в ней одну заявку, уже находящуюся в это время под обслуживанием, то в
источнике непосредственно перед поступлением
заявки находилось N  1 заявок. Если заявка застала
в системе две другие заявки (одну в очереди и одну
под обслуживанием), то соответственно перед поступлением заявки в систему в источнике находилось N  2 заявки. Если в системе уже находились
три другие заявки, то в источнике перед поступлением заявки были N  3 заявки и так далее. Из соотношения (2) получаем
pожид 

p N1
1 N1
k  k
  N k pk  0   Nk N  
N k k 1
N k k 1

p0
 Nk

N!
N!
;
N
k 0
 p1  .
N p0
Nk


p1
 Nk
.
1
N
k 0
k 2
(тогда коэффициент простоя обслуживающего устройства к. п.  1 к. з.  p 0 ). Дисперсия этой величины
(1)
Числовые характеристики установившегося
режима
Вероятность ожидания в данном случае находится из соотношения
N 1 N  k
Nk
pожид  
pk .
k 1
N
N
0
к. з.  m   k pk   pk  1 p 0 ; p 0  1 m
N0   1 – так называемые факториальные многочлены
или обобщённые степени [7]. Ясно, что при этом
p0  1  Nk  k .
  1 p
скольку еще не известно k . Их окончательный вид
будет получен ниже.
Среднее число требований, находящихся
под обслуживанием (в данном случае совпадает со
средней долей занятости обслуживающего устройства или с коэффициентом загрузки),
для всех k  0,1,  , N . Здесь
 N k 

k 2
очевидно, только промежуточными формулами, по-
k p0 или pk  Nk  k p0
Nk   N N  1N  2  N  k  1 
1
 Nk

N
 pk 
Эти формулы для p ожид и pобсл являются,
В общем виде
N  k !

1
 Nk
k 1
pобсл 
N! N  2
N!
N!
 p0 ; pN 1  N1 p0 ; pN  N p0 .
2!
1!
0!
pk 
 k 1  k 1
 
N
Точно так же вероятность немедленного обслуживания поступившей в систему заявки
…;
pN 2 

N 1
(2)
 
В этой формуле N k N – вероятность того, что в
источнике в среднем содержится N k заявок (тогда
как в системе, то есть в очереди и под обслуживанием,
в сумме в среднем k заявок). Весовые коэффициенты
190
1
N
k 0
k 2
2

2

m2   k 2 pk   pk  m  1 p 0  m  m 1 m .
Для СМО замкнутого типа следующими по
порядку рассмотрения числовыми характеристиками (в отличие от изучения открытых систем) являются не те, которые отвечают заявкам, находящимся
в очереди на обслуживание, а те, которые относятся
к требованиям, находящимся в системе в целом (как
в очереди, так и под обслуживанием). Имеем
k   k p k   k  N  Np k  N  p k   N  k p k 
N
N
N
N
k 0
k 0
k 0
k 0
 N  p 0  N  k  Nk  k  N 
N
k 0
N 
p 0 N1 k 1 k 1
N  
 k 0
p 0 N k  k
1 N
 N   N    p k  p 0  

 k 1
  k 0
N
1 p 0
m
N .


(3)
Заметим также, что в соответствии с графом
состояний абсолютная пропускная способность системы в данном случае имеет вид A   N  k , и тогда

m

 


А  Nk
m

  N  k , t обсл  ,
A


Рис. 3 – Зависимость среднего числа заявок в
очереди от приведенной интенсивности входного
потока
(4)
откуда автоматически следует тот же самый результат
(3):
k N
m
.

Среднее число заявок, находящихся в очереди
на обслуживание, вычисляется как разность полного
числа требований в системе и требований, находящихся под обслуживанием, то есть
l k m N
 m  1  
m
1 
m Nm
 N  1
.


N  

При больших значениях   1 , отсюда очевидно, име-
Рис. 4 – Зависимость среднего числа заявок в
системе от приведенной интенсивности входного
потока
Строго говоря, абсолютную пропускную
способность A в данном случае нужно вычислять по
формуле
A    k pk     N  k pk ,
ем k  N , l  N  m , при этом коэффициент загрузки
к. з.  m  1 .
Заметим, что для замкнутых систем массового
обслуживания иногда вводят коэффициент простоя для
требований к. п. т.  l N (соответственно для открытых
СМО к.п. т.  l k ). В том случае, когда коэффициент
простоя к. п. т. близок к единице, говорят, что имеет
место так называемая скученность (требований в очереди). Можно ввести и коэффициент скученности
F  1 к.п. т. 1 l N , при этом скученность образуется
N 1
N 1
k 0
k 0
которая, как легко видеть, дает то же самое соотношение A   N  k . С помощью результата (3), (4)
формулы pожид и p обсл можно переписать как

1
p ожид 

1
N
 pk 
m k 2
m
Проверка: p ожид  p обсл 
 1 p
0
 p1  ; p обсл 
p1
m
.
1 p 0
 1.
m
Дисперсия общего числа заявок в системе
 k2   k 2 p k  k   k  N  N k p k  k 
N
при значениях F  1. Графики величин m, l и k
представлены на рис.2-4.
N
2
k 0
2
k 0
 N  k p k   N  k k p k  k 
N
N
k 0
k 0
2
 
Nk p0  Nk kNk k k k Nk 
N1
k0
 
2
p0 N1 k1 k1
 kN  
 k0
 
1 N1
1 N1
 N k k   k pk 1  k N k   k 11pk 1 

k
0

 k 0
 
 
1N1
1N1
1N
1N
 Nk k  k1 pk1   pk1  Nk k  kpk   pk 
k0
k0
k1
k1
Рис. 2 - Зависимость среднего числа заявок под обслуживанием от приведенной интенсивности входного потока
191
 
 
1N
1 N
k 1p0
 Nk k   k pk    pk p0   Nk k  



k
0
k
0








l k ml
,
 Nk k  


(5)
где l  k  m – средняя длина очереди. Но ковариация
числа заявок в очереди и под обслуживанием


K ml   k  1p k  l m  1 m l , и тогда
N
k 1

 

k m  l   m 1 m
 2 1 m l 

 l2   k2   m2  2 K ml 

  
m  m  1   1 m  1 m l

 2 1 m  l .
2


m   m 1 m  1 m l
 2 1 m l 

лись все N заявок. Если заявка застала в системе
одну заявку (которая находилась в это время под
обслуживанием), то соответственно перед поступлением заявки в систему в источнике находилось
N 1 заявок. Если в системе уже находились две
другие заявки, то в источнике перед поступлением
заявки были N 2 заявки и так далее.
Из формулы (6) в этом случае следует
Fсист ( t )  1







так что с учетом табличного интеграла [8]

a x
n
 x e dx 
0

0


m p ожид   1   1 m l
.

1

1

p0
 Nk

Nk
N 1
Nk k0
k1  k1  t
pk  t e dt 
k! 0
k1 k1! p0 N1
k k
pk k 2 
 Nkk1N  
k0
k!

 Nk
 
k  1 k  1
 k  1N  
N 1
k 0
1 N
k
 k pk  ;
A 0
A
2
 сист
  t 2 fсист t  dt  t сист 

2
0

1
N 1
Nk
k 0

Nk
 1 Fсист t   
N
N1
N2
p0 B0t 
p1 B0t B1t 
p2 B0t B1t B2t   
N
N

 Nk
N1
Nk k0
Коэффициент корреляции числа заявок в очереди и под
обслуживанием находится обычным образом из соотK
ношения rml  ml .
m l
Найдем функцию распределения общего времени нахождения одного требования в системе. Согласно общей схеме [4],
N1 Nk
k
1
pk  Bj t 
 pN1 B0 t B1 t    BN1t  
k0
j0
N
N
j
N1 Nk
k  t 
N1 Nk
 e t 
pk 
 e t 
pk ek  t .
k0
j0
k0
N
j!
N
n!
a n 1
имеем

  2 1 m  l 

k
tсист   t fсистtdt 
m p ожид   1   1 m l

N1
 t  ,

e  t  N  k pk
k 0
k!
Nk
fсист t  
1 p 0  p 1   1   1 m l
 l2 
 2 1 m l 


 N  k  p k e k  t  ,
N  k k 0
N1
откуда

Последнее выражение можно значительно упростить следующим образом. Заметим, что в силу очевидного соотношения  N   l   1  m второе слагаемое числителя можно переписать еще и как
 N   l 1 m , откуда следует
e  t

 N  k 
2
k  2!  t сист
1 N1
 k 1
pk

 N  k 
k 3
k
0

k!

Nk
p0

 Nk
2

2
 k 1  k 2  t
p k  t e dt  t сист 
k!
0

k  k
 N  k k  2k  1N   t сист 
N 1
2
k 0
N 1
2
p0
k  1 k  1
 k  2k  1N   t сист 
k

0
  Nk


p0 N
k  k
 k  1k N  
 A k 0
N
2
1 N 2

  k p k   k p k   t сист 
k 0

 A  k 0

(6)
2
t сист

Здесь, как и выше, N  k N – вероятность того, что за
время t в источнике в среднем находилось N k заявок (тогда в очереди или под обслуживанием – в среднем k заявок). Весовые коэффициенты N k  N в
правой части формулы (6) относятся к соответствующим вероятностям каждого из состояний системы в
целом. Например, если поступившая в систему заявка
застала ее свободной от других заявок, то в источнике
непосредственно перед поступлением заявки находи192

2
1 N 2
1 
l 2
  k p k  k   t сист 
N  1 k    t сист .

 A 
 
 A  k 0
Последнее равенство записано здесь в таком виде в
силу соотношений (5).
В заключение найдем функцию распределения времени ожидания обслуживания заявкой, находящейся в очереди. Имеем
2
Nk
 1 Fожид t  
N

N 1
N2
p1 B 0 t  
p 2 B 0 t   B 1 t 
N
N
N3

p 3 B 0 t   B 1 t   B 2 t   
N

2

N1 N  k
N k k 1  t 
pk 
 e  t 
pk ek1  t  ,
k 1
j0
k 1
N
j!
N
j

 e t 
Fожид ( t )  1
так что
fожид t  
e
 N  k  p k e k 1  t  ,
k 1
k 1
1
0
Nk
k 1
tожид   t fожидt dt 
Nk

k
k 1!
pk  t k e t dt 
N 1
 N k
k 1
   k 11N

k  1

k 1
2
 сист

2
0

1
N 1
Nk
k 1


 N  k 
1
N1
N k
k 1
p0

 Nk
2


2
k
p k  t k  1 e  t dt  t ожид 
k  1! 0
 N  k 


k  1! 2
k
p k k  2  t ожид 
k  1! 
k  k
 N  k k  1 k N   t ожид 
N 1
2
k 1
p0
  Nk

k  1 k  1
 k  1k N   t ожид 
N 1
1.
l  m p ожид  2
2
1 

N  2 l 
  t сист .
2

 A 


Кирпичников А.П., Титовцев А.С. Открытая одноканальная система массового обслуживания с отказами и
неограниченной очередью // Вестник Казанского государственного технологического университета – Казань:
Изд-во Казан. гос. технол. ун-та, 2006 - № 4 - C. 78 – 85.
2. Валеев И.Н., Кирпичников А.П. Многоканальные системы массового обслуживания с отказами // Вестник
Казанского государственного технологического университета – Казань: Изд-во Казан. гос. технол. ун-та,
2006 - № 4 - С. 66-71.
3. Гильмутдинов Р.Ф., Кирпичников А.П. Замкнутые
модели систем массового обслуживания с ограничениями // Вестник Казанского государственного технологического университета – Казань: Изд-во Казан. гос.
технол. ун-та, 2006 - № 4 - С. 220-224.
4. Кирпичников А.П. Прикладная теория массового обслуживания. - Казань: Изд-во КГУ, 2008, 112 с.
2
k 1
p0 N
k  k
 k k 1N  
 A k 1
N
2
2
1 N 2
t ожид 
  k p k   k p k   t ожид 


k
0
k
0


A


 2
  t ожид ;


Характеристики очередей не являются решающими для большинства типов замкнутых СМО.
Тем более это относится к характеристикам реальных очередей, поэтому в данной работе их расчет
опущен. При необходимости все эти характеристики
можно сравнительно несложным образом восстановить по алгоритму, указанному в книге [4]. Подчеркнём также, что в данном случае ключевой величиной, через которую можно в наиболее компактном и удобном для приложений виде выразить любую из характеристик СМО этого типа, является не
вероятность ожидания (в совокупности с вероятностью отказа для СМО с отказами), как для открытых
систем, а среднее число заявок, находящихся под
обслуживанием.
Литература
1 N
l
  k 1pk  ;
A k 1
A
2
 ожид
  t 2 fожид t  dt  t ожид 

l  m p ожид
1 
Nl 

A 

0
 
p0
1 
l 2
2
N  1 k    t ожид   ожид ,
 A 
 
2
 ожид


p N1
k!
k

pk k 1  0  NkkNk k 
 Nk
k 1!   Nk k1
Nk k1
N1
2
имеем
В этом случае
N1
2
m
 2
A
как и следовало ожидать. Заметим, что последние
два соотношения можно также записать с использованием вероятности ожидания p ожид . В этом случае
N1
 t  .

e  t  N  k p k
k

1
k  1!
Nk

2
1 
l  2m 2ml l
N  1 k    2  2  2 
 A 
  A
A
A

N1
Nk

1 
l  2mk 2
1 
l  2k 2
N1 k    2  tожид N1 k     tожид
A 
 A
A 
 A
откуда
 t
2
1 
l k
m

N  1 k    2  2 
A
 A 
  A

N1 Nk
1
pk  Bj t 
 pN1 B0 t B1 t    BN2 t  
k 1
j0
N
N
N1

2
обсл
l  m l
1 

N  1 k   
 A 
 
A2
k 1
1
2
сист
2
1 N 2
1 
l 2
  k pk  k   t ожид 
N1 k    t ожид .

 A  k 0
 A 
 
Для проверки
193
5.
Кирпичников А.П., Титовцев А.С. Системы обслуживания с неоднородным входным потоком требований, отказами и очередью // Вестник Казанского государственного
технологического университета – Казань: Изд-во Казан.
гос. технол. ун-та, 2011 - Т. 14 - № 5 - C. 154 – 161.
6. Кирпичников, А.П. Открытые системы дифференцированного обслуживания поликомпонентных потоков./ А.П.
Кирпичников, А.С. Титовцев // Вестник Казанского госу-
дарственного технологического университета – Казань:
Изд-во Казан. гос. технол. ун-та, 2012. – № 1. – C. 148 –
152.
7. Сачков В.Н. Комбинаторные методы дискретной математики – М.: Наука, 1977, 384 с.
8. Двайт Г.Б. Таблицы интегралов и другие математические формулы / – М.: Наука, 1983.
________________________________________© Р. Ф. Гильмутдинов - ст. препод. каф. интеллектуальных систем и управления информационными ресурсами КНИТУ,
ruslan.gilmutdinov@rambler.ru; А. П. Кирпичников - д-р физ.-мат. наук, проф., зав. каф. интеллектуальных систем и управления информационными ресурсами КНИТУ, kirpichnikov@kstu.ru.
194
Документ
Категория
Без категории
Просмотров
5
Размер файла
338 Кб
Теги
замкнутого, массового, одноканальной, обслуживание, система, математические, модель
1/--страниц
Пожаловаться на содержимое документа