Порядок построения полумарковской модели однолинейной системы обслуживания GI/G/1/0. Нахождения явного вида функции распределения времени пребывания заявки в системе с учетом возможных ее повторных обслуживаний и среднее значение этого времени.
Аннотация к работе
ПОЛУМАРКОВСКАЯ МОДЕЛЬ ОДНОЛИНЕЙНОЙ СИСТЕМЫ ОБСЛУЖИВАНИЯ С ПОТЕРЯМИ И ДИАГНОСТИКОЙ КАЧЕСТВА ОБСЛУЖИВАНИЯ В МОМЕНТ ПОСТУПЛЕНИЯ СЛЕДУЮЩЕЙ ЗАЯВКИ Построена полумарковская модель однолинейной системы обслуживания GI /G/1/0 , в которой осуществляется контроль качества обслуживания требования.В данной работе рассматривается СМО GI /G/1/0 , в которой после проведенного обслуживания заявки, в момент поступления следующей, проводится контроль качества обслуживания предыдущей заявки. После завершения обслуживания заявки в момент поступления следующей заявки начинается диагностика качества проведенного обслуживания. После окончания повторного обслуживания в момент поступления следующей заявки в систему проводится диагностика качества повторного обслуживания.
Введение
Различные аспекты теории систем массового обслуживания (СМО) с потерями освещены во многих монографиях и научных статьях. Обзор основных результатов по этой тематике можно найти, например, в работах [1-4]. Наиболее полные результаты для СМО с потерями получены в предположении показательного распределения длительности интервалов между моментами поступлениями заявок и времени их обслуживания. Если же входящий в систему поток заявок образует процесс восстановления, а распределение времени обслуживания заявок имеет общий вид, то при определении в явном виде характеристик системы возникают существенные трудности. Для их преодоления в работах [5-7] используется аппарат полумарковских процессов с общим фазовым пространством состояний. Так, в [6] найдены стационарные характеристики однолинейной системы
GI /G/1/0 , а в [7] — для этой же системы с абсолютным приоритетом
В данной работе рассматривается СМО GI /G/1/0 , в которой после проведенного обслуживания заявки, в момент поступления следующей, проводится контроль качества обслуживания предыдущей заявки. В случае неудовлетворительного качества обслуживания заявка отправляется на повторное обслуживание. Так продолжается до тех пор, пока обслуживание не будет признано удовлетворительным.
Цель статьи — найти функцию распределения длительности времени пребывания в системе принятой к обслуживанию заявки с учетом возможных ее повторных обслуживаний и среднюю продолжительность этого времени.
Постановка задачи. Рассмотрим СМО GI /G/1/0 с потерями. Время обслуживания заявки — случайная величина (СВ) a с абсолютно непрерывной функцией распределения (ФР) F(t) = P a ? t и
}
{ плотностью f (t) . Время между поступлениями заявок в систему — СВ b с абсолютно непрерывной ФР G(t) = P{b ? t} и плотностью g(t). Если прибор занят обслуживанием, то поступающие в систему заявки теряются. После завершения обслуживания заявки в момент поступления следующей заявки начинается диагностика качества проведенного обслуживания. С вероятностью p обслуживание признается успешным и начинается обслуживание поступившей последней заявки. С вероятностью q =1 p обслуживание заявки признается неудовлетворительным и сразу же начинается ее повторное обслуживание. При этом вновь поступившая в систему заявка теряется. После окончания повторного обслуживания в момент поступления следующей заявки в систему проводится диагностика качества повторного обслуживания. В результате диагностики либо с вероятностью p обслуживание признается успешным, либо с вероятностью q начинается повторное обслуживание заявки и т.д. Время проведения диагностики качества обслуживания заявки — СВ s с абсолютно непрерывной ФР Y(t) = P{s ? t} и плотностью y(t) , а время проведения повторно обслуживания заявки — СВ g с абсолютно непрерывной ФР F(t) = P{g ? t} и плотностью j(t) .
Требуется найти ФР времени t21 пребывания в системе принятой к обслуживанию заявки (с учетом возможных ее повторных обслуживаний) и математическое ожидание этой СВ.
Построение полумарковской модели функционирования системы. Для построения математической модели системы обслуживания используем аппарат полумарковских процессов с дискретно-непрерывным множеством фазовых состояний [5, 6]. Опишем функционирование системы полумарковским процессом ПМП x(t) с фазовым пространством состояний
Вісник СЕВНТУ: зб. наук. пр. Вип. 125/2012. Серія: Автоматизація процесів та управління. — Севастополь, 2012.
56 АВТОМАТИЗАЦІЯ ПРОЦЕСІВ ТА УПРАВЛІННЯ
E = 21, 23,10x,11x,12x, 22x, 21x,23x, 00x}.
{
Расшифруем коды состояния системы: 21 — поступившая в систему заявка начала обслуживаться впервые;
10x — обслуживание заявки закончено, до начала контроля качества ее обслуживания и поступления в систему следующей заявки осталось время x ;
11x — обслуживание заявки признано удовлетворительным; начинается обслуживание заявки, поступившей в момент начала контроля качества; до поступления следующей заявки осталось время x ;
12x — начинается повторное обслуживание заявки; до поступления следующей заявки осталось время x ;
21x — поступившая в систему заявка потеряна; до конца первичного обслуживания заявки осталось время x ;
22x — поступившая в систему заявка потеряна; до конца повторного обслуживания заявки осталось время x ;
23 — в систему поступила заявка и начинается диагностика качества обслуживания предыдущей, поступившая заявка ожидает окончания диагностики качества;
23x — пришедшая в систему заявка потеряна, до конца диагностики качества обслуживания осталось время x ;
00x — завершился контроль качества обслуживания заявки, обслуживание признано успешным, до поступления в систему следующей заявки осталось время x .
Временная диаграмма функционирования системы изображена на рисунке 1, а граф переходов системы — на рисунке 2. a a g g a t s s s s b b b b b b b b b
Рисунок 1 — Временная диаграмма функционирования системы
00x
23х
11х 12х
23
21х 22х
21 10х
Рисунок 2 — Граф переходов системы
Времена пребывания системы в состояниях определяются формулами: q21 = AUB, q10x = x, q11x = AU x, q12x = g U x, q21x = q22x = q23x =BU x, q23 =BUS , q00x = 0, где U — знак минимума. Полумарковское ядро Q(t,x,B) дифференциальной форме имеет вид:
[5] процесса марковского восстановления {xn, qn; n ? 0} в
Вісник СЕВНТУ: зб. наук. пр. Вип. 125/2012. Серія: Автоматизація процесів та управління. — Севастополь, 2012.
АВТОМАТИЗАЦІЯ ПРОЦЕСІВ ТА УПРАВЛІННЯ 57
t t
Q(t,21,21dy) = og(s) f (y s)dsdy, y > 0; Q(t,21,10dy) = o f (s)g(y s)dsdy, y > 0; 0 0 t t
Q(t,23,12dy) = qoy(s)g(y s)dsdy, y > 0; Q(t,23,00dy) = poy(s)g(y s)dsdy, y > 0; 0 0
Q(t,11x,10dy) = f (x y)1x(t)dy, y > 0; Q(t,11x,10dy) = f (x y)1x y(t)dy, 0 < y < x; Q(t,00x,11x) =1(t); Q(t,10x,23) =1x(t).
Представим множество всех состояний системы в виде двух непересекающихся подмножеств E и E : E = E ?E , E ={21, 23,10x,11x,12x, 22x, 21x,23x , E = {00x}
}
.
Пребывание системы в подмножестве E при условии, что при t = 0 система находилась в состоянии 21, равно времени пребывания в системе принятой к обслуживанию заявки (с учетом возможных повторных обслуживаний). Найдем распределения времени пребывания ПМП x(t) в подмножестве состояний E .
Пусть t21, t21x, t22x, t12x , t23, t11x, t10x, t23x — времена пребывания x(t) в E с начальным состоянием 21, 21x, 22x,12x ,23,11x,10x, 23x соответственно, а F21(t), F21x(t), F22x(t), F12x(t) , F23(t), F11x(t), F10x(t), F23x(t) — их функции распределения.
Запишем систему уравнений марковского восстановления [5] для функций
F21(t) =1 F21(t), F21x(t) =1 F21x(t), F22x(t) =1 F22x(t), F12x(t) =1 F12x(t) , F23(t) =1 F23(t), F11x(t) =1 F11x(t), F10x(t) =1 F10x(t), F23x(t) =1 F23x(t) с учетом того, что F21x(t) = F22x(t) = = F11x(t) = F12x(t) = F23x(t) = F10x(t) =1 при 0 ? t < x, и F10x(t) = F23(t x) при t ? x: t s t
?
? F21(t) = o f (s)dsog(s y)F21y(t s y)dy og(s)F(s)F23(t s)ds ? 0 F(t) G(t) F(t)G(t), t ? 0, 0
?
0
?
? x t
? F21x(t) = G(t) og(x y)F21y(t x y)dy og(s)F23(t s)ds, t ? x, ? 0 x
? x t
?
?
F22x(t) = G(t) og(x y)F22y(t x y)dy og(s)F23(t s)ds, t ? x, ? 0x x t x
?
? F23x(t) = QG(t) og(x y)F23y(t x y)dy q og(x y)F12y(t x)dy, t ? x, (1) 0 0
? F23(t) = oy(s)dsog(s y)F23y(t s y)dy qog(s)dsoy(s y)F12y(t s y)dy
?
0
? 0 Y(t) QY(t)G(t), t ? 0, 0 0
? t x
? F11x(t) = F(t) F(x)F23(t x) o f (x y)F12y(t x)dy, t ? x. 0
?
?
Вісник СЕВНТУ: зб. наук. пр. Вип. 125/2012. Серія: Автоматизація процесів та управління. — Севастополь, 2012.
58 АВТОМАТИЗАЦІЯ ПРОЦЕСІВ ТА УПРАВЛІННЯ
Методом последовательных приближений исключаем из второго, третьего и четвертого уравнений системы функции F21x(t) , F22x(t) и F23x(t). При этом получаем: t
F21x(t) = F22x(t) =Vg (x,t x) OF23(t s)vg(x,s x)ds, x
F23x(t) = QVG (x,t где t x x) OF12y(t x)vg(x, y)dy, 0 x
Здесь Vg (x,t) — ФР прямого остаточного времени, а hg (t) = ag (n)(t) — плотность функции n=1
? восстановления Hg(t) процесса восстановления, порожденного СВ b. С учетом найденных выражений для функций F22x(t) и F23x(t) пятое и шестое уравнения системы принимают вид
? s)ds = oky(x)dx , t ky(x) — плотность распределения СВ — длительности времени между началом диагностики качества обслуживания заявки и моментом первого поступления в систему заявки после проведения контроля качества обслуживания (рисунок 3). a(g)
s t x b b b b
23 21y(22y) t
Рисунок 3 — Временная диаграмма функционирования системы между состояниями 23 и 21y(22y)
Из системы уравнений (2) исключаем функцию F12x(t) и получаем относительно функции
Вісник СЕВНТУ: зб. наук. пр. Вип. 125/2012. Серія: Автоматизація процесів та управління. — Севастополь, 2012.
АВТОМАТИЗАЦІЯ ПРОЦЕСІВ ТА УПРАВЛІННЯ 59
? в котором Ky,j(t) = oky,j(x)dx, t x
? o ky,j(x) = y(s)?vg (s,x s)F(x 0 ?
?
x s z s) o j(z)dzovg (s, y)vg (z 0 0
y,x s z)dy?ds ?
?
?
— плотность СВ — длительности времени между двумя соседними моментами начала контроля качества обслуживания при условии, что после первого контроля обслуживание признано некачественным и заявка была направлена на повторное обслуживание (рисунок 4). g t s x b b b
23 23 t
Рисунок 4 — Временная диаграмма функционирования системы между соседними состояниями 23 t
Отметим, что распределение вероятностей QKY,j (t) = qoky,j (x)dx является несобственным. 0
Общая теория процессов восстановления с несобственным распределением содержится, например, в [8]. Решение уравнения (3) находится методом последовательных приближений и имеет вид t
где h(q) (t) = aqnk (n)(t) — плотность функции восстановления Hy,j(t) процесса восстановления, n=1
? y,j y,j
(q) порожденного СВ с несобственной плотностью распределения вероятностей qky,j(t) . Используя свойства этой функции восстановления, функцию F23(t) можно представить в виде t
(q)
F23(t) = q PY(t) POY(t s)hy,j(s)ds. 0
Таким образом, ФР времени пребывания заявки в системе с момента ее первого повторного обслуживания определяется формулой t
F23(t) = PY(t) POY(t s)hy,j(s)ds. 0
(q)
?
Для того, чтобы найти среднее значение Mt23 этого времени, вычислим интеграл OF23(t)dt . 0
Учитывая, что ohy,j(t)dt = q [8], получаем 0
?
(q) p
? ? ? ?
? ?
? ?
? ?
( ) ? l q q
Mt23 = OF23(t)dt = Ms OKY,j (t)dt = Ms Mb?oy(t)Hg (t)dt oj(t)Hg y (t)dt? . 0 0 0 0 p p
Вісник СЕВНТУ: зб. наук. пр. Вип. 125/2012. Серія: Автоматизація процесів та управління. — Севастополь, 2012.
60 АВТОМАТИЗАЦІЯ ПРОЦЕСІВ ТА УПРАВЛІННЯ
Здесь Hg (t) =1 Hg (t), H(ly )(t) — функция восстановления процесса восстановления, порожденного случайными величинами с плотностью распределения ly(t) и b: ? g ly(t) = oy(s)vg (s,t)ds, Ly(t) = oly(s)ds, Hgy )(t) = Ly(t) OLY(t s)hg(s)ds. 0 0 0
(l
? t t
Отметим, что ly(t) — плотность распределения вероятностей СВ, равной величине первого перескока времени контроля качества последовательностью заявок (или величине времени между окончанием контроля качества обслуживания и моментом поступления следующей заявки в систему);
? oy(t)Hg (t)dt — среднее число потерянных заявок за время контроля качества обслуживания одной 0 заявки; oj(t)H(ly )(t)dt — среднее число потерянных заявок за время одного повторного 0
? g обслуживания заявки.
Зная вид функций F23(t) и F21x(t) , нетрудно найти выражение для функции F21(t) из первого уравнения системы (1). Получаем t F21(t) = K f (t) okf (t
0
t y)F23(y)dy =1 pokf (t y)Y(y)dy 0 t y pokf (t y)dyohy,j(y s)Y(s)ds, 0 0
(q)
? x где K f (t) = okf (x)dx, kf (x) = o f (s)vg(s,x s)ds — плотность распределения длительности времени t 0 между началом первичного обслуживания заявки и началом контроля качества проведенного обслуживания (рисунок 5).
a x s t b b b b
21 23 t
Рисунок 5 — Временная диаграмма функционирования системы между состояниями 21 и 23
Следовательно, ФР длительности времени пребывания в системе принятой к обслуживанию заявки с учетом возможных ее повторных обслуживаний определяется выражением t F21(t) = pokf (t
0
t y)Y(y)dy pokf (t
0 y y)dyohy,j(y s)Y(s)ds , 0
(q) а среднее значение времени пребывания заявки в системе находится с помощью формулы
? ? ? ?
? ?
? ?
? ?
( ) ? ? p q l
Mt21 = OF21(t)dt = Ms Mbo f (t)Hg (t)dt Mb?oy(t)Hg (t)dt oj(t)Hgy (t)dt? . (4) 0 0 0 0
?
Отметим, что o f (t)Hg(t)dt — среднее число заявок, потерянных за время первичного 0 обслуживания принятой заявки.
Вісник СЕВНТУ: зб. наук. пр. Вип. 125/2012. Серія: Автоматизація процесів та управління. — Севастополь, 2012.
АВТОМАТИЗАЦІЯ ПРОЦЕСІВ ТА УПРАВЛІННЯ 61
Выпишем формулы для определения среднего времени полного обслуживания заявки с учетом возможных повторных обслуживаний для СМО с конкретными функциями распределения времен между поступлениями заявок и их обслуживания.
В случае СМО M /M /1/0 с плотностями распределений f (t) = le lt, g(t) = me mt , y(t) = he ht, j(t) = ne nt, t ? 0, формула (4) преобразуется к виду
Mt21 = l p ?m h? p n .
? ?
? ?
1 1 1 1 1 q
В случае СМО M /G/1/0 входящий поток заявок в систему является простейшим, т.е. f (t) = le lt , а СВ a, g, s имеют ФР общего вида. Теперь имеем
Mt = Ma 1 ? 1 Ms? q Mg .
? ?
21 m p p
? ?
Для сиtrial GI /M /1/0 входящий поток является рекуррентным, порожденным СВ с плотностью распределения g(t) общего вида, а остальные СВ имеют показательное распределение: f (t) = le lt , y(t) = he ht, j(t) = ne nt, t ? 0 . В этом случае имеем: ? ? ? ?
Здесь символом g(z) обозначено преобразование Лапласа соответствующей функции g(t): ?
~ g(z) = og(t)e ztdt . Среднее время полного обслуживания заявки в данной системе определяется 0 выражением
1 Mb q Mb ? h g(n) g(h)? 21 h 1 g(l) p 1 g(h)? h n 1 g(n) ?
? ?
? ?
~ ~
~ ~ ~
Mt = 1 .
Заключение. С помощью аппарата полумарковских процессов с общим фазовым пространством состояний найдена функция распределения времени пребывания принятой к обслуживанию заявки в СМО GI /G/1/0 с учетом возможных ее повторных обслуживаний в случае не прохождения ею контроля качества. Найдено среднее значение этого времени. Дальнейшие исследования могут быть связаны с построением моделей контроля качества обслуживания более общих СМО и различными стратегиями контроля.
Библиографический список использованной литературы
1. Риордан Дж. Вероятностные системы обслуживания / Дж. Риордан. — М.: Связь,1966. — 184 с. 2 Гнеденко Б.В. Введение в теорию массового обслуживания / Б.В. Гнеденко, И.Н. Коваленко. — М.: Наука, 1987. — 336 с.
3. Анисимов В.В. Элементы теории массового обслуживания и асимптотического анализа систем / В.В. Анисимов, О.К. Закусило, В.С. Донченко. — К.: Вища шк., 1987. — 248 с.
4. Handbuch der Bedienungsteorie II / Formeen und andere Ergebnisse / B.W. Gnedenko, D. Konig (Red.). — Berlin: Verlag, 1984. — 607 s.
5. Королюк В.С. Процессы марковского восстановления в задачах надежности систем / В.С. Королюк, А.Ф. Турбин. — К.: Наук. думка, 1982. — 236 с.
6. Полумарковские модели восстанавливаемых систем и систем массового обслуживания / А.Н. Корлат, В.Н. Кузнецов, М.И. Новиков, А.Ф. Турбин. — Кишинев: Штиинца, 1991. — 209 с.
Вісник СЕВНТУ: зб. наук. пр. Вип. 125/2012. Серія: Автоматизація процесів та управління. — Севастополь, 2012.
62 АВТОМАТИЗАЦІЯ ПРОЦЕСІВ ТА УПРАВЛІННЯ
7. Обжерин Ю.Е. Об однолинейной системе обслуживания с потерями и абсолютным приоритетом / Ю.Е. Обжерин, А.И. Песчанский // Автоматика и телемеханика. — 1990. — № 10. — С. 107-115.
8. Феллер В. Введение в теорию вероятностей и ее приложения. [В 2-х т.]. Т. 2 / В. Феллер. — М.: Мир, 1984. — 738 с.
Поступила в редакцию 24.12.2010 г.
Песчанський О.І. Напівмарківська модель однолінійної системи обслуговування з втратами і діагностикою якості обслуговування в момент надходження наступної заявки
Побудована напівмарківська модель однолінійної системи обслуговування з втратами, в якій здійснюється контроль якості обслуговування вимоги. Знайдено явний вигляд функції розподілу часу перебування заявки в системі з урахуванням можливих її повторних обслуговувань і середнє значення цього часу.
Ключові слова: напівмарківський процес, однолінійна система обслуговування, контроль якості обслуговування, рівняння марківського відновлення.
Peschansky O.I. The Semi-Markovian Model of a Single-server System with Losses and Service Quality Diagnostics at the Moment of Next Request Income
Semi-Markovian model of a single-server system with losses and request service quality control execution is developed. An explicit form of distribution function of request dwelling time in the system is defined with regard to the possibility of its reservicing. The mean duration of the dwelling time is defined as well.