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

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

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

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

1. n-канальная СМО с отказами, с простейшим потоком заявок и произвольным распределением времени обслуживания.

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

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

Если на одноканальную СМО с неограниченной очередью поступает простейший поток заявок с интенсивностью Я, а время обслуживания имеет произвольное распределение с математическим ожиданием и коэффициентом вариации ум, то среднее число заявок в очереди равно

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

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

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

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

3. Одноканальная СМО с произвольным потоком заявок и произвольным распределением времени обслуживания.

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

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

Если входящий поток — простейший, то обе оценки — верхняя и нижняя — совпадают, и получается формула Полячека — Хинчина (21.1).

Для грубо приближенной оценки средней длины очереди М. А. Файнбергом (см. [18]) получена очень простая формула:

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

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

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

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

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

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

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

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