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

 

 

 

 

 

 

 

 

 

 

 

 

Реферат

по дисциплине "Теория систем массового обслуживания"

 

 

 

 

 

 

 

 

 

 

 

 

2015

 

Содержание

 

1.Теория систем массового обслуживания………………………..………… 3

2. Потоки события……………………………….………………………......... 3

3. Графы состояний СМО……….……………………………………………. 6

4. Уравнения Колмогорова для вероятностей состояний. Финальные вероятности состояний…….…………………………………………………………. 8 

5. Уравнения Колмогорова…………………………………………...……… 11

6. Список используемых источников……………………………………......…14

 

 

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

 

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

ТМО опирается на теорию вероятностей и математическую статистику.

Первоначальное развитие ТМО связано с именем датского ученого А.К. Эрланга (1878 – 1929 г.г.), с его трудами в области проектирования и эксплуатации телефонных станций. Большой вклад в развитие этой теории внесли российские ученые математики Колмогоров, Хинчин и др.

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

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

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

 

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

 

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

Выделяют следующие виды потоков:

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

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

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

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

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

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

Если поток одновременно обладает свойствами ординарности, стационарности и отсутствием последствий, то такой поток называю простейшим или потоком Пуассона.

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

a m e m a P

где - а – это среднее число событий попадающих на данный промежуток времени.

Справочно: е = 2,71828….

а – можно определить через интенсивность потока событий λ

а = λ t

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

t k t k e kt P * ) ( ) (

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

чел/мин; руб/час; чеков/час; документов/день; кг/ час и т.д.

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

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

f (tоч.) = v * e-vt

v –  это интенсивность прохода очереди, определяемая средним числом заявок, проходящих на обслуживание в единицу времени:

оч 1 T V

Точ – это среднее время ожидания обслуживания в очереди.

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

f (tобсл.) = μ * e-μt

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

обсл. t 1

tобсл. – среднее время обслуживания заявок.

Важнейшей характеристикой СМО, объединяющей показатели μ и λ, является интенсивность нагрузки ρ:

ρ = λ / μ;

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

Кроме понятия простейшего потока заявок часто приходиться пользоваться понятиями потоков других типов.

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

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

 

Графы состояний СМО

 

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

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

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

λ12

λ01

S 1

S 2

S 0

λ21

λ10

Система может находиться в одном из трех состояний:

S 0 – канал свободен (простаивает)

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

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

Переход системы из состояния S 0 в состояние S 1, происходит под воздействием простейшего потока с интенсивностью λ01, а из состояния S 1 в S 0 систему переводит поток обслуживания с интенсивностью λ10.

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

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

Случайный процесс, происходящий в системе, заключается в том, что случайные моменты времени t0 ,t1 , t2 ………..tn система оказывается в том, или ином заранее известном состоянии последовательно. Такая случайная последовательность событий носит название Марковской цепи. Если для каждого шага вероятность перехода из одного состояния Si в любое другое Sj, не зависит от того, когда и как система перешла в состояние Si.

Марковские случайные процессы (цепи Маркова).

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

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

Основной задачей исследования Марковской цепи является вычисление безусловных вероятностей нахождения системы S на любом (к-отм) шаге в состоянии Si .

Переходные вероятности pij(k) можно записать в виде матрицы.

По главной диагонали матрицы стоят вероятности задержки в данном состоянии:

p11(k) ; p 22(k) ; pij (k) ; pij (k) ; pnn (k)

Т.к. на каждом шаге система S может находиться только в одном из взаимоисключающих состояний, то для любой I – той строки матрицы сумма всех стоящих в ней вероятностей pij (k) = 1.

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

0 ≤ pij ≤ 1;

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

pii (k) = 1 - ) ( 1 k p n j ij

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

Если состояние Si является поглощающим, то вероятность задержки в этом состоянии = 1.

Для того, что бы найти безусловную вероятность нахождения системы S на к – том шаге в состоянии Sj (j = 1,2,…..), если задана матрица переходных вероятностей (или что равнозначно, размеченный граф состояний) и начальное распределение вероятностей, выдвигают гипотезу, состоящую в том, что в начальный момент (к = 0) система находилась в состоянии Si.

В предположении того, что эта гипотеза имеет место, условная вероятность того, что система S на первом шаге будет в состоянии Sj, равна переходной вероятности pij.

По формуле полной вероятности получим:

pi (1) = .n). 1,2,3.....(j ), 0(* 1 i n i ij p p

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

Распределение вероятностей на втором шаге, мы выразим через распределение вероятностей на первом шаге:

pi (2) = ), 1(* 1 i n i ij p p

Переходя таким же способом от к = 2 к к = 3 и т.д., получим рекуррентную формулу.

Рекуррентной называется формула, выражающая каждый член последовательности через предыдущие члены этой последовательности.

 

Уравнения Колмогорова для вероятностей состояний. Финальные

вероятности состояний.

 

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

Итак, на систему, находящуюся в состоянии  , действует простейший поток событий. Как только появится первое событие этого потока, происходит «перескок» системы из состояния  в состояние  (на графе состояний по стрелке  ).

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