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

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

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

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

) входящий поток заявок;

) очередь;

) каналы обслуживания;

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

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

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

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

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

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

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

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

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

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

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

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

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

Основные характеристики СМО

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

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

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

Схема СМО изображена на рисунке 5.1.

Рисунок 5.1 - Схема системы массового обслуживания

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Для простейшего потока частота поступления требований в систему подчиняется закону Пуассона , т. е. вероятность по-ступления за время T ровно k требований задается формулой

где λ — интенсивность потока заявок , т. е. среднее число заявок, поступающих в СМО в единицу времени,

где τ — среднее значение интервала времени между двумя со-седними заявками.

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

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

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

где Т оч - среднее значение времени ожидания в очереди.

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

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

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

Перечисленные показатели k, τ, λ, l оч, Т оч, ν, Т обс, μ, ρ, Р k являются наиболее общими для СМО.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

	Узлы	Требования

Больница	Санитары	Пациенты
Производство
Аэропорт	Выходы на взлетно-посадочные полосы Пункты регистрации	Пассажиры

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

Рис. 1

Генератор заявок – объект, порождающий заявки: улица, цех с установленными агрегатами. На вход поступает поток заявок (поток покупателей в магазин, поток сломавшихся агрегатов (машин, станков) на ремонт, поток посетителей в гардероб, поток машин на АЗС и т. д.).
Диспетчер – человек или устройство, которое знает, что делать с заявкой. Узел, регулирующий и направляющий заявки к каналам обслуживания. Диспетчер:

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

Очередь – накопитель заявок. Очередь может отсутствовать.
Узел обслуживания состоит из конечного числа каналов обслуживания. Каждый канал имеет 3 состояния: свободен, занят, не работает. Если все каналы заняты, то можно придумать стратегию, кому передавать заявку.
Отказ от обслуживания наступает, если все каналы заняты (некоторые в том числе могут не работать).

Кроме этих основных элементов в СМО в некоторых источниках выделяются также следующие составляющие:

терминатор – уничтожитель трансактов;

склад – накопитель ресурсов и готовой продукции;

счет бухгалтерского учета – для выполнения операций типа «проводка»;

менеджер – распорядитель ресурсов;

Классификация СМО

Первое деление (по наличию очередей):

СМО с отказами;
СМО с очередью.

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

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

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

Итак, например, рассматриваются следующие СМО:

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

Типы ограничения очереди могут быть комбинированными.

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

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

Кроме этого СМО делятся на открытые СМО и замкнутые СМО.

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

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

По количеству каналов СМО делятся на:

одноканальные;
многоканальные.

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

Основными характеристиками системы массового обслуживания любого вида являются:

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

Входной поток требований

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

А i – время поступления между требованиями – независимые одинаково распределенные случайные величины;

E(A) – среднее (МО) время поступления;

λ=1/E(A) – интенсивность поступления требований;

Характеристики входного потока:

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

Дисциплина очереди

Очередь – совокупность требований, ожидающих обслуживания.

Очередь имеет имя.

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

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

first in first out (FIFO)

самый распространенный тип очереди.

Какая структура данных подойдет для описания такой очереди? Массив плох (ограничен). Можно использовать структуру типа СПИСОК.

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

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

Действия со списком:

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

Структура, известная как СТЕК. Может быть описан структурой массив или список;

случайный отбор заявок;
отбор заявок по критерию приоритетности.

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

Характеристики очереди

ограничение времени ожидания момента наступления обслуживания (имеет место очередь с ограниченным временем ожидания обслуживания, что ассоциируется с понятием «допустимая длина очереди»);
длина очереди.

Механизм обслуживания

Механизм обслуживания определяется характеристиками самой процедуры обслуживания и структурой обслуживающей системы. К характеристикам процедуры обслуживания относятся:

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

Для аналитического описания характеристик процедуры обслуживания оперируют понятием «вероятностное распределение времени обслуживания требований».

S i – время обслуживания i -го требования;

E(S) – среднее время обслуживания;

μ=1/E(S) – скорость обслуживания требований.

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

Коэффициент использования СМО

N ·μ – скорость обслуживания в системе, когда заняты все устройства обслуживания.

ρ=λ/(N μ) – называется коэффициентом использования СМО , показывает, насколько задействованы ресурсы системы.

Структура обслуживающей системы

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

Пример. Кассы в магазине.

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

Пример. Медицинская комиссия.

Комбинированное обслуживание – обслуживание вкладов в сберкассе: сначала контролер, потом кассир. Как правило, 2 контролера на одного кассира.

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

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

Основные критерии эффективности функционирования СМО

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

вероятность немедленного обслуживания поступившей заявки (Р обсл =К обс /К пост);
вероятность отказа в обслуживании поступившей заявки (P отк =К отк /К пост);

Очевидно, что Р обсл + P отк =1.

Потоки, задержки, обслуживание. Формула Поллачека–Хинчина

Задержка – один из критериев обслуживания СМО, время проведенное заявкой в ожидании обслуживания.

D i – задержка в очереди требования i ;

W i =D i +S i – время нахождения в системе требования i .

(с вероятностью 1) – установившаяся средняя задержка требования в очереди;

(с вероятностью 1) – установившееся среднее время нахождения требования в СМО (waiting).

Q(t) – число требований в очереди в момент времени t;

L(t) – число требований в системе в момент времени t (Q(t) плюс число требований, которые находятся на обслуживании в момент времени t.

Тогда показатели (если существуют)

(с вероятностью 1) – установившееся среднее по времени число требований в очереди;

(с вероятностью 1) – установившееся среднее по времени число требований в системе.

Заметим, что ρ<1 – обязательное условие существования d, w, Q и L в системе массового обслуживания.

Если вспомнить, что ρ= λ/(N μ), то видно, что если интенсивность поступления заявок больше, чем N μ, то ρ>1 и естественно, что система не сможет справиться с таким потоком заявок, а следовательно, нельзя говорить о величинах d, w, Q и L.

К наиболее общим и нужным результатам для систем массового обслуживания относятся уравнения сохранения

Следует обратить внимание, что упомянутые выше критерии оценки работы системы могут быть аналитически вычислены для систем массового обслуживания M/M/N (N >1), т. е. систем с Марковскими потоками заявок и обслуживания. Для М/G/ l при любом распределении G и для некоторых других систем. Вообще распределение времени между поступлениями, распределение времени обслуживания или обеих этих величин должно быть экспоненциальным (или разновидностью экспоненциального распределения Эрланга k-го порядка), чтобы аналитическое решение стало возможным.

Кроме этого можно также говорить о таких характеристиках, как:

абсолютная пропускная способность системы – А=Р обсл *λ;
относительная пропускная способность системы –

Еще один интересный (и наглядный) пример аналитического решения – вычисление установившейся средней задержки в очереди для системы массового обслуживания M/G/ 1 по формуле:

В России эта формула известна как формула Поллачека– Хинчина, за рубежом эта формула связывается с именем Росса (Ross).

Таким образом, если E(S) имеет большее значение, тогда перегрузка (в данном случае измеряемая как d ) будет большей; чего и следовало ожидать. По формуле можно обнаружить и менее очевидный факт: перегрузка также увеличивается, когда изменчивость распределения времени обслуживания возрастает, даже если среднее время обслуживания остается прежним. Интуитивно это можно объяснить так: дисперсия случайной величины времени обслуживания может принять большое значение (поскольку она должна быть положительной), т. е. единственное устройство обслуживания будет занято длительное время, что приведет к увеличению очереди.

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

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

Для всех моделей сетей очередей, описанных в главе 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 положим

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

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

Возможно, будет полезно почитать: