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

     Определим, сколько нужно использовать  ПЭВМ, чтобы сократить число не  обслуженных заявок, поступающих  на ВЦ, в 10 раз, т.е. чтобы  вероятность отказа в решении задач не превосходила 0,0180. Для этого используем формулу вероятности отказа:

    

     Составим следующую таблицу:

     n  1  2  3  4  5  6

P0   0,357  0,226  0,186  0,172  0,167  0,166

Pотк  0,673  0,367  0,18  0,075  0,026  0,0078

 

 

     Анализируя данные таблицы, следует  отметить, что расширение числа  каналов ВЦ при данных значениях λ и μ до 6 единиц ПЭВМ позволит обеспечить удовлетворение заявок на решение задач на 99,22%, так как при n = 6 вероятность отказа в обслуживании (Ротк) составляет 0,0078.

 

6.6. Многоканальная СМО с ожиданием

 

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

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

    

     где

     .

     Решение будет действительным, если  выполняется следующее условие:      

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

     среднее число клиентов в очереди  на обслуживание

     ;

     среднее число находящихся в  системе клиентов (заявок на обслуживание  и в очереди)

     LS=Lq+ρ;

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

     ;

     средняя продолжительность пребывания  клиента в системе

     .

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

      Пример. Механическая мастерская  завода с тремя постами (каналами) выполняет ремонт малой механизации.  Поток неисправных механизмов, прибывающих  в мастерскую,  - пуассоновский  и имеет интенсивность λ=2,5 механизма  в сутки, среднее время ремонта  одного механизма распределено  по показательному закону и  равно tоб=0,5 сут. Предположим, что другой мастерской на заводе нет, и, значит, очередь механизмов перед мастерской может расти практически неограниченно.

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

     - вероятность состояний системы;

     - среднее число заявок в очереди  на обслуживание;

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

     - среднюю продолжительность пребывания  заявки в очереди;

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

     Решение

     Определим параметр потока обслуживаний

    

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

     ρ=λ/μ=2,5/2,0=1,25,

     при этом λ/μ ∙с=2,5/2∙3=0,41<1.

     Поскольку λ/μ∙с<1, то очередь  не растет безгранично и в  системе наступает предельный  стационарный режим работы.

     Вычислим вероятности состояний  системы:

    

    

    

     Вероятность отсутствия очереди  у мастерской

     Ротк≈Р0+Р1+Р2+Р3≈0,279+0,394+0,218+0,091=0,937.

     Среднее число заявок в очереди  на обслуживание

    

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

     Ls=Lq+=0,111+1,25=1,361.

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

     суток.

     Средняя продолжительность пребывания  механизма в мастерской (в системе)

     суток.

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

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

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

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

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

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

1) системы  с ограниченным потоком требований;

2) системы  с неограниченным потоком требований.

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

1) системы  с упорядоченным обслуживанием;

2) системы  с неупорядоченным обслуживанием.

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

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

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

Потоки событий (требований)

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

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

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

Поток событий  называется стационарным, если его  вероятностные характеристики не зависят от времени.

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

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

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

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

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

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

РГТ > I) -1*'.

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

Методы исследования СМО

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

1. Аналитического.

2. Метода  статистического моделирования  или метода Монте-Карло.

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

Аналитическая теория массового обслуживания предлагает достаточно простые расчетные формулы для определения важнейших характеристик функционирования СМО различных классов. Эти подходы изложены в [45].

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

Построение  математической модели Монте-Карло  состоит из следующих этапов:

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

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

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

4. Построение  теоретического распределения с  параметрами данных эмпирического наблюдения.

5. Проверка  соответствия теоретического и  эмпирического распределения.

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

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

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

где — макснмпльное¦ ннвиниик» значение пере-

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

где- ш — энпиричмкие частоты;

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

В результате получаем теоретически накопленные  частоты.

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

распределении Пуассона — два (Л и N параметра. Для полученных величин Х2 и числа степеней свободы К по таблицам отыскивается вероятность Рх2 того, что различие между теоретическим и эмпирическим распределениями носит случайный характер. Если Рх2 больше 0,05 или 5%, можно считать, что эта вероятность достаточно велика, чтобы не исключать случайного характера различий и поэтому распределение считают подчиняющимся данному теоретическому закону. Если же Рх2 меньше 5 %, то считается, что теоретическое и эмпирическое распределение не совпадают и тогда нужно искать новое теоретическое распределение. Значения Рх2 содержатся в специальных таблицах с двумя входами: один соответствует х2, второй