Необычная задача по Системе Массового Обслуживания.

[ILuha]

Уважаемые участники форума, помогите ,пожалуйста, разобраться с задачей!

Несложная , как мне кажется, задача на системы массового обслуживания. Стандартные методы и ходы решения не проходят,но возможно, я просто не до конца что-то понимаю. Изложу задачу и подробно ход моего личного незаконченного решения. Вопрос сформулирован в конце.

Источник - (Свешников гл 39, задача 23*)
В мастерскую ,где сидят 2 сапожника поступает поток заявок с интенсивностью L,
среднее время обслуживание клиента mu. Найти вероятность того, что клиента обслужат не более , чем через время T.

Ход решения.

Система - это двухканальная СМО с неограниченной очередью (так как про нее в условиях не сказано, то разумно полагать ,что она есть). Для решения нужн знать распределение tобсл времени обслуживания,чтобы найти P( tобсл < T).
Полагаем, что время обслуживания сапожником клиента распределено как Э(mu).
Но время обслуживания tобсл клиента системой будет отличатся от этого времени, так как есть очередь.
Обозначим состояния системы:
(0)-(1)-(2)-(3)-...-(n)-...

(0) - очредь пуста, два мастера свободны
(1) - очредь пуста, один мастер свободен
(2)- дина очереди = 0, мастера заняты
(3)- дина очереди = 1, мастера заняты
(4)- дина очереди = 2, мастера заняты
...

Время обслуживания tобсл - это случайная величина, которая будет зависеть от длины очереди и занятости системы. Обозначим время работы мастера как tm (это случайная величина). Будем обозначать за tm1, tm2, tm3,..... - случайные величины, распределенные так же ,как время работы мастера.

Действительно, рассмотрим возможные варианты:

1) система в состоянии (0) , tобсл = tm1
2) система в состоянии (1) , tобсл = tm1
3) система в состоянии (2) , tобсл = tm1 + tm2. То есть ждем, пока любой из мастеров освоюодтся, а потом обслуживаемся сами
4) система в состоянии (3) , tобсл = tm1 + tm2+tm3. Ждем, пока обслужат клиента перед нами, а потом обслуживаемся сами
....
5) система в состоянии (n) , tобсл = tm1 + tm2+tm3 + ...+ tmn. Ждем, пока обслужат клиентов перед нами, а потом обслуживаемся сами

Итак, вопрос, как получить закон распределения для tосбл?
Учитывать здесь надо такие факты:
-Время обслуживания зависит от длины очереди
-Очередь бесконечна
-Как учесть тот факт, что есть состояния (0) (1) с одинаковым временем обслуживания.

Буду благодарен за любые советы по решению.

[antbez]

Что разве Пуассон тут не подойдёт- простейший поток?

[ILuha]

Распределение Пуассона для простейшего потока проявляется в распределении по количеству событий, то есть вероятность P( X(t,dt) = k ) в пределе стремится к Пуассону. Где X(t,dt) - это количество событий, произощедших на интервале (t , t+dt). Поток в задаче дейстивительно простейший, то есть время обслуживания мастером клиента распределено как Э(mu). Но полное время обслуживания складывается из этого времени и еще времен на ожидание.

[eprst]

Цитата:

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

Загадочное утверждение. В системе,как правило, интересны предельные состояния.
Посмотрите Клейнрока. Кажется вы пытаетесь заново вывести марковскую цепь.

[ILuha]

Спасибо за книжку, он классная,многое стал осознавать, но ответа как решать задачу там не нашел.

В первом сообщении вопросы, действительно были глупые
(-Время обслуживания зависит от длины очереди
-Очередь бесконечна )

Пробую другой подход к задачке, найдите ошибку, неточность.

Итак.

Полагаем, что время обслуживания сапожником клиента распределено как Э(mu). Так как в вопросе не фигурирует время от начала работы системы, то полагаем, что режим работы стационарный.

Нужно получить распределение времени tобсл, оно складывается из времени ожидания в очереди tоч и времени работы мастера tм
tобсл = tоч + tм
Идея такова - рассмотреть две задачи для двух разных систем.

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

Вторая задача - система знает об очереди, но не знает о внутреннем устройстве, то есть это черный ящик, куда поступают заказы.

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

Попробуем разобраться с первой.
1)находим вероятности стационарного режима.
2)Строим гипотезы -
-мастера свободны
-один мастер занят
-два заняты
3)потом считаем условные вероятности, то есть вероятности быть обслуженным за время не больше T при условии различных гипотез, причем когда два мастера заняты, то полагаем условную вероятность нулевой, тк заказ все равно не обслужат и он исчезнет из системы
по условию
4)по формуле полной вероятности определяем вероятность быть обслуженным за время не больше Т. Вероятности самих гипотез берем из стационарного режима. Иными словами возникает функция распределения, а значит и плотность для величины tм.

Вот тут возник вопрос - получается ненормированная плотность. Почему?

Буду благодарен за любые советы по решению.

[PAV]

Если я правильно понял, то Вы имеете в виду, что если клиент пришел и оба мастера заняты, то он разворачивается и уходит. Таким образом, есть ненулевая вероятность того, что заказ вообще не обсуживается (можно считать, что время обслуживания бесконечно). Поэтому и получается ненормированная плотность.

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

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

Добавлено спустя 49 минут:

Смотрите, как можно решать эту и подобные задачи.

Делим всю числовую ось на малые промежутки $\Delta t$. Будем считать, пренебрегая бесконечно малыми более высокого порядка, чем линейные, что за один такой промежуток может произойти не более одного события (событием называем освобождение одного клиента или наоборот приход клиента), а также что вероятности этих событий пропорциональны $\Delta t$, коэффициенты пропорциональности - интенсивности соответствующих потоков.

Пусть $p_0, p_1,\ldots$ - это распределение вероятностей на состояниях системы в начале очередного промежутка. При стационарном режиме в начале следующего промежутка мы должны получить те же самые вероятности. С помощью формул полной вероятности можно получить систему уравнений. Собственно, переход от состояния $i$ в состояние $i+1$ означает приход нового клиента, обратный переход - окончание обслуживания клиента одним из мастеров, сохранение старого состояния - ничего не произошло. Выпишите аккуратно эту систему и постарайтесь найти из нее значения этих вероятностей. После этого задача уже решится довольно просто.

[ILuha]

Кажется, что Ваши рассуждения приведут к уравнению Колмогорова-Чепмана.С нахождением стационарных вероятностей проблем не возникает. Так как система - это система гибели-размножения, для нее есть подсчитанный результат.(который кстати и получается из Колмогорова-Чепмана).

Некоторое замечание по задаче - про деление всей задачи на две (см выше). По поводу первой задачи - время обслуживание клиента будет распределено как Э(mu) в независимости от того, сколько мастеров занято. Поэтому первая задача отпадает.

Задачу можно решить без деления на две, а сразу искать время обслуживания.

Подход применяем аналогичный, уже высказанный в моих предыдущих постах

В системе есть очередь

s(0), s(1), .. ,s(n)

s(0)-очередь пуста
s(1)-в очереди один человек
...
s(n)-в очереди n человек

Переход системы из i в i+1 с интенсивностью L, обратно 2mu

Алгоритм таков:

1)находим вероятности стационарного режима.
2)Зададимся вопросом - мы встаем за человеком,который в очереди под номером n, сколько времени потребуется на то,чтобы подождать, пока нас обслужат.
Строим гипотезы - встали без очереди, встали после первого, после второго итд.
H0,H1,H2, ...
3)потом считаем условные вероятности, то есть вероятности быть обслуженным за время не больше T при условии того что в очереди стоим после человека под номером n.
p ( tобсл < T | Hn )
Когда очередь пустует,нас обслуживают, время распределено как Э(mu)
Когда ждем одного, то нас обслужат за время обслуживания первого и наше время обслуживания, в итоге возникает вопрос о суммарном распределении двух величин Э(mu), который легко решается, тк экспоненциальное - частный случай гамма - распределния

Э(mu) = Г(1,mu) Г(1,mu)+Г(1,mu) = Г(2,mu)

итд.
гипотез бесконечное счетное число.
4)по формуле полной вероятности определяем вероятность быть обслуженным за время не больше Т. Вероятности самих гипотез берем из стационарного режима.

p( tобсл < T ) = p (H1) * p ( tобсл < T | H1 ) + ... + p (Hn) * p ( tобсл < T | Hn ) + ...

Получается ряд, который благополучно суммируется по всем гипотезам, кол-во которых счетное.

5) p( tобсл < T ) - это функция распределения для tобсл. Получили плотность для величины tобсл.

(L/2 -- mu)*exp{ (L/2 -- mu)*t }

Условие для существование этой плотности L < 2*mu совпадает с условием на существование
стационарного режима в задаче. Что мне подсказывает что задача решена).

У кого какие добавления - дополнения?

Добавлено спустя 11 минут 31 секунду:

опечатался в посте : p( tобсл < T ) = p (H0) * p ( tобсл < T | H0 ) + p (H1) * p ( tобсл < T | H1 ) ... + p (Hn) * p ( tобсл < T | Hn ) + ...

[PAV]

Все выглядит правильно. Уточнение по поводу расчета времени обслуживания (я не говорю, что у Вас неправильно, просто уточните). Если система в состояниях 0 или 1, то нас сразу обслуживают, тут ясно. Пусть очередь пуста, но оба мастера заняты. Тогда мы ждем того, кто первым освободится, причем в силу свойства отсутствия последействия неважно, когда мастера начали обслуживать этих клиентов (хотя это некоторая условность модели, в жизни распределение должно быть не таким). Но тут будет минимум из двух времен, можно показать, что это будет Э(2*mu)

Если в очереди перед нами стоял один человек, то сначала он будет ждать время Э(2*mu), а потом мы еще один раз столько. Ну и так далее.