книги / Прикладная теория систем массового обслуживания

исследование работы такой системы требует при вычислении более слож­ ного математического аппарата. В большинстве задач прикладного харак­ тера замена не пуассоновских потоков событий пуассоновскими с теми же интенсивностями приводит к получению решения, которое мало отличает­ ся от полученного [8].

Однако, как указано в работах [13, 14], имеются особые условия, ко­ гда погрешность может достигать значительной величины. В связи с этим приходится использовать случайные процессы более сложного характера. Общей тенденцией при этом является нахождение такого случайного про­ цесса, связанного с процессом обслуживания, который можно было бы рассматривать как марковский процесс. Один из наиболее выдающихся специалистов в области теории массового обслуживания Д. Кендалл пред­ ложил использовать метод вложенных цепей Маркова [15]. Вложенная цепь Маркова - это последовательность значений процесса в специально выбранные моменты времени. Вложенную цепь Маркова можно опреде­ лить в том случае, если моменты времени образуют сложную статическую связь, которую нельзя описать цепью Маркова. Важным случаем является полумарковский процесс [11], а дальнейшим развитием - линейчатые про­ цессы [13]. В дальнейшем рассмотрим решения для пуассоновских и непу­ ассоновских систем.

В работах [7-9, 11, 13, 14] исследовались системы массового обслу­ живания, на которые поступал входной поток заявок с некоторой интен­ сивностью, причем эта интенсивность не зависела от состояния СМО, а сами источники находились вне системы и не рассматривались. Такие СМО называются разомкнутыми или открытыми. Значительный интерес представляют так называемые замкнутые системы [И, 13], где интенсив­ ность потока заявок зависит от состояния СМО, а сами источники заявок являются не внешними, а внутренними элементами СМО. Такие системы характерны, например, для области аналого-цифрового преобразования. В них измеряемый входной сигнал канала, находясь на обслуживании (изме­ рении), перестает подавать заявки, а после конца обслуживания снова ста­ новится источником заявок. Моделью указанного входного потока являет­ ся поток Бернулли (см. раздел 2, [11, 16]).

3.1.2. Дисциплина обслуживания заявок

Система массового обслуживания называется системой с отказами (потерями), если заявка, пришедшая в момент, когда канал обслуживания (обслуживающая система) занят, немедленно получает отказ и покидает систему. Другой класс СМО представляет собой системы, в которых при занятости канала обслуживания заявка встает в очередь и ожидает освобо­ ждения канала, который может ее обслужить [11, 13, 14].

Система с ожиданием [И, 13, 14] бывают двух видов: СМО с беско­ нечной очередью («чистого» типа) и СМО с конечной очередью («смешан­ ного» типа). В системах с конечной очередью возможны как отказы, так и ожидание заявки в очереди. Отказы (отсутствие обслуживания) могут быть связаны или с ограниченным числом мест в очереди, или с ограниченным временем ожидания, которым располагает заявка.

Дисциплина очереди определяет как порядок ее формирования, так и выбор заявки на обслуживание. Формирование очереди может зависеть от свойств самих заявок. Заявки могут не становится в очередь вследствие размеров очереди или просто потому, что они вообще не могут ожидать начала обслуживания. Во многих задачах может потребоваться принять решение, к какой из нескольких очередей системы присоединиться, если имеется некоторая информация по ним (приспособление заявки к условиям очереди, уход из очереди, переход заявки из одной очереди в другую и т.д.).

Важной задачей является взаимодействие и объединение очередей [11]. При этом достигается некоторое сокращение среднего времени ожи­ дания, особенно когда велик разброс времени обслуживания устройства, перед которым образовалась отдельная очередь.

Выбор из очереди на обслуживание и распределение заявок по кана­ лам может производиться в порядке прибытия [11, 16], случайным образом [17], в зависимости от приоритета заявки [18]. Изучение систем массового обслуживания с приоритетами разного типа представляет собой важную задачу как в общетеоретическом, так и в прикладном отношении.

Многообразие постановок задач исследования означает и многообра­ зие приложений. При этом определяющим является реальный объект, ко­ торый моделируется той или иной дисциплиной очереди, системой при­ оритетов.

3.1*3. Канал обслуживания

Основным параметром любой системы массового обслуживания яв­ ляется число каналов обслуживания. Каналом обслуживания называется вся совокупность технических устройств, обеспечивающих обслуживание заявки. Обслуживающее устройство может состоять из одного прибора (однолинейные системы) или нескольких (многолинейные системы). Во­ просы изучения таких СМО нашли достаточно прочное отражение, напри­ мер, в работах [13, 14, 16]. При многолинейном обслуживании приборы могут соединяться последовательно с другими для обслуживания заявки [11] или же несколько параллельных приборов могут обслуживать одну за­ явку [13].

Исследование СМО с приборами разной производительности [7- 10, 13] позволяет решать вопросы синтеза с использованием различных обра­ батывающих приборов. Однако в работах [7-10, 13] число обслуживающих приборов и интенсивности обслуживания постоянны. Основной же осо­ бенностью ряда приложений является переменное число требуемых заявок приборов на обслуживание и изменение интенсивности обслуживания за­ явки [И, 12]. Например, требование входной заявки /-го канала на qj раз­ рядов означает, что для обслуживания этой заявки в данный момент вре­ мени требуется j обслуживающих приборов. Вопросы разработки СМО с переменным числом обслуживающих приборов и изменяющейся интен­ сивностью обслуживания требуют дополнительной разработки.

В многолинейных системах [9, 13] большое внимание уделяется во­ просам взаимодействия приборов и заявок. Если в момент поступления требования имеется несколько свободных приборов, то необходимо уточ­ нить, каким образом выбирается прибор (или группа приборов), который будет обслуживать данную заявку. Как правило, рассматриваются два слу­ чая: 1 - интенсивности обслуживания всех приборов одинаковы; 2 - ин­ тенсивности обслуживания приборов различны (приборы неоднородны). В первом случае нет необходимости различать приборы обслуживания и правило выбора не влияет [9] на число требований в очереди или в систе­ ме, но существенно влияет на занятие приборов. Во втором случае правило выбора влияет на функционирование всей системы. В общем случае по­ строение модели СМО с учетом всех нюансов - задача очень важная и сложная.

3.1.4. Выходящий поток

Выходящий поток играет важную роль, особенно когда он сам явля­ ется входящим для другой системы, последовательно соединенной с пер­ вой. Распределение входящего потока и распределение времени обслужи­ вания могут зависеть друг от друга. Такая зависимость существует, когда обслуживание влияет на поступление требований, и наоборот.

В ИИС, АСУТП, АСНИ, САИ и многих других сообщение должно пройти все уровни системы. Поэтому в таких системах моделью является сеть массового обслуживания (СеМО).

Вопросы рассмотрения СеМО заслуживают особого внимания, так как однофазные модели, не учитывающие влияние соседних фаз, как ука­ зано в работах [19-21], дают значительные погрешности. В свою очередь, рассмотрение многофазных моделей приводит к значительным по сложно­ сти и размерности вычислениям [11, 22], однако эти результаты хорошо согласуются с результатами натурных исследований систем [19, 22]. Избе­ жать указанных трудностей позволяют статистические имитационные мо­ дели [20]. Но имитационное моделирование требует, с одной стороны, вы­

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

Э.2. Классификация СМО

Кратко остановимся на классификации СМО, предложенной Кен­ даллом [9]. Если М обозначает, что распределение числа событий в фикси­ рованном промежутке времени является пуассоновским, а распределение промежутков между ними - экспоненциальным, то MIMIC обозначает С- канальную систему с пуассоновским входящим потоком и экспоненциаль­ ным распределением времени на обслуживание. Символ D обозначает вы­ рожденное распределение, Кп- распределение по закону Хл-квадрат с чет­ ным числом степеней свободы, Ms - групповое распределение, Еп - эрланговское распределение с математическим ожиданием, не зависящем от п, GI - символ последовательности независимых, произвольным образом (но одинаковым) распределенных случайных величин, a G - произвольное распределение, в котором не требуется наличие независимости. Таким об­ разом, D/EJX обозначает одноканальную систему с регулярным входящим потоком и распределением времени обслуживания по закону Эрланга.

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

3.3. Процессы гибели и размножения

Для большинства систем массового обслуживания, которые рас­ смотрены в данном пособии, граф состояний имеет вид, показанный на рис. 3.3. Для этих систем характерно то, что каждое состояние (кроме двух крайних) имеет только два соседних состояния. Крайние состояния имеют только по одному соседнему состоянию.

Таким образом, граф состояний можно представить в виде цепи со­ стояний, соединенных между собой стрелками переходов. Другими слова­ ми, из любого состояния Xk (кроме крайних к * 0, к * п) возможен переход только в два соседних состояния (предыдущее) и ^(последующее). Из крайнего левого состояния х0возможен переход только в состояние х \, а из крайнего правого состояния хп- только в состояние х ^ .

Процессы, описываемые с помощью такого графа состояний, в лите­ ратуре принято называть процессами гибели и размножения. Такое назва­ ние они получили потому, что впервые были применены в биологии для анализа численности популяций, распространение ожиданий и при иссле­ довании других проблем. Число п может быть как константным, так и бес­ конечным.

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

Л>(0);Я,(0)..... РА0); £ ^ ( 0) = 1 .

к-0

Если число состояний п в системе конечно, то для любого момента

Иногда рассматривают процесс размножения (чистого размноже­ ния), когда переход из состояния в состояние возможен только слева на­ право. Граф процесса приведен на рис. 3.4.

Для решения этих уравнений введем следующие обозначения:

Тогда уравнения (3.3) примут вид:

UQ= 0,

w- * V1= о.

Анализ системы уравнений (3.4) показывает, что имеет место равен­

ство

ик = 0 (*=0,1,..., л-1),

Таким образом, получаем возможность с помощью рекуррентной формулы (3.5) выразить значение любой вероятности /Vi через все преды­ дущие:

Найденное выражение для всех вероятностей состояния процесса ги­ бели и размножения зависит от вероятности Р0 и параметров потоков. Ве­ роятность Р0можно определить из нормировочного условия (3.2):

*=0!=ОЦ,+1

Итак, совокупность формул (3.6) и (3.7) дает возможность опреде­ лить все вероятности состояний процесса гибели и размножения для ко­ нечного числа состояний п.

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

времени) параметрах Хк и р/. Это объясняется тем, что могут иметь место условия, при которых нет никаких ограничений на рост популяции и про­ цесс все время будет двигаться вправо.

Для того чтобы нормировочное условие (3.2) выполнялось, доста­ точно расходимости ряда

сходится, то существует стационарный режим

Р к = lim PAt).

/->00

Условие (3.9) всегда выполняется, если, начиная с некоторого к, справедливо неравенство

Рм

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

3.4.Системы массового обслуживания с отказами

3.4.1.Классическая система массового обслуживания

сотказами (система Эрланга)

Постановка задачи. На вход л-канальной СМО подается простей­ ший поток заявок с интенсивностью X. Интенсивность простейшего потока обслуживания каждого канала обозначим р. Если заявка застала все л ка­ налов занятыми, то она получает отказ (покидает систему не обслужен­