Зайцев М.Г., Варюхин С.Е. Методы оптимизации управления и принятия решений: примеры, задачи, кейсы. М.: Дело, 2011. - 664 с

([phone]

Варюхин Сергей Евгеньевич

Москва

Количественные методы в менеджменте

44 часа.

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

(4 часа)

Автор:

Варюхин Сергей Евгеньевич, к.ф.-м.н, доцент

Контактные данные преподавателя:

+ [email protected], [email protected]

www.HCXL.ru

Оглавление

ТЕМА 3 УПРАВЛЕНИЕ СИСТЕМАМИ МАССОВОГО ОБСЛУЖИВАНИЯ 111

Важнейшие характеристики систем массового обслуживания (СМО) 113

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

Поток (скорость поступления) клиентов (заявок) 115

Поток (скорость) обслуживания. 115

Число серверов в системе. 118

Размер популяции клиентов. 118

Длина очереди. 118

Надстройка MS Excel – QueueMods.xla. 121

Расчет параметров СМО при помощи надстройки QueueMods. 123

Практические задания. 127

Оценка экономической эффективности СМО. 131

ТЕМА 3

УПРАВЛЕНИЕ СИСТЕМАМИ МАССОВОГО ОБСЛУЖИВАНИЯ

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

Характеристики СМО и соотношения между ними. Примеры простых моделей СМО. Одноканальная СМО с неограниченной очередью. S-канальная СМО с неограниченной очередью. Одноканальная СМО с ограниченной очередью СМО для конечной популяции.

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

Как Вы думаете?

В сберкассу для оплаты коммунальных услуг и др. счетов 9-10 числа каждого месяца заходит в среднем 28 человек в час (этот поток приблизительно постоянен в течении всего рабочего времени кассы). Опыт показывает, что оператор тратит в среднем 4 мин на человека.

· Сколько Вы бы задействовали операторов (окошек), чтобы обслужить этот поток?

· Как Вы оцениваете, будет ли при этом очередь? Какой длины?

В среднем

Максимально

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

Какую долю времени, Вы думаете, они будут не заняты?

Важнейшие характеристики систем массового обслуживания (СМО)

1. Интенсивность потока клиентов (заявок).

2. Средняя скорость обслуживания для каждого сервера.

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

4. Вид очереди

5. Объем популяции клиентов.

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

Поступление клиентов

Поток заявок

· Пуассоновский

· Другой

Популяция клиентов

Размер популяции

· Бесконечный

· Конечный

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

Размер очереди

· Неограниченный

· Ограниченный (с отказами)

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

· FIFO

· С приоритетом

· С «нетерпеливыми» заявками

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

Каналы обслуживания

· Один канал

· S каналов

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

· Одинаковое для всех каналов

· Различное для разных каналов

Распределение времени обслуживания

· Экспоненциальное распределение

· Постоянное время

· Произвольное распределение

l  

Поток (скорость поступления) клиентов (заявок)

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

Если l не зависит от времени - стационарный случайный поток.

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

µ

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

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

Функция распределения для времени обслуживания – экспоненциальное распределение. Формулы теории массового обслуживания выведены большей частью для этого случая!

Пуассоновский (простейший) поток

· Стационарный

· Ординарный

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

Функция распределения для времени между событиями – экспоненциальное распределение

p(t) = µ*exp(-µt)

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

< t > = 1 / µ или < t > = 1 / l

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

σ = 1 / µ или σ = 1 / l

Вероятность того, что до наступления нового события пройдет время не более чем t: P(t) = 1 - exp(-lt)

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

p(N) = e^-ll^N/N!

Если l =3 соответствует 3 событиям в минуту, то распределение на рисунке показывает вероятность поступления ровно 1 клиента в минуту, ровно 2 клиентов в минуту, ровно 3….

Число серверов в системе

S  

Общее количество обслуживающих объектов – количество касс, число телефонных линий, число специалистов и т.д.

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

Размер популяции клиентов

К  

Сколько всего клиентов могут обратиться в систему обслуживания.

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

Длина очереди

N  

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

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

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

Формулы для расчета характеристик СМО для бесконечной популяции клиентов и неограниченной очереди

Параметр	Формула
ρ
P0
Ls
Lq
Pn	или
W
Wq

Здесь:

r – коэффициент утилизации (процент загрузки) любого из серверов системы

S – число серверов (каналов обслуживания)

– средняя скорость прибытия (интенсивность входного потока заявок)

– средняя скорость обслуживания для каждого сервера.

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

L – среднее число клиентов в системе

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

W – среднее время пребывания клиента в системе (ожидание плюс обслуживание)

P₀ – вероятность отсутствия клиентов в системе

P_n – вероятность того, что в системе ровно n клиентов

Надстройка MS Excel – QueueMods.xla

Авторская надстройка к MS Excel, которая называется Queue Mods 12.10.xla (версия, конечно, со временем изменяется) разработана специально для занятий по теме «Системы массового обслуживания».

Эту надстройку можно использовать, как обычный файл MS Excel с макросами, но удобнее всего добавить ее в список надстроек MS Excel. Чтобы использовать Queue Mods.xla как надстройку, следует переписать ее в папку, где содержатся стандартные надстройки MS Excel. Обычно это папка C:\Program files\Microsoft Office\OfficeХХ\Library (в ней же вы можете увидеть и папку с уже знакомой вам надстройкой Поиск решения – Solver.xla). В зависимости от конкретной версии MS Office и процедуры установки названия папок могут немного отличаться. Например, в XP версии Microsoft Office это будет …\Office10\Library, а в MS Office 2010 - …\Office14\Library.

После того, как вы переписали файл в папку Library, следует вызвать в MS Excel меню Сервис \Надстройки... (Tools \ Add-In... в английской версии) и отметить галочкой, появившуюся в списке надстроек новую надстройку Queue Mods 12.10.

В результате этого в меню Сервис добавится новая строка «Расчет параметров СМО»...(Tools\ «Queue systems» в англий

ской версии офиса). Сама надстройка двуязычная, в русской версии офиса она запускается с русским интерфейсом и выводом, в английской - автоматически переключается на английский интерфейс и вывод.

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

Надстройка никак не меняет параметры вашего компьютера. Она легко отключается через то же самое меню Сервис \Надстройки … (нужно только снять галочку напротив Queue Mods), при этом удаляется и дополнительная строка из меню и значок с панели.

Расчет параметров СМО при помощи надстройки QueueMods

При вызове надстройки «Расчет параметров СМО» появляется следующее диалоговое окно.

В диалоговом окне надстройки имеется три вкладки:

- неограниченная очередь,

- ограниченная очередь и

- ограниченная популяция.

-

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

Например, допустим, что интенсивность входного потока заявок на обслуживание равна 15 заявок в час, а среднее время, которое сервер тратит на обслуживание одной заявки равно 3 минуты. Тогда, если выбрать в качестве базовой единицы времени 1 час, интенсивность входного потока l следует задать равной 15, а скорость обслуживания для каждого сервера m - равной 20 (т.к. при среднем времени обслуживания в 3 минуты, в среднем будет обслужено 20 заявок в час).

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

В правой части – характеристики работы данной модели СМО в стационарном состоянии: процент загрузки каждого сервера r, среднее число клиентов в системе L_s, средняя длина очереди L_s, средние времена пребывания в системе W_s и ожидания обслуживания W_q, а также процент времени, когда все серверы свободны (P₀) и вероятность того, что в системе находится ровно N клиентов (P_n).

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

Если бы вместо введенных значений l =15/час, m =20/час, мы ввели бы l =0.25/мин, m =0.3333333/мин, т.е. в качестве базовой единицы времени выбрали 1 минуту, вывод имел бы следующий вид:

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

Практические задания.

Пример 1.

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

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

· Долю времени, когда банкомат загружен

· Долю времени, когда он бездействует.

· Среднее число машин у банкомата

· Среднее число машин в очереди у банкомата

· Среднее время, затрачиваемое клиентом для получения денег

· Среднее время, которое клиент проводит в очереди

· С какой вероятностью возле банкомата будут стоять более

3 машин.

Модель:

Ограничения на очередь:

Популяция:

λ =

μ =

S =

Пример 2.

Предположите, что для системы из примера 1 время обслуживания клиента распределено нормально со средним значением 3мин и стандартным отклонением 3 мин, 1 мин, 0 (постоянное время обслуживания).

Модель:

Ограничения на очередь:

Популяция:

λ =

μ =

S =

Хар-ки СМО	s=3 мин	s=1 мин	s=0 мин
r
L
Lq
W
Wq
P(N>3)

Пример 3.

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

Каковы характеристики СМО в этом случае?

Какое количество клиентов будет терять банк в таком случае?

Модель:

Ограничения на очередь:

Популяция:

λ =

μ =

S =

Пример 4.

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

При этом:

A. Жесткое ограничение на длину очереди снято, но крайне желательно, чтобы у банкоматов было не больше 3 машин.

Какова вероятность, что в очереди действительно будет не более 3 машин. Как изменятся характеристики СМО?

B. Жесткое ограничение на количество машин у банкомата сохранено.

Какое количество клиентов будет терять банк в таком случае? Каковы характеристики СМО в это случае?

Модель:

Ограничения на очередь:

Популяция:

λ =

μ =

S =

Оценка экономической эффективности СМО.

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

Плата за работу серверов обычно пропорциональна числу серверов S и вычисляется по формуле:

Плата за обслуживание = S * Стоимость работы 1 сервера

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

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

Потери от простоя = L (или L_q) * Потери от простоя 1 ед.

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

Доля потерянных клиентов = P_n,

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

Число потерянных клиентов = Доля потерянных клиентов * λ

Задача: Автосервис

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

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

Зарплата кладовщика $6/час Зарплата механика $12/час. Определить оптимальное число кладовщиков, обслуживающих заявки механиков.

Замечание:

Можно задать расчет всех нужных значений S сразу. Для этого следует написать в поле «Количество серверов» начальное и конечное значение для этой величины через тире.

Задача: Прядильная мастерская

В прядильной мастерской находятся 4 машины, каждая из которых останавливается и требует наладки в среднем 1 раз в час. Наладчик затрачивает на наладку в среднем 7.5 мин. Простой машины стоит $40/час. Оплата наладчика $7/час. Определить оптимальное число наладчиков.

Повторить расчет для цеха из 40 машин.

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

Задача: Ж/Д касса

Что лучше:

· Две независимые очереди с одним каналом обслуживания каждая или

· Одна очередь с двумя каналами?

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

Интенсивность «потока заявок» (пассажиров, становящихся в очередь) для обоих пунктов А и Б одинакова и равна l_А= l_Б=0.45 (пассажиров в минуту).

Кассир тратит на обслуживание клиента в среднем 2 минуты.

У кассы скапливаются очереди. Пассажиры жалуются на медлительность кассиров.

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

Оцените разумность предложения.

Литература по части курса

Основная литература.

Конец третьей части материалов курса. Продолжение следует…:)

Дата добавления: 2014-01-05