6.4. Основные принципы построения марковских моделей массового обслуживания

1. Процессы массового обслуживания представляют собой случайные процессы с дискретными состояниями. Переход из одного возможного состояния в другое происходит скачком в момент, когда реализуется какое-то случайное событие (поступление новой заявки, начало или окончание обслуживания, уход заявки из очереди и т.п.), вызывающее такой переход.

2. Для процессов массового обслуживания с простейшим входным потоком и экспоненциальным законом распределения времени обслуживания характерно отсутствие последействия. Таким образом, будущее развитие рассматриваемых процессов зависит лишь от их текущих состояний и не зависит от того, как происходило их развитие в прошлом. А это означает, что процессы массового обслуживания с простейшим входным потоком заявок и экспоненциальным законом распределения времени обслуживания являются марковскими процессами с дискретными состояниями.

3. Предположим, что в систему обслуживания с идентичными параллельными каналами обслуживания поступает простейший входной поток. При наличии хотя бы одного свободного канала немедленно начинается обслуживание заявки, а если все каналы заняты, то заявка становится в очередь (в системах обслуживания с отказами заявка покидает систему; в системах обслуживания с ограниченной длиной очереди заявка становится в очередь, если там есть свободное место, и покидает систему в противном случае).

Пусть — возможное состояние рассматриваемой системы обслуживания, характеризуемое тем, что в ней занято ровно i каналов обслуживания, , а возможное состояние системы характеризуется тем, что все каналов обслуживания заняты и очередь состоит из заявок, где . Если на длину очереди не накладывают ограничений, то может быть сколь угодно большим и система может иметь счетное множество состояний. Системы обслуживания с отказами и с ограничениями на длину очереди могут иметь лишь конечные множества возможных состояний.

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

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

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

если то заняты все каналов и в очереди находится заявок;

если то рассматривают систему обслуживания с отказами;

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

если то рассматривают систему обслуживания с ожиданием без ограничений на длину очереди.

5. Пусть — множество возможных состояний рассматриваемой системы обслуживания. Для введем случайное событие заключающееся в том, что в момент времени система находится в состоянии и обозначим вероятность его реализации через

В любой момент времени исходная система может находиться лишь в одном из возможных состояний, поэтому — полная группа событий и, как следствие,

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

6. Из приведенных выше рассуждений и определения 5.8 марковского процесса с дискретными состояниями следует, что рассматриваемые процессы массового обслуживания являются процессами гибели — размножения. К изложенному в 5.4 добавим следующее:

а) элемент размеченного графа состояний системы S, соответствующий возможному состоянию будем называть вершиной графа; стрелки, указывающие возможные переходы системы S из состояния в состояние, с записанными переходными вероятностями, — нагруженными дугами, а переходные вероятности — весами;

б) при составлении системы уравнений Колмогорова можно использовать следующее правило: производная от вероятности пребывания системы в состоянии , в момент времени t равна сумме произведений весов дуг, инцидентных вершине размеченного графа состояний, на вероятности состояний, к которым они направлены; при этом вес дуги берется со знаком „плюс“, если дуга направлена к вершине, соответствующей состоянию , и со знаком „минус“ в противном случае;

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

Пример 6.2. Рассмотрим простейшую задачу теории массового обслуживания — задачу о функционировании одноканальной системы обслуживания с отказами, на вход которой поступает простейший поток заявок с интенсивностью А (заявка, заставшая канал занятым, покидает систему), а время обслуживания заявки — случайная величина, распределенная по экспоненциальному закону с параметром .

В данном случае система имеет лишь два возможных состояния: — канал свободен; — канал занят. Ее размеченный граф состояний изображен на рис. 6.2.

Рис. 6.2

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

При этом, учитывая, что, согласно (6.16),

математическую модель можно упростить:

Решив полученную задачу Коши, находим (рис. 6.3)

Рис. 6.3

Важнейшими характеристиками системы обслуживания с отказами являются:

а) абсолютная пропускная способность — среднее число заявок, которое может обслужить система в единицу времени;

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

Нетрудно убедиться в том, что в примере 6.2 функцию можно интерпретировать как относительную пропускную способность системы. Действительно, есть вероятность того, что в момент t канал обслуживания свободен, т.е. что заявка, поступившая в момент t, будет обслужена. А это означает, что есть отношение числа обслуженных заявок к их общему числу, или относительная пропускная способность системы.

При стационарном (установившемся) режиме функционирования имеем

Поэтому в рассматриваемом случае относительная пропускная способность системы обслуживания равна

Можно показать, что абсолютная пропускная способность равна величине обратной сумме среднего времени ожидания заявки и среднего времени ее обслуживания:

Пример 6.3. Одноканальная система обслуживания представляет собой телефонную линию. Заявка-вызов, поступившая в момент, когда линия занята, получает отказ. Интенсивность потока заявок 0,8 (вызовов в минуту). Средняя продолжительность разговора 1,5 минуты. Считая поток заявок простейшим, а время обслуживания распределенным по экспоненциальному закону, определим в стационарном режиме функционирования:

1) абсолютную пропускную способность канала связи

2) относительную пропускную способность канала связи

3) вероятность отказа .

Имеем

Таким образом,

Относительная пропускная способность канала связи

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

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