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

Одноканальные системы массового облуживания с неограниченной очередью

Пусть на одноканальную СМО поступает простейший поток заявок с интенсивностью λ, а время обслуживания - показательное с интенсивностью μ. Пусть теперь заявки в случае, если канал обслуживания занят, не получают отказ, а становится в очередь, причем длина очереди неограничена. Считая процесс обслуживания марковским процессом, сформируем состояния системы следующим образом: s₀ – СМО свободна; s₁ – канал занят, очереди нет; s₂ – канал занят, одна заявка стоит в очереди; … ; s_k – канал занят, (k-1) заявок стоит в очереди; … Граф состояний системы представлен на рис. 6.9.1.

 

… …

Рис. 6.9.1

Система уравнений для предельных вероятностей состояний полученная из соответствующих уравнений Колмогорова, имеет вид :

λp₀  = μp₁; (λ + m)×p₁ = lp₀ + mр₂; … ; (λ + m)p_k  = lр_k-1 + μp_k+1; …

Из этой системы уравнений при условиях  и  имеем следующие формулы для финальных вероятностей

                                 p₀ =1-ρ; p_k = ρ^k(1 – ρ), k = 1,2,…                              (6.9.1)

Для характеристик эффективности СМО имеем следующие формулы:

 

A=λ; Q=1; P_отк=0; =ρ/(1-ρ); =ρ²/(1-ρ); _сист= ρ/λ(1-ρ); _ог= ρ²/λ(1-ρ); =λ/μ=ρ.

 

Здесь – среднее число заявок в СМО; – среднее число заявок в очереди.

 

Одноканальные системы массового обслуживания с ограниченной очередью

 

Пусть на одноканальную СМО поступает простейший поток заявок с интенсивностью λ, время обслуживания – показательное с интенсивностью μ=1/ _обс.

Пусть теперь очередь имеет ограниченную длину и состоит из m мест. Если заявка приходит в момент, когда все эти места заняты, она получает отказ и покидает СМО.

     Сформируем состояния следующим образом: s₀ – СМО свободна; s₁ – канал занят, одна заявка стоит в очереди; …; s_k – канал занят, k-1 заявок стоят в очереди; …; s_m+1 – канал занят, m заявок стоит в очереди. Граф состояний системы представлен на рис. 6.9.2.

 

λ

λ

…

Рис. 6.9.2

Система уравнений для предельных вероятностей системы, полученная из соответствующих уравнений Колмогорова, имеет вид:

λp₀ = μp₁;  (λ + m)p₁ = lp₀ + μp₂; … ; λp_m = μp_m+1.

Из этой системы уравнений при условии  и любом ρ = λ/μ имеем следующие формулы :

p₀ = (1-ρ) / ( 1-ρ^m+2 ) ; p_k = ρ^k p₀ , k = 1, 2, … , m+1;               (6.9.3)

Для показателей эффективности системы имеем следующие формулы:

A = λ(1-p_m+1) ; Q = 1-p_m+1 ; P_отк = p_m+1 .  = 1 – p₀ ;

 ; ;  ; . (6.9.4)

Задача 6.9.1. В клинике прием больных обеспечивает один врач ; в салоне ожидания приема 3 кресла. Пусть поток клиентов простейший с интенсивностью λ=2 кл./ч. Время обслуживания (приема клиента) – показательное со средним значением  мин. Если все три кресла в салоне ожидания заняты, клиент в очередь не становится. Считая процесс марковским, сформировать состояния системы, построить граф состояний системы. Найти предельные вероятности системы, а также показатели ее эффективности .

Решение. Пусть s₀ – СМО свободна; s₁ – врач занят, очереди нет; s₂ – врач занят, в очереди один больной; s₃ – врач занят, в очереди 2 больных ; s₄ – врач занят, в очереди 3 больных; λ=2 кл./ч., μ=3 кл./ч.

Граф состояний системы имеет следующий вид:

 

Рис. 6.9.3

Предельные вероятности определяются по формулам (6.9.3) при ρ = 2/3. Имеем p₀ 0,384 ; p₁ 0,256 ; p₂ 0,170 ; p₃ 0,114 ; p₄ 0,076. Это означает, что более трети времени (38,4%) врач свободен.

Средняя доля обслуживаемых клиентов Q=1-P_отк = 1-p₄ = 1-0,076 = 0,924.

Среднее число клиентов обслуживаемых врачом за час, равно A= λQ=2·0,924=1,848. Среднее число клиентов в очереди 0,209. Среднее число занятых клиентов (вероятность того, что канал занят) = 1-p₀ 0,616. Среднее число клиентов в клинике = + 0,825. Среднее время пребывания клиента в системе клиники /λ 0,413 ч.

 

Простейшая многоканальная СМО с неограниченной очередью

Пусть имеем n-канальную СМО, на которую поступает простейший поток заявок с интенсивностью λ; время обслуживания – показательное с параметром μ = 1/ . Если заявка поступает в момент времени, когда все каналы заняты, заявка становится в очередь, длина которой неограничена. Сформируем состояния СМО: s₀ – СМО свободна; s₁ – занят один канал, очереди нет; …; s_k – занято k каналов, очереди нет; …; s_n – заняты все n каналов, очереди нет; …; s_n+1 – заняты все n каналов, одна заявка стоит в очереди; s_n+r – заняты все n каналов, r заявок стоит в очереди и.т.д. Граф состояний СМО имеет следующий вид:

…   …    …

Рис. 6.9.4

 

Система уравнений для предельных вероятностей состояний, получаемая из соответствующих состояний Колмогорова, имеет вид

λp₀ = μp₁; (λ+μ) p₁ = λp₀ + 2μp₂; (λ+2μ) p₂ = λp₁+ 3μp₃; …; (λ+nμ) p_n = λp_n-1 + nμp_n+1;

(λ+nμ) p_n+1 = λp_n + nμp_n+r; …; (λ+nμ) p_n+r = λp_n+r-1 + nμp_n+r-1, …

Из последней системы алгебраических уравнений получим формулы для финальных вероятностей состояний:

p₀=(1+ ρ + ρ²/2! + … + ρⁿ/n! + ρⁿ⁺¹/(n n! (1-æ)))^-1, ρ = λ/μ, æ = ρ/n < 1;

, (1 k n);  (r 1).                                                     (6.9.5)

Для характеристик эффективности имеем следующие формулы:

; = + = +ρ;

                                           /λ; _оч = /λ.                                       (6.9.6)

 

Простейшая многоканальная СМО с ограниченной очередью

Пусть, как и в предыдущем случае, имеем n-канальную СМО, на которую поступает простейший поток заявок с интенсивностью λ; время обслуживания – показательное с параметрами . Но в отличие от предыдущего, если все n каналов заняты, заявка становится в очередь, длина которой ограничена и имеет m мест.

Сформируем состояния СМО: s₀ – СМО свободна; s₁ – занят один канал, очереди нет; …; s_n – заняты n каналов, очереди нет, s_n+1 – заняты n каналов, одна заявка в очереди; …; s_n+m – заняты n каналов, m заявок в очереди.

Граф состояний имеет следующий вид:

… …  

Рис. 6.9.5

Система уравнений для предельных вероятностей состояний, полученная из соответствующих уравнений Колмогорова, имеет вид:

λp₀ = µp₁; (λ+µ) p₁ = λp_{0 +} 2µp₂; …; (λ+nµ) p_n = λp_n-1 + nµp_n+1; …; nµp_n+m = λp_n+m-1.

Из последней системы алгебраических уравнений получим формулы для финальных вероятностей состояний:

p₀ = ( )^-1; p_k = (1 k n); p_n+r =  (1 r m),

где æ = / n = λ/(nµ).                                                                                   (6.9.7)

Для характеристик эффективности СМО имеем

A=λ(1-p_n+m); Q=1-p_n+m; P_отк = p_m+n; = (1-p_n+m); ;

; ; .                                     (6.9.8)

 

Задача 6.9.2. СМО, описанная в задаче 6.9.1, претерпела изменения в связи с эпидемией гриппа. В связи с увеличением в два раза интенсивности потока больных, администрация решила увеличить в два раза число обслуживаемых врачей и число кресел для ожидания без уменьшения среднего времени обслуживания. По-прежнему считаем, что если все кресла в зале ожидания заняты, клиент в очередь не становится. Как изменятся показатели эффективности СМО?

Решение. В данном случае СМО имеет два канала обслуживания; λ=4 кл/ч; µ=3 кл/ч; m=6. Пусть s₀ – СМО свободна; s₁ – один врач занят, очереди нет; s₂ – оба врача заняты, очереди нет; s₃ – оба врача заняты, один больной в очереди; s₄ – оба врача заняты, два больных в очереди; s₅ – оба врача заняты, три больных в очереди; s₆ – оба врача заняты, четыре больных в очереди; s₇ – оба врача заняты, пять больных в очереди; s₈ – оба врача заняты, шесть больных в очереди. Граф состояний имеет следующий вид:

Рис. 6.9.6

С помощью формул (6.9.7) получим значение предельных вероятностей состояний:

p₀ 0,206; p₁ 0,275; p₂ 0,183; p₃ 0,122; p₄ 0,081; p₅ 0,054; p₆ 0,037; p₇ 0,025; p₈ 0,017.

Из этого следует, что 20,6% врачи клиники свободны.

Вероятность отказа для пришедшего в клинику больного определяется величиной P_отк =p₈=0,017. Средняя доля обслуживаемых клиникой больных определяется величиной Q=1-p₈ 0,983; среднее число больных, обслуживаемых клиникой за один час A=λQ 3,932; среднее число занятых каналов (врачей) 1,311; среднее число больных в очереди 1,067; среднее число больных в клинике (за 1 час) 2,378; среднее время пребывания больного в клинике равно 0,59 ч.

Вопросы для самопроверки

1. Дайте определение случайной функции.

2. Что называют реализацией случайной функции?

3. Чем отличается случайный процесс от случайной функции?

4. Дайте определение математического ожидания случайного процесса.

5. Дайте определение дисперсии случайного процесса.

6. Что называют корреляционной функцией случайного процесса?

7. Какой случайный процесс называют марковским?

8. Что называют цепью Маркова?

9. Что выражает матрица вероятностей перехода цепи Маркова?

10. Напишите формулу Маркова. Что она выражает?

11. Какой случайный процесс называют непрерывной цепью Маркова?

12. Чем различаются цепи Маркова с непрерывным и дискретным временем?

13. Напишите уравнения Колмогорова для вероятностей состояния для непрерывной цепи Маркова.

14. Что называют предельными (финальными) вероятностями? Выпишите уравнения для финальных вероятностей.

15. Какой марковский процесс называют эргодическим?

16. Что называют процессом гибели и размножения? Постройте граф состояний.

17. Напишите формулы для финальных вероятностей процесса гибели и размножения.

18. Что называют простейшим потоком событий?

19. Что называют системой массового обслуживания? Что называют каналами СМО?

20. Дайте определение СМО с отказами и СМО с очередью.

21. Какие параметры характеризуют СМО?

22. Что служит характеристиками эффективности работы СМО?

23. Определите простейшую одноканальную СМО с отказами. Постройте граф состояний.

24. Напишите формулы для вероятностей состояний и характеристик эффективности работы одноканальной СМО с отказами.

25. Определите простейшую многоканальную СМО с отказами. Постройте граф состояний.

26. Напишите формулы Эрланга для вероятностей состояний и формулы для характеристик эффективности работы многоканальной СМО с отказами.

27. Определите простейшую одноканальную СМО с неограниченной очередью. Постройте граф состояний. Напишите формулы для предельных вероятностей состояний и основных характеристик эффективности СМО.

28. Определите простейшую одноканальную СМО с ограниченной очередью. Постройте граф состояний. Напишите формулы для предельных вероятностей состояний и основных характеристик эффективности СМО.

29. Определите простейшую многоканальную СМО с неограниченной очередью. Постройте граф состояний. Напишите формулы для предельных вероятностей состояний и основных характеристик эффективности СМО.

30. Определите простейшую многоканальную СМО с ограниченной очередью. Постройте граф состояний. Напишите формулы для предельных вероятностей состояний и основных характеристик эффективности СМО.

Задачи

1. Случайный процесс определяется формулой X (t)=X cos t, где X – случайная величина. Найти математическое ожидание, дисперсию и корреляционную функцию этого процесса, если МХ=а, DX= σ ².

Ответ: m_x(t)= acos t; D_x(t)= σ²cos² t;

        K_x (t₁, t₂)= σ ² cos t₁ cos t₂.

2. Производится многократное бросание «правильной» монеты. Определяет ли последовательность исходов цепь Маркова? Что изменится при бросаниях «правильной» монеты с вероятностью выпадения герба, равной 2/3?

3. В небольшом городе имеются два рынка – «Дешевый» и «Ближний». Покупатели достаточно лояльно относятся к своим рынкам. Однако каждую неделю 10% покупателей «Дешевого» переходят к «Ближнему» и 20% покупателей «Ближнего» меняют его на «Дешевый». Экономист, занимающийся изучением рыночной конъюнктуры, выбирает случайным образом одного местного жителя и еженедельно опрашивает его, выясняя, в каком рынке он производит свои покупки. Определяет ли данная последовательность исходов (ответов) марковскую цепь?

4. Старый политический принцип гласит, что партия, находясь у власти, имеет более высокие шансы победить на президентских выборах, чем партия оппозиции. Более того, считается, что если партия побеждала на президентских выборах несколько раз подряд, то ее шансы на очередных выборах еще более повышаются. Если такой принцип верен, определяет ли последовательность правящих партий цепь Маркова?

5. Часто кажется, что преуспевающим людям везет. Если, скажем, бизнесмен успешно завершил сделку, вероятность того, что он добьется успеха в следующей сделке, кажется нам выше. Более того, после успешного завершения ряда сделок, вероятность добиться успеха в следующей будет еще более высокой. Если это так, определяет ли такая последовательность исходов (сделок) цепь Маркова.

6. Известно, что заявки по телефону в ателье мод поступают с интенсивностью, равной 90 заявок в час, а средняя продолжительность разговора по телефону _об.=2 мин. Пусть поток заявок является простейшим, а время обслуживания – показательным. При наличии только одного телефонного номера телефонная связь в ателье является одноканальной СМО с отказами. Найти финальные вероятности состояний, а также показатели эффективности работы СМО.

                                                                       Ответ: p₀=0,25; p₁=0,75; Q=0,25;

                                                                                    P_отк=0,75; A = 22,5 з./ч.

7. Билетная касса с одним окошком представляет собой одноканальную СМО с неограниченной очередью. Касса продает билеты в пункты А и В. Пассажиров, желающих купить билет в пункт А, приходит в среднем трое за 20 мин, в пункт В – двое за 20 мин. Поток пассажиров считается простейшим, время обслуживания – показательным. Кассир в среднем обслуживает трех пассажиров за 10 мин. Найти первые три финальные вероятности состояний СМО, а также ее основные характеристики эффективности.

Ответ:     p₀ 0,167; p₁ 0,139;

p₂ 0,116; 4,99; 4,16; 20 мин. 16,7 мин.

8. При условиях задачи 6, определить оптимальное число телефонных номеров в ателье мод, если условием оптимальности считать удовлетворение из каждых 100 заявок на переговоры в среднем не менее 90 заявок.

Указание: для решения задачи сделать расчеты показателей эффективности, постепенно увеличивая число каналов (телефонных номеров), n=2,3,…, добиваясь, чтобы Q=0,9.                                            Ответ: n=5.

9. В юридической консультации прием ведут 3 юриста; в холле имеются три кресла для ожидания приема. Поток клиентов – простейший с интенсивностью 1/2 кл/ч. Время обслуживания – показательное со средним значением 20 мин. Если все три кресла в холле ожидания заняты, клиент в очередь не становится. Найти финальные вероятности состояний СМО, а также основные показатели ее эффективности.

Ответ: p₀  0,012; p₁  0,049;

p₂ 0,097; p₃  0,130;

p₄  0,173; p₅  0,231;

p₆  0,307; Q 0,693;

A 8,32; 2,78; 1,56;

4,34; 0,13 ч.; 0,362 ч.

10. Салон одежды с четырьмя кабинами для примерки является многоканальной СМО с неограниченной очередью. В салон прибывает простейший поток покупателей с интенсивностью 45 чел/ч. Время обслуживания (примерки) – показательное; среднее время – 5 мин. Найти основные характеристики эффективности СМО. Что даст увеличение числа кабин для примерки на единицу?

Ответ: а) n=4; p₀ 0,006; 13,01; 16,76; 17,3 мин; 22,3 мин.

          б) n=5; p₀ 0,019; 1,38; 5,13; 1,84 мин; 6,84 мин.

⇐ Предыдущая9101112131415161718Следующая ⇒

Поделиться: