Понятие о системах массового обслуживания (СМО).

27.09.2019

Введение

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

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

1 Марковские цепи с конечным числом состояний и дискретным временем

Пусть некоторая система S может находиться в одном из состояний конечного (или счетного) множества возможных состояний S 1 , S 2 ,…, S n , а переход из одного состояния в другое возможен только в определенные дискретные моменты времени t 1 , t 2 , t 3 , называемые шагами.

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

Случайный процесс называется марковским, если вероятность перехода из любого состояния S i в любое состояние S j не зависит от того, как и когда система S попала в состояние S i (т.е. в системе S отсутствует последствие). В таком случае говорят, что функционирование системы S описывается дискретной цепью Маркова.

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

Рисунок 1 – Пример размеченного графа состояний

Вершины графа S 1 , S 2 , S 3 обозначают возможные состояния системы. Стрелка, направленная из вершины S i в вершину S j обозначает переход ; число, стоящее рядом со стрелкой, обозначает величину вероятности этого перехода. Стрелка, замыкающаяся на i-той вершине графа, обозначает, что система остается в состоянии S i с вероятностью, стоящей у стрелки.

Графу системы, содержащему n вершин, можно поставить в соответствие матрицу NxN, элементами которой являются вероятности переходов p ij между вершинами графа. Например, граф на рис. 1 описывается матрицей P:

называемой матрицей вероятностей переходов. Элементы матрицы p ij удовлетворяют условиям:

Элементы матрицы p ij – дают вероятности переходов в системе за один шаг. Переход

S i – S j за два шага можно рассматривать как происходящий на первом шаге из S i в некоторое промежуточное состояние S k и на втором шаге из S k в S i . Таким образом, для элементов матрицы вероятностей переходов из S i в S j за два шага получим:

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

(3)

Получим два эквивалентных выражения для :

Пусть система S описывается матрицей вероятностей переходов Р:

Если обозначить через Р(m) матрицу, элементами которой являются рi вероятности переходов из S i в S j за m шагов, то справедлива формула

где матрица Р m получается умножением матрицы P саму на себя m раз.

Исходное состояние системы характеризуется вектором состояния системы Q(q i) (называемым также стохастическим вектором).

где q j - вероятность того, что исходным состоянием системы является S j состояние. Аналогично (1) и (2) справедливы соотношения

Обозначим через

вектор состояния системы после m шагов, где q j – вероятность того, что после m шагов система находится в S i состоянии. Тогда справедлива формула

Если вероятности переходов P ij остаются постоянными, то такие марковские цепи называются стационарными. В противном случае марковская цепь называется нестационарной.

2. Марковские цепи с конечным числом состояний и непрерывным временем

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

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

Зная интенсивности переходов можно найти величины p 1 (t), p 2 (t),…, p n (t) – вероятности нахождения системы S в состояниях S 1 , S 2 ,…, S n соответственно. При этом выполняется условие:

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

Состояния S i и Sj называются сообщающимися, если возможны переходы .

Состояние S i называется существенным, если всякое S j , достижимое из S i , является сообщающимся с S i . Состояние S i называется несущественным, если оно не является существенным.

Если существуют предельные вероятности состояний системы:

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

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

Теорема 1. Если S i – несущественное состояние, то т.е. при система выходит из любого несущественного состояния.

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

Если случайный процесс, происходящий в системе с дискретными состояниями является непрерывной марковской цепью, то для вероятностей p 1 (t), р 2 (t),…, p n (t) можно составить систему линейных дифференциальных уравнений, называемых уравнениями Колмогорова. При составлении уравнений удобно пользоваться графом состояний системы. В левой части каждого из них стоит производная вероятности какого-то (j-го) состояния. В правой части – сумма произведений вероятностей всех состояний, из которых возможен переход в данное состояние, на интенсивности соответствующих потоков, минус суммарная интенсивность всех потоков, выводящих систему из данного (j-го) состояния, умноженная на вероятность данного (j-го) состояния.

3 Процессы рождения и гибели

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

Рисунок 2 – Граф состояний для процессов гибели и размножения

Здесь величины , ,…, – интенсивности переходов системы из состояния в состояние слева направо, можно интерпретировать как интенсивности рождения (возникновения заявок) в системе. Аналогично, величины ,,…, – интенсивности переходов системы из состояния в состояние справа налево, можно интерпретировать как интенсивности гибели (выполнения заявок) в системе.

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

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

Для состояния S 0:

Следовательно:

Для состояния S 1:

Следовательно:

С учетом того, что :

(4)

, ,…, (5)

4. Основные понятия и классификация систем массового обслуживания

Заявкой (или требованием) называется спрос на удовлетворение какой-либо потребности (далее потребности предполагаются однотипными). Выполнение заявки называется обслуживанием заявки.

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

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

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

1) отсутствие последействия, т.е. заявки поступают независимо друг от друга;

2) стационарность, т.е. вероятность поступления данного числа заявок на любом временном отрезке зависит лишь от величины этого отрезка и не зависит от значения t 1 , что позволяет говорить о среднем числе заявок за единицу времени, λ, называемом интенсивностью потока заявок;

3) ординарность, т.е. в любой момент времени в СМО поступает лишь одна заявка, а поступление одновременно двух и более заявок пренебрежимо мало.

Для простейшего потока вероятность p i (t) поступления в СМО ровно i заявок за время t вычисляется по формуле:

(6)

т.е. вероятности распределены по закону Пуассона с параметром λt. По этой причине простейший поток называется также пуассоновским потоком.

Функция распределения F(t) случайного интервала времени T между двумя последовательными заявками по определению равна . Но , где – вероятность того, что следующая после последней заявки поступит в СМО по истечении времени t, т.е. за время t в СМО не поступит ни одна заявка. Но вероятность этого события находится из (6) при i = 0. Таким образом:

Плотность вероятности f(t) случайной величины T определяется формулой:

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

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

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

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

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

Если в СМО нет приоритета, то заявки отбираются из очереди в канал по различным правилам.

· Первым пришел – первым обслужен (FCFS – First Came – First Served)

· Последним пришел – первым обслужен (LCFS – Last Came – First Served)

· Первоочередное обслуживание требований с кратчайшей длительностью обслуживания (SPT/SJE)

· Первоочередное обслуживание требований с кратчайшей длительностью дообслуживания (SRPT)

· Первоочередное обслуживание требований с кратчайшей средней длительностью обслуживания (SEPT)

· Первоочередное обслуживание требований с кратчайшей средней длительностью дообслуживания (SERPT)

Приоритеты бывают двух типов – абсолютный и относительный.

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

СМО описываются некоторыми параметрами, которые характеризуют эффективность работы системы.

– число каналов в СМО;

– интенсивность поступления в СМО заявок;

– интенсивность обслуживания заявок;

– коэффициент загрузки СМО;

– число мест в очереди;

– вероятность отказа в обслуживании поступившей в СМО заявки;

– вероятность обслуживания поступившей в СМО заявки (относительная пропускная способность СМО);

При этом:

(8)

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

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

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

, (10)

где – вероятность нахождения системы в S k состоянии.

– коэффициент занятости каналов

– среднее время ожидания заявки в очереди

– интенсивность ухода заявок из очереди

– среднее число заявок в очереди. Определяется как математическое ожидание случайной величины m – числа заявок, состоящих в очереди

(11)

Здесь – вероятность нахождения в очереди i заявок;

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

– среднее время пребывания заявки в очереди

Для открытых СМО справедливы соотношения:

(12)

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

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

5. Основные типы открытых систем массового обслуживания

5.1 Одноканальная система массового обслуживания с отказами

Размеченный граф состояний одноканальной СМО представлен на рисунке 3.

Рисунок 3 – Граф состояний одноканальной СМО

Здесь и – интенсивность потока заявок и выполнения заявок соответственно. Состояние системы S o обозначает, что канал свободен, а S 1 – что канал занят обслуживанием заявки.

Система дифференциальных уравнений Колмогорова для такой СМО имеет вид:

где p o (t) и p 1 (t) – вероятности нахождения СМО в состояниях So и S1 соответственно. Уравнения для финальных вероятностей p o и p 1 получим, приравнивая нулю производные в первых двух уравнениях системы. В результате получим:

(14)

(15)

Вероятность p 0 по своему смыслу есть вероятность обслуживания заявки p обс, т. к. канал является свободным, а вероятность р 1 по своему смыслу является вероятностью отказа в обслуживании поступающей в СМО заявки р отк, т. к. канал занят обслуживанием предыдущей заявки.

5.2 Многоканальная система массового обслуживания с отказами

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

Рисунок 4 – Граф состояний многоканальной СМО с отказами

Состояние S 0 означает, что все каналы свободны, состояние S k (k = 1, n) означает, что обслуживанием заявок заняты k каналов. Переход из одного состояния в другое соседнее правое происходит скачкообразно под воздействием входящего потока заявок интенсивностью независимо от числа работающих каналов (верхние стрелки). Для перехода системы из одного состояния в соседнее левое неважно, какой именно канал освободится. Величина характеризует интенсивность обслуживания заявок при работе в СМО k каналов (нижние стрелки).

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

(16)

При этом для нахождения финальных вероятностей можно воспользоваться формулами (4) и (5). С учётом (16) получим из них:

(17)

(18)

Формулы (17) и (18) называются формулами Эрланга – основателя теории массового обслуживания.

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

(19)

Относительную пропускную способность СМО найдём из (8) и (19):

(20)

Абсолютную пропускную способность найдём из (9) и (20):

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

5.3 Одноканальная система массового обслуживания с ограниченной длиной очереди

В СМО с ограниченной очередью число мест m в очереди ограничено. Следовательно, заявка, поступившая в момент времени, когда все места в очереди заняты, отклоняется и покидает СМО. Граф такой СМО представлен на рисунке 5.

S 0

Рисунок 5 – Граф состояний одноканальной СМО с ограниченной очередью

Состояния СМО представляются следующим образом:

S 0 – канал обслуживания свободен,

S 1 – канал обслуживания занят, но очереди нет,

S 2 – канал обслуживания занят, в очереди одна заявка,

S k +1 – канал обслуживания занят, в очереди k заявок,

S m +1 – канал обслуживания занят, все m мест в очереди заняты.

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

(21)

Выражения для финальных вероятностей состояний рассматриваемой СМО можно найти из (4) и (5) с учётом (21). В результате получим:

При р = 1 формулы (22), (23) принимают вид

При m = 0 (очереди нет) формулы (22), (23) переходят в формулы (14) и (15) для одноканальной СМО с отказами.

Поступившая в СМО заявка получает отказ в обслуживании, если СМО находится в состоянии S m +1 , т.е. вероятность отказа в обслуживании заявки равна:

Относительная пропускная способность СМО равна:

Среднее число заявок, стоящих в очереди L оч, находится по формуле

и может быть записано в виде:

(24)

При формула (24) принимает вид:

– среднее число заявок, находящихся в СМО, находится по формуле(10)

и может быть записано в виде:

(25)

При , из (25) получим:

Среднее время пребывания заявки в СМО и в очереди находится по формулам (12) и (13) соответственно.

5.4 Одноканальная система массового обслуживания с неограниченной очередью

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

Рисунок 6 – Граф состояний одноканальной СМО с неограниченной очередью

Все характеристики такой СМО можно получить из формул предыдущего раздела, полагая в них . При этом необходимо различать два существенно разных случая: а) ; б) . В первом случае, как это видно из формул (22), (23), р 0 = 0 и p k = 0 (при всех конечных значениях k). Это означает, что при очередь неограниченно возрастает, т.е. этот случай практического интереса не представляет.

Рассмотрим случай, когда . Формулы (22) и (23) при этом запишутся в виде:

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

Абсолютная пропускная способность равна:

Среднее число заявок в очереди получим из формулы (24) при :

Среднее число обслуживаемых заявок есть:

Среднее время пребывания заявки в СМО и в очереди определяются формулами (12) и (13).

5.5 Многоканальная система массового обслуживания с ограниченной очередью

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

Граф такой системы представлен на рисунке 7.

Рисунок 7 – Граф состояний многоканальной СМО с ограниченной очередью

– все каналы свободны, очереди нет;

– заняты l каналов (l = 1, n), очереди нет;

Заняты все n каналов, в очереди находится i заявок (i = 1, m).

Сравнение графов на рисунке 2 и рисунке 7 показывает, что последняя система является частным случаем системы рождения и гибели, если в ней сделать следующие замены (левые обозначения относятся к системе рождения и гибели):

Выражения для финальных вероятностей легко найти из формул (4) и (5). В результате получим:

(26)

Образование очереди происходит, когда в момент поступления в СМО очередной заявки все каналы заняты, т.е. в системе находятся либо n, либо (n+1),…, либо (n + m– 1) заявок. Т.к. эти события несовместны, то вероятность образования очереди p оч равна сумме соответствующих вероятностей :

(27)

Относительная пропускная способность равна:

Среднее число заявок, находящихся в очереди, определяется по формуле (11) и может быть записано в виде:

(28)

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

Среднее время пребывания заявки в СМО и в очереди определяется формулами (12) и (13).

5.6 Многоканальная система массового обслуживания с неограниченной очередью

Граф такой СМО изображен на рисунке 8 и получается из графа на рисунке 7 при .

Рисунок 8 – Граф состояний многоканальной СМО с неограниченной очередью

Формулы для финальных вероятностей можно получить из формул для n-канальной СМО с ограниченной очередью при . При этом следует иметь в виду, что при вероятность р 0 = р 1 =…= p n = 0, т.е. очередь неограниченно возрастает. Следовательно, этот случай практического интереса не представляет и ниже рассматривается лишь случай . При из (26) получим:

Формулы для остальных вероятностей имеют тот же вид, что и для СМО с ограниченной очередью:

Из (27) получим выражение для вероятности образования очереди заявок:

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

Абсолютная пропускная способность:

Из формулы (28) при получим выражение для среднего числа заявок в очереди:

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

Среднее время пребывания в СМО и в очереди определяется формулами (12) и (13).

5.7 Многоканальная система массового обслуживания с ограниченной очередью и ограниченным временем ожидания в очереди

Отличие такой СМО от СМО, рассмотренной в подразделе 5.5, состоит в том, что время ожидания обслуживания, когда заявка находится в очереди, считается случайной величиной, распределённой по показательному закону с параметром , где – среднее время ожидания заявки в очереди, а – имеет смысл интенсивности потока ухода заявок из очереди. Граф такой СМО изображён на рисунке 9.

Рисунок 9 – Граф многоканальной СМО с ограниченной очередью и ограниченным временем ожидания в очереди

Остальные обозначения имеют здесь тот же смысл, что и в подразделе.

Сравнение графов на рис. 3 и 9 показывает, что последняя система является частным случаем системы рождения и гибели, если в ней сделать следующие замены (левые обозначения относятся к системе рождения и гибели):

Выражения для финальных вероятностей легко найти из формул (4) и (5) с учетом (29). В результате получим:

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

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

Относительная пропускная способность:

Абсолютная пропускная способность:

Среднее число заявок, находящихся в очереди, находится по формуле (11) и равно:

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

Среднее время пребывания заявки в СМО складывается из среднего времени ожидания в очереди и среднего времени обслуживания заявки:

6. Метод Монте-Карло

6.1 Основная идея метода

Сущность метода Монте-Карло состоит в следующем: требуется найти значение а некоторой изучаемой величины. Для этого выбирают такую случайную величину Х, математическое ожидание которой равно а: М(Х)=а.

Практически же поступают так: производят n испытаний, в результате которых получают n возможных значений Х; вычисляют их среднее арифметическое и принимают в качестве оценки (приближённого значения) a * искомого числа a:

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

6.2 Разыгрывание непрерывной случайной величины

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

где – случайная величина, равномерно распределенная на интервале .

Т.е. выбрав очередное значение надо решить уравнение (30) и найти очередное значение . Для доказательства рассмотрим функцию:

Имеем общие свойства плотности вероятности:

Из (31) и (32) следует, что , а производная .

Значит, функция монотонно возрастает от 0 до 1. И любая прямая , где , пересекает график функции в единственной точке, абсциссу которой мы и принимаем за . Таким образом, уравнение (30) всегда имеет одно и только одно решение.

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

Принадлежит интервалу , и наоборот. Значит: . Т.к. равномерно распределена в , то

, а это как раз и означает, что случайная величина , являющаяся корнем уравнения (30) имеет плотность вероятностей .

6.3 Случайная величина с экспоненциальным распределением

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

Вычислим математическое ожидание:

После интегрирования по частям, получим:

Параметр есть интенсивность потока заявок.

Формулу для розыгрыша получим из уравнения (30), которое в данном случае запишется так: .

Вычислив интеграл, стоящий слева, получим соотношение . Отсюда, выражая , получим:

(33)

Т.к. величина распределена также как и , следовательно, формулу (33) можно записать в виде:

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

7.1 Проверка гипотезы о показательном распределении

Исследуемое мной предприятие представляет собой двухканальную систему массового обслуживания с ограниченной очередью. На вход поступает пуассоновский поток заявок с интенсивностью λ. Интенсивности обслуживания заявок каждым из каналов μ, а максимальное число мест в очереди m.

Начальные параметры:

Время обслуживания заявок имеет эмпирическое распределение, указанное ниже и имеет среднее значение .

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

Таблица 6.1 – Группировка заявок по времени обработки

Выдвигается гипотеза о показательном распределении генеральной совокупности.

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

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

2) Принять в качестве оценки параметра λ показательного распределения величину, обратную выборочной средней:

3) Найти вероятности попадания X в частичные интервалы по формуле:

4) Вычислить теоретические частоты:

где - объем выборки

5) Сравнить эмпирические и теоретические частоты с помощью критерия Пирсона, приняв число степеней свободы , где S – число интервалов первоначальной выборки.

Таблица 6.2 – Группировка заявок по времени обработки с усредненным временным интервалом

Найдем выборочную среднюю:

2) Примем в качестве оценки параметра λ экспоненциального распределения величину, равную . Тогда:

()

3) Найдем вероятности попадания X в каждый из интервалов по формуле:

Для первого интервала:

Для второго интервала:

Для третьего интервала:

Для четвертого интервала:

Для пятого интервала:

Для шестого интервала:

Для седьмого интервала:

Для восьмого интервала:

4) Вычислим теоретические частоты:

Результаты вычислений заносим в таблицу. Сравниваем эмпирические и теоретические частоты с помощью критерия Пирсона.

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

Таблица 6.3 – Результаты вычислений

i
1	22	0,285	34,77	-12,77	163,073	4,690
2	25	0,204	24,888	0,112	0,013	0,001
3	23	0,146	17,812	5,188	26,915	1,511
4	16	0,104	12,688	3,312	10,969	0,865
5	14	0,075	9,15	4,85	23,523	2,571
6	10	0,053	6,466	3,534	12,489	1,932
7	8	0,038	4,636	3,364	11,316	2,441
8	4	0,027	3,294	0,706	0,498	0,151
122

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

7.2 Расчет основных показателей системы массового обслуживания

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

Граф данной системы:

Рисунок 10 – Граф состояний исследуемой СМО

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

(1)

Для состояния S 0:

Следовательно:

Для состояния S 1:

Следовательно:

С учетом того, что :

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

Решение этой системы будет иметь вид:

; ; ; ; ;

; .

Или, с учетом (1):

Коэффициент загруженности СМО:

С учетом этого предельные вероятности перепишем в виде:

Наивероятнейшее состояние – оба канала СМО заняты и заняты все места в очереди.

Вероятность образования очереди:

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

Относительная пропускная способность равна:

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

Абсолютная пропускная способность:

СМО обслуживает в среднем 0,13225 заявок в минуту.

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

Среднее число заявок в очереди близко к максимальной длине очереди.

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

В среднем все каналы СМО постоянно заняты.

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

Для открытых СМО справедливы формулы Литтла:

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

Среднее время пребывания заявки в очереди:

7.3 Выводы о работе исследуемой СМО

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

Чтобы снизить загрузку каналов, сократить время ожидания в очереди и снизить вероятность отказа необходимо увеличить число каналов и ввести систему приоритетов для заявок. Число каналов целесообразно увеличить до 4. Также необходимо сменить дисциплину обслуживания с FIFO на систему с приоритетами. Все заявки теперь будут иметь принадлежность к одному из двух приоритетных классов. Заявки I класса имеют относительный приоритет по отношению к заявкам II класса. Для расчета основных показателей этой видоизмененной СМО целесообразно применить какой-либо из методов имитационного моделирования. Была написана программа на языке VisualBasic, реализующая метод Монте-Карло.

8 Исследование видоизмененной СМО

Пользователю при работе с программой необходимо задать основные параметры СМО, такие как интенсивности потоков, количество каналов, приоритетных классов, мест в очереди (если количество мест в очереди равно нулю, то СМО с отказами), а также временной интервал модуляции и количество испытаний. Программа преобразовывает сгенерированные случайные числа по формуле (34), таким образом, пользователь получает последовательность временных интервалов , распределенных показательно. Затем отбирается заявка с минимальным , и ставится в очередь, согласно ее приоритету. За это же время происходит перерасчет очереди и каналов. Затем эта операция повторяется до окончания времени модуляции, задаваемого изначально. В теле программы присутствуют счетчики, на основании показаний которых и формируются основные показатели СМО. Если для увеличения точности было задано несколько испытаний, то в качестве конечных результатов принимается оценка за серию опытов. Программа получилась достаточно универсальной, с ее помощью могут быть исследованы СМО с любым количеством приоритетных классов, либо вообще без приоритетов. Для проверки корректности работы алгоритма, в него были введены исходные данные классической СМО, исследуемой в разделе 7. Программа смоделировала результат близкий к тому, который был получен с помощью методов теории массового обслуживания (см. приложение Б). Погрешность, возникшая в ходе имитационного моделирования, может быть объяснена тем, что проведено недостаточное количество испытаний. Результаты, полученные с помощью программы для СМО с двумя приоритетными классами и увеличенным числом каналов, показывают целесообразность этих изменений (см. приложение В). Высший приоритет был присвоен более «быстрым» заявкам, что позволяет быстро обследовать короткие задания. Сокращается средняя длина очереди в системе, а соответственно минимизируется средство для организации очереди. В качестве основного недостатка данной организации можно выделить то, что «долгие» заявки находятся в очереди длительно время или вообще получают отказ. Введенные приоритеты могут быть переназначены после оценки полезности того или иного типа заявок для СМО.

Заключение

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

1 Вентцель, Е.С. Исследование операций / Е.С. Вентцель. - М.: «Советское радио», 1972. - 552 с.

2 Гмурман, В.Е. Теория вероятностей и математическая статистика / В.Е. Гмурман. - М.: «Высшая школа», 2003. - 479 с.

3 Лаврусь, О.Е. Теория массового обслуживания. Методические указания/ О.Е. Лаврусь, Ф.С. Миронов. - Самара: СамГАПС, 2002.- 38 с.

4 Саакян, Г.Р. Теория массового обслуживания: лекции / Г.Р. Саакян. - Шахты: ЮРГУЭС, 2006. - 27 с.

5 Авсиевич, А.В. Теория массового обслуживания. Потоки требований, системы массового обслуживания / А.В. Авсиевич, Е.Н. Авсиевич. - Самара: СамГАПС, 2004. - 24 с.

6 Черненко, В.Д. Высшая математика в примерах и задачах. В 3. т. Т. 3/ В.Д. Черненко. - Санкт – Петербург: Политехника, 2003. - 476 с.

7 Клейнрок, Л. Теория массового обслуживания / Л. Клейнрок. Пер.с англ./ Пер. И.И. Грушко; под ред. В.И. Нейман. - М.: Машиностроение, 1979. - 432 с.

8 Олзоева, С.И. Моделирование и расчет распределенных информационных систем. Учебное пособие / С.И. Олзоева. - Улан-Удэ: ВСГТУ, 2004. - 66 с.

9 Соболь, И.М. Метод Монте-Карло / И.М. Соболь. - М.: «Наука», 1968. - 64 с.

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

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

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

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

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

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

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

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

Понятие марковского случайного процесса

Процесс работы СМО представляет собой случайный процесс .

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

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

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

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

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

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

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

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

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

Решение. Возможные состояния системы: - оба узла исправны; - первый узел ремонтируется, второй исправен; - второй узел ремонтируется, первый исправен; - оба узла ремонтируются. Граф системы приведен на рис. 1.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

и обратно по величине интенсивности потока .

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

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

Для простейшего потока с интенсивностью вероятность попадания на

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

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

СМО является внутренним продвижением, а CММ – внешним.

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

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

Если раскрутка сайта направлена на алгоритмы роботов, то в СМО и CММ работают над оптимизацией аудитории.

Составляющие внутренней оптимизации СМО

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

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

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

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

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

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

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

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

P.S. Если вы не хотите вникать во все детали и хитрости продвижения сайта, то рекомендуем доверить это дело профессионалам. Продвижением сайта в интернете на профессиональном уровне занимается компания JoomStudio.com.ua. За раскруткой сайта рекомендуем обращаться именно к ним.

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

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

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

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

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

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

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

б) на время пребывания заявки в очереди;

в) на общее время нахождения заявки в СМО.

В технологии РЭУ чаще всего встречаются СМО смешанного типа.

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

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

где М(Тоб) - математическое ожидание времени обслуживания заявки.

Следовательно, плотность распределения времени обслуживания

Для рассматриваемой системы возможны следующие состояния:

x 0 - свободны все каналы;

x 1 - занят один канал;

x k -- занято k каналов;

x n -- заняты все п каналов.

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

Коэффициент определяют как

где М(Тоб) - математическое ожидание времени обслуживания одной заявки.

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

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

Среднюю долю времени, которое система обслуживания будет простаивать, можно определить вероятностью состояния x 0 , т.е.

Р простоя = р(х 0) = р 0

Пример. Пусть на участок ремонта технологического оборудования поступают приборы со средней плотностью l = 2 ед/ч. Среднее время обслуживания одной единицы оборудования равно 24 мин (0,4 ч.). Заявка, заставшая все каналы занятыми получает отказ в обслуживании.

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

Решение. По условию задачи имеем СМО с отказом. Будем предполагать, что поток заявок, поступающих в СМО, простейший со средней плотностью l.

1. Подсчитаем коэффициент загрузки канала или приведенную плотность заявок

2. Найдем характеристики СМО при числе каналов n= 1. Вероятность необслуживания заявок:

Относительная пропускная способность q определится, как

q=1- Р необ = 1 – 0,44 = 0,56.

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

Вероятность простоя канала р 0

Понятие о системах массового обслуживания (СМО).

Читайте также

Введение

1 Марковские цепи с конечным числом состояний и дискретным временем

2. Марковские цепи с конечным числом состояний и непрерывным временем

3 Процессы рождения и гибели

4. Основные понятия и классификация систем массового обслуживания

5. Основные типы открытых систем массового обслуживания

5.1 Одноканальная система массового обслуживания с отказами

5.2 Многоканальная система массового обслуживания с отказами

5.3 Одноканальная система массового обслуживания с ограниченной длиной очереди

5.4 Одноканальная система массового обслуживания с неограниченной очередью

5.5 Многоканальная система массового обслуживания с ограниченной очередью

5.6 Многоканальная система массового обслуживания с неограниченной очередью

5.7 Многоканальная система массового обслуживания с ограниченной очередью и ограниченным временем ожидания в очереди

6. Метод Монте-Карло

6.1 Основная идея метода

6.2 Разыгрывание непрерывной случайной величины

6.3 Случайная величина с экспоненциальным распределением

7.1 Проверка гипотезы о показательном распределении

7.2 Расчет основных показателей системы массового обслуживания

7.3 Выводы о работе исследуемой СМО

8 Исследование видоизмененной СМО

Заключение

Понятие марковского случайного процесса

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

Составляющие внутренней оптимизации СМО

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