Методы теории массового обслуживания в сфере безопасности. Преобразование равновероятных случайных чисел в числа, подчиняющиеся установленному ранее закону распределения. Модели сетевого планирования
При решении многих задач оптимальной организации торговли, бытового обслуживания, складского хозяйства и т.п. часто используется интерпретация производственной структуры как системы массового обслуживания (СМО), т.е.системы в которой с одной стороны, постоянно возникают запросы на выполнение каких-либо работ, а с другой стороны происходит постоянное удовлетворение этих запросов.
Всякая СМО включает 4 элемента:
1) источник требований (ИТ);
2) входящий поток требований;
3) система обслуживания, которая включает в себя:
· очередь,
· обслуживающее устройство (каналы обслуживания);
4) выходящий поток требований.
Требованием называется каждый отдельный запрос на выполнение какой-либо работы. Поступив в обслуживающую систему, требование (заявка) на обслуживание присоединяется к очереди других ранее поступивших требований и ждет обслуживания. Блок обслуживания выбирает очередное требование и начинает его обслуживать. После завершения обслуживания обслуживающая система приступает к обслуживанию следующего требования. Этот цикл работы СМО многократно повторяется.
К основным характеристикам СМО относятся:
· среднее число заявок находящихся в системе;
· среднее число заявок в очереди (ее длина);
· средняя продолжительность пребывания клиента в системе;
· средняя продолжительность пребывания клиента в очереди;
· среднее количество занятых средств обслуживания;
· среднее время обслуживания;
· вероятность отказа в обслуживании и др.
Для классификации СМО используется ряд признаков:
1. В зависимости от условий ожидания начала обслуживания различают:
· СМО с отказами (потерями) – требования получившие отказ (каналы заняты) теряются;
· СМО с ожиданием - требования становятся в очередь и ожидают обслуживания, такие СМО делятся на:
o СМО с ограниченной длиной очереди;
o СМО с неограниченной длиной очереди;
o СМО с ограниченным временем ожидания.
2. По числу каналов обслуживания различают два вида СМО:
· одноканальные;
· многоканальные.
3. По месту нахождения источника требования (ИТ) СМО делятся на два вида:
· разомкнутые – ИТ вне системы;
· замкнутые – ИТ в составе системы.
4. По дисциплине обслуживания (в зависимости от порядка выбора заявок на обслуживание) выделяют:
· СМО с приоритетом – вначале обслуживаются заявки с более высоким приоритетом;
· СМО без приоритета – приоритет в обслуживании заявок отсутствует.
Методы и модели исследования СМО можно разделить на
· аналитические;
· статистические.
Аналитические методы позволяют получить характеристики СМО как функции её параметров, но применимы эти методы к ограниченному кругу задач теории массового обслуживания (ТМО).
Простейший поток требований
В настоящее время достаточно хорошо разработана ТМО применительно к простейшему (Пуассоновскому) потоку заявок на обслуживание.
Для простейшего потока частота поступления требований в систему подчиняется закону Пуассона, то есть вероятность поступления за время t ровно k требований задается формулой , где λ – параметр потока (число требований, поступающих в единицу времени).
Основные свойства простейшего потока:
Ординарность – практическая невозможность одновременного поступления двух и более требований.
Стационарность – означает, что среднее число требований (математическое ожидание) поступающих в систему в ед. времени (λ=const ) не меняется во времени.
Отсутствие последействия – число требований, поступивших в систему до момента времени t не определяет того, сколько требований поступит в систему за промежуток времени от t до t + Δt .
Время обслуживания требований в системе
Важной характеристикой СМО является время обслуживания одного требования в системе. Оно является случайной величиной и может быть описано законом распределения.
Наиболее часто рассматривается как случайная величина (СВ), которая подчиняется экспоненциальному закону распределения.
Для этого закона функция распределения вероятности имеет вид: 
, т.е. вероятность того, что время обслуживания не превосходит некоторой величины t
, определяется формулой , где μ
– параметр экспоненциального закона распределения времени обслуживания требований в системе – т.е. величина, обратная среднему времени обслуживания одного требования , т.е. .
4 – Основы теории массового обслуживания.
Определение 1. Пусть имеется некоторая физическая система S , которая с течением времени меняет свое состояние (переходит из одного состояния в другое), причем заранее неизвестным, случайным образом. Тогда мы будем говорить, что в системе S протекает случайный процесс.
Под «физической системой» можно понимать что угодно: техническое устройство, предприятие, живой организм и т.д.
Пример. S – техническое устройство, состоящее из ряда узлов, которые время от времени выходят из строя, заменяются или восстанавливаются. Процесс, протекающий в системе, – случайный. Вообще, если подумать, труднее привести пример «неслучайного» процесса, чем случайного. Даже процесс хода часов – классический пример точной, строго выверенной работы («работают как часы») подвержен случайным изменениям (уход вперед, отставание, остановка).
Определение 2. Случайный процесс, протекающий в системе, называется марковским, если для любого момента времени t 0 вероятностные характеристики процесса в будущем зависят только от его состояния в данный момент t 0 и не зависят от того, когда и как система пришла в это состояние.
Пусть в настоящий момент t 0 система находится в определенном состоянии S 0 . Мы наблюдаем процесс со стороны и в момент t 0 знаем состояние системы S 0 и всю предысторию процесса, все, что было при t < t 0 . Нас, естественно. Интересует будущее: t > t 0 . Можем ли мы его предугадать? В точности – нет. Наш процесс случайный, следовательно – непредсказуемый. Но какие-то вероятностные характеристики процесса в будущем мы найти можем. Например, вероятность того, что через некоторое время t система S окажется в состоянии S 1 или сохранит состояние S 0 и т.д.
Если процесс марковский, то предсказывать можно, только учитывая настоящее состояние системы S 0 и забыв о его «предыстории» (поведение системы при t < t 0 ). Само состояние S 0 , разумеется, зависит от прошлого, но как только оно достигнуто, о прошлом можно забыть. Т.е. в марковском процессе «будущее зависит от прошлого только через настоящее» .
Пример. Система S – счетчик Гейгера, на который время от времени попадают космические частицы; состояние системы в момент времени t характеризуется показаниями счетчика – числом частиц, пришедших до данного момента. Пусть в момент t 0 счетчик показывает S 0 . Вероятность того, что в в момент t > t 0 счетчик покажет то или другое число частиц S 1 (или менее S 1 ) зависит от S 0 , но не зависит от того, в какие именно моменты приходили частицы до момента t 0 .
На практике часто встречаются процессы, которые если не в точности марковские, то могут быть в каком-то приближении рассмотрены как марковские. Например, S – группа самолетов, участвующих в воздушном бою. Состояние системы характеризуется числом самолетов «красных» – x и «синих» – y , сохранившихся (не сбитых) к какому-то моменту. В момент t 0 нам известны численности сторон x 0 и y 0 . Нас интересует вероятность того, что в какой-то момент времени t 0 + t численный перевес будет на стороне «красных». От чего зависит эта вероятность? В первую очередь от того, в каком состоянии находится система в данный момент времени t 0 , а не от того, когда и в какой последовательности погибали сбитые до момента времени t 0 самолеты.
В сущности любой процесс можно рассматривать как марковский, если все параметры из «прошлого», от которых зависит «будущее», перенести в «настоящее». Например, пусть речь идет о работе какого-то технического устройства; в какой-то момент времени t 0 оно ещё исправно, и нас интересует вероятность того, что оно проработает ещё время t . Если за настоящее время считать просто «система исправна», то процесс безусловно не марковский, потому что вероятность, что она не откажет за время t , зависит, в общем случае, от того, сколько времени она уже проработала и когда был последний ремонт. Если оба эти параметра (общее время работы и время после ремонта) включить в настоящее состояние системы. То процесс можно будет считать марковским.
Определение 3. Процесс называется с дискретными состояниями, если его возможные состояния S 1 , S 2 ,... можно заранее перечислить (перенумеровать), и переход системы из состояния в состояние происходит «скачком», практически мгновенно.
Определение 4. Процесс называется процессом с непрерывным временем, если моменты возможных переходов из состояния в состояние не фиксированы заранее, а неопределенны, случайны, если переход может осуществиться, в принципе, в любой момент.
Мы будем рассматривать только процессы с дискретными состояниями.
Пример. Техническое устройство S состоит из двух узлов. Каждый из которых в случайный момент времени может выйти из строя (отказать), после чего мгновенно начинается ремонт узла, тоже продолжающийся заранее неизвестное, случайное время.
| Рис.4.1 |
Возможные состояния системы:
S 0 – оба узла исправны;
S 1 – первый узел ремонтируется, второй исправен;
S 2 – второй узел ремонтируется, первый исправен;
S 3 – оба узла ремонтируются.
Стрелка, направленная из S 0 в S 1 означает момент отказа первого узла и т. д. На рисунке нет стрелки из состояния S 0 в состояние S 3 , поскольку вероятность того, что два прибора откажут одновременно, стремится к нулю.
Определение 5. Потоком событий называется последовательность однородных событий, следующих одно за другим в какие-то случайные моменты времени (например, поток сбоев на ЭВМ, поток вызовов на телефонной станции).
Важнейшей характеристикой потока событий является его интенсивность l – среднее число событий, приходящееся на единицу времени. интенсивность потока может быть постоянной (l = const ), так и переменной, зависящей от времени. Например, поток автомашин, движущихся по улице, днем интенсивнее, чем ночью, а поток автомашин с 14-ти до 15-ти часов дня можно считать постоянным.
Определение 6. Поток событий называется регулярным, если события следуют одно за другим через определенные, равные промежутки времени.
Определение 7. Поток событий называется стационарным, если его вероятностные характеристики не зависят от времени. В частности, интенсивность l стационарного потока должна быть постоянной. Это отнюдь не означает, что фактическое число событий, появляющееся в единицу времени, постоянно, – нет, поток неизбежно (если только он не регулярный) имеет какие-то случайные сгущения и разрежения. Важно, что для стационарного потока эти сгущения и разрежения не носят закономерного характера: на один участок длины 1 может попасть больше, а на другой – меньше событий, но среднее число событий, приходящееся на единицу времени, постоянно и от времени не зависит.
Например, поток вызовов, поступающих на АТС между 13 и 14 часами. Практически стационарен, но тот же поток в течение суток уже не стационарен.
Определение 8. Поток событий называется потоком без последействия, если для любых двух непересекающихся участков времени t 1 и t 2 число событий, попадающих на один из них, не зависит от того, сколько событий попало на другой. По сути это означает, что события, образующие поток, появляются в те или другие моменты независимо друг от друга, вызванные каждое своими собственными причинами.
Например, поток пассажиров, входящих в метро, практически не имеет последействия. А вот поток покупателей, отходящих от прилавка с купленными товарами, уже имеет последействие (хотя бы потому, что интервал времени между отдельными покупателями не может быть меньше, чем минимальное время обслуживания каждого из них).
Определение 9. Поток событий называется ординарным, если события в нем появляются поодиночке, а не группами сразу.
Например поток клиентов к зубному врачу – обычно ординарный. Поток поездов, подходящих к станции – ординарен, а поток вагонов – неординарен.
Определение 10.
Поток событий называется простейшим (или стационарным Пуассоновским), если он обладает сразу тремя свойствами: стационарен, ординарен и не имеет последействия, а сам входной поток распределен по закону Пуассона (
).
Для описания случайного процесса, протекающего в системе с дискретными состояниями S 1 , S 2 , ..., S n часто пользуются вероятностями состояний p 1 ( t ),..., p n ( t ) , где p k ( t ) – вероятность того, что в момент времени t система находится в состоянии S k . Вероятности p k ( t ) удовлетворяют условию: .
Если процесс, протекающий в системе с дискретными состояниями и непрерывным временем является марковским, то для вероятностей состояний p 1 ( t ), ..., p n ( t ) можно составить систему линейных дифференциальных уравнений. При составлении этих уравнений удобно пользоваться графом состояний системы, на котором против каждой стрелки, ведущей из состояния в состояние, проставлена интенсивность потока событий, переводящего систему по стрелке (рис.4.2):
|
Рис.4.2 l ij – интенсивность потока событий, переводящего систему из состояния S i в состояние S j . Правило создания системы линейных дифференциальный уравнений для нахождения вероятностей состояний. Для каждого состояния выписывается собственное уравнение. В левой части каждого уравнения стоит производная , а в правой – столько членов, сколько стрелок связано непосредственно с данным состоянием; если стрелка ведет в данное состояние, то член имеет знак «+», иначе - знак «–». Каждый член равен интенсивности потока событий, переводящего систему по данной стрелке, умноженной на вероятность того состояния, из которого стрелка выходит. Т.о. система линейных дифференциальных уравнений в нашем случае имеет вид:
|
Начальные условия для интегрирования такой системы отражают состояние системы в начальный момент времени. Если, например, система при t =0 была в состоянии S k , то . Эти уравнения можно решать аналитически, но это удобно только тогда, когда число уравнений не превышает двух (иногда трех). В случае, когда уравнений оказывается больше, применяют численные методы.
Что будет происходить с вероятностями состояний при ? Будут ли
p
1
(
t
), ...,
p n
(
t
)
стремиться к каким-то пределам? Если эти пределы существуют и не зависят от начального состояния системы, то они называются финальными вероятностями состояний: 
.
p i
– среднее относительное время пребывания системы в
i
-ом состоянии.
Как найти финальные вероятности? Поскольку все p i = const , то производные, стоящие в левой части каждого уравнения равны нулю. Т.о. мы получили систему линейных алгебраических уравнений. Поскольку ни одно уравнение в этой системе не имеет свободного члена, то система является вырожденной (т.е. все переменные будут выражены через одну). Чтобы этот избежать, необходимо воспользоваться нормировочным условием (), при этом любое уравнение можно отбросить.
Классификация систем массового обслуживания
По количеству обслуживающих приборов СМО делятся на одноканальные и многоканальные. Многоканальные СМО состоят из нескольких приборов, и каждый них может обслуживать заявку.
Также СМО подразделяются на системы без ожидания и с ожиданием. В первых заявка покидает очередь, если к моменту её прихода отсутствует хотя бы один канал, способный немедленно приступить к обслуживанию данной заявки. Вторые, в свою очередь, делятся на системы без ограничения и с ограничениями по длине очереди.
Также СМО делятся на системы с приоритетами и без них. В свою очередь системы с приоритетом делятся на СМО с прерыванием и без.
Одноканальная СМО с неограниченной очередью
Рис.4.3
Найдем вероятности p k :
Для состояния
S
0
: 
, отсюда ;
Для состояния
S
1
n
:
, подставляем полученное значение для
p
1
: 
. Аналогично, .
Вероятность p 0 найдем из нормировочного условия :
, 
– геометрическая прогрессия, при
r
<1
сходится. 
– вероятность того, что нет заявок.
– вероятность того, что прибор занят обслуживанием заявки. r = l / m – мера загрузки одноканальной СМО.
В текущий момент времени в системе может быть 0, 1, 2, ..., k , ... заявок с вероятностями p 0 , p 1 p 2 , ... Математическое ожидание количества заявок:
учитывая, что 
, получим:
Средняя длина очереди равна разности между средним числом заявок в системе и средним числом заявок, находящихся под обслуживанием: 
.
Формулы Литтла
|
Рис.4.4 |
Первая формула Литтла позволяет определить время реакции СМО (время пребывания заявки в системе).
Пусть
X
(
t
)
– число заявок, поступивших в СМО до момента времени
t
,
Y
(
t
)
– покинувших СМО до
t
. Обе функции случайны и увеличиваются скачком на единицу в моменты прихода и ухода заявок. Тогда число заявок в системе в момент времени
t
можно определить как: 
. Рассмотрим очень большой промежуток времени
T
и вычислим среднее число заявок в системе:
.
Интеграл равен площади ступенчатой фигуры, ограниченной функциями
X
(
t
)
и
Y
(
t
)
, эта сумма состоит из прямоугольников, ширина которых равна единице, а длина – времени пребывания
i
-ой заявки в системе. Сумма распространяется на все заявки, поступившие в систему за время
T
. Правую часть домножим и разделим на
l
: .
T
l
– среднее количество заявок, пришедших за время
T
. Поделив сумму всех времен
t i
на среднее число заявок, получим среднее время пребывания заявки в системе: 
.
Совершенно аналогично можно получить среднее время пребывания заявки в очереди: .
Многоканальная СМО с неограниченной очередью
Рис.4.5
Найдем вероятности p k :
Для состояния
S
0
: ;
Для состояний S 1 – S n : ;
Для S n +1 : ; ...
Для S n+s-1 : ;
Для S n+s : .
Из первых
n
+1 уравнений получаем: 
Из последнего уравнения выражаем: 
и подставляем в предпоследнее: , 
. Тогда 
.
Продолжая аналогию: 
.
Теперь найдем
p
0
, подставив полученные выражения в нормировочное условие (): 
. Отсюда 
.
Показатели эффективности СМО
– Вероятность потери требования в СМО. Особенно часто ею пользуются при исследовании военных вопросов. Например, при оценке эффективности противовоздушной обороны объекта она характеризует вероятность прорыва воздушных целей к объекту. Применительно к СМО с потерями она равна вероятности занятости обслуживанием требований всех n приборов системы. Чаще всего эту вероятность обозначают p n или p отк .
– Вероятность того, что обслуживанием требований в системе занято k приборов, равна p k .
– Среднее число занятых приборов: 
характеризует степень загрузки обслуживающей системы.
– Среднее число свободных от обслуживания приборов:
.
– Коэффициент простоя приборов: .
– Коэффициент занятости оборудования: .
– Средняя длина очереди: 
,
p k
- вероятность того, что в системе находится
k
требований.
– Среднее число заявок, находящихся в сфере обслуживания: 
.
– Вероятность того, что число заявок в очереди, ожидающих начала обслуживания, больше некоторого числа
m
: 
. Этот показатель особенно необходим при оценке возможностей размещения требований при ограниченности времени для ожидания.
Кроме перечисленных критериев при оценке эффективности СМО могут быть использованы стоимостные показатели:
q об – стоимость обслуживания каждого требования в системе;
q ож – стоимость потерь, связанных с простаиванием заявок в очереди в единицу времени;
q у – убытки, связанные с уходом из системы заявки;
q k – стоимость эксплуатации каждого прибора в единицу времени;
q k пр – стоимость простоя единицы времени k -го прибора системы.
При выборе оптимальных параметров СМО по экономическим показателям можно использовать функцию стоимости потерь в системе (для СМО с ожиданием): T – интервал времени.
Для СМО с отказами: .
Для смешанных: .
Критерий экономической эффективности СМО: 
, с
– экономический эффект, получаемый при обслуживании каждой заявки.
СМО замкнутого типа
|
|
Пример. С1, С2, С3 – станки; НЦ – центральный накопитель; B – манипулятор. Транспортная тележка (манипулятор) транспортирует отработанную деталь от станка к накопителю и укладывает ее там, забирает новую деталь (заготовку), транспортирует ее к станку и устанавливает в рабочую позицию для зажима. Во время всего периода, необходимого для выгрузки–загрузки, станок простаивает. Время T з смены заготовки и есть время обслуживания.
Интенсивность обслуживания станков определяется как , – среднее время обслуживания станка, которое вычисляется как 
, где
n
– число заявок. Интенсивность подачи станком заявки на обслуживание определяется как (где – среднеее время обработки детали станком).
Станочная система с однозахватным манипулятором представляет собой СМО с ожиданием с внутренней организацией FIFO : каждая заявка станка на обслуживание удовлетворяется, в случае когда манипулятор занят, заявка становится в очередь и станок ожидает когда манипулятор освободится. Данный процесс марковский, т.е. случайная выдача заявки на обслуживание в определенный момент времени t 0 не зависит от предыдущих заявок, т.е. от течения процесса в предшествующий период. Продолжительность исполнения заявки может быть различной и является случайной величиной, не зависящей от числа поданных заявок. Весь процесс не зависит от того, что произошло ранее момента времени t 0 .
В станочной системе число заявок на обслуживание может быть равно 0, 1, 2, ... m , где m – общее число станков. Тогда возможны следующие состояния:
S 0 – все станки работают, манипулятор стоит.
S 1 – все станки, кроме одного, работают, манипулятор обслуживает станок, от которого поступила заявка на смену заготовок.
S 2 – работают m -2 станка, на одном станке идет смена заготовки, другой ожидает.
S 3 – работают m -2 станка, один станок обслуживается манипулятором, два станка ожидают в очереди.
S m – все станки стоят, один обслуживается манипулятором, остальные ожидают очереди исполнения заказа.
Рис.4.6.
Вероятность перехода в состояние S k из одного из возможных состояний S 1 , S 2 , ... S m зависит от случайного поступления заявок на обслуживание и вычисляется как:
p 0 – вероятность того, что все станки работают.
Манипулятор работает при состояниях системы от S 1 до S m . Тогда вероятность его загрузки равна: .
Число станков, находящихся в очереди связано с состояниями
S
2
, –
S m
, при этом один станок обслуживается, а (k
-1) – ожидают. Тогда, среднее число станков в очереди: 
.
Коэффициент простоя одного станка (из-за ожидания при многостаночном обслуживании): 
.
Среднее использование одного станка:
Применение метода Монте-Карло для решения задач,
связанных с теорией массового обслуживания
Для того, чтобы описать поток однородных событий, достаточно знать закон распределения моментов времени t 1 , t 2 , ..., t k , ..., в которые поступают события.
Для удобства дальнейших рассмотрений целесообразно от величин t 1 , t 2 , ..., перейти к случайным величинам z 1 , z 2 , ..., z m , ... , таким образом, что:
Случайные величины z k являются длинами интервалов времени между последовательными моментами t k .
Совокупность случайных величин z i считается заданной, если определена совместная функция распределения: . Обычно рассматриваются только непрерывные случайные величины z k , поэтому часто пользуются соответствующей функцией плотности f ( z 1 , z 2 ,..., z k ) .
Обычно в теории СМО рассматриваются потоки однородных событий без последействия, для которых случайные величины z k независимы. Поэтому . Функции f i ( z i ) при i >1 представляют собой условные функции плотности при условии, что в начальный момент интервала z k ( i >1) поступила заявка. В отличие от этого функция f 1 ( z 1 ) является безусловной функцией плотности, т.к. относительно появления или непоявления заявки в начальный момент времени не делается никаких предположений.
Широкое применение имеют так называемые стационарные потоки, для которых вероятностный режим их во времени не изменяется (т.е. вероятность появления k заявок за промежуток времени (t 0 , t 0 + t ) не зависит от t 0 , а зависит только от t и k ). Для стационарных потоков без последействия имеют место соотношения:
где l – плотность стационарного потока.
Поступившая в систему заявка может занимать только свободные линии. Относительно порядка занятия линий могут быть сделаны различные предположения:
а) линии занимаются в порядке их номеров. Линия с большим номером не может быть привлечена к обслуживанию заявки, если имеется свободная линии с меньшим номером;
б) линии занимаются в порядке очереди. Освободившаяся линия поступает в очередь и не начинает обслуживания заявок до израсходования всех ранее освободившихся линий;
в) линии занимаются в случайном порядке в соответствии с заданными вероятностями. Если в момент поступления очередной заявки имеется
n
св
свободных линий, то в простейшем случае вероятность занять некоторую определенную линию может быть принята равной . В более сложных случаях вероятности
считаются зависящими от номеров линий, моментов их освобождения и других параметров.
Аналогичные предположения можно сделать и относительно порядка принятия заявок к обслуживанию в том случае, когда в системе образуется очередь заявок:
а) заявки принимаются к обслуживанию в порядке очереди. Освободившаяся линия приступает к обслуживанию той заявки, которая ранее другой поступила в систему;
б) заявки принимаются к обслуживанию по минимальному времени получения отказа. Освободившаяся линия приступает к обслуживанию той заявки, которая в кратчайшее время может получить отказ;
в) заявки принимаются к обслуживанию в случайном порядке в соответствии с заданными вероятностями. Если в момент освобождения линии имеется m заявок в очереди, то в простейшем случае вероятность выбрать для обслуживания некоторую определенную заявку может быть принята равной q =1/ m . В более сложных случаях вероятности q 1 , q 2 ,..., q m считаются зависящими от времени пребывания заявки в системе, времени, остающегося до получения отказа и других параметров.
· Для решения ряда прикладных задач оказывается необходимым учитывать такой важный фактор, как надежность элементов обслуживающей системы. Будем предполагать, что с точки зрения надежности каждая линия в данный момент времени может быть либо исправной, либо неисправной. Надежность линии определяется вероятностью безотказной работы R = R ( t ) , задаваемой как функция времени. Будем также предполагать, что линия, вышедшая из строя по причине неполной надежности, может быть введена в строй (отремонтирована), для чего требуется затратить время t p . Величину t p будем считать случайной величиной с заданным законом распределения.
Относительно судьбы заявки, при обслуживании которой линия выходит из строя, могут быть сделаны различные предположения: заявка получает отказ; заявка остается в системе (с общим временем пребывания в системе не более t n ) как претендент на обслуживание вне очереди; заявка поступает в очередь и обслуживается на общих основаниях и т.д.
Сущность метода статистических испытаний применительно к задачам массового обслуживания состоит в следующем. Строятся алгоритмы, при помощи которых можно вырабатывать случайные реализации заданных потоков однородных событий, а также «моделировать» процессы функционирования обслуживающих систем. Эти алгоритмы используются для многократного воспроизведения реализаций случайного процесса обслуживания при фиксированных условиях задачи. Получаемая при этом информация о состояниях процесса подвергается статистической обработке с целью оценки, являющихся показателями качества обслуживания.
Метод статистических испытаний позволяет более полно, по сравнению с асимптотическими формулами, исследовать зависимость качества обслуживания от характеристик потока заявок и параметров обслуживающей системы.
Это достигается благодаря двум обстоятельствам. Во-первых, при решении задач теории массового обслуживания методом статистических испытаний может быть использована более обширная информация о процессе, чем это обычно удается сделать, применяя аналитические методы.
С другой стороны, значения показателей качества обслуживания, получаемые из асимптотических формул, строго говоря, относятся к моментам времени, достаточно удаленным от начала процесса. Реально, для моментов времени, близких к началу процесса, когда еще не наступил стационарный режим, значения показателей качества обслуживания в общем случае существенно отличаются от асимптотических значений. Метод статистических испытаний позволяет достаточно обстоятельно изучать переходные режимы.
Для многих прикладных задач предположения, при которых справедливы аналитические формулы, оказываются слишком стеснительными. При решении задач методом статистических испытаний некоторые предположения могут быть существенно ослаблены.
В первую очередь это относится к многофазному обслуживанию (т.е. рассматриваются обслуживающие системы, состоящие из нескольких последовательно действующих в общем случае неоднотипных агрегатов).
Другим важным обобщением задачи является предположение о характере потока заявок, поступающих на обслуживание. Допускается рассмотрение потоков однородных событий с практически произвольным законом распределения. Последнее обстоятельство оказывается существенным по следующим двум причинам. Во-первых, реальные потоки заявок в некоторых случаях заметно отличаются от простейшего. Для пояснения второй причины предположим, что исходный поток заявок достаточно точно аппроксимируется простейшим потоком. При этом поток заявок, обслуженных на первой фазе, уже, строго говоря не будет простейшим. Поскольку поток, являющийся выходным для первой фазы, будет входным потоком для агрегата, обслуживающего заявки на второй фазе, мы снова приходим к задаче обслуживания потоков, не являющимися простейшими.
· Структура алгоритма, моделирующего
процесс обслуживания заявок
Рассмотрим однофазную СМО, имеющую n линий, на которые поступают заявки в случайные моменты времени t i . Если вмомент поступления заявки оказываются в наличии свободные линии (их число n св ), заявка занимает одну из них на время t p . В противном случае заявка находится в системе до момента t n , ожидая обслудивания. В т t чение времени ожидания некоторые линии могут освободиться (их число m ), и в этом случае будет возможность обслужить заявку. Если до момента времени t n ни одна из линий не освобождается (m =0 ), заявка получает отказ.
Будем считать, что в силу недостаточно высокой надежности системы, линии обслуживающие заявку, могут выходить из строя, тогда заявка получает отказ, а линия может быть отремонтирована и через промежуток времнеи t pem введена в строй.
Для исследования качества обслуживания заявок предусматривается N * кратное моделирование процесса функционирования системы в интервале (0, T ) . В процессе моделирования число обследованных реализаций обозначим через N .
Алгоритм:
1. Определяется момент t i поступления очередной заявки в систему.
2. Если t i < T , то переход на шаг 3, иначе – на шаг 11.
3. Проверка возможности обслужить поступившую заявку: если n св >0 , то переход на шаг 4, иначе – на шаг 12. (Значение времени поступления заявки t i сравнивается с t осв для всех линий, т.о. выявляются свободные линии.)
4.Если n св >1 , то переход на шаг 5, иначе – на шаг 6.
5. Выбирается номер свободной линии по специальным правилам.
6. Назначается выбранная линия.
7. Проверка: имеет ли место срыв обслуживания по причине недостаточной надежности? Если да, то переход на шаг 8, иначе – на шаг 10.
8. Определение времени t рем ремонта линии, вышедшей из строя (t рем имеет определенный закон распределения).
9. N отк = N отк +1 . Переход на шаг 1.
10. Определение времени занятости t з линии, которая назначена обслуживать заявку (некая случайная величина с определенным законом распределения) и времени освобождения линии: t осв = t i + t з . Переход к очередной заявке (шаг 1).
11. Проверка: если N < N * , то N = N +1 и переход на шаг 1, иначе – обработка результатов опыта и конец.
12. Определить:
А) времени t n пребывания заявки в системе;
Б) число освободившихся каналов m за время t n .
13. Если m >0 , то переход на шаг 14, иначе – на шаг 9.
14. Если m >1 , то переход на шаг 15, иначе – на шаг 6.
15. Выбирается определенная линия в соответствии с принятыми правилами и переход на шаг 6.
Методы исследования систем массового обслуживания
В качестве входного потока заявок используют следующие модели потоков: регулярный, простейший, или пуассоновский, рекуррентный (с ограниченным последействием), нестационарный. Физически наиболее простым, хотя и не самым удобным для исследования и не самым распространенным в приложениях, является регулярный входящий поток, при котором заявки поступают по одной в моменты, отстоящие друг от друга на равные промежутки времени. Самый распространенный в приложениях – простейший (пуассоновский) поток, при котором заявки в систему поступают случайно.
Рекуррентный входящий поток является естественным математическим обобщением двух предыдущих. Поток называется рекуррентным, если интервалы времени между последовательными поступлениями заявок независимы и подчинены одному и тому же закону распределения. Примером такого потока может служить поток заявок, интервалы между поступлениями которых подчинены распределению Эрланга (поток Эрланга) -го порядка:
, .
Здесь - плотность распределения Эрланга; - параметр распределения; - порядок распределения. При распределение Эрланга совпадает с экспоненциальными моментами поступления заявок потока Эрланга представляются в виде суммы независимых случайных величин, имеющих показательное распределение с параметром 
.
Все описанные потоки являются стационарными. В случае, если параметр потока – это функция времени или состояния СМО, входящий поток называется нестационарным. К нестационарным потокам прибегают, когда необходимо учесть изменение интенсивностей потоков в течение дня, месяца, при изменении длины очереди и т.п.
Дисциплина очереди позволяет описать порядок обслуживания заявок, поступающих на вход системы. Обычно рассматривают следующие виды дисциплины очереди: в порядке прибытия, случайным образом, в зависимости от приоритета (прибыл последним – обслужен первым). Обслуживание заявок в зависимости от приоритета означает, что при поступлении в систему заявок с более высоким приоритетом обслуживание заявок с более низким приоритетом прекращается.
Распределение времени обслуживания характеризует механизм обслуживания (обслуживающий прибор, канал обслуживания). Обычно интервал времени, требуемый для реализации процедуры обслуживания, принадлежит к одному из следующих типов распределений: экспоненциальному, эрланговскому, нормальному, равномерному.
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 число событий, попадающих на один из них, не зависит от того, сколько событий попало на другой интервал.
Марковские случайные события описываются обыкновенными дифференциальными уравнениями . Переменными в них служат вероятности состояний р 0 (t), p 1 (t),…,p n (t) .
Для очень больших моментов времени функционирования систем (теоретически при t → ∞) в простейших системах (системы, все потоки в которых – простейшие, а граф – схема гибели и размножения) наблюдается установившийся, или стационарный режим работы. В этом режиме система будет изменять свое состояние, но вероятности этих состояний (финальные вероятности ) р к , к= 1, 2 ,…, n, не зависят от времени и могут рассматриваться как среднее относительное время пребывания системы в соответствующем состоянии.
На промышленных предприятиях теория игр может использоваться для выбора оптимальных решений, например при создании рациональных запасов сырья, материалов, полуфабрикатов, в вопросах качества продукции и других экономических ситуациях. В первом случае противоборствуют две тенденции: увеличения запасов, в том числе и страховых, гарантирующих бесперебойную работу производства; сокращения запасов, обеспечивающих минимизацию затрат на их хранение; во втором - стремления к выпуску большего количества продукции, ведущего к снижению трудовых затрат; к повышению качества, сопровождающемуся часто уменьшением количества изделий и, следовательно, возрастанием трудовых затрат. В машиностроительном производстве противоборствующими направлениями являются стремление к максимальной экономии металла в конструкциях, с одной стороны, и обеспечение необходимой прочности конструкций - с другой.
В сельском хозяйстве теория игр может применяться при решении экономических задач, в которых оппозиционной силой выступает природа, и когда вероятность наступления тех или иных событий многовариантна или неизвестна.
Природные условия нередко сказываются и на эффективности работы промышленных предприятий.
Математическая теория массового обслуживания
Теория массового обслуживания является очень актуальной в наше время. От её совершенствования порой зависят очень важные компоненты современной жизни. Из сказанного выше мы видим, что СМО применяются во многих областях деятельности человека, которые связаны с удовлетворением потребностей заявителей на обслуживание.
Одним из самых главных мест применения СМО является экономика. Ведь где, как не в экономике больше всего сталкиваются с удовлетворением потребностей. Когда запросов на удовлетворение потребностей много, а средств удовлетворения меньше, чем запросов. Очень важным является правильно рассчитать систему обслуживания запросов, ведь если запросы будут потеряны из-за того, что их вовремя не обслужили – фирма (предприятие, банк и т.д.) потеряет значительную часть прибыли. Для оптимизации системы обслуживания и используется СМО. Её разработкой для конкретных условий занимаются менеджеры.
Теория массового обслуживания – это очень многогранное понятие. А, так как человеку свойственно все систематизировать для облегчения понимания, теория массового обслуживания стала базироваться на математическом аппарате. Математическое моделирование СМО является наиболее прогрессивным и точным.
Теория массового обслуживания впервые применялась в телефонии, а затем и в других областях хозяйственной деятельности.
Например, организация нормального процесса обслуживания покупателей связана с правильным определением следующих показателей: количества предприятий данного торгового профиля, численности продавцов в них (в том числе и "механических"), наличия соответствующих основных фондов, частоты завоза товаров, численности обслуживаемого населения, плотности обращаемости и потребности в соответствующих товарах (по групповому и внутригрупповому ассортименту). Если предположить, что предприятие располагает необходимыми основными фондами, торгует товарами, имеющимися в достаточном количестве (при нормальной частоте завоза), то и тогда в процессе обслуживания остаются такие переменные величины, которые могут существенно повлиять на качество обслуживания. Надлежит, следовательно, выбрать такой оптимальный вариант организации торгового обслуживания населения, при котором время обслуживания будет минимальным, качество - высоким, не будет излишних народнохозяйственных затрат. Математический аппарат теории массового обслуживания облегчает решение этой задачи.
Аналитическое моделирование на основе теории систем массового обслуживания.
При аналитическом моделировании исследование процессов или объектов заменяется построением их математических моделей и исследованием этих моделей. В основу метода положены идентичность формы уравнений и однозначность соотношений между переменными в уравнениях, описывающих оригинал и модель. Поскольку события, происходящие в локальных вычислительных сетях, носят случайный характер, то для их изучения наиболее подходящими являются вероятностные математические модели теории массового обслуживания. Объектами исследования в теории массового обслуживания являются системы массового обслуживания (СМО) и сети массового обслуживания (Семо). Системы массового обслуживания классифицируются по следующим признакам:
Закону распределения входного потока заявок;
Числу обслуживающих приборов;
Закону распределения времени обслуживания в обслуживающих приборах;
Числу мест в очереди;
Дисциплине обслуживания.
СМО классифицируются на разные группы в зависимости от состава, от времени пребывания в очереди до начала обслуживания, от дисциплины обслуживания требований.
По составу СМО бывают одноканальные (с одним обслуживающим устройством) и многоканальными (с большим числом обслуживающих устройств). Многоканальные системы могут состоять из обслуживающих устройств как одинаковой, так и разной производительности.
По времени пребывания требований в очереди до начала обслуживания системы делятся на три группы:
1) с неограниченным временем ожидания (с ожиданием),
2) с отказами;
3) смешанного типа.
В СМО с неограниченным временем ожидания очередное требование, застав все устройства занятыми, становится в очередь и ожидает обслуживания до тех пор, пока одно из устройств не освободится.
В системах с отказами поступившее требование, застав все устройства занятыми, покидает систему. Классическим примером системы с отказами может служить работа автоматической телефонной станции.
В системах смешанного типа поступившее требование, застав все (устройства занятыми, становятся в очередь и ожидают обслуживания в течение ограниченного времени. Не дождавшись обслуживания в установленное время, требование покидает систему.
В системах с определенной дисциплиной обслуживания поступившее требование, застав все устройства занятыми, в зависимости от своего приоритета, либо обслуживается вне очереди, либо становится в очередь.
Основными элементами СМО являются: входящий поток требований, очередь требований, обслуживающие устройства (каналы) и выходящий поток требований.
Таким образом, из вышеописанного можно сделать вывод о том, что теория массового обслуживания просто необходима в нашей жизни. Так как мы ежедневно имеем дело с очередями, то эта теория позволяет решать многие жизненные ситуации.
С точки зрения тех, кого обслуживают, очередь связана с бесполезной потерей времени и всегда ассоциируется только с отрицательным восприятием. Одной из важнейших экономических характеристик СМО является время, теряемое заявкой в очереди на ожидание обслуживания. Большое количество заявок, ожидающих обслуживания, кроме отрицательного влияния на субъективное восприятие, мешает нормальной работе даже при небольших временных затратах. Хорошо организованное обслуживание соответствует реально незначительному времени нахождения заявки в очереди. В условиях рыночной экономики и при наличии конкуренции низкий уровень обслуживания приводит к потере потенциальных заявок и снижению конкурентоспособности. Поэтому для менеджера важным является контролировать процессы образования очереди. Пренебрежение этой стороной менеджмента может привести к серьезным экономическим потерям, вплоть до вытеснения из рынка. Теория массового обслуживания дает методы анализа характеристик очереди и выявления путей ее уменьшения.
