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

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

В начале 20 века в связи с нуждами телефонного дела, рациональной организации массового обслуживания (билетные кассы, магазины, автоматы и пр.) возникло понятие систем массового обслуживания. Возник такжецелый ряд математических задач и способов их решения, составляющих содержание теории массового обслуживания. На начальном этапе важную роль в развитии данного направления сыграли работы датского ученого А.К. Эрланга – многолетнего сотрудника Копенгагенской телефонной компании. Со временем выяснилось, что задачи типа телефонных возникают в самых разнообразных исследованиях: в естествознании, в технике, экономике, на транспорте, в военном деле, при организации производства.

Работа любой системы массового обслуживания состоит в выполнении поступающего на нее потока требований или заявок. Заявки поступают одна за другой в некоторые, вообще говоря, случайные моменты времени. Обслуживание поступившей заявки продолжается какое-то время, после чего канал освобождается и снова готов для приема следующей заявки.

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

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

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

1.9.2.Понятие о цепях Маркова

1.9.2.1. Цепь Маркова

Для описания процесса функционирования систем массового обслуживания широко используется математический аппарат цепей Маркова. Цепью Маркова называют последовательность испытаний, в каждом из которых появляется только одно из несовместных событий полной группы, причем условная вероятность того, что в -м испытании наступит событие , при условии, что в -м испытании наступило событие , не зависит от результатов предыдущих испытаний (т.е. от того, какие события имели место на шагах). Например, если последовательность испытаний образует цепь Маркова и полная группа состоит из четырех несовместных событий , причем известно, что в шестом испытании появилось событие , то условная вероятность того, что в следующем, седьмом испытании наступит событие , не зависит от того, какие события появились в первом, втором,…, пятом испытаниях (система без «памяти»).

Можно сразу отметить: привычная схема независимых испытаний (схема Бернулли) является частным случаем цепи Маркова. Цепь Маркова, таким образом, является обобщением понятия независимых испытаний.

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

Цепью Маркова с дискретным временем называют цепь, изменение состояний которой происходит в определенные фиксированные моменты времени.

Цепью Маркова с непрерывным временем называют цепь, изменение состояний которой происходит в любые случайные моменты времени.

1.9.2.2. Однородная цепь Маркова. Переходные вероятности. Матрица перехода

Однородной называют цепь Маркова, если условная вероятность (перехода из состояния в состояние ) не зависит от номера испытания. Поэтому вместо пишут просто .

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

Таким образом, случайное блуждание – пример однородной цепи Маркова с дискретным временем.

Далее ограничимся элементами теории конечных однородных цепей Маркова.

Переходной вероятностью называют условную вероятность того, что из состояния (в котором система оказалась в результате предыдущих испытаний) в итоге следующего испытания система перейдет в состояние . Таким образом, первый индекс в переходной вероятности указывает номер предшествующего, а второй – номер последующего состояния. Например, – вероятность «перехода» из первого состояния в первое, а – вероятность перехода из второго состояния в третье.

Пусть число состояний конечно и равно .

Матрицей перехода системы называют матрицу, которая содержит все переходные вероятности этой системы:

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

Например, матрица перехода системы, которая может находиться в трех состояниях, может иметь такой вид:

1.9.2.3. Равенство Маркова

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

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

. (*)

Эта формула называется равенством Маркова.

Зная все переходные вероятности , т.е. зная матрицу перехода из состояний в состояния за один шаг, можно найти все вероятности перехода из состояния в состояние за два шага, следовательно, и саму матрицу перехода ; по известной матрице можно найти матрицу перехода из состояний в состояния за 3 шага, и т.д.

Действительно, полагая в (*) , получим

Из этой записи очевидно, что Аналогично, полагая в равенстве Маркова , можно убедиться, что В общем случае

Пример. Шахтный вентилятор местного проветривания может находиться в двух состояниях: 1) в работе; 2) в ремонте. Матрица перехода имеет вид

Найти

Решение. Перемножая матрицы, получим