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

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

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

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

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

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

Основными элементами СМО являются:

Входящий поток заявок (требований) на обслуживание;

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

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

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

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

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

Рисунок 8.5 - Обобщенная схема СМО

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

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

Какова вероятность потери требования (клиента)?

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

К этому перечню можно добавить еще целый ряд задач.

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

Часто входной поток заявок представляется в виде про­стейшего потока, обладающего свойством стационарности, от­сутствия последствия и ординарности.

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

Для простейшего потока поступление заявок в СМО описы­вается законом распределения Пуассона

Р к (τ ) ,

где Р к (τ ) -вероятность поступления к заявок за время τ ;

λ - интенсивность входного потока.

Важное для исследования свойство, которым обладает пуассоновский поток, заключается в том, что процедура разделения и объединения дает снова пуассоновские потоки. Тогда, если входной по­ток формируется из N независимых источников, каждый из которых порождает пуассоновский поток интенсивностью λ i (i = 1, 2, ..., N), то его интенсивность будет определяться по формуле

λ = λ l + λ 2 +...+ λ N .

В случае разделения пуассоновского потока на N независимых по­токов получим, что интенсивность потока λ i будет равна r i λ ,где r i - доля i-го потока во входном потоке требований.

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

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

1. СМО с отказами - формирование очереди не разрешено, поэтому заявка, пришедшая в момент, когда все каналы заняты, получает отказ и теряется. Пример: АТС (выполнение заказов к определенному сроку), система ПВО объекта (цель в зоне об­стрела пребывает мало времени).

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

3. СМО смешанного типа. В этих системах имеется очередь,
на которую накладываются ограничения. Например: на макси­мальную длину очереди (I тип – с ограниченной ДО) или на время ожидания заявки в очереди (П тип – с ограниченным ВО). Примерами СМО I-го типа являются мастер­ские по ремонту радиоаппаратуры с ограниченными площадями для ее хранения. Торговые точки по продаже фруктов, овощей, которые могут храниться ограниченное время, являются смешан­ными СМО II -го типа.

Порядок поступления заявок на обслужива­ние называется дисциплиной обслуживания.

В СМО с очередью могут быть следующие варианты дисцип­лины обслуживания:

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

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

в) в соответствии с приоритетом (участники ВОВ в поликлинике);

г) в случайном порядке (в системе ПВО объекта при отра­жении воздушного налета противника).

Основным параметром процесса обслужи­вания считается время обслуживания заявки каналом (обслуживающим прибором j) – t j (j=1,2,…,m).

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

F(t) = l – e - μt ,

где m - положительный параметр, определяющий интенсивность обслужи­вания требований;

где Е (t) - математическое ожидание случайной величины обслуживания тре­бования t j .

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

Если СМО состоит из неоднородных каналов, то , если
же все каналы однородные, то .

По количеству обслуживающих приборов (каналов) СМО де­лятся на:

Одноканальные;

Многоканальные.

Структура СМО и характерис­тика ее элементов приведены на рисунке 8.6.

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

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

Рисунок 8.6 – Структура и характеристика элементов СМО

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

средняя длина очереди,

среднее время ожидания в очереди,

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

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

В качестве критерия оптимизации применяют:

Максимум прибыли от эксплуатации СМО;

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

Обеспечение заданной пропускной способности.

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

Вопросы для самопроверки

1. Понятие о математических моделях и моделировании.

2. Что представляет собой экономико-статистическая модель и производственная функция?

3. Применение графических и графоаналитических моделей в управлении.

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

5. Виды и методы построения регрессионных моделей.

6. Статистическое исследование причинно-следственных связей.

7. Классификация математических моделей по четырем аспектам детализации (по В.А. Кардашу).

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

9. Этапы моделирования. Проверка модели на адекватность.

10. Понятие о системах массового обслуживания (СМО). Составные части СМО.

11. СМО с отказами и с очередью. Разновидности очередей.

12. Одноканальные и многоканальные СМО. Дисциплины обслуживания

13. Моделирование СМО. Показатели, получаемые при экспериментах на модели СМО.

14. Критерии оптимизации систем массового обслуживания.

Задача 1. На диспетчерский пульт поступает поток заявок, который является потоком Эрланга второго порядка. Интенсивность потока заявок равна 6 заявок в час. Если диспетчер в случайный момент оставляет пульт, то при первой же очередной заявке он обязан вернуться к пульту. Найти плотность распределения времени ожидания очередной заявки и построить ее график. Вычислить вероятность того, что диспетчер сможет отсутствовать от 10 до 20 минут. Решение . Поскольку поток Эрланга второго порядка является стационарным потоком с ограниченным последействием, то для него справедлива формула Пальма

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

. (2)

По условиям задачи поток заявок является Эрланговским порядка =2. Тогда из (1) и (2) получим
.
Из последнего соотношения при λ=6 будем иметь

f1(θ)=3е-6θ(1+6 θ), θ≥0. (3)

Построим график функции f1(θ) . При θ <0 имеем f1(θ) =0 . При θ =0 , f1(0)=3 . Рассмотрим предел

При вычислении предела для раскрытия неопределенности типа использовано правило Лопиталя . По результатам исследований строим график функции f1(θ) (Рис. 1).

Обратим внимание на размерности времени в тексте задачи: для интенсивности это заявки в час, для времени-минуты. Перейдем к одним единицам времени: 10 мин=1/6 час, 20 мин=1/3 час. Для этих значений можно вычислить f1(θ) и уточнить характер кривой

Эти ординаты указаны на графике над соответствующими точками кривой.
Из курса теории вероятностей известно, что вероятность попадания случайной величины Х в отрезок [α, β] численно равна площади под кривой плотности распределения вероятностей f(х) . Эта площадь выражается определенным интегралом

Следовательно, искомая вероятность равна

Этот интеграл легко вычисляется по частям, если положить
U=1+6θ и dV=е-6θ dθ . Тогда dU=6 dθ и V= .
Используя формулу получим

Ответ: вероятность того, что диспетчер сможет отсутствовать от 10 до 20 минут равна 0,28.

Задача 2. Дисплейный зал имеет 5 дисплеев. Поток пользователей простейший. Среднее число пользователей, посещающих дисплейный зал за сутки, равно 140. Время обработки информации одним пользователем на одном дисплее распределено по показательному закону и составляет в среднем 40 минут. Определить, существует ли стационарный режим работы зала; вероятность того, что пользователь застанет все дисплеи занятыми; среднее число пользователей в дисплейном зале; среднее число пользователей в очереди; среднее время ожидания свободного дисплея; среднее время пребывания пользователя в дисплейном зале. Решение. Рассматриваемая в задаче СМО относится к классу многоканальных систем с неограниченной очередью. Число каналов =5. Найдем λ-интенсивность потока заявок: где (час.) - среднее время между двумя последовательными заявками входящего потока пользователей. Тогда польз./час.

Найдем -интенсивность потока обслуживания: , где М[Т обсл.]=40 мин=0,67 часа - среднее время обслуживания одного пользователя одним дисплеем,

тогда польз/час.

Таким образом, классификатор данной системы имеет вид СМО (5, ∞; 5,85; 1,49).
Вычислим коэффициент загрузки СМО . Известно, что для СМО такого класса стационарный режим существует, если отношение коэффициента загрузки системы к числу каналов меньше единицы. Находим это отношение
.
Следовательно, стационарный режим существует. Предельное распределение вероятностей состояний вычисляется по формулам

Поскольку =5, имеем

Вычислим Р*- вероятность того, что пользователь застанет все дисплеи занятыми. Очевидно, она равна сумме вероятностей таких событий: все дисплеи заняты, очереди нет (р5); все дисплеи заняты, один пользователь в очереди (р6); все дисплеи заняты, два пользователя в очереди (р7) и так далее. Поскольку для полной группы событий сумма вероятностей этих событий равна единице, то справедливо равенство

Р*=р5+р6+р7+…=1 - ро - р1 - р2 - р3 - р4.

Найдем эти вероятности: ро =0,014; р1 =3,93*0,014; р2 =7,72*0,014; р3 =10,12*0,014; р4 =9,94*0,014.
Вынося за скобки общий множитель, получим
Р*=1-0,0148*(1+3,93+7,72+10,12+9,94)=1-0,014*32,71=1-0,46=0,54.
Используя формулы для вычисления показателей эффективности? найдем:

• 1. среднее число пользователей в очереди

2. среднее число пользователей в дисплейном зале

3. среднее время ожидания свободного дисплея

4. среднее время пребывания пользователя в дисплейном зале

Ответ: стационарный режим работы дисплейного зала существует и характеризуется следующими показателями Р* =0,54; пользователя; пользователя; ; .

Задача 3. В двухканальную систему массового обслуживания (СМО) с отказами поступает стационарный пуассоновский поток заявок. Время между поступлениями двух последовательных заявок распределено по показательному закону с параметром λ=5 заявок в минуту. Длительность обслуживания каждой заявки равна 0,5 мин. Методом Монте-Карло найти среднее число обслуженных заявок за время 4 мин. Указание: провести три испытания. Решение. Изобразим статистическое моделирование работы заданной СМО с помощью временных диаграмм. Введем следующие обозначения для временных осей:
Вх -входящий поток заявок, здесь ti -моменты поступления заявок; Ti -интервалы времени между двумя последовательными заявками. Очевидно, что ti =ti -1 +Т i .
К1-первый канал обслуживания;
К2-второй канал обслуживания; здесь жирные линии на временной оси обозначают интервалы занятости канала. Если оба канала свободны, то заявка становится под обслуживание в канал К1, в случае его занятости заявка обслуживается каналом К2.
Если заняты оба канала, то заявка покидает СМО необслуженной.
Вых ОБ-выходящий поток обслуженных заявок.
Вых ПТ-выходящий поток потерянных заявок за счет отказов СМО (случай занятости обоих каналов).
Статистические испытания продолжаются в течение временного интервала . Очевидно, что любое превышение времени tmax влечет за собой сброс заявки в выходящий поток Вых ПТ. Так на рис. 3 заявка №10, пришедшая в систему в момент t10 , не успевает обслужиться до момента tmax , так как t10+Тобсл.>tmax . Следовательно, она не принимается свободным каналом К1 на обслуживание и сбрасывается в Вых ПТ, получая отказ.

Рис. 3

Из временных диаграмм видно, что необходимо научиться моделировать интервалы Т i . Применим метод обратных функций. Поскольку случайная величина Тi распределена по показательному закону с параметром λ =5, то плотность распределения имеет вид f (τ)=5е-5τ . Тогда значение F(Ti) функции распределения вероятностей определяется интегралом

.

Известно, что область значений функции распределения F (T ) есть отрезок . Выбираем из таблицы случайных чисел число и определяем Т i из равенства , откуда . Однако, если . Поэтому можно сразу получать из таблицы случайных чисел реализации . Следовательно,
е-5Т i = ri , или –5Т i = lnri , откуда . Результаты вычислений удобно заносить в таблицу.
Для проведения испытания №1 были взяты случайные числа из приложения 2, начиная с первого числа первой строки. Далее выборка осуществлялась по строкам. Проведем еще два испытания.
Обратите внимание на выборку случайных чисел из таблицы приложения 2, если в испытании №1 последнее случайное число для заявки №16 было 0,37 (первое случайное число во второй строке), то испытание №2 начинается со следующего за ним случайного числа 0,54. Испытание №2 содержит последним случайное число 0,53 (пятое число в третьей строке). Следовательно, третье испытание начнется с числа 0,19. Вообще в пределах одной серии испытаний случайные числа из таблицы выбираются без пропусков и вставок по определенному порядку, например, по строкам.

Таблица 1. ИСПЫТАНИЕ №1

№ зая-вки i	Сл. число ri		-ln ri Тi	Момент поступления заявки ti=ti-1+Ti	Момент окончания обслужив. ti+0,50		Счетчик заявок
					К1

Таблица 2 ИСПЫТАНИЕ №2

№ зая-вки i	Сл. число ri		-ln ri Т i	Момент поступления заявки ti=ti-1+Ti	Момент окончания обслужив. ti+0,50		Счетчик заявок

Таблица №3 ИСПЫТАНИЕ №3

№ зая-вки i		Сл. число ri		-ln ri Т i	Момент поступления заявки ti=ti-1+Ti	Момент окончания обслужив. ti+0,50		Счетчик заявок
						К1

Таким образом, по результатам трех испытаний число обслуженных заявок составило соответственно: х1 =9, х2 =9, х3 =8. Найдем среднее число обслуженных заявок:

Ответ: среднее число заявок, обслуженных СМО за 4 минуты, равно 8,6(6).

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

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

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

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

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

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

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

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

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

В качестве характеристик СМО рассматриваются:

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

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

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

Каждую СМО может характеризовать выражением: (a / b / c) : (d / e / f) , где

a - распределение входного потока заявок;

b - распределение выходного потока заявок;

c – конфигурация обслуживающего механизма;

d – дисциплина очереди;

e – блок ожидания;

f – емкость источника.

Теперь рассмотрим подробнее каждую характеристику.

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

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

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

1. один канал обслуживания (одна взлетно-посадочная полоса, один продавец);
2. один канал обслуживания, включающий несколько последовательных узлов (столовая, поликлиника, конвейер);
3. несколько однотипных каналов обслуживания, соединенных параллельно (АЗС, справочная служба, вокзал).

Таким образом, можно выделить одно- и многоканальные СМО.

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

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

Дисциплина очереди – это правило обслуживания заявок из очереди. К основным типам очереди можно отнести следующие:

1. ПЕРППО (первым пришел – первым обслуживаешься) – наиболее распространенный тип;
2. ПОСППО (последним пришел – первым обслуживаешься);
3. СОЗ (случайный отбор заявок) – из банка данных.
4. ПР – обслуживание с приоритетом.

Длина очереди может быть

• неограничена – тогда говорят о системе с чистым ожиданием;
• равна нулю – тогда говорят о системе с отказами;
• ограничена по длине (система смешанного типа).

Блок ожидания – «вместимость» системы – общее число заявок, находящихся в системе (в очереди и на обслуживании). Таким образом, е=с+ d .

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

Количество моделей СМО соответствует числу всевозможных сочетаний этих компонент.

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

С каждым отрезком времени [a , a + T ], свяжем случайную величину Х , равную числу требований, поступивших в систему за время Т .

Поток требований называется стационарным , если закон распределения не зависит от начальной точки промежутка а , а зависит только от длины данного промежутка Т . Например, поток заявок на телефонную станцию в течение суток (Т =24 часа) нельзя считать стационарным, а вот с 13 до 14 часов (Т =60 минут) – можно.

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

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

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

Основная теорема. Если поток – простейший, то с.в. Х [ a . a + T ] распределена по закону Пуассона, т.е. .

Следствие 1 . Простейший поток также называется пуассоновским.

Следствие 2 . M (X )= M (Х [ a , a + T ] )= l T , т.е. за время Т l T заявок. Следовательно, за одну единицу времени в систему поступает в среднем l заявок. Эта величина и называется интенсивностью входного потока.

Рассмотрим ПРИМЕР.

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

Решение.

По условию задачи, l =3, Т =2 дня, входной поток пуассоновский, n ³5. при решении удобно ввести противоположное событие, состоящее в том, что за время Т поступит меньше 5 заявок. Следовательно, по формуле Пуассона, получим

^

3.3 Состояние системы. Матрица и граф переходов.

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

Е 0 – все каналы свободны;

Е 1 – занят один канал;

Е n – заняты все каналы;

Е n +1 – заняты все каналы и одна заявка в очереди;

Е n + m – заняты все каналы и все места в очереди.

Аналогичная система с отказами может находиться в состояниях E 0 – E n .

Для СМО с чистым ожиданием существует бесконечное множество состояний. Таким образом, состояниеE n СМО в момент времени t – это количество n заявок (требований), находящихся в системе в данный момент времени, т.е. n = n (t ) – случайная величина, E n (t ) – исходы этой случайной величины, а P n (t ) – вероятность пребывания системы в состоянии E n .

С состоянием системы мы уже знакомы. Отметим, что не все состояния системы равнозначны. Состояние системы называется источником , если система может выйти из этого состояния, но не может в него вернуться. Состояние системы называется изолированным, если система не может выйти из этого состояния или в него войти.

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

Рисунок 3.1 – граф переходов

Сост.	Е 0	Е 1	Е 2
Е 0	Р 0,0	Р 0,1	Р 0,2
Е 1	Р 1,0	Р 1,1	Р 1,2
Е 2	Р 2,0	Р 2,2	Р 2,2

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

Так как система обязательно перейдет из одного

состояния в другое, то сумма вероятностей в каждой строке всегда равна единице.

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

3.4.1 Одноканальные СМО с отказами.

Будем рассматривать системы, удовлетворяющие требованиям:

(Р/Е/1):(–/1/¥) . Предположим также, что время обслуживания требования не зависит от количества требований, поступивших в систему. Здесь и далее «Р» означает, что входной поток распределен по закону Пуассона, т.е. простейший, «Е» означает, что выходной поток распределен по экспоненциальному закону. Также здесь и далее основные формулы даются без доказательства.

Для такой системы возможно два состояния: Е 0 – система свободна и Е 1 – система занята. Составим матрицу переходов. Возьмем D t – бесконечно малый промежуток времени. Пусть событие А состоит в том, что в систему за время D t поступило одно требование. Событие В состоит в том, что за время D t обслужено одно требование. Событие А i , k – за время D t система перейдет из состояния E i в состояние E k . Так как l – интенсивность входного потока, то за время D t в систему в среднем поступает l*D t требований. То есть, вероятность поступления одного требования Р(А)= l* D t , а вероятность противоположного событияР(Ā)=1- l*D t . Р(В)= F (D t )= P (b < D t )=1- e - m D t = m D t – вероятность обслуживания заявки за время D t . Тогда А 00 – заявка не поступит или поступит, но будет обслужена. А 00 =Ā+А* В. Р 00 =1- l*D t . (мы учли, что(D t ) 2 – бесконечно малая величина)

А 01 – заявка поступит, но не будет обслужена. А 01 =А* . Р 01 = l*D t .

А 10 – заявка будет обслужена и новой не будет. А 10 =В* Ā. Р 10 = m*D t .

А 11 – заявка не будет обслужена или поступит новая, которая еще не обслужена. А 11 =+В* А. Р 01 =1- m*D t .

Таким образом, получим матрицу переходов:

Сост.	Е 0	Е 1
Е 0	1-l* Dt	l* Dt
Е 1	m* Dt	1-m* Dt

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

Найдем теперь вероятность нахождения системы в состоянии Е 0 в любой момент времени t (т.е. р 0 ( t ) ). График функции
изображен на рисунке 3.2.

Асимптотой графика является прямая
.

Очевидно, начиная с некоторого момента t ,

1

Рисунок 3.2

Окончательно получим, что
и
, где р 1 (t ) – вероятность того, что в момент времени t система занята (т.е. находится в состоянии Е 1 ).

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

Стационарный режим работы и коэффициент загрузки системы.

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

На автомойке один блок для обслуживания. Автомобили прибывают по пуассоновскому распределению с интенсивностью 5 авто/час. Среднее время обслуживания одной машины – 10 минут. Найти вероятность того, что подъехавший автомобиль найдет систему занятой, если СМО работает в стационарном режиме.

Решение. По условию задачи, l =5, m y =5/6. Надо найти вероятность р 1 – вероятность отказа системы.
.

3.4.2 Одноканальные СМО с неограниченной длиной очереди.

Будем рассматривать системы, удовлетворяющие требованиям: (Р/Е/1):(d/¥/¥). Система может находиться в одном из состояний E 0 , …, E k , … Анализ показывает, что через некоторое время такая система начинает работать в стационарном режиме, если интенсивность выходного потока превышает интенсивность входного потока (т.е. коэффициент загрузки системы меньше единицы). Учитывая это условие, получим систему уравнений

решая которую найдем, что . Таким образом, при условии, что y <1, получим
Окончательно,
и
– вероятность нахождения СМО в состоянии Е k в случайный момент времени.

Средние характеристики системы.

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

• n – количество требований, находящихся в СМО (в очереди и на обслуживании);
• v – длину очереди;
• w – время ожидания начала обслуживания;
• w 0 – общее время нахождения в системе.

Нас будут интересовать средние характеристики (т.е. берем математическое ожидание от рассматриваемых случайных величин, и помним, что y <1).

– среднее число заявок в системе.

– средняя длина очереди.

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

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

На автомойке один блок для обслуживания и есть место для очереди. Автомобили прибывают по пуассоновскому распределению с интенсивностью 5 авто/час. Среднее время обслуживания одной машины – 10 минут. Найти все средние характеристики СМО.

Решение. l =5, m =60мин/10мин = 6. Коэффициент загрузки y =5/6. Тогда среднее число автомобилей в системе
, средняя длина очереди
, среднее время ожидания начала обслуживания
часа = 50 мин, и, наконец, среднее время нахождения в системе
час.

3.4.3 Одноканальные СМО смешанного типа.

Предположим, что длина очереди составляет m требований. Тогда, для любого s £ m , вероятность нахождения СМО в состоянии Е 1+ s , вычисляется по формуле
, т.е. одна заявка обслуживается и еще s заявок – в очереди.

Вероятность простоя системы равна
,

а вероятность отказа системы -
.

Даны три одноканальные системы, для каждой l =5, m =6. Но первая система – с отказами, вторая – с чистым ожиданием, а третья – с ограниченной длиной очереди, m =2. Найти и сравнить вероятности простоя этих трех систем.

Решение. Для всех систем коэффициент загрузки y =5/6. Для системы с отказами
. Для системы с чистым ожиданием
. Для системы с ограниченной длиной очереди
. Вывод очевиден: чем больше заявок находится в очереди, тем меньше вероятность простоя системы.

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

3.5.1 Многоканальные СМО с отказами.

Будем рассматривать системы (Р/Е/s):(-/s/¥) в предположении, что время обслуживания не зависит от входного потока и все линии работают независимо. Многоканальные системы, помимо коэффициента загрузки, можно также характеризовать коэффициентом
, где s – число каналов обслуживания. Исследуя многоканальные СМО, получим следующие формулы (формулы Эрлáнга ) для вероятности нахождения системы в состоянии Е k в случайный момент времени:

, k=0, 1, …

Функция стоимости.

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

Для поиска оптимального варианта надо найти (и это можно сделать) минимальное значение функции стоимости: С(s ) = с 1* l * p s +с 2* , график которой представлен на рисунке 3.3:

Рисунок 3.3

Поиск минимального значения функции стоимости состоит в том, что мы находим ее значения сначала дляs =1, затем для s =2, потом для s =3, и т.д. до тех пор, пока на каком-то шаге значение функции С(s ) не станет больше предыдущего. Это и означает, что функция достигла своего минимума и начала расти. Ответом будет то число каналов обслуживания (значение s ), для которого функция стоимости минимальна.

ПРИМЕР.

Сколько линий обслуживания должна содержать СМО с отказами, если l =2треб/час, m =1треб/час, штраф за каждый отказ составляет 7 тыс.руб., стоимость простоя одной линии – 2 тыс.руб. в час?

Решение. y = 2/1=2. с 1 =7, с 2 =2.

Предположим, что СМО имеет два канала обслуживания, т.е. s =2. Тогда
. Следовательно, С(2) = с 1 *l* p 2 +с 2 *(2- y* (1-р 2 )) = =7*2*0.4+2*(2-2*0.6)=7.2.

Предположим, что s =3. Тогда
, С(3) = с 1 *l* p 3 +с 2 *
=5.79.

Предположим, что имеется четыре канала, т.е. s =4. Тогда
,
, С(4) = с 1 *l* p 4 +с 2 *
=5.71.

Предположим, что СМО имеет пять каналов обслуживания, т.е. s =5. Тогда
, С(5) = 6.7 – больше предыдущего значения. Следовательно, оптимальное число каналов обслуживания – четыре.

3.5.2 Многоканальные СМО с очередью.

Будем рассматривать системы (Р/Е/s):(d/d+s/¥) в предположении, что время обслуживания не зависит от входного потока и все линии работают независимо. Будем говорить, что в системе установилсястационарный режим работы , если среднее число поступающих требований меньше среднего числа требований, обслуженных на всех линиях системы, т.е. l

P(w>0) – вероятность ожидания начала обслуживания,
.

Последняя характеристика позволяет решать задачу об определении оптимального числа каналов обслуживания с таким расчетом, чтобы вероятность ожидания начала обслуживания была меньше заданного числа. Для этого достаточно просчитать вероятность ожидания последовательно при s =1, s =2, s =3 и т.д.

ПРИМЕР.

СМО – станция скорой помощи небольшого микрорайона. l =3 вызова в час, а m = 4 вызова в час для одной бригады. Сколько бригад необходимо иметь на станции, чтобы вероятность ожидания выезда была меньше 0.01?

Решение. Коэффициент загрузки системы y =0.75. Предположим, что в наличие имеется две бригады. Найдем вероятность ожидания начала обслуживания при s =2.
,
.

Предположим наличие трех бригад, т.е. s =3. По формулам получим, что р 0 =8/17, Р(w >0)=0.04>0.01 .

Предположим, что на станции четыре бригады, т.е. s =4. Тогда получим, что р 0 =416/881, Р(w >0)=0.0077<0.01 . Следовательно, на станции должно быть четыре бригады.

3.6 Вопросы для самоконтроля

1. Предмет и задачи теории массового обслуживания.
2. СМО, их модели и обозначения.
3. Входной поток требований. Интенсивность входного потока.
4. Состояние системы. Матрица и граф переходов.
5. Одноканальные СМО с отказами.
6. Одноканальные СМО с очередью. Характеристики.
7. Стационарный режим работы. Коэффициент загрузки системы.
8. Многоканальные СМО с отказами.
9. Оптимизация функции стоимости.
10. Многоканальные СМО с очередью. Характеристики.

3.7 Упражнения для самостоятельной работы

1. Закусочная на АЗС имеет один прилавок. Автомобили прибывают в соответствии с пуассоновским распределением, в среднем 2 автомобиля за 5 минут. Для выполнения заказа в среднем достаточно 1.5 минуты, хотя продолжительность обслуживания распределена по экспоненциальному закону. Найти: а) вероятность простоя прилавка; b) средние характеристики; c) вероятность того, что количество прибывших автомобилей будет не менее 10.
2. Рентгеновский аппарат позволяет обследовать в среднем 7 человек в час. Интенсивность посетителей составляет 5 человек в час. Предполагая стационарный режим работы, определить средние характеристики.
3. Время обслуживания в СМО подчиняется экспоненциальному закону,
   m = 7требований в час. Найти вероятность того, что а) время обслуживания находится в интервале от 3 до 30 минут; b) требование будет обслужено в течение одного часа. Воспользоваться таблицей значений функции е х .
4. В речном порту один причал, интенсивность входного потока – 5 судов в день. Интенсивность погрузочно-разгрузочных работ – 6 судов в день. Имея в виду стационарный режим работы, определить все средние характеристики системы.
5. l =3, m =2, штраф за каждый отказ равен 5, а стоимость простоя одной линии равна 2?
6. Какое оптимальное число каналов обслуживания должна иметь СМО, если l =3, m =1, штраф за каждый отказ равен 7, а стоимость простоя одной линии равна 3?
7. Какое оптимальное число каналов обслуживания должна иметь СМО, если l =4, m =2, штраф за каждый отказ равен 5, а стоимость простоя одной линии равна 1?
8. Определить число взлетно-посадочных полос для самолетов с учетом требования, что вероятность ожидания должна быть меньше, чем 0.05. При этом интенсивность входного потока 27 самолетов в сутки, а интенсивность их обслуживания – 30 самолетов в сутки.
9. Сколько равноценных независимых конвейерных линий должен иметь цех, чтобы обеспечить ритм работы, при котором вероятность ожидания обработки изделий должна быть меньше 0.03 (каждое изделие выпускается одной линией). Известно, что интенсивность поступления заказов 30 изделий в час, а интенсивность обработки изделия одной линией – 36 изделий в час.
10. Непрерывная случайная величина Х распределена по показательному закону с параметром l=5. Найти функцию распределения, характеристики и вероятность попадания с.в. Х в интервал от 0.17 до 0.28.
11. Среднее число вызовов, поступающих на АТС за одну минуту, равно 3. Считая поток пуассоновским, найти вероятность того, что за 2 минуты поступит: а) два вызова; б) меньше двух вызовов; в) не менее двух вызовов.
12. В ящике 17 деталей, из которых 4 – бракованные. Сборщик наугад извлекает 5 деталей. Найти вероятность того, что а) все извлеченные детали – качественные; б) среди извлеченных деталей 3 бракованных.
13. Сколько каналов должна иметь СМО с отказами, если l =2треб/час, m =1треб/час, штраф за каждый отказ составляет 8т.руб., стоимость простоя одной линии – 2т.руб. в час?

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

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

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

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

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

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

Рассмотрим следующий пример.

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

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

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

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

1.Входящий поток требований.

2.Дисциплину очереди.

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

4.Выходящий поток требований.

Рис. 9.1. Модель теории массового обслуживания

В некоторых системах «очередь» отсутствует.

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

Приоритет может быть абсолютным или относительным.

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

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

Классификация СМО не ограничивается приведенными разновидностями.

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

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

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

ность может быть как постоянной, так и зависящей от t. Например, поток машин ночью не так интенсивен, как днем.

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

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

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

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

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

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

Пусть случайная величинаобозначает число требований на интервале .

Поток называется ординарным, если

Заметим, что

где

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

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

Можно показать, что для простейшего потока число требований в промежутке времени длиной t распределено по закону Пуассона с параметром(см. п. 7.2.1), т. е.

Стационарность и отсутствие последействия налицо, ординарность (т. е. условие (9.1)) вытекает из равенства

которое можно проверить по правилу Лопиталя.

Параметр X здесь характеризует интенсивность потока. Действительно,

Простейший поток еще называют стационарным пуассоновским.

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

Решение. Пусть интенсивностьполомки/ч. По формуле (9.2)

прии t =1 найдем вероятность k поломок в течение часа

Составим табл. 9.1. Таблица 9.1

k

....

p k (1)

0,05

0,15

0,22

0,22

0,17

0,05

....

Следующее важное понятие ТМО - это время обслуживания.

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

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

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

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

Далее коротко опишем я-канальную систему массового обслуживания с отказами. Это «классическая» задача ТМО, возникшая из практических нужд телефонии и решенная в начале ХХ века датским математиком Эрлангом. Задача ставится так.

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

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

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

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

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

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

. Р отк - вероятность отказа, или того, что заявка покинет СМО необслуженной;

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

. - вероятность того, что занято ровно k каналов, и, в частности, Р 0 - вероятность простоя системы;

. - коэффициент занятости каналов в процентах (%);

.
- коэффициент простоя каналов

в процентах (%). Обозначим

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

а вероятностиприимеют вид

Формулы (9.6), (9.7) для вероятностей Р к называются формулами Эрланга - в честь основателя ТМО. С их помощью можно вычислить остальные интересующие нас характеристики СМО. Так, вероятность Действительно, для того чтобы пришедшая заявка получила отказ, необходимо, чтобы все я каналов были заняты. Итак,

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

Абсолютную пропускную способность получим, умножая интенсивность потока заявок на Q:

Среднее число занятых каналовпо определению математического ожидания с учетом формул (9.6) и (9.7) равно

Отметим, что, зная вероятность отказав обслуживании

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

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

Отсюда заключаем, что на АТС в среднем занято 2 линии из 5, каждая линия загружена всего на 39 %, теряется приблизительно 4 вызова из 100. Таким образом, АТС работает не слишком эффективно, и вполне можно сократить общее число линий и (или) увеличить интенсивность потока заявок.

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

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

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

Таким образом, загрузка каждого из двух оставшихся продавцов немного вырастет (с 0,53 до 1/2 . 1,2 = 0,6 рабочего дня), зато «коэффициент полезного действия» аптеки упадет с 0,79 до 0,6, поскольку в сложившейся ситуации будет обслужено лишь 60 % ((1 - 0,4) . 100 %) потенциальных клиентов, а не 79 % как ранее при трех продавцах.

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

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

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

• показатели, характеризующие систему в целом: число n занятых каналов обслуживания, число обслуженных (λ b ), ожидающих обслуживание или получивших отказ заявок (λ c ) в единицу времени и т.д.;
• вероятностные характеристики : вероятность того, что заявка будет обслужена (P обс) или получит отказ в обслуживании (P отк), что все приборы свободны (p 0) или определенное число их занято (p k ), вероятность наличия очереди и т.д.;
• экономические показатели : стоимость потерь, связанных с уходом не обслуженной по тем или иным причинам заявки из системы, экономический эффект, полученный в результате обслуживания заявки, и т.д.

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

Многоканальная система с отказами

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

Смешанные системы

1. Система с ограничением на длину очереди .
   Состоит из накопителя (очереди) и узла обслуживания. Заявка покидает очередь и уходит из системы, если в накопителе к моменту ее появления уже находятся m заявок (m – максимально возможноечисло мест в очереди). Если заявка поступила в систему и застала, хотя бы один канал свободным, она мгновенно начинает обслуживаться. Если в момент поступления заявки в систему все каналы заняты, то заявка не покидает систему, а занимает место в очереди. Заявка покидает систему не обслуженной, если к моменту её поступления в систему заняты все каналы обслуживания и все места в очереди.
   Для каждой системы определяется дисциплина очереди. Это система правил, определяющих порядок поступления заявок из очереди в узел обслуживания. Если все заявки и каналы обслуживания равнозначны, то чаще всего действует правило «кто раньше пришел, тот раньше обслуживается».
2. Система с ограничением на длительность пребывания заявки в очереди .
   Состоит из накопителя (очереди) и узла обслуживания. От предыдущей системы она отличается тем, что заявка, поступившая в накопитель (очередь), может ожидать начала обслуживания лишь ограниченное время Т ож (чаще всего это случайная величина). Если её время Т ож истекло, то заявка покидает очередь и уходит из системы не обслуженной.

Математическое описание СМО

СМО рассматриваются как некоторые физические системы с дискретными состояниями х 0 , х 1 , …, х n , функционирующие при непрерывном времени t . Число состояний n может быть конечным или счетным (n → ∞). Система может переходить из одного состояния х i (i= 1, 2, … , n) в другое х j (j= 0, 1, … ,n) в произвольный момент времени t . Чтобы показать правила таких переходов, используют схему, называемую графом состояний . Для типов перечисленных выше систем графы состояний образуют цепь, в которой каждое состояние (кроме крайних) связано прямой и обратной связью с двумя соседними состояниями. Это схема гибели и размножения.
Переходы из состояния в состояние происходят в случайные моменты времени. Удобно считать, что эти переходы происходят в результате действия каких-то потоков (потоков входных заявок, отказов в обслуживании заявок, потока восстановления приборов и т.д.). Если все потоки простейшие, то протекающий в системе случайный процесс с дискретным состоянием и непрерывным временем будет марковским.
Поток событий - это последовательность однотипных событий, протекающих в случайные моменты времени. Его можно рассматривать как последовательность случайных моментов времени t 1 , t 2 , … появления событий.
Простейшим называют поток, обладающий следующими свойствами:

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

В простейшем потоке интервалы времени Т 1 , Т 2 ,… между моментами t 1 , t 2 , … появления событий случайны, независимы между собой и имеют показательное распределение вероятностей f(t)=λe -λt , t≥0, λ=const, где λ - параметр показательного распределения, являющийся одновременно интенсивностью потока и представляющий собой среднее число событий, происходящих в единицу времени. Таким образом, .
Марковские случайные события описываются обыкновенными дифференциальными уравнениями . Переменными в них служат вероятности состояний р 0 (t), p 1 (t),…,p n (t) .
Для очень больших моментов времени функционирования систем (теоретически при t → ∞) в простейших системах (системы, все потоки в которых – простейшие, а граф – схема гибели и размножения) наблюдается установившийся, или стационарный режим работы. В этом режиме система будет изменять свое состояние, но вероятности этих состояний (финальные вероятности ) р к , к= 1, 2 ,…, n, не зависят от времени и могут рассматриваться как среднее относительное время пребывания системы в соответствующем состоянии.