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

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

Параметрами источника заявок;

Структурой, определяющей конфигурацию связей и вероятности передачи заявок между узлами сети;

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

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

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

Число заявок, ожидающих обслуживания в сети;

Число заявок, находящихся в сети (в состоянии ожидания и обслуживания);

Суммарное время ожидания заявки в сети;

Суммарное время пребывания заявки в сети.

Определение стохастических сетей

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

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

Для описания ВС используются разомкнутые и замкнутые стохастические сети. В разомкнутой (открытой) сети интенсивность входного потока заявок https://pandia.ru/text/78/299/images/image004_1.gif" width="614" height="134 src=">.gif" width="16" height="19 src=">

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

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

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

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

2.2. Детерминированные сети очередей.

Рассмотрим систему, которая характеризуется наличием каналов прямого доступа в память со стороны накопителей на лентах (НМЛ) и дисках (НМД), а также со стороны терминалов объекта управления. Схема системы представлена на рис. 2.3.(а)..gif" width="19" height="17 src=">, каналам, каждому из НМД и НМЛ. Современные мультипрограммные ОС поддерживают одновременную обработку заданий путем разделения между ними системных ресурсов. При этом достигается максимальное совмещение прикладных задач пользователей при чередовании обработки на центральном процессоре и периферийных средствах.

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

На рис. 2.3 (б) изображена схема действия процесса, рассматриваемая с позиций проблемного программиста. Операции прикладной программы расположены в порядке их выполнения и включают: 1 – работа прикладной программы (счет 1); 2 – печать данных; 3 – обмен с НМД; 4 – работа прикладной программы (счет 2); 5 – выдача информации на объект управления. Макрокоманды запроса к печати, обмена с НМД и объектом управления интерпретируются управляющими программами ОС и инициируют работу соответствующих каналов. Эти операции пронумерованы следующими цифрами: 6 – выполнение программы управления печатью; 7 – выполнение программы управления НМД; 8 – управляющие действия на терминале объекта. Из рис. 2.3.(б) видно, что выполнение операций прикладной программы и ОС чередуется и в очереди к процессору размещаются запросы на обслуживание различного типа.

https://pandia.ru/text/78/299/images/image009_1.gif" width="13" height="15 src=">.gif" width="12" height="15 src="> - НМД..gif" width="15" height="19 src=">, у которого очередь не возникает, так как число терминалов равно числу процессов в системе. Совокупность узлов и очередей соединена дугами, каждая из которых указывает возможные пути движения процессов. Процесс может занимать ресурс узла или находиться в очереди к нему..gif" width="15" height="19 src=">.gif" width="13" height="19 src=">, являющийся источником заявок. На дуге, соединяющей узлы и https://pandia.ru/text/78/299/images/image017_0.gif" width="40" height="19 src=">, которая указывает на формирование начального значения атрибута-операции, которая становится равной 1..gif" width="13" height="15 src=">.gif" width="41" height="19 src=">. Эта запись указывает как дальнейший путь процесса после операции 1, так и новое значение его атрибута-операции..gif" width="13" height="19 src=">..gif" width="13" height="15 src=">.gif" width="12" height="13 src=">.gif" width="13" height="15 src=">, 6.gif" width="13" height="15 src=">, 7.gif" width="13" height="15 src=">.gif" width="15" height="19 src=">.gif" width="13" height="13 src=">.gif" width="57" height="27 src=">.gif" height="17 src=">-м узле.

2.3. Стохастические сети очередей

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

Сетевая модель с элементами случайности представлена на рис. 2.4. Модель процессора представлена узлом Ввод данных" href="/text/category/vvod_dannih/" rel="bookmark">ввода-вывода данных с НМД описаны двумя последовательными этапами: подвод головки дисковода и поиск информации представлены узлами https://pandia.ru/text/78/299/images/image011_0.gif" width="12" height="15 src=">, а обмен через канал узлом.gif" width="15" height="19 src=">.gif" width="15" height="17 src=">.gif" width="15 height=17 src=" height="17">.gif" width="19" height="17 src=">.gif" width="21" height="24 src="> создается процесс..gif" width="19" height="17 src=">. Если при выполнении программы (операция 1) возникает запрос к базе данных , то процесс переходит к операции 2 (переход 1https://pandia.ru/text/78/299/images/image007_1.gif" width="19" height="17 src="> может быть направлен к одному из накопителей информации..gif" width="13" height="19 src=">,.gif" width="15" height="19 src=">.gif" width="13" height="19 src=">), он получит обслуживание, связанное с позиционированием головок чтения-записи на необходимые цилиндр и сектор..gif" width="13" height="15 src="> обеспечивает создание данных, передаваемых канальной программе..gif" width="19" height="17 src=">, где получает обслуживание, необходимое для выхода из прерывания по обращению к канальной программе и планирования возврата к проблемной программе..gif" width="20" height="15 src=">1). Таким образом, завершается цикл выполнения системных операций по организации обмена данными между основной памятью и диском.

https://pandia.ru/text/78/299/images/image027_0.gif" width="15" height="17 src=">.gif" width="20" height="15 src=">.gif" width="13" height="15 src=">.gif" width="20" height="15 src=">.gif" width="20" height="2 src=">Рассмотрим сети с активными ресурсами (узлами), трудоёмкость выполнения заявки в которых характеризуется временем vir, где r = 1,R - тип заявки и её цепь. Если r-заявки поступают в сеть из внешнего источника и после обслуживания покидают её, сеть называется открытой (разомкнутой) по отношению к цепи r. Сеть, не имеющая внешних источников, называется замкнутой. В смешанных сетях существуют как открытые, так и замкнутые цепи заявок.

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

Коэффициент посещения в стационарном режиме обслуживания можно определить из отношения:

αir = λir / λ0r, (2.1)

где λ0r - интенсивность потока r-заявок из начального узла маршрутной цепи заявок.

λir - интенсивность потока заявок в узел i.

Для разомкнутой цепи величину λ0r задают. Для замкнутой цепи величина λ0r определяется множеством параметров сети и характеризует её производительность (пропускную способность).

В стохастической сети движение r-заявок описывают маршрутной матрицей вероятностей переходов Pr = | pijr |, где pijr - вероятность того, что r-заявка после обслуживания в узле i переходит к узлу j.

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

λir = ∑λjir (2.2)

Здесь https://pandia.ru/text/78/299/images/image035_0.gif" width="308" height="138 src=">.gif" width="25" height="2 src=">λir = ∑ pjir λjr, i =0,N. (2.4)

Поскольку для разомкнутой цепи задают поток из внешнего источника λ0r и маршрутную матрицу Pr, то из уравнений (2.1) и (2.4) можно найти λir и αir.

Для замкнутой цепи уравнение балансов потоков (2.4) представляется однородной системой с бесконечным множеством решений. Поэтому для расчёта процессов в замкнутых цепях в качестве исходных данных берут величины λir. Поскольку за полный цикл заявка посещает начальный узел трассы один раз, коэффициент посещения нулевого узла равен единице. Учитывая, что λ0r=1 и подставляя λir = αir λ0r (из (2.1)) в левую и правую части системы уравнений (2.4), получаем уравнения для расчёта коэффициентов посещения замкнутой цепи:

https://pandia.ru/text/78/299/images/image039_0.gif" width="132" height="49 src="> i =0,N, т. е. имеем систему уравнение аналогичную (2.4) для расчёта αir,

https://pandia.ru/text/78/299/images/image041_0.gif" width="90" height="45 src="> i =0,N.

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

Мультиклассовая сеть

https://pandia.ru/text/78/299/images/image042_0.gif" width="29" height="26 src="> |. Элементы DIV_ADBLOCK37">

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

Интенсивность потока заявок в классе s системы i из других систем сети обозначим λis. Уравнения баланса потоков стационарного режима сети имеют вид:

https://pandia.ru/text/78/299/images/image044_0.gif" width="144" height="49 src="> (2.6)

Разработаны эффективные способы расчёта сетей, реализующих в узлах следующие дисциплины обслуживания:

· обслуживание в порядке поступления (FiFo);

· разделение времени (PS), предполагающее, что если в узле находится n запросов, то в единицу времени каждому из них будет представлен квант обслуживания длиною 1/n;

· прерывание на основе абсолютных приоритетов с дообслуживанием в обратном порядке(P);

· обслуживание без ожидания (Д)

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

Введём обозначения:

niq - среднее число заявок класса q в узле i;

ni = ∑q niq - среднее число заявок в узле i;

Kr = ∑i ni - среднее число заявок цепи r;

K = ∑r Kr - число заявок в сети.

Gif" width="14" height="2 src=">.gif" width="14" height="2 src=">.gif" width="14" height="2 src=">Состояние сети описывается вектором n = (n1 ,n2 ,…,ni,…,nN), где ni - состояние узла i .

Gif" width="14" height="2 src=">.gif" width="10" height="2 src=">.gif" width="19" height="26 src="> ,…,SN) = (P1(S1), P2(S2),…,Декомпозиция" href="/text/category/dekompozitciya/" rel="bookmark">декомпозиции (структурирования). Основой классических алгоритмов вычисления G(K) является операция свертки нескольких векторов, которая представима в виде рекуррентных выражений по многомерной схеме Горнера.

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

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

· интенсивность внешних источников пуассоновских потоков – λ0r;

· экспоненциально распределённой трудоёмкостью обслуживания в i-ом узле– vi = 1/μ, где μ - интенсивность обслуживания;

· коэффициентами посещения в i –e узлы - αir.

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

Характеристики сети рассчитывают следующим образом. Загрузка узла i со стороны потока заявок типа r:

https://pandia.ru/text/78/299/images/image052.gif" width="20" height="26 src="> = λi/μi , vi = 1/μi, https://pandia.ru/text/78/299/images/image052.gif" width="20 height=26 src=" height="26"> =https://pandia.ru/text/78/299/images/image052.gif" width="20" height="26 src="> vi/(1-https://pandia.ru/text/78/299/images/image052.gif" width="20" height="26 src="> ).

Воспользовавшись формулой Литла (ni = λiVi), найдём число заявок каждого типа в узле i:

nir = λir Vir = https://pandia.ru/text/78/299/images/image055.gif" width="67" height="39 src="> .

Замкнутые сети. Алгоритм расчёта сети через вероятности состояний.

Для замкнутых марковских сетей вероятности состояний определяются из решений, представимых в форме произведения (2.7). Если сеть состоит из FiFo-узлов, то вероятности состояний:

P(n1 n2…nN) =1/G(K) * Π https://pandia.ru/text/78/299/images/image052.gif" width="20" height="26 src="> = λi/μi - загрузка i-ой системы, равная отношению интенсивности потока к интенсивности обслуживания в i-й системе: m =1,K1; n = 1,K2; i = 1,N.Vi2(K1,K2) = vi2. (2.13)

Приведённые зависимости верны, если в FIFO-узлах время обслуживания не зависит от цепи, т. е. vi1 =vi2. В PS-узлах оно может различаться. При необходимости через G можно найти вероятности состояний и другие характеристики.

Основной недостаток алгоритма – большой диапазон изменения величины G, приводящий к переполнению, потери значности, погрешностям округления.

Метод анализа средних (МАС)

МАС может быть легко получен из алгоритма свертки и формул (ni = λiVi) Литла для цепи и узлов сети. Так, в случае одноцепной сети при K1 = K из выражения (2.13) имеем:

Vi(K) = vi. (2.14)

tпреб. tобсл. tожид. vi

Исходя из формулы Литла для цепи и учитывая, что время полного цикла заявки в сети,

C(K) = ∑i αiVi(K), (2.15)

получаем:

λ0(K) = K/C, (2.16)

а из формулы Литла для узла находим:

ni(K) = αiλ0(K)Vi(K). (2.17)

Заметим, что ni(0) =0. Рекуррентные вычисления по формулам (2.13) – (2.16) сразу дают искомые характеристики процессов и узлов сети. Загрузку находят из соотношения:

https://pandia.ru/text/78/299/images/image067.gif" width="88" height="39 src="> (2.15)

Рассмотрим более общий случай обслуживания в узлах. Введём величину bi(j), характеризующую ёмкость узла i, когда в нём находится j заявок. Для одноканальных обслуживающих приборов с постоянной скоростью обслуживания bi(j) =1. Для Д-узлов bi(j) =j. Для узлов, скорость обслуживания в которых зависит от нагрузки, имеем 0 < bi(j)<∞. Обычно bi(j) - монотонная неубывающая функция j, т. е.

bi(j) > bi(j-1) и bi(j+1) - bi(j) ≤ bi(j) - bi(j-1).

Например, если в узле находится двухканальный обслуживающий прибор, то bi(1) =1, bi(j) =2 для всех j ≥2.

Ёмкость узла (нагрузочная способность) определяется отношением:

bi(j) = μi(j)/μi(1), (2.19)

где μi(j) - интенсивность обслуживания в узле i, если в нём находится j заявок, а μi(1) - если одна заявка.

Если скорость обслуживания в узле зависит от нагрузки, как это описано формулой (2.19), то время пребывания можно вычислить по формуле:

Vi(K) = vi , (2.20)

где bm - максимальная нагрузочная способность узла i, bm≤K.

https://pandia.ru/text/78/299/images/image069.gif" width="614" height="87 src=">

https://pandia.ru/text/78/299/images/image071.gif" width="26" height="62 src="> Vir(K) = vir,

1 – для FIFO-, PS-узлов;

0 – для Д-узлов.

3. λ0r(K) = Kr/ ∑i αir left">

Рис. 2.5. Порядок обхода узлов при расчёте двухцепной сети с популяцией К = (2,2). ↓ - направление движения линии фронта.

Изображённый на рисунке граф – это не диаграмма состояний сети, а диаграмма возможных объёмов заявок в сети, содержащая несравнимо меньшее число вершин, чем диаграмма состояний. Число вершин в графе не зависит от числа узлов в сети.

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

Применение различных математических методов к формализации. Акцент на сложную систему - непредсказуемую. Носитель неопределенности является человек.

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

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

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

Примерами СМО могут служить:

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

посты ремонта автомобилей;

аудиторские фирмы и т.д.

Основоположником теории массового обслуживания, в частности, теории очередей, является известный датский ученый А.К.Эрланг (1878-1929), который исследовал процессы обслуживания на телефонных станциях.

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

Чтобы описать систему массового обслуживания, необходимо задать:

- входной поток заявок;

- дисциплину обслуживания;

- время обслуживания

- количество каналов обслуживания.

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

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

первым пришел – первым обслуживаешься;

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

случайный отбор заявок;

отбор заявок по критерию приоритетности.

Время обслуживания заявки в СМО является случайной величиной. Наиболее распространенным законом распределения является экспоненциальный закон.  - скорость обслуживания. =количество заявок обслуживания/ед. времени.

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

Обобщенная структура СМО представлена на рис.

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

Проблемы проектирования СМО.

К задачам определения характеристик структуры СМО относятся задача выбора количества каналов обслуживания (базовых элементов {Ф i }), задача определения способа соединения каналов (множества элементов связей {Hj}), а также задача определения пропускной способности каналов.

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

Отметим, что при определении количества каналов системы, в случае их параллельного расположения, необходимо соблюдать условие работоспособности системы . Обозначим:  - среднее число заявок, поступающих в единицу времени, т.е. интенсивность входного потока;  - среднее число заявок, удовлетворяемых в единицу времени, т.е. интенсивность обслуживания; S - количество каналов обслуживания. Тогда условие работоспособности СМО запишется

или
. Выполнение этого условия позволяет вычислить нижнюю границу количества каналов.

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

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

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

1. Показатели эффективности использования СМО.

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

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

Средняя продолжительность периода занятости СМО.

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

2. Показатели качества обслуживания заявок.

Среднее время ожидания заявки в очереди.

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

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

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

Закон распределения времени ожидания заявки в очереди.

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

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

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

3. Показатели эффективности функционирования пары «СМО - потребитель».

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

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

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

Классификация систем массового обслуживания

1. По характеру обслуживания выделяют следующие виды СМО:

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

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

Системы с ограниченной очередью . (ремонт в гараже)

Системы с отказами . Все заявки, прибывшие в момент обслуживания заявки, получают отказ. (ГТС)

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

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

Одноканальные СМО.

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

3. По кругу обслуживаемых объектов различают два вида.

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

Открытые СМО.

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

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

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

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

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

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

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

5.2.1 Описание сети. Обозначения

Рассмотрим сеть МО, для описания которой будем использовать следующие обозначения:

М - конечное множество узлов сети,

М - число узлов в сети МО,

Номер узла, .

Узлы предполагаются следующих типов:

0) экспоненциальные многолинейные с бесконечной емкостью накопителя и дисциплиной FIFO (отметим, что приведенную ниже теорему нетрудно перенести на экспоненциальные узлы со случайным выбором прибора или места в очереди);

1) бесконечнолинейные;

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

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

Множество узлов типа обозначается а число приборов в узле - .

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

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

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

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

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

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

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

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

Статистические характеристики случайной величины задаются совместной функцией распределения (ФР)

совместную ФР маршрута и объемов заявки на этапах, через

условную совместную ФР длительностей обслуживания заявки на этапах при фиксированных маршруте и объемах и через

условную ФР длительности обслуживания заявки на этапе (в узле с номером ) при фиксированных маршруте и объемах.

Относительно введенных функций делаются следующие предположения.

(П 1.) Длительности обслуживания предполагаются условно независимыми вдоль маршрута, т.е. условная ФР имеет вид

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

Таким образом, если , т.е. на этапе маршрута заявка обслуживается в узле s типа 0, то

Иными словами, длительность обслуживания в узле типа 0 не зависит ни от маршрута R, ни от объемов Y (включая объем ) и имеет экспоненциальное с параметром распределение.

(П 3). Функции распределения не содержат сингулярной компоненты.

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

Кроме того, для узлов типов 1-3 положим

и для сокращения записи результатов обозначим дополнительно через

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