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

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

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

Рис. 6.2.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Классификация, основные понятия, элементы модели, расчет основных характеристик.

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

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

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

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

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

СМО классифицируются по разным признакам .

1. По числу каналов обслуживания СМО делятся на одноканальные и многоканальные.

2. В зависимости от условий ожидания требованием начала обслуживания различают СМО с потерями (отказами) и СМО с ожиданием.

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

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

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

Для СМО с ожиданием основными характеристиками являются математические ожидания длины очереди и времени ожидания.

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

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

В качестве характеристик эффективности может применяться вероятность отказа как в системах с потерями (или характеристики времени ожидания) и в системах с ожиданием.

3. По дисциплине обслуживания СМО делятся на системы с приоритетом в обслуживании и на системы без приоритета в обслуживании.

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

4. СМО могут быть однофазными и многофазными.

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

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

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

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

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

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

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

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

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

где λ - параметр потока (см. ниже).

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

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

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

Отсутствие последействия означает, что число требований, поступивших в систему до момента t, не определяет того, сколько требований поступит в систему за время t + Δt.

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

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

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

т.е. вероятность того, что время обслуживания не превосходит некоторой величины t, определяется формулой (1 – e -μt), где μ -параметр экспоненциального закона времени обслуживания требований в системе - величина, обратная среднему времени обслуживания, т.е. .

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

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

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

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

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

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

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

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

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

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

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

P k = α k P 0 , (1 ≤ k ≤ n),

где

λ - частота (интенсивность) поступления требований в систему от одного источника;

Средняя продолжительность обслуживания одного требования;

m - наибольшее возможное число требований, находящихся в обслуживающей системе одновременно;

n - число обслуживающих аппаратов;

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

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

P k = α k P 0 , (n ≤ k ≤ m),

где

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

следовательно,

4. Среднее число требований, ожидающих начала обслуживания (средняя длина очереди):

5. Коэффициент простоя требования в ожидании обслуживания:

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

7. Среднее число требований, находящихся в обслуживающей системе (обслуживаемых и ожидающих обслуживания):

8. Коэффициент полного простоя требований на обслуживании и в ожидании обслуживания:

9. Среднее время простоя требования в очереди на обслуживание:

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

11. Коэффициент простоя обслуживающих аппаратов:

12. Вероятность того, что число требований, ожидающих обслуживания, больше некоторого числа В (вероятность того, что в очереди на обслуживание находится более В требований):

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

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

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

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

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

Рассмотрим схему работы СМО (рис. 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 ) будет большей; чего и следовало ожидать. По формуле можно обнаружить и менее очевидный факт: перегрузка также увеличивается, когда изменчивость распределения времени обслуживания возрастает, даже если среднее время обслуживания остается прежним. Интуитивно это можно объяснить так: дисперсия случайной величины времени обслуживания может принять большое значение (поскольку она должна быть положительной), т. е. единственное устройство обслуживания будет занято длительное время, что приведет к увеличению очереди.

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

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

ВВЕДЕНИЕ

ГЛАВА 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 % . Таким образом, задача состоит в выборе такой мощности кассового узла, которая позволит получит минимальные совокупные затраты на массовое обслуживание покупателей.

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

23 октября 2013 в 14:22

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

• Программирование ,
• ООП ,
• Параллельное программирование

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

Пару слов о Squeak

Squeak это открытая, кросс-платформенная реализация языка программирования Smalltalk-80 c динамической типизацией и сборщиком мусора. Интерфейс довольно специфический, но вполне удобный для отладки и анализа. Squeak полностью отвечает концепции ООП. Все состоит из объектов, даже конструкции if-then-else, for, while реализованы с их помощью. Весь синтаксис сводится к посылке объекту сообщения в виде:

<объект> <сообщение>

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

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

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

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

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

Немного математики

Для пуассоновского потока число событий X , попадающих в интервал длины τ (тау), примыкающий к точке t , распределено по закону Пуассона:
где a (t, τ) - среднее число событий, наступающих на интервале времени τ .
Среднее число событий, наступающих в единицу времени, равно λ(t) . Следовательно, среднее число событий на интервале времени τ , примыкающему к моменту времени t , будет равно:

Время T между двумя событиями при λ(t) = const = λ распределено по закону:
Плотность распределения случайной величины T имеет вид:
Для получения псевдослучайных пуассоновских последовательностей интервалов времени t i решают уравнение:
где r i - равномерно распределенное на интервале случайное число.
В нашем случае это дает выражение:

По генерации случайных чисел можно писать целые тома. Здесь же, для генерации равномерно распределенных на интервале целых чисел используем следующий алгоритм:
где R i - очередное случайное целое число;
Р - некоторое большое простое число (например 2311);
Q - целое число - верхняя граница интервала, например, 2 21 = 2097152;
rem - операция получения остатка от деления целых чисел.

Начальное значение R 0 обычно задают произвольно, например, используя показания таймера:
Time totalSeconds
Для получения равномерно распределенных на интервале чисел воспользуемся оператором языка:

Класс Rand

Для получения равномерно распределенных на интервале случайных чисел создаем класс - генератор вещественных чисел:

Float variableWordSubclass: #Rand "имя класса" instanceVariableNames: "" "переменные экземпляра" classVariableNames: "R" "переменные класса" poolDictionaries: "" "общие словари" category: "Sample" "имя категории"
Методы:

"Инициализация" init R:= Time totalSeconds.next "Следующее псевдослучайное число" next R:= (R * 2311 + 1) rem: 2097152. ^(R/2097152) asFloat
Для установки начального состояния датчика посылаем сообщение Rand init .
Для получения очередного случайного числа посылаем Rand next .

Программа обработки заявок

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

Код на Squeak

"Объявление временных переменных" | proc1 proc2 t1 t2 s1 s2 sysPriority queue continue r | "Начальные установки переменных" Rand init. SysTime:= 0. s1:= 0. s2:= 0. t1:= -1. t2:= -1. continue:= true. sysPriority:= Processor activeProcess priority. "Текущий приоритет" queue:= Semaphore new. "Модель очереди заявок" "Создание процесса - модели канала 1" (Process forContext: [ proc1:= Processor activeProcess. whileTrue: "Цикл обслуживания" [ queue wait. "Ждать заявку" t1:= SysTime + 2. "Следующее время активизации" s1:= s1 + 1. proc1 suspend. "Приостановить процесс в ожидании окончания обслуживания" ]. proc1:= nil. "Удалить ссылку на процесс 1" ] priority: (sysPriority + 1)) resume. "Новый приоритет больше фонового" "Создание процесса - модели канала 2" (Process forContext: [ proc2:= Processor activeProcess.. whileTrue: [ queue wait. t2:= SysTime + 7. s2:= s2 + 1. proc2 suspend. ]. proc2:= nil. ] priority: (sysPriority + 1)) resume. "Продолжение описания главного процесса и модели источника" whileTrue: [ r:= (Rand next * 10) rounded. (r = 0) ifTrue: . ((SysTime rem: r) = 0) ifTrue: . "Послать заявку" "Коммутатор процессов обслуживания" (t1 = SysTime) ifTrue: . (t2 = SysTime) ifTrue: . SysTime:= SysTime + 1. "Тикает модельное время" ]. "Показать состояние счетчика заявок" PopUpMenu inform: "proc1: ",(s1 printString),", proc2: ",(s2 printString). continue:= false.

При запуске видим, что процесс 1 успел обработать 31 заявку, а процесс 2 только 11: