Типы систем массового обслуживания и критерии эффективности

Разбить на страницы

Показывать лекцию целиком

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Укажем еще на один признак, по которому различаются обслуживающие системы. Если аппараты обслуживающей системы расположены последовательно (пронумерованы) и очередное требование поступает сначала на первый из них и лишь только в том случае, если он занят, передается второму аппарату, и так далее, то, следуя А.Я.Хинчину, такую систему будем называть упорядоченной . Следовательно, в упорядоченной системе требование поступит на обслуживающий аппарат с номером $$n$$ только в том случае, если в момент его поступления аппараты с номерами $$1,2,3,...,(n-1)$$ заняты.

Критерии эффективности

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

Критерии эффективности систем обслуживания с потерями

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

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

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

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

Критерии эффективности систем обслуживания без потерь

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

Математическое ожидание длины очереди.

Время ожидания начала обслуживания.

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

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

Среднее число занятых обслуживающих аппаратов (это число – величина случайная).

Вероятность иметь более m единиц в очереди в момент при заданном начальном состоянии системы.

Критерии эффективности системы обслуживания смешанного типа

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

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

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

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

Задача 1.

Оценки параметров загруженности линий связи на междугородних телефонных станциях и линиях провайдеров. Аннотация

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

Критерии эффективности

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

$$\mathop{max}\limits_i \mathop{min}\limits_j u_{ij}$$.

Минимаксный критерий (критерий потерь или минимаксного риска). В соответствии с этим критерием оптимальным считается действие, для которого величина потерь (риска) принимает наименьшее значение при самой неблагоприятной обстановке, то есть действие $$i$$, для которого достигается

$$\mathop{min}\limits_i \mathop{max}\limits_j r_{ij}$$,

где $$r_{ij}$$ определяется как величина, которую нужно прибавить к $$u_{ij}$$, чтобы получить максимальный выигрыш.

Критерий Гурвица (критерий пессизма-оптимизма). В соответствии с этим критерием оптимальным считается действие $$i$$, для которого достигается

$$\mathop{max}\limits_i\{\alpha \mathop{min}\limits_j u_{ij}+(1-\alpha)\mathop{max}\limits_j u_{ij}\}$$,

где $$0\le\alpha\le 1$$.

Из приведенного условия видно, что критерий Гурвица является взвешенной средней из наименьших и наибольших выигрышей для принятого коэффициента $$\alpha$$. В частности, при $$\alpha =1$$ критерий Гурвица соответствует критерию Вальда. Заметим, что минимальный критерий учитывает только наибольший выигрыш, получаемый в результате применения любой стратегии, и безразличен к любым другим вариантам.

Критерий Байеса (Лапласа). В соответствии с этим критерием оптимальным считается действие, которому соответствует

$$\mathop{max}\limits_i \frac{1}{n}\sum\limits_{j=1}^{n}u_{ij}$$.

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

Механизмы оценки эффективности системы АТС на основе элементов теории массового обслуживания

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

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

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

Данная система относится к системе с потерями, так как всякое вновь поступившее требование (выход на междугороднюю станцию по системе "Кварц" либо соединение с линией провайдера), застав все линии связи занятыми, покидает систему. В системах массового обслуживания с потерями используют математическую модель распределения Эрланга [2].

Математическая модель решения задачи анализа работы линий связи

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

Рассмотрим однородное событие $$E$$, следующее одно за другим через случайные промежутки времени. Число $$n$$ реализаций события $$E$$, происходящее в течение интервала времени $$T$$, является случайной величиной, которую обозначим через $$N(T)$$ ; вероятность того, что $$N=n$$, обозначим $$P_n(T)$$. [3]

Определим распределение вероятностей для такого потока, (то есть найдем величины $$P_n(T)$$, где $$n=0,1,..$$.). Для любого времени $$T$$ имеем

$$P_0(T)+P_1(T)+...+P_k(T)+...=1$$

Вероятность того, что событие $$E$$ произойдет более одного раза в интервале времени $$dt$$, есть величина бесконечно малая по сравнению с $$dt$$. Вероятность того, что событие $$E$$ произойдет 1 раз, пропорциональна $$dt$$ и равна $$\lambda$$, следовательно $$P_k(dt)$$, где $$k=2,3,..$$. бесконечно малые, поэтому $$P_0(dt)+P_1(dt)=1; P_1(dt)=ldt; P_0(dt)=1-ldt$$ После аналитического преобразования Лапласа получим:

$$P_0(T)=e^{-\lambda T};P_1(T)=\frac{(\lambda T)*e^{-\lambda t}}{1!};...P_n(T)=\frac{(\lambda T)*e^{-\lambda T}}{n!}$$

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

В установившемся режиме Эрлангом были найдены следующие зависимости.

Вероятность того, что обслуживанием заняты $$k$$ линий связи:

вероятность того, что линии связи свободны,

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

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

Коэффициент простоя линий связи.

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

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

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

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

Одним из определяющих факторов в этой задаче являются состояния, в которых могут находится линии связи в зависимости от коэффициента простоя $$S1,S2,…,Sk$$, — эти коэффициенты нам неизвестны.

Тогда математическую модель в условиях неопределенности можно сформулировать следующим образом [2]:

имеется некоторая матрица $$L$$ размерностью $$m*n$$.

Элементы этой матрицы $$L_{ij}$$ можно рассматривать как полезность результата $$Oi$$ (которое складывается из среднего между коэффициентом простоя и вероятностью, что все линии связи свободны) при использовании стратегии $$Xi$$ — выбора числа линий связи.

Критерий Гурвица основан на следующих двух предположениях: среда может находиться в самом невыгодном состоянии с вероятностью 1-a, т.е. с вероятностью, что поток заявок на обслуживание очень низкий, и в самом выгодном — с вероятностью $$\alpha$$ — коэффициент доверия.

Тогда решающее правило Гурвица записывается так [5]:

$$\mathop{max}\limits_i\{\alpha \mathop{min}\limits_j u_{ij} +(1-\alpha)\mathop{max}\limits_j u_{ij}\}$$

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

Хранение исходных данных организовано по средствам СУБД Access.

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

Вторая версия программного обеспечения по анализу работы линий связи выполняется на C # в Visual Studio.NET.

В качестве основного языка объектно-ориентированной платформы выбран C #.

C # создан на базе опыта разработки других языков программирования:

Высокая производительность (от C).

Объектно-ориентированная структура (от С++).

Сбор мусора, высокая безопасность (от Java).

Быстрая разработка (от Visual Basic).

Поэтому C # — язык идеально подходящий для разработки компонентных $$n$$ -уровневых распределенных веб-приложений Visual Studio.NET.

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

В данной работе новыми являются:

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

создание веб- и Windows- приложений на платформе .NET, работающих как на локальном компьютере, так и в Internet.

Задача 2.

Пусть через противолодочный рубеж прорываются подводные лодки. Известно, что в среднем за сутки через рубеж проходят три подводные лодки. Моменты начала форсирования неизвестны, но можно предполагать, что поток прорывающихся подводных лодок простейший. Необходимо определить, какое количество противолодочных самолетов $$n$$ должно осуществлять патрулирование на рубеже для того, чтобы в момент появления очередной подводной лодки с вероятностью, не меньшей 0,9, хотя бы один самолет был свободен (осуществлял поиск). Предполагается, что после появления очередной подводной лодки самолет занят ее "обслуживанием". Среднее время занятости самолета $$M[\gamma]=2,4час$$. Точное значение занятости самолета неизвестно, но можно предполагать, что оно случайно и подчинено показательному закону. В такой постановке задачу можно рассматривать как одну из задач массового обслуживания. В качестве критерия эффективности выбрана вероятность того, что хотя бы один из самолетов ПЛО был свободен к моменту появления лодки на рубеже. Предполагается, что вероятность обнаружения лодки на рубеже ПЛО равна единице.

В абстрактной постановке эта задача формулируется следующим образом.

Имеется обслуживающая система, состоящая из $$n$$ аппаратов. Она относится к числу систем с потерями, то есть требование, поступившее в момент, когда все обслуживающие аппараты заняты, покидает систему. Если в системе в момент поступления требования (лодки) есть хотя бы один свободный аппарат (самолет ПЛО), то он немедленно приступает к обслуживанию требования (лодки). Каждый аппарат (самолет) может одновременно обслужить только одно требование (лодку). Для рассматриваемой задачи безразлично, относится система к числу упорядоченных или нет. Время обслуживания одного требования одним аппаратом подчинено показательному закону с параметром $$\gamma =\frac{1}{2,4}$$. Напомним, что это означает следующее: вероятность того, что время обслуживания $$\gamma$$ меньше $$t$$, равна

$$p\{\gamma < t\} =F(t)=1-e^{-\gamma t}$$

а $$\frac{1}{\gamma}$$ есть математическое ожидание времени обслуживания, равное 2,4 часа.

В систему на обслуживание поступает простейший поток требований (лодок) с параметром $$\lambda$$. Вероятность поступления равно $$k$$ требований за время $$t$$ равна

$$V_k(t)=\frac{(\lambda t)^k}{k!}e^{-\lambda t}$$,

где $$\lambda$$ — математическое ожидание числа требований за единицу времени.

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

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

$$P_k=\frac{P_0}{k!}(\frac{\lambda}{\gamma})^k(k=1,2,...,n)$$.

Вероятность того, что все обслуживающие аппараты свободны, будет

$$P_0=\frac{1}{\sum\limits_{m=0}^{n}\frac{1}{m!}(\frac{\lambda}{\gamma})^m}$$

Здесь $$n$$ — число обслуживающих аппаратов системы (число самолетов ПЛО).

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

$$P_n=\frac{(\frac{\lambda}{\gamma})^n\frac{1}{n!}}{\sum\limits_{m=0}^{n}\frac{1}{m!}(\frac{\lambda}{\lambda})^m}$$.

Среднее число занятых обслуживающих аппаратов:

$$M=\sum\limits_{k=1}^{n} \frac{1}{(k-1)!}(\frac{\lambda}{\gamma})^k P_0$$

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

Искомая вероятность $$P=1-P_n$$. В нашем примере $$\lambda =3$$ (среднее число прорывающихся подводных лодок в сутки):

$$\gamma =\frac{1}{M[\gamma]}=10$$, так как $$M[\gamma]=2,4 час=0,1 суток$$.

Таким образом, нужно найти $$n$$ из условия $$1-P_n \ge 0,9$$ или $$P_n\le 0,1$$. При $$n=1$$ вероятность того, что все самолеты заняты "обслуживанием" подводных лодок, $$P_n=0,23$$. Следовательно, одного самолета мало для обеспечения заданной надежности обслуживания.

При $$n=2$$ значение $$P_n=0,03$$, поэтому $$P=0,97$$.

Таким образом, из двух самолетов, находящихся на рубеже, с вероятностью 0,97 хотя бы один из них будет свободен в любой момент времени.

Интересно, насколько при этом будут заняты "работой" самолеты. Количественно эту занятость можно описать величиной $$\mu$$ — средним числом занятых самолетов. При $$m=2$$ эта величина равна $$\mu \approx 0,3$$, то есть в среднем 85% времени каждый самолет будет свободен.

Страницы: