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

 

Во многих областях экономики, финансов, производства и быта важную роль играют системы^[1] специального вида, реализующие многократное выполнение однотипных задач. Подобные системы называют системами массового обслуживания (СМО). В качестве примеров СМО в финансово-экономической сфере можно привести системы, представляющие собой банки, страховые организации, налоговые инспекции, аудиторские службы. В сфере производства и обслуживания примерами СМО могут служить: различные системы связи (телефонные станции), погрузочно-разгрузочные комплексы, автозаправочные станции, магазины, парикмахерские, билетные кассы, пункты обмена валюты, и т.д. Такие системы как компьютерные сети, системы сбора, хранения и обработки информации, системы противовоздушной или противоракетной обороны также могут рассматриваться как своеобразные СМО.

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

 

СМО могут быть одноканальными или многоканальными.

 

Каждая СМО предназначена для обслуживания (выполнения) некоторого потока ^[2] заявок (требований), поступающих на вход системы большей частью не регулярно, а случайные моменты времени. Обслуживание заявок, также длится не постоянное, заранее известное время, а случайное время, которое зависит от многих случайных причин. После обслуживания заявки канал освобождается и готов к приему следующей заявки. Случайный характер потока заявок и времени их обслуживания приводит к неравномерной загруженности СМО: на входе СМО могут скапливаться необслуженные заявки, что приводит к перегрузке СМО, а при свободных каналах на входе СМО заявки не будет, что приводит к недогрузке СМО, т.е. к простаиванию ее каналов. Заявки, скапливающиеся на входе СМО, либо «становятся» в очередь, либо по причине невозможности дальнейшего пребывания в очереди покидают СМО необслуженными.

 

 

Во всякой СМО можно выделить следующие основные элементы:

1) входящий поток заявок;

2) очередь;

3) каналы обслуживания;

4) выходящий поток обслуженных заявок.

 

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

Предметом изучения теории массового обслуживания является СМО.

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

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

 

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

 

1. Показатели эффективности использования СМО:

1.1. Абсолютная пропускная способность СМО — среднее число заявок, которое может обслужить СМО в единицу времени.

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

1.3. Средняя продолжительность периода занятости СМО.

1.4. Коэффициент использования СМО — средняя доля времени, в течение которого СМО занята обслуживанием заявок.

 

2. Показатели качества обслуживания заявок:

2.1. Среднее время ожидания заявки в очереди.

2.2. Среднее время пребывания заявки в СМО.

2.3. Вероятность отказа заявке в обслуживании без ожидания.

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

2.5. Закон распределения времени ожидания заявки в очереди.

2.6. Закон распределения времени пребывания заявки в СМО.

2.7. Среднее число заявок, находящихся в очереди.

2.8. Среднее число заявок, находящихся в СМО.

 

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

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

 

Случайный характер потока заявок и длительности их обслуживания порождает в СМО случайный процесс ^[3].

Случайным процессом (или случайной функцией) называется соответствие, при котором каждому значению аргумента (в данном случае — моменту из промежутка времени проводимого опыта) ставится в соответствие случайная величина (в данном случае — состояние СМО).

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

Математическое изучение функционирования СМО значительно упрощается, если протекающий в ней случайный процесс является марковским^[4]. В этом случае работа СМО сравнительно легко описывается с помощью аппарата конечных систем обыкновенных линейных дифференциальных уравнений первого порядка, а в предельном режиме (при достаточно длительном функционировании СМО) — с помощью аппарата конечных систем линейных алгебраических уравнений, и в результате удается выразить в явном виде основные характеристики эффективности функционирования СМО через параметры СМО, потока заявок и дисциплины работы СМО.

Чтобы случайный процесс был марковским, необходимо и достаточно, чтобы все потоки событий, под воздействием которых происходят переходы системы из состояния в состояние, были пуассоновскими^[5]. В СМО потоками событий являются потоки заявок, потоки «обслуживания» заявок и т.д.

 

1. Потоки событий

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

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

Поток событий называется стационарным, если вероятность появления k событий за промежуток времени длительностью t зависит только от длительности промежутка t и не зависит от начала отсчета. Стационарность потока означает независимость от времени его вероятностных характеристик.

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

Поток событий называется потоком без последействия, если для любых двух непересекающихся участков времени t ₁ и t ₂ - число событий, попадающих на один из них, не зависит от числа событий, попадающих на другие. Например, поток покупателей, входящих в магазин, можно считать потоком без последействия потому, что причины, обусловившие приход каждого из них, не связаны с аналогичными причинами других покупателей.

Поток событий называется простейшим (или пуассоновским), если он одновременно стационарен, ординарен и не имеет последействия. Название "простейший" объясняется тем, что СМО с простейшими потоками имеет наиболее простое математическое описание. Заметим, что регулярный поток не является "простейшим", так как он обладает последействием: моменты появления событий в таком потоке жестко зафиксированы.

Рассмотрим некоторый промежуток времени t. Для простейшего потока число m событий (точек), попадающих на произвольный участок времени t, распределено по закону Пуассона

(6.1)

 

Вероятность того, что за время t не произойдет ни одного события (m =0), равна

(6.2)

 

Найдём распределение интервала времени Т между произвольными двумя соседними событиями простейшего потока. В соответствии с (2) вероятность того, что на участке времени длиной t не появится ни одного из последующих событий, равна

(6.3)

 

а вероятность противоположного события, т.е. функция распределения случайной величины Т, есть

(6.4)

 

Плотность вероятности случайной величины есть производная её функции распределения, т.е.

(6.5)

 

Распределение, задаваемое плотностью вероятности (5) или функцией распределения (4), называется показательным (или экспоненциальным). Таким образом, интервал времени между двумя соседними произвольными событиями имеет показательное распределение, для которого математическое ожидание равно среднему квадратическому отклонению случайной величины и обратно по величине интенсивности потока l.

Важнейшее свойство показательного распределения (присущее только показательному распределению) состоит в следующем: если промежуток времени, распределенный по показательному закону, уже длился некоторое время t, то это никак не влияет на закон распределения оставшейся части промежутка (T - t): он будет таким же, как и закон распределения всего промежутка Т.

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

Для простейшего потока с интенсивностью l вероятность попаданияна элементарный отрезок времени D t хотя бы одного события потока равна

(6.6)

 

Данная формула, получаемая заменой функции лишь двумя первыми членами её разложения в ряд по степеням D t, тем точнее, чем меньше D t.

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

(6.7)

 

Пользуясь полученной функцией распределения, можно получить числовые характеристики случайной величины T: математическое ожидание , дисперсию и среднее квадратическое отклонение

(6.8)

 

Отсюда вывод: средний интервал времени T между двумя соседними событиями в простейшем потоке в среднем равен и его среднее квадратическое отклонение также равно , где l - интенсивность потока, т.е. среднее число событий, происходящих в единицу времени.

 

Процесс называется процессом с дискретными состояниями, если его возможные состояния S ₁, S ₂, …, S_m, можно заранее перечислить, а переход системы из состояния в состояние происходит мгновенно (скачком). Случайный процесс, происходящий в СМО, заключается в её переходе в случайные моменты времени t ₀, t ₂, …, t_n в одно из заранее известных дискретных состояний S_i, причем переход из одного состояния в другое происходит скачкообразно, в случайные моменты времени, и поэтому называется процессом с непрерывным временем. Такая случайная последовательность событий называется марковской цепью, если для каждого шага вероятность перехода из одного состояния S_i в любое другое S_j не зависит от того, когда и как система перешла в состояние S_i. Такие процессы называются процессами без последствия, или марковскими, в которых при фиксированном настоящем будущее состояние СМО не зависит от прошлого. Например, возможность получения с завода продукции зависит от наличия её на складе готовой продукции, т.е. его состояния в данный момент, и не зависит от того, когда и как получали и увозили в прошлом эту продукцию. Математический анализ работы СМО существенно упрощается, если процесс работы - марковский. Случайный процесс называется марковским или случайным процессом без последствия, если для любого момента времени t ₀ вероятностные характеристики процесса в будущем зависят только от его состояния в данный момент t ₀ и не зависят от того, когда и как система пришла в это состояние.

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

 

 

Контрольные вопросы

1. Какой поток событий называется простейшим?

2. Какой поток событий называется потоком без последействия?

3. Какой поток событий называется ординарным?

4. Какой поток событий называется регулярным?

5. Какой поток событий называется стационарным?

6. Какой процесс называется марковским?

7. Как средний интервал времени между двумя соседними событиями в простейшем потоке связан с интенсивностью потока?

8. Чему равна вероятность попадания на элементарный отрезок времени D t хотя бы одного события?

2. Уравнения Колмогорова

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

 

Рисунок 7.1 - Размеченный граф состояний СМО

 

Система может находиться в одном из трех состояний: S ₀ - канал свободен, простаивает, S ₁ - канал занят обслуживанием заявки, S ₂ - канал занят обслуживанием и одна заявка в очереди. Переход системы из состояния S ₀ в S ₁ происходит под воздействием простейшего потока заявок интенсивностью l ₀₁, а из состояния S ₁ в состояние S систему переводит поток обслуживания с интенсивностью l ₁₀. Вероятностью i -го состояния называется вероятность p_i (t) того, что в момент t система будет находиться в состоянии S_i. Описывается марковская цепь с помощью вероятности состояний, причём они образуют полную группу событий, поэтому их сумма равна единице. Если вероятность перехода не зависит от номера k, то марковская цепь называется однородной.

Рассмотрим математическое описание марковского случайного процесса с дискретными состояниями системы S ₀, S ₁, S ₂(см. рис. 1) и непрерывным временем. Будем полагать, что переходы СМО из состояния S_i в состояние S_j происходят под воздействием простейших потоков событий с интенсивностями l_ij а обратный переход - под воздействием потока l_ii Введем обозначение p_i как вероятность того, что в момент времени t система находится в состоянии S_i. Для любого момента времени t справедливо записать нормировочное условие - сумма вероятностей всех состояний равна 1:

(7.1)

 

Задав малое приращение времени D t найдем вероятность p_i (t +D t) того, что система в момент времени (t +D t) будет находиться в состоянии S ₁, которое может быть достигнуто следующими способами:

а) система в момент t с вероятностью p_i (t) находилась в состоянии S ₁и за малое приращение времени D t так и не перешла в другое соседнее состояние – ни в S ₀, ни в S ₂. Вывести систему из состояния S ₁ можно суммарным простейшим потоком с интенсивностью (l ₁₀+ l ₁₂), поскольку суперпозиция простейших потоков также является простейшим потоком. На этом основании вероятность выхода из состояния S ₁ за малый промежуток времени D t приближенно равна (l ₁₀+ l ₁₂)D t. Тогда вероятность невыхода из этого состояния равна 1-(l ₁₀+ l ₁₂)D t. В соответствии с этим вероятность того, что система останется в состоянии S ₁ на основании теоремы умножения вероятностей, равна:

;

 

б) система находилась в соседнем состоянии S ₀ и за малое время D t перешла в состояние S ₁. Переход системы происходит под воздействием потока l ₀₁ с вероятностью, приближенно равной l ₀₁D t. Вероятность того, что система будет находиться в состоянии S ₁, в этом варианте равна p ₀(t) l ₀₁D t;

 

в) система находилась в состоянии S ₂и за время D t перешла в состояние S ₁под воздействием потока интенсивностью l ₂₁ c вероятностью, приближенно равной l ₂₁D t. Вероятность того, что система будет находиться в состоянии S ₁,равна p ₂(t) l2 ₀₁D t. Применяя теорему сложения вероятностей для этих вариантов, получим выражение:

 

,

 

которое можно записать иначе:

 

 

Переходя к пределу при D t ®0, (приближенные равенства перейдут в точные), получим производную первого порядка

что является дифференциальным уравнением.

 

Проводя рассуждения аналогичным образом для всех других состояний системы, получим систему дифференциальных уравнений, которые называются уравнениями А.Н. Колмогорова:

(7.2)

 

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

Уравнения Колмогорова дают возможность найти все вероятности состояний как функции времени. Особый интерес представляют вероятности системы p_i (t) в предельном стационарном режиме, т.е. при t ®¥, которые называются предельными (или финальными) вероятностями состояний. В теории случайных процессов доказывается, что если число состояний системы конечно и из каждого из них можно (за конечное число шагов) перейти в любое другое состояние, то предельные вероятности существуют.

Предельная вероятность состояния S_i имеет четкий смысл: она показывает среднее относительное время пребывания системы в этом состоянии. Например, если предельная вероятность состояния S ₀, т.е. р ₀=0,2, то это означает, что в среднем 20% времени система находится в состоянии S ₀.

Так как предельные вероятности постоянны, то, заменяя в уравнениях Колмогорова их производные нулевыми значениями, получим систему линейных алгебраических уравнений, описывающих стационарный режим. Для системы S с графом состояний, изображённом на рис. 7.1, такая система уравнений имеет вид:

(7.3)

 

Систему (7.3) можно составить непосредственно по размеченному графу состояний, если руководствоваться следующим правилом. Слева в уравнениях записывается предельная вероятность состояния p_i, умноженная на суммарную интенсивность всех потоков, ведущих из данного состояния, а справа - сумма произведений интенсивностей всех потоков, входящих в i -e состояние, на вероятности тех состояний, из которых эти потоки исходят.

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

Граф состояний процесса гибели и размножения имеет вид, показанный на рисунке 7.2:

 

Рисунок 7.2 - Граф состояний процесса гибели и размножения

 

Рассмотрим упорядоченное множество состояний системы S ₀, S ₁, S ₂, …, S_k. Переходы могут осуществляться из любого состояния только в состояния с соседними номерами, т.е. из состояния S_k возможны переходы только либо в состояние S_{k -1}, либо в состояние S_{k +1}.

Предположим, что все потоки событий, переводящие систему по стрелкам графа, простейшие. По графу, представленному на рис. 2, составим и решим уравнения для предельных вероятностей состояний (их существование вытекает из возможности перехода из каждого состояния в каждое другое и конечности числа состояний). В соответствии с правилом составления таких уравнений получим: для состояния S ₀:

(7.4)

 

для состояния S ₁:

 

(7.5)

 

которое с учётом (4) приводится к виду

 

(7.6)

 

Аналогично, записывая уравнения для предельных вероятностей других состояний, можно получить следующую систему уравнений:

(7.7)

 

к которой добавляется нормировочное условие

(7.8)

 

Решая систему (7.7), (7.8), получим

 

(7.9)

(7.10)

 

Легко заметить, что в формулах (7.10) для р ₁, р ₂, …, р_n, коэффициенты при р ₀ есть слагаемые, стоящие после единицы в формуле (5). Числители этих коэффициентов представляют произведение всех интенсивностей, стоящих у стрелок, ведущих слева направо до данного состояния S_k, k =1, 2, …, n, а знаменатели - произведение всех интенсивностей, стоящих у стрелок, ведущих справа налево до состояния S_k.

Рассмотрим следующий пример. Узел расчёта состоит из двух кассовых аппаратов, размеченный граф которого имеет вид, изображённый на рисунке 7.3.

Рисунок. 7.3 - Граф состояний работы узла расчёта

 

Найдём предельные вероятности состояний p ₀, p ₁, p ₂при следующих исходных данных:

- S ₀ - состояние, когда обе кассы свободны;

- S ₁ - одна касса занята (любая из двух);

- S ₂ - обе кассы заняты;

- l ₀=1 покупатель в минуту;

- l ₁=0,8 покупателя в минуту;

- m ₀=0,6 покупателя в минуту;

- m ₁=0,6 покупателя в минуту,

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

 

Система уравнений Колмогорова для данного узла получена ранее (7.3). Заменив в ней второе уравнение на нормировочное условие (7.1), получим следующую систему:

 

В результате решения этой системы получим следующие значения предельных вероятностей: р ₀=0,204; р ₁=0,341; р ₂=0,455.Это означает, что доля времени, когда узел простаивает (нет покупателей) составляет 20,4% всего рабочего времени, 34,1% - обслуживается один покупатель и 45,5% - обе кассы заняты обслуживанием покупателей.

 

 

Контрольные вопросы

 

1. Какой граф называется размеченным?

2. В чём суть нормировочного условия?

3. Сформулируйте правило составления уравнений Колмогорова.

4. Поясните граф состояний процесса гибели и размножения.

5. Составьте и решите систему уравнений Колмогорова для изображённого на рисунке 7.4 графа при

l ₀₁=l, l ₀₂=2, l ₁₀=2, l ₁₃=2, l ₂₀=3, l ₂₃=1, l ₃₁=3, l ₃₂=2.

 

Рисунок. 7.4 - Граф состояний работы узла расчёта

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