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

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

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

, .

Здесь - плотность распределения Эрланга; - параметр распределения; - порядок распределения. При распределение Эрланга совпадает с экспоненциальными моментами поступления заявок потока Эрланга представляются в виде суммы независимых случайных величин, имеющих показательное распределение с параметром .

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

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

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

5.10. Задача: Марковская модель рождения и гибели

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

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

Постановка задачи синтеза модели.

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

, , (5.79)

где - вероятности перехода.

Уравнение (5.79) справедливо также и для безусловных вероятностей состояний

. (5.80)

Рассмотрим дискретную последовательность процесс , в которой допускаются как положительные, так и отрицательные скачки. Эта последовательность называется процессом рождения и гибели и определяется следующими постулатами: 1) если в момент времени система находится в состоянии , то вероятность перехода в малом интервале времени равна ; 2) если в момент времени система находится в состоянии , то вероятность перехода в интервале времени равна ; 3) вероятность перехода в состояние, отличное от двух соседних, есть ; 4) вероятность сохранения прежнего состояния равна
; 5) состояние является поглощающим; если изображающая точка попала в это состояние, то процесс прекращается.

Решение . На основании постулатов 1-5 записываем уравнение (5.80):

, (5.81)

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

. (5.82)

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

(5.83)

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

, , (5.84)

где , . (5.85)

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

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

Задача анализа СМО заключается в определении ряда показателей ее эффективности, которые можно разделить на следующие группы:

показатели, характеризующие систему в целом: число n занятых каналов обслуживания, число обслуженных (λ b ), ожидающих обслуживание или получивших отказ заявок (λ c ) в единицу времени и т.д.;
вероятностные характеристики : вероятность того, что заявка будет обслужена (P обс) или получит отказ в обслуживании (P отк), что все приборы свободны (p 0) или определенное число их занято (p k ), вероятность наличия очереди и т.д.;
экономические показатели : стоимость потерь, связанных с уходом не обслуженной по тем или иным причинам заявки из системы, экономический эффект, полученный в результате обслуживания заявки, и т.д.

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

Многоканальная система с отказами

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

Смешанные системы

Система с ограничением на длину очереди .
Состоит из накопителя (очереди) и узла обслуживания. Заявка покидает очередь и уходит из системы, если в накопителе к моменту ее появления уже находятся m заявок (m – максимально возможноечисло мест в очереди). Если заявка поступила в систему и застала, хотя бы один канал свободным, она мгновенно начинает обслуживаться. Если в момент поступления заявки в систему все каналы заняты, то заявка не покидает систему, а занимает место в очереди. Заявка покидает систему не обслуженной, если к моменту её поступления в систему заняты все каналы обслуживания и все места в очереди.
Для каждой системы определяется дисциплина очереди. Это система правил, определяющих порядок поступления заявок из очереди в узел обслуживания. Если все заявки и каналы обслуживания равнозначны, то чаще всего действует правило «кто раньше пришел, тот раньше обслуживается».
Система с ограничением на длительность пребывания заявки в очереди .
Состоит из накопителя (очереди) и узла обслуживания. От предыдущей системы она отличается тем, что заявка, поступившая в накопитель (очередь), может ожидать начала обслуживания лишь ограниченное время Т ож (чаще всего это случайная величина). Если её время Т ож истекло, то заявка покидает очередь и уходит из системы не обслуженной.

Математическое описание СМО

СМО рассматриваются как некоторые физические системы с дискретными состояниями х 0 , х 1 , …, х n , функционирующие при непрерывном времени t . Число состояний n может быть конечным или счетным (n → ∞). Система может переходить из одного состояния х i (i= 1, 2, … , n) в другое х j (j= 0, 1, … ,n) в произвольный момент времени t . Чтобы показать правила таких переходов, используют схему, называемую графом состояний . Для типов перечисленных выше систем графы состояний образуют цепь, в которой каждое состояние (кроме крайних) связано прямой и обратной связью с двумя соседними состояниями. Это схема гибели и размножения.
Переходы из состояния в состояние происходят в случайные моменты времени. Удобно считать, что эти переходы происходят в результате действия каких-то потоков (потоков входных заявок, отказов в обслуживании заявок, потока восстановления приборов и т.д.). Если все потоки простейшие, то протекающий в системе случайный процесс с дискретным состоянием и непрерывным временем будет марковским.
Поток событий - это последовательность однотипных событий, протекающих в случайные моменты времени. Его можно рассматривать как последовательность случайных моментов времени t 1 , t 2 , … появления событий.
Простейшим называют поток, обладающий следующими свойствами:

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

В простейшем потоке интервалы времени Т 1 , Т 2 ,… между моментами t 1 , t 2 , … появления событий случайны, независимы между собой и имеют показательное распределение вероятностей f(t)=λe -λt , t≥0, λ=const, где λ - параметр показательного распределения, являющийся одновременно интенсивностью потока и представляющий собой среднее число событий, происходящих в единицу времени. Таким образом, .
Марковские случайные события описываются обыкновенными дифференциальными уравнениями . Переменными в них служат вероятности состояний р 0 (t), p 1 (t),…,p n (t) .
Для очень больших моментов времени функционирования систем (теоретически при t → ∞) в простейших системах (системы, все потоки в которых – простейшие, а граф – схема гибели и размножения) наблюдается установившийся, или стационарный режим работы. В этом режиме система будет изменять свое состояние, но вероятности этих состояний (финальные вероятности ) р к , к= 1, 2 ,…, n, не зависят от времени и могут рассматриваться как среднее относительное время пребывания системы в соответствующем состоянии.

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

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

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

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

Модель входного пуассоновского потока представляется функцией вида:

Следующее важное для исследования свойство, которым обладает пуассоновский поток, заключается в том, что процедура разделения и объединения дает снова пуассоновские потоки. Тогда, если входной поток формируется из N независимых источников, каждый из которых порождает пуассоновский поток интенсивностью λ i (i =1,2,…, N ) , то его интенсивность будет определяться по формуле:

В случае разделения пуассоновского потока на N независимых потоков, получим, что интенсивность потока λ i будет равна r i λ , где r i – доля i – го потока во входном потоке требований.

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

Процесс обслуживания . Основным параметром процесса обслуживания считается время обслуживания требования каналом j - t j (j =1,2,…, m ) . Величина τ j в каждом конкретном случае определяется рядом факторов: интенсивностью поступления заявок, квалификацией исполнителя, технологией работ, окружающей средой и т.д. Законы распределения случайной величины τ j могут быть самыми различными, но наибольшее распространение в практических приложениях получил экспоненциальный закон распределения. Функция распределения случайной величины τ j имеет вид:

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

Если СМО состоит из неоднородных каналов, то
, если же все каналы однородные, то
.

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

,
	W S - среднее время пребывания требования в системе.

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

система с потерями или отказами;

система с ожиданием;

система с ограниченным временем ожидания (ВО);

система с ограниченной длиной очереди (ДО).

По числу каналов обслуживания системы делятся на одноканальные (m =1 ) и многоканальные (m >1 ). Структура СМО и характеристика ее объектов представлена на рисунке 1.21.

Одной из форм классификации СМО служит кодовая классификация Д. Кендалла. В соответствии с этой классификацией характеристику СМО записывают в виде трех, четырех или пяти символов. Например, a / b / c , где a – тип распределения входного потока требований, b – тип распределения времени обслуживания, c – число каналов обслуживания. Для пуассоновского и экспоненциального распределений принимают символ M , для любого произвольного распределения G . Например, запись М/М/2 означает, что входной поток требований пуассоновский, время обслуживания распределено по экспоненциальному закону, в системе имеются два канала. Четвертый символ (d) указывает допустимую длину очереди, пятый (e) – порядок отбора требований.

Рисунок 1.21 – Структура и характеристика объектов СМО

Модели СМО могут быть детерминированными или вероятностными. В первом случае параметры и переменные модели – это постоянные величины, во втором – случайные.

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

1. При установленных или проектных параметрах входящего потока:

а) вероятность поступления n требований в систему за период t (P n (T )) ;

б) вероятность наличия n требований в системе (P n ) .

2. При установленных или проектных параметрах обслуживания:

а) вероятность того, что все обслуживающие m каналов свободны (P 0 ) ;

б) вероятность того, что обслуживанием занято определенное число каналов (менеджеров, агентов) (P m ) ;

в) вероятность того, что r требований находится в очереди (P m + r ) .

3. При установленных или проектных параметрах входящего потока и системы обслуживания:

б) среднее число каналов m , занятых обслуживанием: E (m )= m k ;

в) среднее число простаивающих каналов: E (m 0 )=(m - m k ) ;

г) коэффициент использования (занятости) канала (K S ) ;

д) коэффициент простоя (отказа) канала (K 0 ) ;

е) относительная (Q ) и абсолютная (A ) пропускная способность СМО;

ж) среднее число требований, находящихся в системе (L S ) ;

з) среднее число требований, ожидающих в очереди (L q ) ;

и) среднее время ожидания требования в очереди (W q ) ;

к) среднее время пребывания требования в системе (W S ) .

Рассмотрим приемы вычисления показателей первой группы на примере наиболее распространенной модели СМО (M / M / m ≥2 ) с ожиданием, содержащей m параллельных обслуживающих каналов. Здесь поступающие требования не теряются и оставляют систему лишь после обслуживания. Каналы выполняют однородные операции, и время обслуживания каждым каналом t распределено по экспоненциальному закону с параметром m , а входящий поток - пуассоновский с параметром λ ; дисциплина очереди не регламентирована, и отсутствует ограничение на число поступающих требований. Модель СМО представляется в виде системы уравнений для стационарного состояния.

Определение вероятности наличия n требований (P n ) в системе зависит от соотношений числа поступающих требований (n ) за единицу времени и количества каналов обслуживания (m ).

1. Для условия, когда m =1, P n определяется по формуле математического ожидания дискретной случайной величины.

2. Для условия, когда 1≤ n ≤ m (вероятность, что все требования на обслуживании или очереди нет), P n рассчитывается по формуле:

Если ρ/ m <1 , то вероятность отсутствия требований в системе P 0 определяется по формуле для стационарного режима:

или по формуле математического ожидания дискретной случайной величины:

Коэффициенты использования (загрузки) каналов и простоя каналов соответственно определяются по формулам:

и
.

Среднее число требований, ожидающих очереди, находится из выражения:

Среднее время ожидания в очереди составит:

Среднее время пребывания требования в системе рассчитывается по формуле:

Среднее число требований, находящихся в системе, определяется следующим образом:

Для общего случая L S определяется по формуле математического ожидания дискретной случайной величины:

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

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

Экономическая эффективность функционирования системы массового обслуживания составит:

Величина потерь определяется по следующим выражениям:

а) система с отказами:

б) система с ожиданием:

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

Пример 1.9. Требуется провести оценку эффективности централизации нескольких отделов или служб с однородными функциями. В качестве объекта рассматриваются две службы такси, которые приобрела компания «Автосервис». Заявки клиентов между службами распределяются поровну. Спрос на такси к диспетчеру поступает с частотой 10 вызовов в час. Среднее время обслуживания одного клиента составляет 11,5 минут. Вызовы такси распределены во времени по пуассоновскому закону, а продолжительность обслуживания одного клиента – по экспоненциальному закону. Каждая служба такси оснащена двумя автомобилями.

Возникает вопрос об экономической целесообразности централизации управления таксопарком. Для этого необходимо сравнить два варианта:

1) вариант с независимым обслуживанием системами типа (М/М/2 ) при λ=10 вызовов/час, τ=11,5 мин. и m = 2;

2) вариант с одной очередью типа (М/М/4 ) при λ=10*2=20 вызовов/час, τ=11,5 мин. и m = 4;

Для начала определим коэффициенты загруженности службы по первому и второму вариантам. При m = 2 имеем:

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

Вычислим W q (среднее время ожидания клиентом автомобиля-такси).

Для первого случая при m = 2 имеем ρ=1,917. Определим вероятность того, что в системе нет требований (P 0 ):

Используя значение P 0 определим W q :

ч.

Для второго случая при m = 4 имеем ρ=3,83 и определим P 0 :

При значении P 0 =0,0042, получим, что

ч.

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

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

Рис. 3.1. Схема СМО.

Поступающие на вход СМО однородные заявки в зависимости от порождающей причины делятся на типы, интенсивность потока заявок типа i (i=1…M) обозначено  i . Совокупность заявок всех типов - входящий поток СМО.

Обслуживание заявок выполняется m каналами. Различают универсальные и специализированные каналы обслуживания. Для универсального канала типа j считается известными функции распределения F ji () длительности обслуживания заявок произвольного типа. Для специализированных каналов функции распределения длительности обслуживания каналов заявок некоторых типов являются неопределёнными, назначение этих заявок на данный канал.

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

Q - схемы можно исследовать аналитически и имитационными моделями. Последнее обеспечивает большую универсальность.

Рассмотрим понятие массового обслуживания.

В любом элементарном акте обслуживания можно выделить две основные составляющие: ожидание обслуживания заявкой и собственно обслуживание заявки. Это можно отобразить в виде некоторого i-ого прибора обслуживания П i , состоящего из накопителя заявок, в котором может находится одновременно l i =0…L i H заявок, где L i H - ёмкость i-ого накопителя, и канала обслуживания заявок, k i .

Рис. 3.2. Схема прибора СМО

На каждый элемент прибора обслуживания П i поступают потоки событий: в накопитель H i поток заявок w i , на канал k i - поток обслуживания u i .

Потоком событий (ПС) называется последовательность событий, происходящих одно за другим в какие-то случайные моменты времени. Различают потоки однородных и неоднородных событий. Однородный ПС характеризуется только моментами поступления этих событий (вызывающими моментами) и задаётся последовательностью {t n }={0t 1 t 2 …t n …}, где t n - момент поступления n- ого события - неотрицательное вещественное число. ОПС может быть также задан в виде последовательности промежутков времени между n-ым и n-1-ым событиями { n }.

Неоднородным ПС называется последовательность {t n , f n } , где t n - вызывающие моменты; f n - набор признаков события. Например, может быть задана принадлежность к тому или иному источнику заявок, наличие приоритета, возможность обслуживания тем или иным типом канала и т.п.

Рассмотрим ОПС, для которого  i { n }- случайные величины, независимые между собой. Тогда ПС называется потоком с ограниченным последействием.

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

Если для любого интервала t событие P 0 (t, t) + P 1 (t, t) + Р  1 (t, t)=1, P 1 (t, t) - вероятность попадания на интервал t ровно одного события. Как сумма вероятностей событий, образующих полную группу и несовместных, то для ординарного потока событий P 0 (t, t) + P 1 (t, t)  1, Р  1 (t, t)=(t), где (t)- величина, порядок малости который выше, чем t, т.е. lim((t))=0 при t0.

Стационарным ПС называется поток, для которого вероятность появления того или иного числа событий на интервале времени  зависит от длины этого участка и не зависит от того, где на оси времени 0 - t взят этот участок. Для ОПС справедливо 0*P 0 (t, t) + 1*P 1 (t, t)= P 1 (t, t) - среднее число событий на интервале t. Среднее число событий, наступающих на участке t в единицу времени составляет P 1 (t, t)/t. Рассмотрим предел этого выражения при t0

lim P 1 (t, t)/t=(t)*(1/един.вр.).

Если этот предел существует, то он называется интенсивностью (плотностью) ОПС. Для стандартного ПС (t)==const.

Применительно к элементарному каналу обслуживания k i можно считать что поток заявок w i W, т.е. интервалы времени между моментами появления заявок на входе k i образуют подмножество неуправляемых переменных, а поток обслуживания u i U, т.е. интервалы времени между началом и окончанием обслуживания заявки образуют подмножество управляемых переменных.

Заявки, обслуженные каналом k i и заявки, покинувшие прибор П i по различным причинам не обслуженными, образуют выходной поток y i Y.

Процесс функционирования прибора обслуживания П i можно представить как процесс изменения состояний его элементов во времени Z i (t). Переход в новое состояние для П i означает изменение кол-ва заявок, которые в нём находятся (в канале k i и накопителе H i). Т.о. вектор состояний для П i имеет вид: , где- состояния накопителя, (=0 - накопитель пуст,=1- в накопителе одна заявка…,=- накопитель занят полностью;- состояние каналаk i (=0 - канал свободен,=1 канал занят).

Q-схемы реальных объектов образуются композицией многих элементарных приборов обслуживания П i . Если k i различных приборов обслуживания соединены параллельно, то имеет место многоканальное обслуживание (многоканальная Q-схема), а если приборы П i и их параллельные композиции соединены последовательно, то имеет место многофазное обслуживание (многофазная Q-схема).

Т.о. для задания Q-схемы необходимо оператор сопряжения R, отражающий взаимосвязь элементов структуры.

Связи в Q-схеме изображают в виде стрелок (линий потока, отражающих направление движения заявок). Различают разомкнутые и замкнутые Q-схемы. В разомкнутой выходной поток не может снова поступить на какой-либо элемент, т.е. обратная связь отсутствует.

Собственными (внутренними) параметрами Q-схемы будут являться кол-во фаз L Ф, количество каналов в каждой фазе, L kj , j=1… L Ф, количество накопителей каждой фазы L kj , k=1… L Ф, ёмкость i-ого накопителя L i H . Следует отметить, что в теории массового обслуживания в зависимости от ёмкости накопителя применяют следующую терминологию:

системы с потерями (L i H =0, накопитель отсутствует);

системы с ожиданием (L i H );

системы с ограниченной ёмкостью накопителя Н i (смешанные).

Обозначим всю совокупность собственных параметров Q-схемы как подмножество Н.

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

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

В зависимости от динамики приоритетов Q-схемы различают статические и динамические. Статические приоритеты назначаются заранее и не зависят от состояний Q-схемы, т.е. они являются фиксированными в пределах решения конкретной задачи моделирования. Динамические приоритеты возникают при моделировании. Исходя из правил выбора заявок из накопитель Н i на обслуживание каналом k i можно выделить относительные и абсолютные приоритеты. Относительный приоритет означает, что заявка с более высоким приоритетом, поступившая в накопитель Н, ожидает окончания обслуживания представляющей заявки каналом k i и только после этого занимает канал. Абсолютный приоритет означает, что заявка с более высоким приоритетом, поступившая в накопитель, прерывает обслуживание каналом k i заявки с более низким приоритетом и сами занимает канал (при этом вытесненная из k i заявка может либо покинуть систему, либо может быть снова записана на какое-то место в Н i).

Необходимо также знать набор правил, по которым заявки покидают Н i и k i: для Н i – либо правила переполнения, либо правила ухода, связанные с истечением времени ожидания заявки в Н i ; для k i – правила выбора маршрутов или направлений ухода. Кроме того, для заявок необходимо задать правила, по которым они остаются в канале k i , т.е. правила блокировок канала. При этом различают блокировки k i по выходу и по входу. Такие блокировки отражают наличие управляющих связей в Q‑схеме, регулирующих поток заявок в зависимости от состояний Q‑схемы. Набор возможных алгоритмов поведения заявок в Q‑схеме можно представить в виде некоторого оператора алгоритмов поведения заявок А.

Т.о. Q‑схема, описывающая процесс функционирования СМО любой сложности однозначно задаётся в виде набора множеств: Q = .

Потоки событий (требований)

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

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

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

Поток событий называется стационарным, если его вероятностные характеристики не зависят от времени.

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

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

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

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

для которого математическое ожидание случайной величины равно ее дисперсии:

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

В соответствии с этой формулой вероятность того, что на участке времени длиной t не появится ни одного из последующих событий, равна

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

Методы исследования СМО

Процессы массового обслуживания исследуются на основе двух методов:

1. Аналитического.
2. Метода статистического моделирования или метода Монте-Карло.

Каждый из этих методов имеет свои особенности и сферу практического применения.

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

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

Построение математической модели Монте-Карло состоит из следующих этапов:

1. Формирование целей задачи и выбор ограничительных условий функционирования системы обслуживания.
2. Проведение наблюдений за ходом производства, т.е. получение исходных данных.
3. Первичная обработка данных, построение рядов распределения и их графический анализ. Выдвижение гипотезы о характере закона распределения.
4. Построение теоретического распределения с параметрами данных эмпирического наблюдения.
5. Проверка соответствия теоретического и эмпирического распределения.

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

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

Рассмотрим, как происходит поиск этой кривой. Вначале собираются исходные данные, строится гистограмма и определяют закон распределения. Далее строится теоретическая кривая, параметры которой совпадают с параметрами эмпирического распределения. Для этого необходимо найти параметры эмпирического распределения и по ним построить теоретическую кривую. Выдвинуть форму гипотезы, найти параметры и построить кривую и далее проверить, насколько соответствует теоретическая кривая и эмпирическое распределение. Если они полностью совпадают, то, значит, закон найден. Но если между теоретической кривой и эмпирической гистограммой имеются различия, необходимо проверить на сколько существенны эти различия. Если они носят случайный характер, тогда можно считать, что эмпирическое распределение описывается данной теоретической кривой. Если же различия очень велики, значит, теоретический закон подобран в данном случае неверно, и нужно искать новый закон распределения. Для оценки существенности различий теоретической кривой и эмпирического распределения используется два критерия X2 (х-квадрат) Пирсона и λ лямбда Колмогорова. X2 определяется по следующей формуле:

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

В результате получаем теоретически накопленные частоты.

Оценка на основе критерия х2 производится следующим образом. После того, как найдено х определяют число степеней свободы К, которое равно числу интервалов минус число статистических характеристик, использованных при расчете распределения (параметров). При нормальном законе - три (x,σ,N) параметра, а при распределении Пуассона - два (λ и N) параметра. Для полученных величин X2 и числа степеней свободы К по таблицам отыскивается вероятность Рх2 того, что различие между теоретическим и эмпирическим распределениями носит случайный характер. Если Рх2 больше 0,05 или 5%, можно считать, что эта вероятность достаточно велика, чтобы не исключать случайного характера различий и поэтому распределение считают подчиняющимся данному теоретическому закону. Если же Рх2 меньше 5 %, то считается, что теоретическое и эмпирическое распределение не совпадают и тогда нужно искать новое теоретическое распределение. Значения Рх2 содержатся в специальных таблицах с двумя входами: один соответствует х2, второй - К. На их пересечении Рх2. Проверка по критерию λ. производится так: вначале определяют

После того, как найдена А, по таблицам находят Р (λ). И, если оно больше 0,05, считают, что различия распределения носят случайный характер, если меньше, то не случайный. Критерий λ по сравнению х2 являются менее жестким, т. е. обычно он показывает большую вероятность того, что различие между распределениями носит случайный характер. Это объясняется тем, что для использования критерия λ нужно дополнительное условие, а именно, теоретический анализ должен показать, что эмпирическое распределение должно подчиняться данному закону.

Рис.6.3.

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

Преобразование равновероятных случайных чисел в числа, подчиняющиеся установленному ранее закону распределения

Имеется несколько переходов от нормально распределенных чисел к случайным числам.

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

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

Поскольку вероятность любого значения от 0 до 1, т. е. 0 ≤ F(t) < 1, может быть рассчитано с любой точностью до 2, 3 и т.д. знаков. Найдя по таблице случайных чисел значения случайных чисел, можно приравнять их к величинам F(t)t и известным значениям x и σ значения χ. Эти значения χ и представляют собой случайные величины промежутков между обслуживанием или длительность обслуживания, подчиняющимся закону нормального распределения С параметрами σ и χ. Такой метод очень трудоемкий, и поэтому на практике употребляется графический метод как наиболее удобный.

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

1. Потери и затраты состоят из затрат на обслуживание (зарплата наладчиков) и потерь, связанных с простоями.
2. Экономически наибольшую сложность представляет определение потерь от простоев.
3. Важно установить, сколько нужно произвести испытаний, чтобы определить норму обслуживания. Жесткой цифры нет.

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

Затем сравниваем tрасч с табличным значением. Если tрасч больше табличного, значит, расхождения между средними велики. Это говорит о том, что испытаний в таком случае недостаточно. Испытания продолжают и затем делают снова проверку.

Величина t находится по таблицам Стьюдента в зависимости от вероятности возможной ошибки. Обычно в пределах 5 % и от числа степеней свободы.

Задачи, решаемые методами теории массового обслуживания

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

Другое