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

В этом параграфе мы кратко рассмотрим некоторые вопросы, относящиеся к немарковским СМО. До сих пор все формулы нами выводились или, по крайней мере, могли быть выведены читателем, вооруженным схемой гибели и размножения, формулой Литтла и умением дифференцировать. То, что будет рассказано в данном параграфе, читателю придется принять на веру.

До сих пор мы занимались только простейшими СМО, для которых все потоки событий, переводящий их из состояния в состояние, были простейшими. А как быть, если они не простейшие? Насколько реально это допущение? Насколько значительны ошибки, к которым оно приводит, когда оно нарушается? На все эти вопросы мы попытаемся ответить здесь.

Как это ни грустно, но надо признаться, что в области немарковской теории массового обслуживания похвастать нам особенно нечем. Для немарковских СМО существуют только отдельные, считанные результаты, позволяющие выразить в явном, аналитическом виде характеристики СМО через заданные условия задачи — число каналов, характер потока заявок, вид распределения времени обслуживания. Приведем некоторые из этих результатов.

1. n-канальная СМО с отказами, с простейшим потоком заявок и произвольным распределением времени обслуживания. В предыдущем параграфе мы вывели формулы Эрланга (20.4), (20.5) для финальных вероятностей состояний СМО с отказами. Сравнительно недавно (в 1959 г.) Б. А. Севастьянов [19] доказал, что эти формулы справедливы не только при показательном, но и при произвольном распределении времени обслуживания.

^ 2. Одноканальная СМО с неограниченной очередью, простейшим потоком заявок и произвольным распределением времени обслуживания. Если на одноканальную СМО с неограниченной очередью поступает простейший поток заявок с интенсивностью λ, а время обслуживания имеет произвольное распределение с математическим ожиданием t_об = 1/μ. и коэффициентом вариации v_μ, то среднее число заявок в очереди равно

(21.1)

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

(21.2)

где, как и ранее, ρ = λ/μ., a v_μ — отношение среднего квадратического отклонения времени обслуживания к его математическому ожиданию. Формулы (21.1), (21.2) носят название формул Полячека — Хинчина.

Деля L_оч, и L_сист на λ, получим, согласно формуле Литтла, среднее время пребывания заявки в очереди и среднее время пребывания в системе:

(21.3)

(21.4)

Заметим, что в частном случае, когда время обслуживания — показательное, v_μ = 1 и формулы (21.1), (21.2) превращаются в уже знакомые нам формулы (20.16), (20.20) для простейшей одноканальной СМО. Возьмем другой частный случай — когда время обслуживания вообще не случайно и v_μ = 0. Тогда среднее число заявок в очереди уменьшается вдвое по сравнению с простейшим случаем. Это и естественно: если обслуживание заявки протекает более организованно, «регулярно», то СМО работает лучше, чем при плохо организованном, беспорядочном обслуживании.

^ 3. Одноканальная СМО с произвольным потоком заявок и произвольным распределением времени обслуживания. Рассматривается одноканальная СМО с неограниченной очередью, на которую поступает произвольный рекуррентный поток заявок с интенсивностью λ и коэффициентом вариации v_λ интервалов между заявками, заключенным между нулем и единицей: 0 < v_λ < 1. Время обслуживания Т_об также имеет произвольное распределение со средним значением t_об = 1/μ и коэффициентом вариации v_μ, тоже заключенным между нулем и единицей. Для этого случая точных аналитических формул получить не удается;

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

Доказано, что в этом случае

(21.5)

Если входящий поток — простейший, то обе оценки — верхняя и нижняя — совпадают, и получается формула Полячека — Хинчина (21.1). Для грубо приближенной оценки средней длины очереди М. А. Файнбергом (см. [18]) получена очень простая формула:

(21.6)

Среднее число заявок в системе получается из L_очпростым прибавлением ρ — среднего числа обслуживаемых заявок:

L_сист = L_оч + ρ. (21.7)

Что касается средних времен пребывания заявки в очереди и в системе, то они вычисляются через L_очи L_сист по формуле Литтла делением на λ.

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

Возникает естественный вопрос: а как же обстоит дело с многоканальными немарковскими СМО? Со всей откровенностью ответим: плохо. Точных аналитических методов для таких систем не существует. Единственное, что мы всегда можем найти, это среднее число занятых каналов k = ρ. Что касается L_оч, L_сист, W_оч, W_сист, то для них таких общих формул написать не удается.

Правда, если каналов действительно много (4—5 или больше), то непоказательное время обслуживания не страшно: был бы входной поток простейшим. Действительно, общий поток «освобождений» каналов складывается из потоков освобождений отдельных каналов, а в результате такого наложения («суперпозиции») получается, как мы знаем, поток, близкий к простейшему. Так что в этом случае замена непоказательного распределения времени обслуживания показательным приводит к сравнительно малым ошибкам. К счастью, входной поток заявок вомногих задачах практики близок к простейшему.

Хуже обстоит дело, когда входной поток заведомо не простейший. Ну, в этом случае приходится пускаться на хитрости. Например, подобрать две одноканальные СМО, из которых одна по своей эффективности заведомо «лучше» данной многоканальной, а другая — заведомо «хуже» (очередь больше, время ожидания больше). А для одноканальной СМО мы худо-бедно уже умеем находить характеристики в любом случае.

Как же подобрать такие одноканальные СМО — «лучшую» и «худшую»? Это можно сделать по-разному. Оказывается, заведомо худший вариант можно получить, если расчленить данную n-канальную СМО на п одноканальных, а общий поступающий на них простейший поток распределять между этими одноканальными СМО в порядке очереди: первую заявку — в первую СМО, вторую — во вторую и т. д. Мы знаем, что при этом на каждую СМО будет поступать поток Эрланга n-го порядка, с коэффициентом вариации, равным 1/ . Что касается коэффициента вариации времени обслуживания, то он остается прежним. Для такой одноканальной СМО мы уже умеем вычислять время пребывания заявки в системе W_сист; оно будет заведомо больше, чем для исходной n-канальной СМО. Зная это время, можно дать «пессимистическую» оценку и для среднего числа заявок в очереди, пользуясь формулой Литтла и умножая среднее время на интенсивность λ общего потока заявок. «Оптимистическую» оценку можно получить, заменяя n-канальную СМО одной одноканальной, но с интенсивностью потока обслуживании в n раз большей, чем у данной, равной nμ. Естественно, при этом параметр ρ тоже должен быть, изменен, уменьшен в n раз. Для такой СМО время пребывания заявки в системе W_сист уменьшается за счет того, что обслуживание продолжается в n раз меньше времени. Пользуясь измененным значением , коэффициентом вариации входящего потока v_λ и времени обслуживания v_μ, мы можем приближенно вычислить среднее число заявок в системе . Вычитая из него первоначальное (не измененное) значение ρ, мы получим среднее число заявок в очереди . Обе характеристики будут меньше, чем для исходной n-канальной СМО (будут представлять собой «оптимистические» оценки). От них, деля на λ, можно перейти к «оптимистическим» оценкам для времени пребывания в СМО и в очереди.

ГЛАВА 7

^ СТАТИСТИЧЕСКОЕ МОДЕЛИРОВАНИЕ СЛУЧАЙНЫХ ПРОЦЕССОВ (МЕТОД МОНТЕ-КАРЛО)