Цели

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

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

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

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

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

Система массового обслуживания;

Очередь;

Темп поступления заявок;

Темп обслуживания;

Среднее время, которое заявка проводит в очереди;

Средняя длина очереди;

Среднее время, которое заявка проводит в системе обслужи­вания;

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

Издержки функционирования системы обслуживания;

Издержки ожидания.

Модели

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

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

1) появление заявки на входе в систему;

2) прохождение очереди;

3) процесс обслуживания, после которого заявка покидает систему.

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

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

1) число заявок на входе (размер популяции);

2) режим поступления заявок в систему обслуживания;

3) поведение клиентов.

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

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

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

Где Р (х) - вероятность поступления Х заявок в единицу вре­мени;

Х - число заявок в единицу времени;

L - среднее число заявок в единицу времени (темп по­ступления заявок);

Соответствующие значения вероятностей Р(х) нетрудно опре­делить с помощью таблицы пуассоновского распределения. Если, например, средний темп поступления заявок - два клиента в час, то вероятность того, что в течение часа в систему не поступит ни одной заявки, равна 0,135, вероятность появления одной заявки - около 0,27, двух - также около 0,27, три заявки могут появиться с вероятностью 0,18, четыре - с вероятностью около 0,09 и т. д. Вероятность того, что за час в систему поступят 9 заявок или бо­лее, близка нулю.

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

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

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

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

2) правило обслуживания.

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

Правило обслуживания. Большинство реальных систем исполь­зует правило «первым пришел - первым ушел» (FIFO - first in, first out). В некоторых случаях, например в приемном покое боль­ницы, в дополнение к этому правилу могут устанавливаться раз­личные Приоритеты. Пациент с инфарктом в критическом со­стоянии, по-видимому, будет иметь приоритет в обслуживании по сравнению с пациентом, сломавшим палец. Порядок запуска компьютерных программ - другой пример установления приорите­тов в обслуживании.

Характеристики процесса обслуживания:

1) конфигурация системы обслуживания (число каналов и чис­ло фаз обслуживания);

2) режим обслуживания.

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

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

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

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

F(T) = P(T< t) =1 – е–tm, где Р (T < t) - вероятность того, что фактическое время T обслу­живания заявки не превысит заданной величи­ны t;

M - среднее число заявок, обслуживаемых в едини­цу времени;

Е = 2,7182 - основание натурального логарифма.

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

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

1) среднее время, которое клиент проводит в очереди;

2) средняя длина очереди;

3) среднее время, которое клиент проводит в системе обслужи­вания (время ожидания плюс время обслуживания);

4) среднее число клиентов в системе обслуживания;

5) вероятность того, что система обслуживания окажется незанятой;

6) вероятность определенного числа клиентов в системе.

Среди Экономических характеристик наибольший интерес пред­ставляют следующие:

1) издержки ожидания в очереди;

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

3) издержки обслуживания.

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

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

А) пуассоновское распределение вероятностей поступления заявок;

Б) стандартное поведение клиентов;

В) правило обслуживания FIFO (первым пришел - первым об­служен);

Г) единственная фаза обслуживания.

I. Модель А - модель одноканальной системы массового об­служивания М/М/ 1 с Пуассоновским входным потоком заявок и Экспоненциальным временем обслуживания.

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

1. Заявки обслуживаются по принципу «первым пришел - пер­вым обслужен» (FIFO), причем каждый клиент ожидает своей очереди до конца независимо от длины очереди.

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

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

4. Время обслуживания описывается экспоненциальным рас­пределением вероятностей.

5. Темп обслуживания выше темпа поступления заявок.

Пусть l - число заявок в единицу времени;

M - число клиентов, обслуживаемых в единицу времени;

П - число заявок в системе.

Тогда система массового обслуживания описывается уравнени­ями, приведенными ниже.

Формулы для описания системы М/М/ 1:

- среднее число клиентов в системе;

Среднее время обслуживания одного клиента в системе (время ожидания плюс время обслуживания);

Среднее число клиентов в очереди;

Среднее время ожидания клиента в очереди;

Характеристика загруженности системы (доля време­ни, в течение которого система занята обслуживанием);

Вероятность отсутствия заявок в системе;

Вероятность того, что в системе находится бо­лее чем K заявок.

II. Модель В - многоканальная система обслуживания M/ M/ S. В многоканальной системе для обслуживания открыты два ка­нала или более. Предполагается, что клиенты ожидают в общей очереди и обращаются в первый освободившийся канал обслужи­вания.

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

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

Время нахождения заявки в очереди;

Время нахождения заявки в системе.

III. Модель С- модель с постоянным временем обслуживания M/ D/ 1.

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

Формулы, описывающие модель С:

- средняя длина очереди;

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

Среднее число клиентов в системе;

Среднее время ожидания в системе.

IV. Модель D - модель с ограниченной популяцией.

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

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

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

Как частный случай модели с ограниченной очередью можно рассматривать Модель с отказами, если количество мест в очере­ди сократить до нуля.

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

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

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

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

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

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

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

Рис. 1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

first in first out (FIFO)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

.

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

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

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

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

Простейший поток и применение практических задач.

Нестационарные пуассоновские потоки.

Потоки с ограниченными последствиями (потоки Пальма).

Потоки восстановления.

1. Введение.

1.1. Историческая справка.

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

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

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

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

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

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

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

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

Задача: Обеспечить определенный объем перевозок при минимальных расходах. При этом сократить простои судов при погрузочно-разгрузочных работах.

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

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

Пример 5 . На рис 1.1. изображена структурная схема типичной системы массового обслуживания – ремонтного предприятия (например, по ремонту ПЭВМ). Порядок ее работы ясен из схемы и не требует разъяснений.

рис 1.1.

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

Характерным для таких задач является:

1. условия “двойной” случайности –

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

2)проблема бича нашего времени – очередей: судов перед шлюзами, машин перед прилавками, задач на входе процессоров вычислительного комплекса и т.д.

А.К. Эрланг обратил внимание на то, что СМО могут быть разделены на два типа, а именно: на системы с ожиданием и системы с потерями. В первом случае – заявка, поступившая на вход системы “ждет” очереди на выполнение, во втором – она из-за занятости канала обслуживания получает отказ и теряется для СМО.

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

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

1.3. Понятия, определения, терминология.

Все СМО имеют вполне определенную структуру, изображенную на рис 1.2

рис 1.2

Определения, термины

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

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

1.4.1. По характеру источника требований различают СМО с конечным и бесконечным количеством требований на входе.

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

Во втором случае источник генерирует бесконечное число требований.

Пример 1. Цех с постоянным количеством станков или определенное количество ПЭВМ в терминальном классе, требующих постоянного профилактического осмотра и ремонта.

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

Первый вид СМО называют замкнутой, второй – разомкнутой.

СМО различают:

1.4.2. По дисциплине обслуживания:

1. обслуживание в порядке поступления;
2. обслуживание в случайном порядке (в соответствии с заданным законом распределения);
3. обслуживание с приоритетом.

1.4.3. по характеру организации:

1. с отказами;
2. с ожиданиями;
3. с ограничением ожидания.

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

1.4.4. По количеству единиц обслуживания:

1. одноканальные;
2. двухканальные;
3. многоканальные.

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

1.4.6. По свойствам каналов: на однородные, когда каналы имеют одинаковую характеристику и неоднородные в противном случае.

ВВЕДЕНИЕ

ГЛАВА I. ПОСТАНОВКА ЗАДАЧ МАССОВОГО ОБСЛУЖИВАНИЯ

1.1 Общие понятие теории массового обслуживания

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

1.3 Графы состояний СМО

1.4 Случайные процессы

Глава II. УРАВНЕНИЯ, ОПИСЫВАЮЩИЕ СИСТЕМЫ МАССОВОГО ОБСЛУЖИВАНИЯ

2.1 Уравнения Колмогорова

2.2 Процессы «рождения – гибели»

2.3 Экономико-математическая постановка задач массового обслуживания

Глава III. МОДЕЛИ СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ

3.1 Одноканальная СМО с отказами в обслуживании

3.2 Многоканальная СМО с отказами в обслуживании

3.3 Модель многофазной системы обслуживания туристов

3.4 Одноканальная СМО с ограниченной длиной очереди

3.5 Одноканальная СМО с неограниченной очередью

3.6 Многоканальная СМО с ограниченной длиной очереди

3.7 Многоканальная СМО с неограниченной очередью

3.8 Анализ системы массового обслуживания супермаркета

ЗАКЛЮЧЕНИЕ

Введение

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

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

Теория массового обслуживания - область прикладной математики, занимающаяся анализом процессов в системах производства, обслуживания, управления, в которых однородные события повторяются многократно, например, на предприятиях бытового обслуживания; в системах приема, переработки и передачи информации; автоматических линиях производства и др. Большой вклад в развитие этой теории внесли российские математики А.Я. Хинчин, Б.В. Гнеденко, А.Н. Колмогоров, Е.С. Вентцель и др.

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

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

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

Глава I . Постановка задач массового обслуживание

1.1 Общие понятие теории массового обслуживания

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

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

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

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

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

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

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

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

Действительно, продолжительность пребывания покупателя в супермаркете зависит, с одной стороны, от личностных качеств покупателя, его запросов, от ассортимента товаров, который он собирается приобрести, а с другой - от формы организации обслуживания и обслуживающего персонала, что может значительно повлиять на время пребывания покупателя в супермаркете и интенсивность обслуживания. Например, овладение кассирами-контролерами работы «слепым» методом на кассовом аппарате позволило увеличить пропускную способность узлов расчета в 1,3 раза и сэкономить время, затрачиваемое на расчеты с покупателями по каждой кассе более чем на 1,5 ч в день. Внедрение единого узла расчета в супермаркете дает ощутимые преимущества покупателю. Так, если при традиционной форме расчетов время обслуживания одного покупателя составляло в среднем 1,5 мин, то при введении единого узла расчета - 67 с. Из них 44 с уходят на оформление покупки в секции и 23 с непосредственно на расчеты за покупки. Если покупатель делает несколько покупок в разных секциях, то потери времени сокращаются при приобретении двух покупок в 1,4 раза, трех - в 1,9, пяти - в 2,9 раза.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

P m, n = a m _e -a ; (m=0,n),

где величина а = пр - среднее число событий, попадающих на промежуток времени t, которое можно определить через интенсивность потока событий Xследующим образом: a= λ τ

Размерность интенсивности потока X есть среднее число событий в единицу времени. Между п и λ, р и τ имеется следующая связь:

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

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

По условию в течение времени T не должно произойти ни одного события, а на интервале времени t должно появиться хотя бы одно событие. Эта вероятность вычисляется с помощью вероятности противоположного события на промежутке времени (0; t), куда не попало ни одного события, т.е. m= 0, тогда

F(t)=1-P 0 =1-(a 0 *e -a)0!=1-e -Xt ,t≥0

Для малых ∆tможно получить приближенную формулу, получаемую заменой функции e - Xt , только двумя членами разложения в ряд по степеням ∆t, тогда вероятность попадания на малый промежуток времени ∆t хотя бы одного события составляет

P(T<∆t)=1-e - λ t ≈1- ≈ λΔt

Плотность распределения промежутка времени между двумя последовательными событиями получим, продифференцировав F(t) по времени,

f(t)= λe- λ t ,t≥0

Пользуясь полученной функцией плотности распределения, можно получить числовые характеристики случайной величины Т: математическое ожидание М (Т), дисперсию D(T) и среднее квадратическое отклонение σ(Т).

М(Т)= λ ∞ ∫ 0 t*e - λt *dt=1/ λ ; D(T)=1/ λ 2 ; σ(T)=1/ λ .

Отсюда можно сделать следующий вывод: средний интервал времени Т между любыми двумя соседними событиями в простейшем потоке в среднем равен 1/λ , и его среднее квадратическое отклонение также равно 1/λ, λ где, - интенсивность потока, т.е. среднее число событий, происходящих в единицу времени. Закон распределения случайной величины, обладающей такими свойствами М(Т) = Т, называется показательным (или экспоненциальным), а величина λ, является параметром этого показательного закона. Таким образом, для простейшего потока математическое ожидание интервала времени между соседними событиями равно его среднеквадратическому отклонению. В этом случае вероятность того, что число заявок, поступающих на обслуживание за промежуток времени t, равно к, определяется по закону Пуассона:

P k (t)=(λt) k / k! *e -λ t ,

где λ - интенсивность поступления потока заявок, среднее число событий в СМО за единицу времени, например[чел/мин; руб./час; чеков/час; докум./день; кг./час; т./год] .

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

ƒ(t)= λe - λ t .

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

ƒ (t оч)=V*e - v t оч,

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

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

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

ƒ(t обс)=µ*е µ t обс,

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

µ=1/ t обс [чел/мин; руб./час; чеков/час; докум./день; кг./час; т./год] ,

где t обс - среднее время обслуживания заявок.

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

Кроме понятия простейшего потока событий часто приходится пользоваться понятиями потоков других типов. Поток событий называется потоком Пальма, когда в этом потоке промежутки времени между последовательными событиями T 1 , T 2 , ..., Т k ..., Т n являются независимыми, одинаково распределенными, случайными величинами, нов отличие от простейшего потока не обязательно распределенными по показательному закону. Простейший поток является частным случаем потока Пальма.

Важным частным случаем потока Пальма является так называемый поток Эрланга.

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

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

Можно получить потоки Эрланга любого к-го порядка. Очевидно, простейший поток есть поток Эрланга первого порядка.

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

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

Перечисленные выше характеристики к, τ, λ, L оч, Т оч, v, t обс, µ, р, Р k являются наиболее общими для СМО, которые являются обычно лишь некоторой частью целевой функции, поскольку необходимо учитывать еще и показатели коммерческой деятельности.

1.3 Графы состояний СМО

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

12

Рис. 1.3. Размеченный граф состояний СМО

Система может находиться в одном из трех состояний: S 0 -канал свободен, простаивает, S 1 - канал занят обслуживанием, S 2 - канал занят обслуживанием и одна заявка в очереди. Переход системы из состояния S 0 в S l происходит под воздействием простейшего потока заявок интенсивностью λ 01 а из состояния S l в состояние S 0 систему переводит поток обслуживания с интенсивностью λ 01 . Граф состояний системы обслуживания с проставленными интенсивностями потоков у стрелок называется размеченным. Поскольку пребывание системы в том или ином состоянии носит вероятностный характер, то вероятность:p i (t) того, что система будет находиться в состоянии S i в момент времени t, называется вероятностью i-го состояния СМО и определяется числом поступивших заявок k на обслуживание.

Случайный процесс, происходящий в системе, заключается в том, что в случайные моменты времени t 0 , t 1, t 2 ,..., t k ,..., t n система оказывается в том или другом заранее известном дискретном состоянии последовательно. Такая. случайная последовательность событий называется Марковской цепью, если для каждого шага вероятность перехода из одного состояния S t в любое другое Sjне зависит от того, когда и как система перешла в состояние S t . Описывается марковская цепь с помощью вероятности состояний, причем они образуют полную группу событий, поэтому их сумма равна единице. Если вероятность перехода не зависит от номера к, то марковская цепь называется однородной. Зная начальное состояние системы обслуживания, можно найти вероятности состояний для любого значения к-числа заявок поступивших на обслуживание.

1.4 Случайные процессы

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

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

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

Марковские случайные процессы делятся на два класса: процессы с дискретными и непрерывными состояниями. Процесс с дискретными состояниями возникает в сиcтемах, обладающих только некоторыми фиксированными состояниями, между которыми возможны скачкообразные переходы в некоторые, заранее не известные моменты времени. Рассмотрим пример процесса с дискретными состояниями. В офисе фирмы имеются два телефона. Возможны следующие состояния у этой системы обслуживания: S o -телефоны свободны; S l - один из телефонов занят; S 2 - оба телефона заняты.

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

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

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

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

Для описания процессов с непрерывным временем используется модель в виде так называемой марковской цепи с дискретными состояниями системы, или непрерывной марковской цепью.

Глава II . Уравнения описывающие системы массового обслуживания

2.1 Уравнения Колмогорова

Рассмотрим математическое описание марковского случайного процесса с дискретными состояниями системы S o , S l , S 2 (см. рис. 6.2.1) и непрерывным временем. Полагаем, что все переходы системы массового обслуживания из состояния S i в состояние Sjпроисходят под воздействием простейших потоков событий с интенсивностями λ ij , а обратный переход под воздействием другого потока λ ij ,. Введем обозначение p i как вероятность того, что в момент времени t система находится в состоянии S i . Для любого момента времени tсправедливо записать нормировочное условие-сумма вероятностей всех состояний равна 1:

Σp i (t)=p 0 (t)+ p 1 (t)+ p 2 (t)=1

Проведем анализ системы в момент времени t, задав малое приращение времени Δt, и найдем вероятность р 1 (t+ Δt) того, что система в момент времени (t+ Δt) будет находиться в состоянии S 1 которое достигается разными вариантами:

а) система в момент t с вероятностью p 1 (t) находилась в состоянии S 1 и за малое приращение времени Δt так и не перешла в другое соседнее состояние - ни в S 0 , ни bS 2 . Вывести систему из состояния S 1 можно суммарным простейшим потоком c интенсивностью (λ 10 +λ 12), поскольку суперпозиция простейших потоков также является простейшим потоком. На этом основании вероятность выхода из состояния S 1 за малый промежуток времени Δtприближенно равна (λ 10 +λ 12)* Δt. Тогда вероятность невыхода из этого состояния равна .Bсоответствии с этим вероятность того, что система останется в состоянии Siна основании теоремы умножения вероятностей, равна:

p 1 (t) ;

б)система находилась в соседнем состоянии S o и за малое время Δt перешла в состояние S o Переход системы происходит под воздействием потока λ 01 с вероятностью, приближенно равной λ 01 Δt

Вероятность того, что система будет находиться в состоянии S 1 , в этом варианте равна p o (t)λ 01 Δt;

в) система находилась в состоянии S 2 и за время Δt перешла в состояние S 1 под воздействием потока интенсивностью λ 21 с вероятностью, приближенно равной λ 21 Δt. Вероятность того, что система будет находиться в состоянии S 1 , равна p 2 (t) λ 21 Δt.

Применяя теорему сложения вероятностей для этих вариантов, получим выражение:

p 2 (t+Δt)= p 1 (t) + p o (t)λ 01 Δt+p 2 (t) λ 21 Δt ,

которое можно записать иначе:

p 2 (t+Δt)-p 1 (t)/ Δt= p o (t)λ 01 + p 2 (t) λ 21 - p 1 (t) (λ 10 +λ 12) .

Переходя к пределу при Δt-> 0, приближенные равенства перейдут в точные, и тогда получим производную первого порядка

dp 2 /dt= p 0 λ 01 +p 2 λ 21 -p 1 (λ 10 +λ 12) ,

что является дифференциальным уравнением.

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

dp 0 /dt= p 1 λ 10 ,

dp 1 /dt= p 0 λ 01 +p 2 λ 21 -p 1 (λ 10 +λ 12) ,

dp 2 /dt= p 1 λ 12 +p 2 λ 21 .

Для составления уравнений Колмогорова существуют общие правила.

Уравнения Колмогорова позволяют вычислить все вероятности состояний СМО S i в функции времени p i (t). В теории случайных процессов показано, что если число состояний системы конечно, а из каждого из них можно перейти в любое другое состояние, то существуют предельные (финальные) вероятности состояний, которые показывают на среднюю относительную величину времени пребывания системы, в этом состоянии. Если предельная вероятность состояния S 0 – равна p 0 = 0,2, то, следовательно, в среднем 20% времени, или 1/5 рабочего времени, система находится в состоянии S o . Например, при отсутствии заявок на обслуживание к = 0, р 0 = 0,2,; следовательно, в среднем 2 ч в день система находится в состоянии S o и простаивает, если продолжительность рабочего дня составляет 10 ч.

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

Например, для СМО, имеющей размеченный граф из трех состояний S o , S 1 , S 2 рис. 6.2.1, система уравнений Колмогорова, составленная на основе изложенного правила, имеет следующий вид:

Для состояния S o → p 0 λ 01 = p 1 λ 10

Для состояния S 1 →p 1 (λ 10 +λ 12) = p 0 λ 01 +p 2 λ 21

Для состояния S 2 → p 2 λ 21 = p 1 λ 12

p 0 +p 1 +p 2 =1

dp 4 (t)/dt=λ 34 p 3 (t) - λ 43 p 4 (t) ,

p 1 (t)+ p 2 (t)+ p 3 (t)+ p 4 (t)=1 .

К этим уравнениям надо добавить еще начальные условия. Например, если при t = 0 система S находится в состоянии S 1, то начальные условия можно записать так:

p 1 (0)=1, p 2 (0)= p 3 (0)= p 4 (0)=0 .

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

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

p i (t), p 2 (t),…., p n (t) .

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

lim p i (t) = p i (i=1,2,…,n) ; t→∞

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

Вычислить предельные вероятности состояния р i можно, если в системе положить все производные равными 0, поскольку в уравнениях Колмогорова при t-> ∞ зависимость от времени пропадает. Тогда система дифференциальных уравнений превращается в систему Обычных линейных алгебраических уравнений, которая совместно с нормировочным условием позволяет вычислить все предельные вероятности состояний.

2.2 Процессы «рождения – гибели»

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

S 3

kjlS n

μ 0 μ 1 μ 3 μ 4 μ n-1

Рис. 2.1 Размеченный граф процесса «рождения - гибели»

Этот граф воспроизводит известную биологическую интерпретацию: величина λ k отображает интенсивность рождения нового представителя некоторой популяции, например, кроликов, причем текущий объем популяции равен k; величина μ является интенсивностью гибели (продажи) одного представителя этой популяции, если текущий объем популяции равен k. В частности, популяция может быть неограниченной (число n состояний марковского процесса является бесконечным, но счетным), интенсивность λ может быть равна нулю (популяция без возможности возрождения), например, при прекращении воспроизводства кроликов.

Для Марковского процесса «рождения - гибели», описанного стохастическим графом, приведенным на рис. 2.1, найдем финальное распределение. Пользуясь правилами составления уравнений для конечнего числа n предельных вероятностей состояния системы S 1 , S 2 , S 3 ,… S k ,…, S n , составим соответствующие уравнения для каждого состояния:

для состояния S 0 -λ 0 p 0 =μ 0 p 1 ;

для состояния S 1 -(λ 1 +μ 0)p 1 = λ 0 p 0 +μ 1 p 2 , которое с учетом предыдущего уравнения для состояния S 0 можно преобразовать к виду λ 1 р 1 = μ 1 p 2 .

Аналогично можно составить уравнения для остальных состояний системы S 2 , S 3 ,…, S k ,…, S n . В результате получим следующую систему уравнений:

Решая эту систему уравнений, можно получить выражения, определяющие финальные состояния системы массового обслуживания:

Следует заметить, что в формулы определения финальных вероятностей состояний р 1 , р 2 , р 3 ,…, р n , входят слагаемые, являющиеся составной частью суммы выражения, определяющей р 0 . В числителях этих слагаемых находятся произведения всех интенсивностей, стоящих у стрелок графа состояний, ведущих слева на право до рассматриваемого состояния S k , а знаменатели представляют собой произведения всех интенсивностей, стоящих у стрелок, ведущих справа на лево до рассматриваемого состояния S k , т.е. μ 0 , μ 1 , μ 2 , μ 3 ,… μ k . В связи с этим запишем эти модели в более компактном виде:

к=1,n

2.3 Экономико-математическая постановка задач массового обслуживания

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

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

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

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

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

Например, особенностями показателей СМО с отказами являются: время ожидания заявок в очереди Т оч =0, поскольку по своей природе в таких системах существование очереди невозможно, то L оч =0 и, следовательно, вероятность ее образования Р оч =0. По числу заявок k определятся режим работы системы, ее состояние: при k=0 – простой каналов, при 1n – обслуживание и отказ. Показателями таких СМО являются вероятность отказа в обслуживании Р отк, вероятность обслуживания Р обс, среднее время простоя канала t пр, среднее число занятых n з и свободных каналов n св, среднее обслуживания t обс, абсолютная пропускная способность А.

Для СМО с неограниченным ожиданием характерно, что вероятность обслуживания заявки Р обс =1, поскольку длина очереди и время ожидания начала обслуживания не ограничены, т.е. формально L оч →∞ и Т оч →∞. В системах возможны следующие режимы работы: при k=0 наблюдается простой каналов обслуживания, при 1n – обслуживание и очередь. Показателями таких эффективности таких СМО являются среднее число заявок в очереди L оч, среднее число заявок в системе k, среднее время пребывания заявки в системе Т смо, абсолютная пропускная способность А.

В СМО с ожиданием с ограничением на длину очереди, если число заявок в системе k=0, то наблюдается простой каналов, при 1n+m- обслуживание, очередь и отказ в ожидании обслуживания. Показателями эффективности таких СМО являются вероятность отказа в обслуживании Р отк - вероятность обслуживания Р обс, среднее число заявок в очереди L оч, среднее число заявок в системе L смо среднее время пребывания заявки в системе Т смо, абсолютная пропускная способность А.

Таким образом, перечень характеристик систем массового обслуживания можно представить следующим образом: среднее время обслуживания – t обс; среднее время ожидания в очереди – Т оч; среднее пребывания В СМО – Т смо; средняя длина очереди - L оч; среднее число заявок в СМО- L смо; количество каналов обслуживания – n; интенсивность входного потока заявок – λ; интенсивность обслуживания – μ; интенсивность нагрузки – ρ; коэффициент нагрузки – α; относительная пропускная способность – Q; абсалютная пропускная способность – А; доля времени простоя в СМО – Р 0 ; доля обслуженных заявок – Р обс; доля потерянных заявок – Р отк, среднее число занятых каналов – n з; среднее число свободных каналов - n св; коэффициент загрузки каналов – К з; среднее время простоя каналов - t пр.

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

Это часто связано с решением вопросов согласованной рабоиы цепочки или совокупностей СМО.

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

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

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

С= (С ио +С ип) →min

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

С={(С пр n св +С экз n з)+С оч Р обс λ(Т оч +t обс)+С из Р отк λ}→min.

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

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

С={С экз n з +C пр (n-n з)+C отк *Р отк *λ+С сист * n з }→min

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

К об =[(З пу *К у)+(З пв *К в)+(З пд *К д)+(З пз *К з)+(З по *К 0)+(З кт *К кт)]*К мп,

где З пу – значимость показателя устойчивости ассортимента товаров;

К у - коэффициент устойчивости ассортимента товаров;

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

К в – коэффициент внедрения прогрессивных методов продажи товаров;

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

К д - коэффициент дополнительного обслуживания;

З пз - значимость показателя завершенности покупки;

К з - коэффициент завершенности покупки;

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

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

З кт – значимость показателя качества труда коллектива;

К кт – коэффициент качества труда коллектива;

К мп – показатель культуры обслуживания по мнению покупателей;

Для анализа СМО можно выбирать и другие критерии оценки эффективности работы СМО. Например, в качестве такого критерия для систем с отказами можно выбирать вероятность отказа Р отк, значение которого не превышало бы заранее заданной величины. Например, требование Р отк <0,1 означает, что не менее чем в 90% случаев система должна справляться с обслуживанием потока заявок при заданной интенсивности λ. Можно ограничить среднее время пребывания заявки в очереди или в системе. В качестве показателей, подлежащих определению, могут выступать: либо число каналов n при заданной интенсивности обслуживания μ, либо интенсивность μ при заданном числе каналов.

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

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

3.1 Одноканальная СМО с отказами в обслуживании

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

Работу одноканальной СМО n=1 можно представить в виде размеченного графа состояний (3.1).

Переходы СМО из одного состояния S 0 в другое S 1 происходят под действием входного потока заявок с интенсивностью λ, а обратный переход – под действием потока обслуживания с интенсивностью μ.

S 0

S 1

S 0 – канал обслуживания свободен; S 1 – канал занят обслуживанием;

Рис. 3.1 Размеченный граф состояний одноканальной СМО

Запишем систему дифференциальных уравнений Колмогорова для вероятностей состояния по изложенным выше правилам:

Откуда получим дифференциальное уравнение для определения вероятности р 0 (t) состояния S 0:

Это уравнение можно решить при начальных условиях в предположении, что система в момент t=0 находилась в состоянии S 0 , тогда р 0 (0)=1, р 1 (0)=0.

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

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

Вероятность р 0 (t) уменьшается с течением времени и в пределе при t→∞ стремится к величине

а вероятность р 1 (t) в то же время увеличивается от 0, стремясь в пределе при t→∞ к величине

Эти пределы вероятностей могут быть получены непосредственно из уравнений Колмогорова при условии

Функции р 0 (t) и р 1 (t) определяют переходный процесс в одноканальной СМО и описывают процесс экспоненциального приближения СМО к своему предельному состоянию с постоянной времени характерной для рассматриваемой системы.

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

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

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

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

В пределе при t→∞ практически уже при t>3τ значение относительной пропускной способности будет равно

Абсолютная пропускная способность, определяющая число заявок, обслуживаемых в единицу времени в пределе при t→∞, равна:

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

а общее число не обслуженных заявок равно

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

3.2 Многоканальная СМО с отказами в обслуживании

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

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

Туристические фирмы по продаже путевок имеют два, три, четыре и более каналов, как, например, фирма Express-Line.

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

S 0

S 1

S k

S n

μ 2μkμ (k+1)μ nμ

Рис. 3.2. Размеченный граф состояний многоканальной СМО с отказами

Поток обслуживания в каждом канале имеет интенсивность μ. По числу заявок СМО определяются ее состояния S k , представленные в виде размеченного графа:

S 0 – все каналы свободны k=0,

S 1 – занят только один канал, k=1,

S 2 – заняты только два канала, k=2,

S k – заняты k каналов,

S n – заняты все n каналов, k= n.

Состояния многоканальной СМО меняются скачкообразно в случайные моменты времени. Переход из одного состояния, например S 0 в S 1 , происходит под воздействием входного потока заявок с интенсивностью λ, а обратно – под воздействием потока обслуживания заявок с интенсивностью μ. Для перехода системы из состояния S k в S k -1 безразлично, какой именно из каналов освободиться, поэтому поток событий, переводящий СМО, имеет интенсивность kμ, следовательно, поток событий, переводящий систему из S n в S n -1 , имеет интенсивность nμ. Так формулируется классическая задача Эрланга, названная по имени датского инженера – математика- основателя теории массового обслуживания.

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

.

Вычислив все вероятности состояний n – канальной СМО с отказами р 0 , р 1 , р 2 , …,р k ,…, р n , можно найти характеристики системы обслуживания.

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

k=n.

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

Р отк +Р обс =1

На этом основании относительная пропускная способность опредляется по формуле

Q = P обс = 1-Р отк =1-Р n

Абсолютную пропускную способность СМО можно определить по формуле

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

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

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

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

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

Среднее время пребывания заявки в системе в установившемся режиме определятся формулой Литтла

Т смо = n з /λ.

3.3 Модель многофазной системы обслуживания туристов

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

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

Поиск Выбор Выбор Решение

референт

поиск фирмы тура по туру

Оплата Перелет Исход

Рис. 3.3 Модель многофазной системы обслуживания туристов

Проблема с позиции массового обслуживания туристов, уезжающих на отдых, заключается в определении точного места отдыха (тура), адекватного требованиям претендента, соответствующего его здоровью и финансовым возможностям и представлениям об отдыхе в целом. В этом ему могут способствовать турфирмы, поиск которых осуществляется обычно из рекламных сообщений СМО р, затем после выбора фирмы происходит получение консультаций по телефону СМО т, после удовлетворительного разговора приезд в турфирму и получение более детальных консультаций лично с референтом, затем оплата путевки и получение обслуживания от авиакомпании по перелету СМО а и в конечном счете обслуживания в отеле СМ0 0 . Дальнейшее развитие рекомендаций по улучшению работы СМО фирмы связано с изменением профессионального содержания переговоров с клиентами по телефону. Для этого необходимо углубить анализ, связанный с детализацией диалога референта с клиентами, поскольку далеко не каждый переговоры по телефону приводит к заключению договора на приобретение путевки. Проведение формализации задачи обслуживания указало на необходимость формирования полного (необходимого и достаточного) перечня характеристик и их точных значений предмета коммерческой сделки. Затем проводятся ранжирование этих характеристик, например методом парных сравнений, и расположения в диалоге по степени их значимости, например: время года (зима), месяц (январь), климат (сухой), температура воздуха (+25"С), влажность (40%), географическое место (ближе к экватору), время авиаперелета (до 5 часов), трансферт, страна (Египет), город (Хургада), море (Красное), температура воды в море (+23°С), ранг отеля (4 звезды, работающий кондиционер, гарантия наличия шампуня в номере), удаленность от моря (до 300 м), удаленность от магазинов (рядом), удаленность от дискотек и других источников шума (подальше, тишина в течение сна в отеле), питание (шведский стол - завтрак, ужин, частота изменения меню за неделю), отели (Princes, Marlin-In, Hour-Palace), экскурсии (Каир, Луксор, коралловые острова, подводное плавание), увеселительные шоу, спортивные игры, цена путевки, форма оплаты, содержание страховки, что брать с собой, что купить на месте, гарантии, штрафные санкции.

Есть еще один очень существенный показатель, выгодный для клиента, установить который предлагается самостоятельно въедливому читателю. Затем можно, используя метод опарного сравнения перечисленных характеристик х i , сформировать матрицу п х п сравнения, элементы которой заполняются последовательно по строкам по следующему правилу:

0, если характеристика менее значима,

а ij = 1, если характеристика равнозначима,

2, если характеристика доминирует.

После этого определяются значения сумм оценок по каждому показателю строки S i =∑a ij , вес каждой характеристики M i = S i /n 2 и соответственно интегральный критерий, на основе которого можно провести выбор турфирмы, тура или отеля, по формуле

F = ∑ M i * x i -» max.

С целью исключения возможных ошибок в этой процедуре вводят, например, 5-балльную шкалу оценок с градацией характеристик Б i (х i) по принципу хуже (Б i = 1 балл) - лучше (Б i = 5 баллов). Например, чем дороже тур, тем хуже, чем он дешевле, тем лучше. На этом основании целевая функция будет иметь другой вид:

F b = ∑ M i * Б i * x i -> max.

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

3.4 Одноканальная СМО с ограниченной длиной очереди

В коммерческой деятельности чаще встречаются СМО с ожиданием (очередью).

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

Граф этой СМО представлен на рис. 3.4 и совпадает с графом рис. 2.1 описывающим процесс «рождения-гибели», с тем отличием, что при наличии только одного канала.

S m

S 3

S 2

S 1

S 0

λ λλλ... λ

μ μμμ... μ

Рис. 3.4. Размеченный граф процесса «рождения - гибели» обслуживания все интенсивности потоков обслуживания равны

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

S 0 - канал обслуживания свободен,

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

S 2 - канал обслуживания занят, в очереди стоит одна заявка,

S 3 - канал обслуживания занят, в очереди стоят две заявки,

S m +1 - канал обслуживания занят, в очереди все т мест заняты, любая следующая заявка получает отказ.

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

p 1 = ρ * ρ о

p 2 =ρ 2 * ρ 0

p k =ρ k * ρ 0

P m+1 = p m=1 * ρ 0

p 0 = -1

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

ρ= (1- ρ )

Эта формула справедлива для всех р, отличных от 1, если же р = 1, то р 0 = 1/(т + 2), а все остальные вероятности также равны 1/(т + 2). Если предположить т = 0, то мы переходим от рассмотрения одноканальной СМО с ожиданием к уже рассмотренной одноканальной СМО с отказами в обслуживании. Действительно, выражение для предельной вероятности р 0 в случае т = 0 имеет вид:

p о = μ / (λ+μ)

И в случае λ = μ имеет величину р 0 = 1 / 2.

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

Заявка получает отказ, если она поступает в момент времени, когда СМО уже находится в состоянии S m +1 и, следовательно, все места в очереди да заняты и один канал обслуживает Поэтому вероятность отказа определяется вероятностью появлением

Состояния S m +1:

P отк = p m +1 = ρ m +1 * p 0

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

Q = 1- p отк = 1- ρ m+1 * p 0

абсолютная пропускная способность равна:

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

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

1 - в очереди стоит одна заявка,

2 - в очереди две заявки,

т-в очереди все места заняты

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

k	1	2	m
p i	p 2	p 3	p m+1

Математическое ожидание этой случайной величины равно:

L оч = 1* p 2 +2* p 3 +...+ m* p m +1

В общем случае при p ≠1 эту сумму можно преобразовать, пользуясь моделями геометрической прогрессии, к более удобному виду:

L оч = p 2 * 1- p m * (m-m*p+1) * p 0

В частном случае при р = 1, когда все вероятности p k оказываются равными, можно воспользоваться выражением для суммы членов числового ряда

1+2+3+ m = m ( m +1)

Тогда получим формулу

L’ оч = m(m+1) * p 0 = m(m+1) (p=1).

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

Т оч = L оч /А (при р ≠ 1) и Т 1 оч = L’ оч /А(при р = 1).

Такой результат, когда оказывается, что Т оч ~ 1/ λ, может показаться странным: с увеличением интенсивности потока заявок как будто бы должна возрастать длина очереди и уменьшается среднее время ожидания. Однако следует иметь в виду, что, во-первых, величина L оч является функцией от λ и μ и, во-вторых, рассматриваемая СМО имеет ограниченную длину очереди не более mзаявок.

Заявка, поступившая в СМО в момент времени, когда все каналы заняты, получает отказ, и, следовательно, время ее «ожидания» в СМО равно нулю. Это приводит в общем случае (при р ≠ 1) к уменьшению Т оч ростом λ, поскольку доля таких заявок с ростом λ увеличивается.

Если отказаться от ограничения на длину очереди, т.е. устремить m-> →∞, то случаи р < 1 и р ≥1 начинают существенно различаться. Записанные выше формулы для вероятностей состояний преобразуются в случае р < 1 к виду

p k =р k *(1 - р)

При достаточно большом к вероятность p k стремится к нулю. Поэтому относительная пропускная способность будет Q= 1, а абсолютная пропускная способность станет равной А -λ Q - λ следовательно, обслуживаются все поступившие заявки, причем средняя длина очереди окажется равной:

L оч =p 2 1-p

а среднее время ожидания по формуле Литтла

Т оч = L оч /А

В пределе р << 1 получаем Т оч = ρ / μт.е. среднее время ожидания быстро уменьшается с увеличением интенсивности потока обслуживания. В противном случае при р ≥ 1 оказывается, что в СМО отсутствует установившийся режим. Обслуживание не успевает за потоком заявок, и очередь неограниченно растет со временем (при t → ∞). Предельные вероятности состояний поэтому не могут быть определены: при Q= 1 они равны нулю. Фактически СМО не выполняет своих функций, поскольку она не в состоянии обслужить все поступающие заявки. Нетрудно определить, что доля обслуживаемых заявок и абсолютная пропускная способность соответственно составляют в среднем ρ и μ, однако неограниченное увеличение очереди, а следовательно, и времени ожидания в ней приводит к тому, что через некоторое время заявки начинают накапливаться в очереди на неограниченно долгое время.

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

L смо= m +1 ;2

Т смо= L смо; при p ≠1

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

Т смо= m +1 при p ≠1 2μ

3.5 Одноканальная СМО с неограниченной очередью

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

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

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

Рассмотрим простейшую одноканальную СМО с ожиданием обслуживания, на которую поступает пуассоновский поток заявок с интенсивностью λ и интенсивностью обслуживания µ.

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

Размеченный граф состояний такой системы приведен на рис. 3.5

Количество возможных состояний ее бесконечно:

Канал свободен, очереди нет, ;

Канал занят обслуживанием, очереди нет, ;

Канал занят, одна заявка в очереди, ;

Канал занят , заявка в очереди.

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

Рис. 3.5 Граф состояний одноканальной СМО с неограниченной очередью.

Следует заметить, что для СМО с ограниченной длиной очереди в формуле

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

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

Вероятность пребывания в очереди k заявок равна:

;

Среднее число заявок в очереди –

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

;

Среднее время пребывания заявки в системе –

;

Среднее время пребывания заявки с системе –

.

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

3.6 Многоканальная СМО с ограниченной длиной очереди

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

Все каналы свободны, ;

Занят только один канал (любой), ;

Заняты только два канала (любых), ;

Заняты все каналов, .

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

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

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

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

Граф состояний n-канальной СМО с очередью, ограниченной m местами на рис.3.6

Рис. 3.6 Граф состояний n-канальной СМО с ограничением на длину очереди m

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

Запишем выражения для предельных вероятностей состояний:

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

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

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

Относительная пропускная способность будет равна:

Абсолютная пропускная способность –

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

Среднее число простаивающих каналов –

Коэффициент занятости (использования) каналов –

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

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

В случае если , эта формула принимает другой вид –

Среднее время ожидания в очереди определяется формулами Литтла –

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

3.7 Многоканальная СМО с неограниченной очередью

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

S - все каналы свободны, k=0;

S - занят один канал, остальные свободны, k=1;

S - заняты два канала, остальные свободны, k=2;

S - заняты все n каналов, k=n, очереди нет;

S - заняты все n каналов, одна заявка в очереди, k=n+1,

S - заняты все n каналов, r заявок в очереди, k=n+r,

Вероятности состояний получим из формул для многоканальной СМО с ограниченной очередью при переходе к пределу при m. Следует заметить, что сумма геометрической прогрессии в выражении для p расходится при уровне загрузки p/n>1, очередь будет бесконечно возрастать, а при p/n<1 ряд сходится, что определяет установившийся стационарный режим работы СМО.

Очереди нет

…

…

Рис.3.7 Размеченный граф состояний многоканальной СМО

с неограниченной очередью

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

Поскольку отказа в обслуживании в таких системах не может быть, то характеристики пропускной способности равны:

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

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

среднее число заявок в СМО –

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

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

На этом основании можно определить вероятность, или долю времени занятости всех каналов обслуживанием

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

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

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

Среднее время ожидания заявки в очереди по формуле Литтла: и в системе

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

среднее число свободных каналов:

коэффициент занятости каналов обслуживанием:

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

3.8 Анализ системы массового обслуживания супермаркета

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

СМО

СМО

Интенсивность входного потока покупателей;

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

Интенсивность прихода покупателей в расчетный узел;

Интенсивность потока обслуживания.

Рис.4.1. Модель двухфазной СМО торгового зала универсама

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

1) экономико-организационные факторы: система материальной ответственности в универсаме; средняя стоимость и структура одной покупки;

2) организационная структура кассового узла;

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

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

Рассмотрим обе фазы системы обслуживания:

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

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

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

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

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

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

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

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

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

Часы работы	День недели
	пятница			суббота			воскресенье
	оче-редь,	количество покупателей без покупок		оче-редь,	количество покупателей без покупок		оче-редь,	количество покупателей без покупок
		чел.	%		чел.	%		чел.	%
с 9 до 10	2	38	5	5	60	5,4	7	64	4,2
с 10 до 11	3	44	5,3	5	67	5	6	62	3,7
с 11 до 12	3	54	6,5	4	60	5,8	7	121	8,8
с 12 до 13	2	43	4,9	4	63	5,5	8	156	10
с 14 до 15	2	48	5,5	6	79	6,7	7	125	6,5
с 15 до 16	3	61	7,3	6	97	6,4	5	85	7,2
с 16 до 17	4	77	7,1	8	140	9,7	5	76	6
с 17 до 18	5	91	6,8	7	92	8,4	4	83	7,2
с 18 до 19	5	130	7,3	6	88	5,9	7	132	8
с 19 до 20	6	105	7,6	6	77	6
с 20 до 21	6	58	7	5	39	4,4
Итого	749	6,5	862	6,3	904	4,5

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

Дни недели	Потоки покупателей			Товарооборот
	всего	по экспресс-кассам	% к дневномупотоку	всего	по экспресс-кассам	% к дневному товарообороту
Летний период
Понедельник	11182	3856	34,5	39669,2	3128,39	7,9
Вторник	10207	1627	15,9	38526,6	1842,25	4,8
Среда	10175	2435	24	33945	2047,37	6
Четверг	10318	2202	21,3	36355,6	1778,9	4,9
Пятница	11377	2469	21,7	43250,9	5572,46	12,9
Суббота	10962	1561	14,2	39873	1307,62	3,3
Воскресенье	10894	2043	18,8	35237,6	1883,38	5,1
Зимний период
Понедельник	10269	1857	18,1	37121,6	2429,73	6,5
Вторник	10784	1665	15,4	38460,9	1950,41	5,1
Среда	11167	3729	33,4	39440,3	4912,99	12,49,4
Четверг	11521	2451	21,3	40000,7	3764,58	9,4
Пятница	11485	1878	16,4	43669,5	2900,73	6,6
Суббота	13689	2498	18,2	52336,9	4752,77	9,1
Воскресенье	13436	4471	33,3	47679,9	6051,93	12,7

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

1) функцию распределения времени покупателей на выбор товаров в зоне самообслуживания;

2) функцию распределения времени работы контролера-кассира для обычных касс и экспресс-касс;

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

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

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

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

Функция распределения времени обслуживания покупателей контролерами-кассирами является экспоненциальной, такое допущение не приводит к большим ошибкам.

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

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

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

где - кассовый узел состоит из =7 касс обычного типа и =2 экспресс-касс,

Интенсивность обслуживания покупателей в зоне обычных касс – 0,823 чел./мин;

Интенсивность нагрузки кассовых аппаратов в зоне обычных касс – 6,65,

Интенсивность обслуживания покупателей в зоне экспресс-касс – 2,18 чел./мин;

Интенсивность входящего потока в зону обычных касс – 5,47 чел./мин

Интенсивность нагрузки кассовых аппаратов в зоне экспресс-касс – 1,63,

Интенсивность входящего потока в зону экспресс-касс – 3,55 чел./мин;

Для модели СМО с ограничением на длину очереди в соответствии с проектируемой зоной кассового узла максимально допустимое число покупателей, стоящих в очереди в одну кассу, принимается равным m=10 покупателей.

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

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

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

Из приведенных данных в табл. 4.3 следует, что если бы для расчета была выбрана:

1) модель с отказами, то 22,6% потока покупателей, обслуживаемых обычными кассами, и соответственно 33,6% потока покупателей, обслуживаемых экспресс-кассами, должны были бы уйти без покупок;

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

Табл. 4.3 Характеристики системы массового обслуживания покупателей в зоне расчетного узла

Тип кассы	Количество касс в узле	Тип СМО	Характеристики СМО
			Среднее число занятых касс,	среднее время ожидания обслуживания,	Вероятность потери заявок,
Обычные кассы	7	с отказами с ожиданием с ограничением
Экспресс-кассы	2	с отказами с ожиданием с ограничением

3) модель с ограничением на длину очереди, то только 0,12% потока покупателей, обслуживаемых обычными кассами, и 1,8% потока покупателей, обслуживаемых экспресс-кассами, покинут торговый зал без покупок. Следовательно, модель с ограничением на длину очереди позволяет более точно и реально описать процесс обслуживания покупателей в зоне кассового узла.

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

Анализ данных этой таблицы показывает, что не учет фактора «Структура потока покупателей по типу кассового обслуживания» на стадии технологического проектирования может привести к увеличению зоны расчетного узла на 22-33%, а отсюда соответственно и к уменьшению установочных и выставочных площадей торгово-технологического оборудования и товарной массы, размещаемой в торговом зале.

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

№ п/п	Характеристики СМО	Единица измерения	Обозначение		Показатели, рассчитанные по типам универсамов торговой площади, кв. м
					Без экспресс-касс						С учетом экспресс-касс
					650		1000		2000		650			1000			2000
											Обычные кассы		Экспресс-кассы	Обычные кассы		экспресс-кассы	Обычные кассы		экспресс-кассы
1	Количество покупателей	чел.	k		2310		3340		6680		1460		850	2040		1300	4080		2600
2	Интенсивность входящего потока		λ		9,64		13,9		27,9		6,08		3,55	8,55		5,41	17,1		10,8
3	Интенсивность обслуживания	чел./мин	μ		0,823		0,823		0,823		0,823		2,18	0,823		2,18	0,823		2,18
4	Интенсивность нагрузки	-	ρ		11,7		16,95		33,8		6,65		1,63	10,35		2,48	20,7		4,95
5	Количество кассовых аппаратов	шт.	n		12		17		34		7		2	11		3	21		5
6	Общее количество касс расчетного узла	шт.		∑n		12		17		34		9			14			26

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

На основе анализа данных табл. 4.5 можно сделать вывод, что по мере увеличения количества касс время ожидания покупателей в очереди растет, а затем после определенного момента резко падает. Характер изменения графика времени ожидания покупателей понятен, если параллельно рассматривать изменение вероятности потери требования Вполне очевидно, что когда мощность кассового узла чрезмерно мала, то более 85% покупателей будут уходить необслуженными, а оставшаяся часть покупателей будет обслужена за очень короткое время. Чем больше мощность кассового узла, тем вероятность потери требований будет дожидаться своего обслуживания, а значит, и время их ожидания в очереди соответственно будет расти. После того как ожидания и вероятность потерь будут резко уменьшаться.

Для универсама торговой площадью 650 этот предел для зоны обычных касс лежит между 6 и 7 кассовыми аппаратами. При 7 кассовых аппаратах соответственно среднее время ожидания – 2,66 мин, а вероятность потери заявок очень мала – 0,1%. Таким образом, которая позволит получить минимальные совокупные затраты на массовое обслуживание покупателей.

Тип кассового обслуживания	Количество кассовых аппаратов в узле n, шт.	Характеристики системы обслуживания		Средняя выручка за 1 ч. руб.	Средняя потеря выручки за 1 ч. руб	Число покупателей в зоне расчетного узла	Площадь зоны расчетного узла, Sy, м	Удель ный вес площади зоны узла 650/ Sy
		Среднее время ожидания, Т,мин	Вероятность потери заявок
Зоны Обычных касс
Зоны экспресс-касс

Заключение

На основе анализа данных табл. 4.5 можно сделать вывод, что по мере увеличения количество касс время ожидания покупателей в очереди растет. А затем после определенного момента резко падает. Характер изменения графика времени ожидания покупателей понятен, если параллельно рассматривать изменение вероятности потери требований Вполне очевидно, что когда мощность кассового узла чрезмерно мала, то более 85% покупателей будут уходить необслуженными, а оставшаяся часть покупателей будет обслужена за очень короткое время. Чем больше мощность кассового узла. Тем вероятность потери требований будет уменьшаться и соответственно тем большее число покупателей будет дожидаться своего обслуживания, а значит, и время их ожидания в очереди соответственно будет расти. После того как расчетный узел превысит оптимальный мощность, время ожидания и вероятность потерь будут резко уменьшаться.

Для универсама торговой площадью 650 кв. метров этот предел для зоны обычных касс лежит между 6-8 кассовыми аппаратами. При 7 кассовых аппаратах соответственно среднее время ожидания- 2,66 мин, а вероятность потери заявок очень мало - 0,1 % . Таким образом, задача состоит в выборе такой мощности кассового узла, которая позволит получит минимальные совокупные затраты на массовое обслуживание покупателей.

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

Примеры решения задач систем массового обслуживания

Требуется решить задачи 1–3. Исходные данные приведены в табл. 2–4.

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

n – число каналов в СМО;

λ – интенсивность входящего потока заявок П вх;

v – интенсивность выходящего потока заявок П вых;

μ – интенсивность потока обслуживания П об;

ρ – показатель нагрузки системы (трафик);

m – максимальное число мест в очереди, ограничивающее длину очереди заявок;

i – число источников заявок;

p к – вероятность k-го состояния системы;

p о – вероятность простаивания всей системы, т. е. вероятность того, что все каналы свободны;

p сист – вероятность принятия заявки в систему;

p отк – вероятность отказа заявке в принятии ее в систему;

р об – вероятность того, что заявка будет обслужена;

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

Q – относительная пропускная способность системы;

Оч – среднее число заявок в очереди;

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

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

Оч – среднее время ожидания заявки в очереди;

Об – среднее время обслуживания заявки, относящееся только к обслуженным заявкам;

Сис – среднее время пребывания заявки в системе;

Ож – среднее время, ограничивающее ожидание заявки в очереди;

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

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

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

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

1) определение типа СМО по табл. 4.1;

2) выбор формул в соответствии с типом СМО;

3) решение задачи;

4) формулирование выводов по задаче.

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

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

Граф состояний для схемы гибели и размножения имеет вид, показанный на рис. 19.1. Особенность этого графа в том, что все состояния системы можно вытянуть в одну цепочку, в которой каждое из средних состояний (S 1 , S 2 ,…,S n-1) связано прямой и обратной стрелкой с каждым из соседних состояний - правым и левым, а крайние состояния (S 0 , S n) - только с одним соседним состоянием. Термин «схема гибели и размножения» ведет начало от биологических задач, где подобной схемой описывается изменение численности популяции.

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

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

Пользуясь графом рис. 19.1, составим и решим алгебраические уравнения для финальных вероятностей состоянии), существование вытекает из того, что из каждого состояния можно перейти в каждое другое, в число состояний конечно). Для первого состояния S 0 имеем:

(19.1)

Для второго состояния S 1:

В силу (19.1) последнее равенство приводится к виду

где k принимает все значения от 0 до п. Итак, финальные вероятности p 0 , p 1 , ..., р n удовлетворяют уравнениям

(19.2)

кроме того, надо учесть нормировочное условие

p 0 + p 1 + p 2 +…+ p n =1. (19.3)

Решим эту систему уравнений. Из первого уравнения (19.2)выразим p 1 через р 0 :

p 1 = p 0. (19.4)

Из второго, с учетом (19.4), получим:

(19.5)

Из третьего, с учетом (19.5),

(19.6)

и вообще, для любого k (от 1 до n ):

(19.7)

Обратим внимание на формулу (19.7). В числителе стоит произведение всех интенсивностей, стоящих у стрелок, ведущих слева направо (с начала и до данного состояния S k), а в знаменателе - произведение всех интенсивностей, стоящих у стрелок, ведущих справа налево (с начала и до S k).

Таким образом, все вероятности состояний р 0 , p 1 , ..., р n выражены через одну из них (р 0). Подставим эти выражения в нормировочное условие (19.3). Получим, вынося за скобку р 0:

отсюда получим выражение для р 0 :

(скобку мы возвели в степень -1, чтобы не писать двухэтажных дробей). Все остальные вероятности выражены через р 0 (см. формулы (19.4) - (19.7)). Заметим, что коэффициенты при р 0 в каждой из них представляют собой не что иное, как последовательные члены ряда, стоящего после единицы в формуле (19.8). Значит, вычисляя р 0 , мы уже нашли все эти коэффициенты.

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

^ 2. Формула Литтла. Теперь мы выведем одну важную формулу, связывающую (для предельного, стационарного режима) среднее число заявок L сист, находящихся в системе массового обслуживания (т. е. обслуживаемых или стоящих в очереди), и среднее время пребывания заявки в системе W сист.

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

Обозначим: X(t} - число заявок, прибывших в СМО до момента t. Y (t ) - число заявок покинувших СМО

до момента t. И та, и другая функции являются случайными и меняются скачком (увеличиваются на единицу) в моменты приходов заявок (X (t )) и уходов заявок (Y(t)). Вид функций X(t) и Y(t) показан на рис. 19.2; обе линии - ступенчатые, верхняя - X(t), нижняя-Y(t). Очевидно, что для любого момента t их разность Z (t ) = X(t) - Y(t) есть не что иное, как число заявок, находящихся в СМО. Когда линии X(t) и Y(t) сливаются, в системе нет заявок.

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

L сист. = . (19.9) о

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

(19.10)

где сумма распространяется на все заявки, пришедшие за время Т.

Разделим правую и левую часть (.19.10) на длину интервала Т. Получим, с учетом (19.9),

L сист. = . (19.11)

Разделим и умножим правую часть (19.11) на интенсивность X:

L сист. = .

Но величина Тλ есть не что иное, как среднее число заявок, пришедших за время ^ Т. Если мы разделим сумму всех времен t i на среднее число заявок, то получим среднее время пребывания заявки в системе W сист. Итак,

L сист. = λW сист. ,

W сист. = . (19.12)

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

Точно таким же образом выводится вторая формула Литтла, связывающая среднее время пребывания заявки в очереди ^ W оч и среднее число заявок в очереди L оч:

W оч = . (19.13)

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

Формулы Литтла (19.12) и (19.13) играют большую роль в теории массового обслуживания. К сожалению, в большинстве существующих руководств эти формулы (доказанные в общем виде сравнительно недавно) не приводятся 1).

§ 20. Простейшие системы массового обслуживания и их характеристики

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

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

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

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

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

^ 1. п -канальная СМО с отказами (задача Эрланга). Здесь мы рассмотрим одну из первых по времени, «классических» задач теории массового обслуживания;

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

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

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

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

k - среднее число занятых каналов.

Решение. Состояния системы ^ S (СМО) будем нумеровать по числу заявок, находящихся в системе (в данном случае оно совпадает с числом занятых каналов):

S 0 - в СМО нет ни одной заявки,

S 1 - в СМО находится одна заявка (один канал занят, остальные свободны),

S k - в СМО находится k заявок (k каналов заняты, остальные свободны),

S n - в СМО находится п заявок (все n каналов заняты).

Граф состояний СМО соответствует схеме гибели в размножения (рис. 20.1). Разметим этот граф - проставим у стрелок интенсивности потоков событий. Из S 0 в S 1 систему переводит поток заявок с интенсивностью λ (как только приходит заявка, система перескакивает из S 0 в S 1). Тот же поток заявок переводит

Систему из любого левого состояния в соседнее правое (см. верхние стрелки на рис. 20.1).

Проставим интенсивности у нижних стрелок. Пусть система находится в состоянии ^ S 1 (работает один канал). Он производит μ обслуживании в единицу времени. Проставляем у стрелки S 1 → S 0 интенсивность μ. Теперь представим себе, что система находится в состоянии S 2 (работают два канала). Чтобы ей перейти в S 1 , нужно, чтобы либо закончил обслуживание первый канал, либо второй; суммарная интенсивность их потоков обслуживании равна 2μ; проставляем ее у соответствующей стрелки. Суммарный поток обслуживании, даваемый тремя каналами, имеет интенсивность 3μ, k каналами - kμ. Проставляем эти интенсивности у нижних стрелок на рис. 20.1.

А теперь, зная все интенсивности, воспользуемся уже готовыми формулами (19.7), (19.8) для финальных вероятностей в схеме гибели и размножения. По формуле (19.8) получим:

Члены разложения будут представлять собой коэффициенты при р 0 в выражениях для p 1

Заметим, что в формулы (20.1), (20.2) интенсивности λ и μ входят не по отдельности, а только в виде отношения λ/μ. Обозначим

λ/μ = ρ (20.3)

И будем называть величину р «приведенной интенсивностью потока заявок». Ее смысл-среднее число заявок, приходящее за среднее время обслуживания одной заявки. Пользуясь этим обозначением, перепишем формулы (20.1), (20.2) в виде:

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

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

Р отк = р n = . (20.6)

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

Q = 1 – P отк. = 1 - (20.7)

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

A = λQ = λ . (20.8)

Осталось только найти среднее число занятых каналов k. Эту величину можно было бы найти «впрямую», как математическое ожидание дискретной случайной величины с возможными значениями 0, 1, ..., п и вероятностями этих значений р 0 р 1 , ..., р n:

k = 0 · р 0 + 1 · p 1 + 2 · р 2 + ... + п · р n .

Подставляя сюда выражения (20.5) для р k , (k = 0, 1, ..., п) и выполняя соответствующие преобразования, мы, в конце концов, получили бы верную формулу для k. Но мы выведем ее гораздо проще (вот она, одна из «маленьких хитростей»!) В самом деле, нам известна абсолютная пропускная способность А. Это - не что иное, как интенсивность потока обслуженных системой заявок. Каждый занятый i .шал в единицу времени обслуживает в среднем |л заявок. Значит, среднее число занятых каналов равно

k = A/μ, (20.9)

или, учитывая (20.8),

k = (20.10)

Рекомендуем читателю самостоятельно решить пример. Имеется станция связи с тремя каналами (n = 3), интенсивность потока заявок λ = 1,5 (заявки в минуту); среднее время обслуживания одной заявки t об = 2 (мин.), все потоки событий (как и во всем этом параграфе) - простейшие. Найти финальные вероятности состояний и характеристики эффективности СМО: А, Q, P отк, k. На всякий случай сообщаем ответы: p 0 = 1/13, p 1 = 3/13, p 2 = 9/26, р 3 = 9/26 ≈ 0,346,

А ≈ 0,981, Q ≈ 0,654, P отк ≈ 0,346, k ≈ 1,96.

Из ответов видно, между прочим, что наша СМО в значительной мере перегружена: из трех каналов занято в среднем около двух, а из поступающих заявок около 35% остаются не обслуженными. Предлагаем читателю, если он любопытен и неленив, выяснить: сколько потребуется каналов для того, чтобы удовлетворить не менее 80% поступающих заявок? И какая доля каналов при этом будет простаивать?

Тут уже проглядывает некоторый намек на оптимизацию. В самом деле, содержание каждого канала в единицу времени обходится в какую-то сумму. Вместе с тем, каждая обслуженная заявка приносит какой-то доход. Умножая этот доход на среднее число заявок А, обслуживаемых в единицу времени, мы получим средний доход от СМО в единицу времени. Естественно, при увеличении числа каналов этот доход растет, но растут и расходы, связанные с содержанием каналов. Что перевесит - увеличение доходов или расходов? Это зависит от условий операции, от «платы за обслуживание заявки» и от стоимости содержания канала. Зная эти величины, можно найти оптимальное число каналов, наиболее эффективное экономически. Мы такой задачи решать не будем, предоставляя все тому же «неленивому и любопытному читателю» придумать пример и решить. Вообще, придумывание задач больше развивает, чем решение уже поставленных кем-то.

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

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

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

W сист. - среднее время пребывания заявки в системе,

^ L оч - среднее число заявок в очереди,

W оч - среднее время пребывания заявки в очереди,

P зан - вероятность того, что канал занят (степень загрузки канала).

Что касается абсолютной пропускной способности А и относительной Q, то вычислять их нет надобности:

в силу того, что очередь неограниченна, каждая заявка рано или поздно будет обслужена, поэтому А = λ, по той же причине Q = 1.

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

S 0 - канал свободен,

S 1 - канал занят (обслуживает заявку), очереди нет,

S 2 - канал занят, одна заявка стоит в очереди,

S k - канал занят, k - 1 заявок стоят в очереди,

Теоретически число состояний ничем не ограничено (бесконечно). Граф состоянии имеет вид, показанный на рис. 20.2. Это - схема гибели и размножения, но с бесконечным числом состояний. По всем стрелкам поток заявок с интенсивностью λ переводит систему слева направо, а справа налево - поток обслуживании с интенсивностью μ.

Прежде всего спросим себя, а существуют ли в этом случае финальные вероятности? Ведь число состояний системы бесконечно, и, в принципе, при t → ∞ очередь может неограниченно возрастать! Да, так оно и есть: финальные вероятности для такой СМО существуют не всегда, а только когда система не перегружена. Можно доказать, что если ρ строго меньше единицы (ρ< 1), то финальные вероятности существуют, а при ρ ≥ 1 очередь при t → ∞ растет неограниченно. Особенно «непонятным» кажется этот факт при ρ = 1. Казалось бы, к системе не предъявляется невыполнимых требований: за время обслуживания одной заявки приходит в среднем одна заявка, и все должно быть в порядке, а вот на деле - не так. При ρ = 1 СМО справляется с потоком заявок, только если поток этот - регулярен, и время обслуживания - тоже не случайное, равное интервалу между заявками. В этом «идеальном» случае очереди в СМО вообще не будет, канал будет непрерывно занят и будет регулярно выпускать обслуженные заявки. Но стоит только потоку заявок или потоку обслуживании стать хотя бы чуточку случайными - и очередь уже будет расти до бесконечности. На практике этого не происходит только потому, что «бесконечное число заявок в очереди» - абстракция. Вот к каким грубым ошибкам может привести замена случайных величин их математическими ожиданиями!

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

p 0 = -1 =

= (1 + р + р 2 + ... + р k +… .) -1 . (20.11)

Ряд в формуле (20.11) представляет собой геометрическую прогрессию. Мы знаем, что при ρ < 1 ряд сходится - это бесконечно убывающая геометрическая прогрессия со знаменателем р. При р ≥ 1 ряд расходится (что является косвенным, хотя и не строгим доказательством того, что финальные вероятности состояний р 0 , p 1 , ..., p k , ... существуют только при р<1). Теперь предположим, что это условие выполнено, и ρ <1. Суммируя прогрессию в (20.11), имеем

1 + ρ + ρ 2 + ... + ρ k + ... = ,

p 0 = 1 - ρ. (20.12)

Вероятности р 1 , р 2 , ..., р k , ... найдутся по формулам:

p 1 = ρp 0 , p 2 = ρ 2 p 0 ,…,p k = ρp 0 , ...,

Откуда, с учетом (20.12), найдем окончательно:

p 1 = ρ (1 - ρ), p 2 = ρ 2 (1 - ρ), . . . , p k = ρ k (1 - ρ), . . .(20.13)

Как видно, вероятности p 0 , p 1 , ..., p k , ... образуют геометрическую прогрессию со знаменателем р. Как это ни странно, максимальная из них р 0 - вероятность того, что канал будет вообще свободен. Как бы ни была нагружена система с очередью, если только она вообще справляется с потоком заявок (ρ<1), самое вероятное число заявок в системе будет 0.

Найдем среднее число заявок в СМО ^ L сист . . Тут придется немного повозиться. Случайная величина Z - число заявок в системе - имеет возможные значения 0, 1, 2, .... k, ... с вероятностями p 0 , р 1 , р 2 , ..., p k , ... Ее математическое ожидание равно

L сист = 0 · p 0 + 1 · p 1 + 2 · p 2 +…+k · p k +…= (20.14)

(сумма берется не от 0 до ∞, а от 1 до ∞, так как нулевой член равен нулю).

Подставим в формулу (20.14) выражение для p k (20.13):

L сист. =

Теперь вынесем за знак суммы ρ (1-ρ):

L сист. = ρ (1-ρ)

Тут мы опять применим «маленькую хитрость»: k ρ k -1 есть не что иное, как производная по ρ от выражения ρ k ; значит,

L сист. = ρ (1-ρ)

Меняя местами операции дифференцирования п суммирования, получим:

L сист. = ρ (1-ρ) (20.15)

Но сумма в формуле (20.15) есть не что иное, как сумма бесконечно убывающей геометрической прогрессии с первым членом ρ и знаменателем ρ; эта сумма

равна , а ее производная .Подставляя это выражение в (20.15), получим:

L сист = . (20.16)

Ну, а теперь применим формулу Литтла (19.12) и найдем среднее время пребывания заявки в системе:

W сист = (20.17)

Найдем среднее число заявок в очереди L оч. Будем рассуждать так: число заявок в очереди равно числу заявок в системе минус число заявок, находящихся под обслуживанием. Значит (по правилу сложения математических ожиданий), среднее число заявок в очереди L оч равно среднему числу заявок в системе L сист минус среднее число заявок под обслуживанием. Число заявок под обслуживанием может быть либо нулем (если канал свободен), либо единицей (если он занят). Математическое ожидание такой случайной величины равно вероятности того, что канал занят (мы ее обозначили Р зан). Очевидно, Р зан равно единице минус вероятность р 0 того, что канал свободен:

Р зан = 1 - р 0 = ρ. (20.18)

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

^ L об = ρ, (20.19)

L оч = L сист – ρ =

и окончательно

L оч = (20.20)

По формуле Литтла (19.13) найдем среднее время пребывания заявки в очереди:

(20.21)

Таким образом, все характеристики эффективности СМО найдены.

Предложим читателю самостоятельно решить пример: одноканальная СМО представляет собой железнодорожную сортировочную станцию, на которую поступает простейший поток составов с интенсивностью λ = 2 (состава в час). Обслуживание (расформирование)

состава длится случайное (показательное) время со средним значением t об = 20 (мин.). В парке прибытия станции имеются два пути, на которых могут ожидать обслуживания прибывающие составы; если оба пути заняты, составы вынуждены ждать на внешних путях. Требуется найти (для предельного, стационарного режима работы станции): среднее, число составов l сист, связанных со станцией, среднее время W сист пребывания состава при станции (на внутренних путях, на внешних путях и под обслуживанием), среднее число L оч составов, ожидающих очереди на расформирование (все равно, на каких путях), среднее время W оч пребывания состава на очереди. Кроме того, попытайтесь найти среднее число составов, ожидающих расформирования на внешних путях L внеш и среднее время этого ожидания W внеш (две последние величины связаны формулой Литтла). Наконец, найдите суммарный суточный штраф Ш, который придется заплатить станции за простои составов на внешних путях, если за один час простоя одного состава станция платит штраф а (руб.). На всякий случай сообщаем ответы: L сист. = 2 (состава), W сист. = 1 (час), L оч = 4/3 (состава), W оч = 2/3 (часа), L внеш = 16/27 (состава), W внеш = 8/27 ≈ 0,297 (часа). Средний суточный штраф Ш за ожидание составов на внешних путях получим, перемножая среднее число составов, прибывающих на станцию за сутки, среднее время ожидания состава на внешних путях и часовой штраф а : Ш ≈ 14,2а .

^ 3. re-канальная СМО с неограниченной очередью. Совершенно аналогично задаче 2, но чуточку более сложно, решается задача об n -канальной СМО с неограниченной очередью. Нумерация состояний - опять по числу заявок, находящихся в системе:

S 0 - в СМО заявок нет (все каналы свободны),

S 1 - занят один канал, остальные свободны,

S 2 - занято два канала, остальные свободны,

S k - занято k каналов, остальные свободны,

S n - заняты все п каналов (очереди нет),

S n+1 - заняты все n каналов, одна заявка стоит в очереди,

S n+r - заняты вес п каналов, r заявок стоит в очереди,

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

λ λ λ λ λ λ λ λ λ

μ 2μ kμ (k+1)μ nμ nμ nμ nμ nμ

есть схема гибели и размножения, но с бесконечным числом состояний. Сообщим без доказательства естественное условие существования финальных вероятностей: ρ/n <1. Если ρ/n ≥ 1, очередь растет до бесконечности.

Предположим, что условие ρ/n < 1 выполнено, и финальные вероятности существуют. Применяя все те же формулы (19.8), (19.7) для схемы гибели и размножения, найдем эти финальные вероятности. В выражении для р 0 будет стоять ряд членов, содержащих факториалы, плюс сумма бесконечно убывающей геометрической прогрессии со знаменателем ρ/n . Суммируя ее, найдем

(20.22)

Теперь найдем характеристики эффективности СМО. Из них легче всего находится среднее число занятых каналов k == λ/μ, = ρ (это вообще справедливо для любой СМО с неограниченной очередью). Найдем среднее число заявок в системе L сист и среднее число заявок в очереди L оч. Из них легче вычислить второе, по формуле

L оч =

выполняя соответствующие преобразования по образцу задачи 2

(с дифференцированием ряда), получим:

L оч = (20.23)

Прибавляя к нему среднее число заявок под обслуживанием (оно же - среднее число занятых каналов) k = ρ, получим:

L сист = L оч + ρ. (20.24)

Деля выражения для L оч и L сист на λ, по формуле Литтла получим средние времена пребывания заявки в очереди и в системе:

(20.25)

А теперь решим любопытный пример. Железнодорожная касса по продаже билетов с двумя окошками представляет собой двухканальную СМО с неограниченной очередью, устанавливающейся сразу к двум окошкам (если одно окошко освобождается, ближайший в очереди пассажир его занимает). Касса продает билеты в два пункта: А и В. Интенсивность потока заявок (пассажиров, желающих купить билет) для обоих пунктов А и В одинакова: λ А = λ В = 0,45 (пассажира в минуту), а в сумме они образуют общий поток заявок с интенсивностью λ А + λ В = 0,9. Кассир тратит на обслуживание пассажира в среднем две минуты. Опыт показывает, что у кассы скапливаются очереди, пассажиры жалуются на медленность обслуживания, Поступило рационализаторское предложение: вместо одной кассы, продающей билеты и в А и в В, создать две специализированные кассы (по одному окошку в каждой), продающие билеты одна - только в пункт А , другая - только в пункт В. Разумность этого предложения вызывает споры - кое-кто утверждает, что очереди останутся прежними. Требуется проверить полезность предложения расчетом. Так как мы умеем считать характеристики только для простейших СМО, допустим, что все потоки событий - простейшие (на качественной стороне выводов это не скажется).

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

Вариант I (существующий). На двухканальную СМО поступает поток заявок с интенсивностью λ = 0,9; интенсивность потока обслуживании μ = 1/2 = 0,5; ρ = λ/μ = l,8. Так как ρ/2 = 0,9<1, финальные вероятности существуют. По первой формуле (20.22) находим р 0 ≈ 0,0525. Среднее, число заявок в очереди находим по формуле (20.23): L оч ≈ 7,68; среднее время, проводимое заявкой в очереди (по первой из формул (20.25)), равно W оч ≈ 8,54 (мин.).

Вариант II (предлагаемый). Надо рассмотреть две одноканальные СМО (два специализированных окошка); на каждую поступает поток заявок с интенсивностью λ = 0,45; μ. по-прежнему равно 0,5; ρ = λ/μ = 0,9<1; финальные вероятности существуют. По формуле (20.20) находим среднюю длину очереди (к одному окошку) L оч = 8,1.

Вот тебе и раз! Длина очереди, оказывается, не только не уменьшилась, а увеличилась! Может быть, уменьшилось среднее время ожидания в очереди? Посмотрим. Деля L оч на λ = 0,45, получим W оч ≈ 18 (минут).

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

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

Ну, ладно,- готов согласиться читатель,- увеличение можно объяснить, но почему оно такое существенное? Нет ли тут ошибки в расчете?

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

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

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

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

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

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

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

^ 5. Замкнутая СМО с одним каналом и m источниками заявок. Для конкретности поставим задачу в следующей форме: один рабочий обслуживает т станков, каждый из которых время от времени требует наладки (исправления). Интенсивность потока требований каждого работающего станка равна λ. Если станок вышел из строя в момент, когда рабочий свободен, он сразу же поступает на обслуживание. Если он вышел из строя в момент, когда рабочий занят, он становится в очередь и ждет, пока рабочий освободится. Среднее время наладки станка t об = 1/μ. Интенсивность потока заявок, поступающих к рабочему, зависит от того, сколько станков работает. Если работает k станков, она равна k λ. Найти финальные вероятности состояний, среднее число работающих станков и вероятность того, что рабочий будет занят.

Заметим, что и в этой СМО финальные вероятности

будут существовать при любых значениях λ и μ = 1/t об, так как число состояний системы конечно.