Дисциплина: Теория случайных процессов

1.1 Основные понятия систем массового обслуживания

Система массового обслуживания -- математический (абстрактный) объект, элементами которого являются (рис. 1.1.):

* входной (входящий) поток заявок (требований) на обслуживание;

* приборы (каналы) обслуживания;

* очередь заявок, ожидающих обслуживания;

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

* поток заявок на дообслуживание после прерывания обслуживания;

* поток необслуженных заявок.

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

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

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

Обслуживание -- задержка заявки в обслуживающем приборе на некоторое время.

Длительность обслуживания -- время задержки (обслуживания) заявки в приборе.

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

Заявка, поступившая в СМО, может находиться в двух состояниях:

1) обслуживания (в приборе);

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

Заявки, находящиеся в накопителе и ожидающие обслуживания, образуют очередь заявок. Количество заявок в накопителе, ожидающих обслуживания, -- длина очереди.

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

Дисциплина обслуживания -- правило выбора заявок из очереди для обслуживания в приборе.

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

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

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

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

В системах ИМ при реализации СМО принимаются следующие ограничения и допущения:

· * поступившая в систему заявка мгновенно попадает на обслуживание, если в очереди нет заявок и прибор свободен;

· * в приборе на обслуживании в каждый момент времени может находиться только одна заявка;

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

· * поступление заявок в СМО и длительности их обслуживания не зависят от числа заявок, уже находящихся в системе, или от каких- либо других факторов;

· * длительность обслуживания заявок не зависит от интенсивности поступления заявок в систему.

Остановимся на некоторых элементах СМО более подробно.

Входной (входящий) поток заявок. Потоком событий называется последовательность однородных событий, следующих одно за другим и происходящих в какие-то, вообще говоря, случайные моменты времени. Если событие заключается в появлении заявок, имеем поток заявок. Для описания потока заявок в общем случае необходимо задать интервалы времени т = t_k - t_k-1 между соседними моментами t_k__k и t_k поступления заявок с порядковыми номерами к - 1 и к соответственно (к -- 1, 2,...; t₀ -- 0 -- начальный момент времени).

Основной характеристикой потока заявок является его интенсивность X -- среднее число заявок, поступающих на вход СМО за единицу времени. Величина T = 1/Х определяет средний интервал времени между двумя последовательными заявками.

Поток называется детерминированным, если интервалы времени T_к между соседними заявками принимают определенные заранее известные значения. Если при этом интервалы одинаковы (х_к = T для всех к = 1, 2,...), то поток называется регулярным. Для полного описания регулярного потока заявок достаточно задать интенсивность потока X или значение интервала T = 1/Х.

Поток, в котором интервалы времени х_к между соседними заявками представляют собой случайные величины, называется случайным. Для полного описания случайного потока заявок в общем случае необходимо задать законы распределений F_fc(x_fc) каждого из интервалов времени х_к, к = 1,2,....

Случайный поток, в котором все интервалы времени х_ь х₂,... между соседними последовательными заявками представляют собой независимые случайные величины, описываемые функциями распределений FjCij, F₂(x₂),... соответственно, называется потоком с ограниченным последействием.

Случайный поток называется рекуррентным, если все интервалы времени х_ь T₂,... между заявками распределены по одному и тому же закону F(t). Рекуррентных потоков много. Каждый закон распределения порождает свой рекуррентный поток. Рекуррентные потоки иначе называют потоками Пальма.

Если интенсивность X и закон распределения F(t) интервалов между последовательными заявками не меняются со временем, то поток заявок называется стационарнъш. В противном случае поток заявок является нестационарным.

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

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

Стационарный ординарный поток без последействия называется простейшим.

Интервалы времени т между заявками в простейшем потоке распределены по экспоненциальному (показательному) закону: с функцией распределения F(t) = 1 - е~^м; плотностью распределения/(f) = Хе~'^л, где X > 0 -- параметр распределения -- интенсивность потока заявок.

Простейший поток часто называют пуассоновским. Название происходит от того, что для этого потока вероятность P_fc(At) появления ровно к заявок за некоторый интервал времени At определяется законом Пуассона:

Размещено на http://www.allbest.ru/

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

* стационарным, если интенсивность X не меняется со временем;

* нестационарным, если интенсивность потока зависит от времени: X = >.(t).

В то же время простейший поток, по определению, всегда является стационарным.

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

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

Сумма N независимых стационарных ординарных потоков с интенсивностями Х_ь Х₂,..., X_N образует простейший поток с интенсивностью

N X=Y,^i

при условии, что складываемые потоки оказывают более или =1 менее одинаково малое влияние на суммарный поток. На практике суммарный поток близок к простейшему при N > 5. Значит, при суммировании независимых простейших потоков суммарный поток будет простейшим при любом значении N.

2. Вероятностное разрежение потока. Вероятностное (но не детерминированное) разрежение простейшего потока заявок, при котором любая заявка случайным образом с некоторой вероятностью р исключается из потока независимо от того, исключены другие заявки или нет, приводит к образованию простейшего потока с интенсивностью X* = рХ, где X -- интенсивность исходного потока. Поток исключенных заявок с интенсивностью X** = (1 - р)Х -- тоже простейший поток.

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

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

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

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

Важной характеристикой входного потока является коэффициент вариации

Размещено на http://www.allbest.ru/

где т_инт -- математическое ожидание длины интервала; о -- среднее квадратическое отклонение длины интервала х_инт (случайной величины).

Для простейшего потока (а =--, т = --) имеем v = 1. Для большинства X X реальных потоков 0 < v < 1. При v = 0 поток регулярный, детерминированный. Коэффициент вариации -- характеристика, отражающая степень неравномерности поступления заявок.

Каналы (приборы) обслуживания. Основная характеристика канала -- длительность обслуживания.

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

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

Размещено на http://www.allbest.ru/

где ц -- интенсивность обслуживания, здесь р = _---; т₀бсл -- математическое ожидание времени обслуживания.

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

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

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

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

Способы управления потоками заявок определяются дисциплинами:

* буферизации;

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

Дисциплины буферизации и обслуживания могут быть классифицированы по следующим признакам:

* наличие приоритетов между заявками разных классов;

* способ вытеснения заявок из очереди (для дисциплин буферизации) и назначения заявок на обслуживание (для дисциплин обслуживания);

* правило вытеснения или выбора заявок на обслуживание;

* возможность изменения приоритетов.

Вариант классификации дисциплин буферизации (постановки в очередь) в соответствии с перечисленными признаками представлен на рис. 1.2.

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

По способу вытеснения заявок из накопителя можно выделить следующие классы дисциплин буферизации:

* без вытеснения заявок -- заявки, поступившие в систему и заставшие накопитель полностью заполненным, теряются;

* с вытеснением заявки данного класса, т.е. такого же класса, что и поступившая заявка;

* с вытеснением заявки из класса самого низкого приоритета;

* с вытеснением заявки из группы классов низких приоритетов.

Рис. 1.2 Вариант классификации дисциплин буферизации

Дисциплины буферизации могут использовать следующие правила вытеснения заявок из накопителя:

* случайное вытеснение;

* вытеснение последней заявки, т.е. поступившей в систему позже всех;

* вытеснение «долгой» заявки, т.е. находящейся в накопителе дольше всех поступивших ранее заявок.

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

Иногда емкость накопителя в моделях полагают неограниченной, хотя в реальной системе она ограничена. Такое допущение оправдано, когда вероятность потери заявки в реальной системе из-за переполнения емкости накопителя меньше 10^_3. В этом случае дисциплина практически не влияет на показатели обслуживания заявок.

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

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

* одиночного режима;

* группового режима;

* комбинированного режима.

Рис. 1.3 Вариант классификации дисциплин обслуживания

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

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

Комбинированный режим -- комбинация одиночного и группового режимов, когда часть очередей заявок обрабатывается в одиночном режиме, а другая часть -- в групповом.

Дисциплины обслуживания могут использовать следующие правила выбора заявок на обслуживание.

Бесприоритетные (заявки не имеют привилегий на досрочное обслуживание -- захват ресурсов):

* обслуживание в порядке поступления -- заявка выбирается из очереди в режиме FIFO (first in --first out, первый вошел -- первый вышел);

* обслуживание в обратном порядке -- заявка выбирается из очереди в режиме LIFO (last in -- first out, последний вошел -- первый вышел);

* обслуживание в случайном порядке -- заявка выбирается из очереди в режиме RAND (random -- случайным образом);

* обслуживание в циклическом порядке -- заявки выбираются в процессе циклического опроса накопителей в последовательности 1, 2,Н СН -- количество накопителей), после чего указанная последовательность повторяется;

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

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

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

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

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

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

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

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

* длительностью обслуживания;

* приоритетами.

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

Для математического описания дисциплин обслуживания со смешанными приоритетами используется матрица приоритетов, представляющая собой квадратную матрицу Q = (q,_;), i,j - 1,..., Я, Я -- число классов заявок, поступающих в систему.

Элемент q_(j матрицы задает приоритет заявок класса i по отношению к заявкам класса и может принимать следующие значения:

* 0 -- нет приоритета;

* 1 -- приоритет относительный;

* 2 -- приоритет абсолютный.

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

* q_n = 0, так как между заявками одного и того же класса не могут быть установлены приоритеты;

* если q₍j = 1 или 2, то q^ = 0, так как если заявки класса i имеют приоритет к заявкам класса j, то последние не могут иметь приоритет к заявкам класса i (i,j = 1,..., Я).

В зависимости от возможности изменения приоритетов в процессе функционирования системы приоритетные дисциплины буферизации и обслуживания делятся на два класса:

1) со статическими приоритетами, которые не изменяются со временем;

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

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

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

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

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

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

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

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

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

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

СеМО называют также многофазными СМО.

Пример построения ИМ СеМО мы рассмотрим позже.

Основными элементами СеМО являются узлы (У) и источники (генераторы) заявок (Г).

Узел сети -- это система массового обслуживания.

Источник -- генератор заявок, поступающих в сеть и требующих определенных этапов обслуживания в узлах сети.

Для упрощенного изображения СеМО используется граф.

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

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

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

1.2 Пуассоновский процесс

Пуассоновский процесс, случайный процесс, описывающий моменты наступления 0 < t₁ <...< t_n <...<... каких-либо случайных событий, в котором число событий, происходящих в течение любого фиксированного интервала времени, имеет Пуассона распределение и независимы числа событий, происходящих в непересекающиеся промежутки времени.

Пусть m(s, t) -- число событий, моменты наступления которых t_i удовлетворяют неравенствам 0 Ј s < t_i Ј t, и пусть l(s, t) -- математическое ожидание m(s, t). Тогда при любых 0 Ј s₁ < t₁ Ј s₂ < t₂ Ј... Ј s_r < t_r случайные величины m(s₁, t₁), m(s₂, t₂),... m(s_r, t_r) независимы и вероятность того, что m(s, t) = n, равна

e^{-l (s, t)} [l(s, t)] ⁿ /n!.

В однородном l(s, t) = a (t -- s), где а -- среднее число событий в единицу времени, расстояния t_n -- t_n-1 между соседними моментами t_n независимы и имеют показательное распределение с плотностью ae^-at, t і 0.

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

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

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

1.3 Цепи Маркова

Цепь Маркова -- последовательность случайных событий с конечным или счётным числом исходов, где вероятность наступления каждого события зависит только от состояния, достигнутого в предыдущем событии^[1]. Характеризуется тем свойством, что, говоря нестрого, при фиксированном настоящем будущее независимо от прошлого. Названа в честь А. А. Маркова (старшего), который впервые ввёл это понятие в работе 1906 года.^[2]

Цепь Маркова с дискретным временем

Последовательность дискретных случайных величин { X n } n ? 0 {\displaystyle \{X_{n}\}_{n\geqslant 0}} называется простой цепью Маркова (с дискретным временем), если

P ( X n + 1 = i n + 1 ? X n = i n, X n ? 1 = i n ? 1, …, X 0 = i 0 ) = P ( X n + 1 = i n + 1 ? X n = i n ) {\displaystyle \mathbb {P} (X_{n+1}=i_{n+1}\mid X_{n}=i_{n},X_{n-1}=i_{n-1},\ldots,X_{0}=i_{0})=\mathbb {P} (X_{n+1}=i_{n+1}\mid X_{n}=i_{n})}

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

Область значений случайных величин { X n } {\displaystyle \{X_{n}\}} называется пространством состояний цепи, а номер n {\displaystyle n} n -- номером шага.

Переходная матрица и однородные цепи

Матрица P ( n ) {\displaystyle P{(n)}} P(n), где

P i j ( n ) ? P ( X n + 1 = j ? X n = i ) {\displaystyle P_{ij}{(n)}\equiv \mathbb {P} (X_{n+1}=j\mid X_{n}=i)}

называется матрицей переходных вероятностей на n n {\displaystyle n} -м шаге, а вектор

p = ( p 1, p 2, … ) ? {\displaystyle \mathbf {p} =(p_{1},p_{2},\ldots )^{\top }} ,

где p i ? P ( X 0 = i ) {\displaystyle p_{i}\equiv \mathbb {P} (X_{0}=i)}

-- начальным распределением цепи Маркова.

Очевидно, матрица переходных вероятностей является стохастической, то есть

? j P i j ( n ) = 1, ? n ? N {\displaystyle \sum \limits _{j}P_{ij}(n)=1,\quad \forall n\in \mathbb {N} }

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

P i j ( n ) = P i j, ? n ? N {\displaystyle P_{ij}{(n)}=P_{ij},\quad \forall n\in \mathbb {N} }

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

Конечномерные распределения и матрица перехода за n шагов

Из свойств условной вероятности и определения однородной цепи Маркова получаем:

P ( X n = i n, …, X 0 = i 0 ) = P i n ? 1, i n ? P i 0, i 1 P i 0 {\displaystyle \mathbb {P} (X_{n}=i_{n},\ldots,X_{0}=i_{0})=P_{i_{n-1},i_{n}}\cdots P_{i_{0},i_{1}}P_{i_{0}}}

откуда вытекает специальный случай уравнения Колмогорова -- Чепмена:

P ( X n = i n ? X 0 = i 0 ) = ( P n ) i 0, i n {\displaystyle \mathbb {P} (X_{n}=i_{n}\mid X_{0}=i_{0})=(P^{n})_{i_{0},i_{n}}}

то есть матрица переходных вероятностей за n {\displaystyle n} n шагов однородной цепи Маркова есть n {\displaystyle n} n-я степень матрицы переходных вероятностей за 1 шаг. Наконец,

P ( X n = i n ) = ( ( P T ) n p ) i n {\displaystyle \mathbb {P} (X_{n}=i_{n})=\left((P^{T})^{n}\mathbf {p} \right)_{i_{n}}}

система массовый обслуживание заявка

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

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

- системы массового обслуживания с отказами, в которых заявка, поступившая в систему в момент, когда все каналы заняты, получает отказ и сразу же покидает очередь;

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

В системах с ограниченным ожиданием может ограничиваться:

-длина очереди;

-время пребывания в очереди.

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

Все системы массового обслуживания различают по числу каналов обслуживания:

- одноканальные системы;

-многоканальные системы.

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

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

Современная теория систем массового обслуживания является совокупностью аналитических методов исследования.

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

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

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

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

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

-среднее время ожидания в очереди;

-закон распределения времени ожидания;

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

-закон распределения числа заявок в очереди;

-средний доход, приносимый СМО в единицу времени и т. д.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2. Практическая часть

2.1 Анализ реальной системы массового обслуживания

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

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

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

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

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

Было рассмотрена программа Notion, которое используется в реальном времени в деятельности Международного студенческого клуба СибГУ им. М.Ф. Решетнева.

Notion объединяет в себе огромное количество инструментов. Заметки и списки дел, документы и таблицы, канбан-доски и базы знаний -- здесь есть всё, с чем нам приходится иметь дело ежедневно.

Сервис представляет всё это в виде единого рабочего пространства. Подобно деталям LEGO, в него легко добавить нужные элементы и собрать свой идеальный инструмент продуктивности для хранения идей, планирования и совместной работы с коллегами. Интерфейс Notion изображен на (рис. 2.).

Рис. 2 Интерфейс программы Notion

Можно сравнить Notion с гибридом Evernote, Google Docs, Trello и Todoist. Главная цель приложения -- заменить множество сервисов для решения конкретных задач, чтобы сделать работу проще и удобнее.

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

Как этот инструмент работает

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

Весь контент здесь хранится на страницах, которые состоят из разнообразных блоков -- главной сущности сервиса. Ими могут быть тексты, списки, код, изображения или ссылки, которые показаны на (рис.2.1.).

В любой момент блоки легко трансформировать, за секунду превратив маркированный список в контрольный, а текст -- в отдельную страницу, блок кода или цитату.

Рис. 2.1 Функциональность программы

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

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

Для чего можно использовать Notion