Теория очередей
.rtfМодели теории очередей
Знания о линиях обслуживания, часто называемые теорией очередей, являются важной частью производственного/ операционного менеджмента и ценным инструментом принятия решений. Линии обслуживания являются общим понятием; они могут, например, иметь форму очереди автомобилей, ожидающих ремонта в центре автосервиса или обслуживания
на автозаправочной станции; очереди работ на выполнение в рабочем центре промышленно-
го предприятия и т.д.
Анализ очередей в терминах длины очереди, среднего времени ожидания и других фак- торов помогает установить уровень сервиса при обслуживании клиентов (заявок потребите- лей). Менеджеры хотят иметь очереди такой длины, насколько это допустимо с точки зрения времени ожидания покупателей и затрат фирмы на сервис. Для этого есть средство - провес-
ти анализ общих затрат, как показано на рис.1.5. Общие затраты являются суммой расчет-
ных сервисных затрат и расчетных затрат ожидания.
З
а т
р Общие затраты
а
т ы
Затраты обслуживания
min
Затраты ожидания
opt
Уровень сервиса
Рис.1.5. Соотношение между затратами ожидания
и затратами обслуживания
Сервисные затраты показаны возрастающими при стремлении фирмы увеличить уро-
вень сервиса. Менеджеры могут регулировать мощность изменением загрузки и количества используемых машин, площадей, персонала, предотвращая или сокращая излишне длинные очереди. Затраты ожидания показаны убывающими при стремлении фирмы увеличить уро- вень сервиса. Эти затраты могут отражать убытки от потери производительности рабочих центров, пока инструменты или машины в них ожидают ремонта и техобслуживания, или могут отражать убытки от потери покупателей по причине низкого уровня сервиса (в т.ч. длинных очередей). В некоторых сервисных системах, например, неотложной медицинской помощи или аварийно-спасательных работ, цена ожидания может быть недопустимо высока.
Характеристики линейных систем ожидания. Выделяют три составляющие линей-
ных систем ожидания, или очередей: прибытия, или входы системы; дисциплина очереди,
или собственно система ожидания; узел обслуживания, или сервисное оборудование.
Каждая из составляющих имеет определенные характеристики, которые используются
в математических моделях очередей.
Характеристики прибытий. Входной источник, который генерирует прибытия или клиентов сервисной системы, имеет три главные характеристики: размер источника, модели прибытия в систему и поведения прибытия. Размер источника рассматривается либо как не- ограниченный (практически бесконечный), либо как ограниченный (конечный). Когда число клиентов или прибытий в любой момент происходит лишь малыми порциями от числа по- тенциальных прибытий, источник прибытий рассматривается неограниченным, или беско- нечным. В практической жизни примеры неограниченных источников включают автомобили
на автозаправках, покупателей в супермаркете, студентов, записывающихся на занятия в большом университете. Пример ограниченного, или конечного, источника - это рабочий центр с несколькими параллельно работающими рабочими местами на операции, которые могут выйти из строя и потребовать обслуживания. Модели прибытий в систему можно про- иллюстрировать следующим образом: заказчики приходят в пункт обслуживания либо по какому-либо известному расписанию, либо случайным образом. Прибытия считаются слу- чайными, если они не зависимы друг от друга, и их появление невозможно точно предска- зать. Часто в теории очередей число прибытий за единицу времени может быть определено с помощью распределения вероятности, известного как распределение Пуассона. Поведение прибытий может быть, например, таким, что принято называть “приходящие заказчики яв- ляются терпеливыми”. Терпеливые заказчики - это люди или машины, которые ожидают своей очереди до тех пор, пока их не обслужат, не покидая и не меняя очередь. Но есть и за- казчики, которые являются нетерпеливыми; они отказываются присоединиться к очереди, если она слишком длинна (по их мнению), или становятся в очередь, но затем покидают ее
без завершения действия, если приходится слишком долго ждать (по их мнению).
Характеристики очереди. Очереди характеризуются длиной и дисциплиной очереди. Длина очереди может быть или ограниченна, или неограниченна. Очередь ограниченна, если она не может по закону или физическим ограничениям увеличиваться до бесконечной дли- ны. Пример: прибытие объектов на обработку из накопителя ограниченной емкости. Очередь неограниченна, если нет ограничений на ее длину. Пример: прибытие автомобилей на за- правку и техобслуживание. Дисциплина очереди касается правила, по которому клиенты в очереди получают обслуживание. Большинство систем используют дисциплину очереди “первым пришел, первым обслужен” (FIFS); пример: обслуживание покупателей в очереди в кассу универсама. Другая распространенная дисциплина очереди “последним пришел, пер- вым обслужен” (LIFS); пример: разгрузка контейнера, когда материалы уложены так, что достать их можно только сверху. Могут применяться и иные дисциплины обслуживания в очереди, в частности, когда заявки помечены грифом “высший приоритет”; пример: обслу- живание в аэропорту V.I.P.-клиентов, в госпитале – больных в критическом состоянии.
Характеристики узла обслуживания. Узел обслуживания имеет две основные характе- ристики: конфигурация системы обслуживания и модель времени обслуживания. Конфигу- рация систем обслуживания обычно классифицируется по числу каналов, например, числу серверов, и числу фаз, например, числу позиций обслуживания, которые должны быть прой- дены. Соответственно различают одноканальные и многоканальные, однофазные и много-
фазные системы обслуживания. На рис.1.6. представлены возможные конфигурации систем обслуживания.
1. Одноканальная однофазная система
Узел обслуживания
2. Одноканальная многофазная система
Фаза 1 Фаза 2
3. Многоканальная однофазная система
Канал 1
Прибытия Канал 2 Убытия
Очередь
Канал 3
(после обслуживания)
4. Многоканальная многофазная система
-
Канал 1. Фаза 1
Канал 1. Фаза 2
Канал 2. Фаза 1
Канал 2. Фаза 2
Рис.1.6. Основные конфигурации систем обслуживания
Модели времени обслуживания, как и модели прибытий, могут быть или постоянными,
или случайными. Если время обслуживания постоянно, то одно и то же время затрачивается
на обслуживание каждого клиента или обработку каждой детали. Во многих случаях случай- ное время обслуживания описывается отрицательным экспоненциальным вероятностным распределением; это математически удобная посылка, если прибытия распределены согласно распределению Пуассона. Рис.1.7. иллюстрирует случай, когда время обслуживания соответ- ствует этому распределению, поэтому вероятность любого очень долгого времени обслужи- вания низка. Когда среднее время обслуживания 20 минут, редко бывает, что на обслужива- ние одного клиента потребуется больше, чем 90 минут. Если среднее время обслуживания 1 час, то вероятность затратить более, чем 180 минут на обслуживание, практически равна нулю.
Основные измерители состояний очереди: среднее время, которое тратит каждый кли- ент в очереди; средняя длина очереди; среднее время нахождения клиента в системе (время ожидания плюс время обслуживания); среднее число клиентов в системе; вероятность того, что узел об- служивания будет свободен; коэффициент использования системы; вероятность определен- ного числа клиентов в системе.
Модели очередей. В производственном/ операционном менеджменте может использо- ваться большое число разнообразных моделей очередей. Рассмотрим наиболее распростра- ненные из них, которые описывают простую систему, многоканальную, с постоянным вре-
менем обслуживания и ограниченным размером источника. Они также полагают: прибытия
распределяются по закону Пуассона; используется FIFS-дисциплина; осуществляется одно- фазное обслуживание. В дополнение они описывают системы сервиса, которые оперируют в стабильных условиях, т.е. прибытие и обслуживание остаются стабильными во время анали-
за. Рассматриваемые модели очередей представлены в табл.1.1.
Вероят-
ность для интерва- лов
1 мин.
Вероятность того, что обслуживание длится дольше, чем х мин.
Среднее время обслуживания 20 мин.
Среднее время обслуживания 60 мин.
0 30 60 90 120 150 180
Время обслуживания, мин.
Рис.1.7. Примеры отрицательного экспоненциального распределения
для времени обслуживания
Модели очередей
Таблица 1.1.
К о д |
Наименова- ние модели |
Пример |
Число каналов |
Число фаз |
Распреде- ление прибытий |
Распреде- ление вре- мени об- служивания |
Размер источни- ка |
Дисцип- лина очереди |
A |
Простая (М/M/1) |
Прилавок в от- деле магазина |
Однока- нальная |
Одна |
Пуассона |
Экспонен- циальное |
Не огра- ничен |
FIFS |
B |
Многока- нальная (М/M/S) |
Окно продажи авиабилетов |
Много- каналь- ная |
Одна |
Пуассона |
Экспонен- циальное |
Не огра- ничен |
FIFS |
C |
С постоян- ным време- нем обслу- живания (М/D/1) |
Автоматиче- ская мойка ма- шин |
Однока- нальная |
Одна |
Пуассона |
Постоян- ное |
Не огра- ничен |
FIFS |
D |
С ограни- ченным раз- мером ис- точника |
Узлы машины, которые могут ломаться |
Однока- нальная |
Одна |
Пуассона |
Экспонен- циальное |
Ограни- чен |
FIFS |
Модель А: одноканальная модель очередей. Одноканальная, или односерверная, систе-
ма обслуживания. Прибытия формируют простую очередь на обслуживание к одной стан- ции. Используется пуассоновское распределение прибытий и экспоненциальное время об- служивания.
Допускается, что следующие условия относятся к этому типу систем.
1. Прибытия обслуживаются по правилу “первым пришел, первым обслужен” (FIFS),
каждое прибытие ожидает обслуживания в зависимости от длины очереди.
2. Прибытия являются независимыми от предыдущих прибытий, но среднее число при-
бытий не изменяется во времени.
3. Прибытия описываются пуассоновским распределением вероятности и поступают из неограниченного (или бесконечно большого источника).
4. Времена обслуживания изменяются от одного клиента к другому и не зависимы друг
от друга, но их среднее время известно.
5. Время обслуживания подчинено отрицательному экспоненциальному закону распре-
деления.
6. Время обслуживания меньше времени между прибытиями.
Формулы для модели А, или М/М/1, представлены в табл.1.2.
Формулы для модели очередей А - простой, или М/M/1
l - среднее число прибытий за период времени;
m - среднее число обслуженных за период времени
Среднее число единиц (клиентов) в системе Ls = l /(m-l)
Таблица 1.2.
Среднее время единицы, проводимое в системе (время ожидания + время обслуживания)
Ws = 1/(m-l)
2
Среднее число единиц в очереди Lq = l
/m(m-l)
Среднее время единицы, проводимое в ожидании в очереди Wq = l/m(m-l)
Коэффициент использования системы r = l/m
Вероятность 0 единиц в системе (когда обслуживание бесполезно) P0 = 1 - l/m
k+1
Вероятность более, чем k единиц в системе Pn>k = (l/m)
Пример 1.7. Модель М/М/1. Рабочий в мастерской автосервиса способен обслуживать
три автомобиля в час (или около 20 минут на один автомобиль) согласно отрицательному экспоненциальному распределению. Клиенты, нуждающиеся в этом обслуживании в мастер- ской, появляются по два в час, подчиняясь распределению Пуассона. Клиенты обслуживают-
ся по правилу FIFS и появляются из практически неограниченного источника возможных по-
требителей услуг.
Операционные характеристики системы очередей мастерской:
l = 2 автомобиля, поступившие за час
m = 3 автомобиля, обслуженные за час
Ls = l/(m-l) = 2/(3-2) = 2/1=2 автомобиля в системе в среднем
Ws = 1/(m-l)= 1/(3-2) = 1 - среднее время ожидания в системе
Lq = l2/m(m-l) = 22/3(3-2)= 4/3(1)=4/3=1.33 автомобиль, ожидающий в очереди в среднем
Wq = l/m(m-l) = 2/3(3-2) =2/3 час = 40 минут - среднее время ожидания в очереди на 1 авто-
мобиль
r = l/m = 2/3 = 66.6% времени механик занят
P0 = 1 - l/m = 1 - 2/3 = 0.33 - вероятность 0 автомобилей в системе
Вероятность более, чем k автомобилей в системе
k+1
k Pn>k = (2/3)
0 .667 <------- Это эквивалентно 1-Р0=1-.33=.667
1 .444
2 .296
3 .198 <------- Означает, что в 19.8% случаев больше, чем 3 автомобиля находятся
в системе
4 .132
5 .088
6 .058
7 .039
После того, как рассчитаны операционные характеристики системы очередей, можно провести их экономический анализ.
Пример 1.8. Анализ затрат для модели М/М/1. Владелец мастерской автосервиса уста- новил, что затраты ожидания в терминах неудовлетворенности клиента уровнем обслужива- ния, составляют $10 за час времени, проведенного в ожидании в очереди. С поступающего автомобиля имеем 2/3 часа ожидания (Wq), распространяя это на 16 автомобилей, обслужи- ваемых в день (два в час на восемь часов работы в день), получаем общее число часов, ко- торое клиенты ожидают в очереди на ремонт каждый день - 2/3 (16) = 32/3 = 10 2/3 часа.
Затраты клиентов на ожидание в очереди = $10 (10 2/3) = $107/день.
Другие основные затраты владельца мастерской могут определяться заработком меха-
ника, который получает $7/час, или $56/день.
Общие рассчитанные затраты = $107 +$56 = $163/день.
Модель В: многоканальная модель очередей. Многоканальная система очередей, в ко- торой два или более канала (сервера) способны обслуживать клиентов. Предполагается, что клиенты, ожидающие в очереди, обслуживаются первым освободившимся сервером. Прибы- тия подчиняются пуассоновскому распределению вероятности, время обслуживания имеет экспоненциальное распределение. Обслуживание ведется по правилу FIFS, и все серверы ра- ботают по этому правилу. Остаются и другие предположения, описанные ранее для однока- нальной модели.
Уравнения очередей для модели В, или M/M/S, показаны в табл.1.3.
Формулы для модели очередей В - многоканальной, или M/M/S
M - число открытых каналов; l - средняя скорость прибытий;
m - средняя скорость обслуживания для каждого канала
Вероятность, что ноль клиентов или единиц в системе
Таблица 1.3.
P0
M 1
[ е
1
1 (l / m)n ] 1
(l / m) M Mm
для
Mm 1
n0 n!
M ! Mm l
Среднее число клиентов или единиц в системе
M
Ls lm(l / m)
(M 1)!(Mm l )2
P0
l / m
Среднее время единицы, проводимое в ожидании или обслуживании (а именно в системе)
M
Ws
m(l / m)
(M 1)!(Mm l )2
P0 1/ m Ls / l
Среднее число клиентов или единиц в очереди на обслуживание Lq = Ls - l/m
Среднее время единицы, проводимое в ожидании в очереди на обслуживание
Wq = Ws - 1/m = Lq/l
Пример 1.9. Модель M/M/S. Мастерская автосервиса открывает второй пункт ремонта и нанимает второго механика. Заказы, которые появляются по правилу l=2/час, будут выстрое-
ны в очередь, пока один из двух механиков не освободится. Каждый механик ремонтирует автомобили по правилу m=3/час.
Чтобы выяснить, как эта система будет конкурировать со старой одноканальной систе-
мой очередей, вычисляем ряд операционных характеристик для М=2 канала и сравниваем результаты с найденными в первом примере.
Р0
1 1(2 / 3)n
[ е
1
] 1 (2 / 3)2
2(3)
1
1 2 / 3 1/ 2(4 / 9)(6 / 4)
n 0
1
n! 2!
1/ 2
2(3) 2
Тогда
1 2 / 3 1/ 3
т.е. 0.5 - вероятность 0 автомобилей в системе.
2
L (2)(3)(2 / 3)
s 1![2(3) 2]2
(1/ 2) 2 / 3 8 / 3 (1/ 2) 2 / 3 3 / 4
16
= .75 - среднее число автомобилей в системе.
Ws = Ls/l = .75/2= 3/8 час = 22.5 минуты - среднее время автомобиля, проводимое в системе.
Lq = Ls - l/m = 3/4 - 2/3 = 1/12 = 0.083 - среднее число автомобилей в очереди.
Wq = Lq/l =.083/2 =.0415 чаc = 2.5 минуты - среднее время автомобиля в ожидании в очереди.
Можем обобщить эти характеристики и сравнить их с одноканальной моделью.
Одноканальная модель Двухканальная модель
P0 |
.33 |
.5 |
Ls |
2 автомобиля |
.75 автомобиля |
Ws |
60 минут |
22.5 минуты |
Lq |
1.33 автомобиль |
.083 автомобиля |
Wq |
40 минут |
2.5 минуты |
Расширение обслуживания имеет эффект практически на всех характеристиках. Осо-
бенно на времени ожидания в очереди, которое сокращается с 40 минут до 2.5 минут.
Модель С: модель с постоянным временем обслуживания. Время обслуживания посто- янное взамен экспоненциального распределения времени обслуживания. Поэтому размер Lq, Wq, Ls, Ws всегда меньше, чем в модели А. Средняя длина очереди и среднее время ожида- ния в очереди короче в два раза. Формулы для модели С, или M/D/1, даны в табл.1.4.
Таблица 1.4.
Формулы для модели очередей С - с постоянным временем обслуживания, или M/D/1
l 2
Средняя длина очереди:
Lq
2m(m l )
l
Среднее время ожидания в очереди:
Wq
2m(m l )
Среднее число каналов в системе: Ls = Lq + l/m
Среднее время, проводимое в системе: Ws = Wq + 1/m
Пример 1.10. Модель M/D/1. Компания имеет грузовые автомобили, которые привозят материалы для переработки, ожидая в среднем по 15 минут перед разгрузкой. Затраты води- теля и автомобиля в очереди составляют $60/час. Может быть закуплен новый разгрузчик, чтобы процесс разгрузки выполнялся по правилу 12 автомобилей в час (то есть 5 минут на автомобиль). Грузовые автомобили появляются согласно распределению Пуассона со сред- ней 8 автомобилей в час. Если использовать новый разгрузчик, его затраты на амортизацию составят $3 на разгрузку. Анализ изменения затрат и результатов от покупки разгрузчика дал следующие результаты.
Существующие затраты ожидания на 1 рейс = (1/4 час ожидания)($60/час затрат) = $15/рейс. Новая система: l=8 грузовиков/час поступающих, m=12 грузовиков/час обслуживаемых. Среднее время ожидания в очереди Wq = l/[2m(m-l)]=8/[2(12)(12-8)]=1/12 час.
Затраты ожидания на 1 рейс с новым разгрузчиком = (1/12 час очереди)($60/час затрат) =
= $5/рейс.
Экономия с новым оборудованием =$15(существующая система)-$5(новая система) =
= $10/рейс.
Затраты на амортизацию нового оборудования $3/рейс. Чистая экономия $7/рейс.
Модель D: модель с ограниченным источником. Имеется ограниченный источник по-
тенциальных клиентов для узла обслуживания, т.е. в системе обслуживается некоторое огра-
ниченное число клиентов (объектов). Существует связь между длиной очереди и правилом появления заявки: чем длиннее очередь, тем меньше прибытий клиентов.
Табл.1.5. показывает формулы для модели D с ограниченным источником.