Теория очередей

Модели теории очередей

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

на автозаправочной станции; очереди работ на выполнение в рабочем центре промышленно-

го предприятия и т.д.

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

ти анализ общих затрат, как показано на рис.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)}

₂

^{Среднее число единиц в очереди Lq = l}

_/m(m-l)

Среднее время единицы, проводимое в ожидании в очереди Wq = l/m(m-l)

Коэффициент использования системы r = l/m

Вероятность 0 единиц в системе (когда обслуживание бесполезно) P₀ = 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 = l²/m(m-l) = 2²/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% времени механик занят

P₀ = 1 - l/m = 1 - 2/3 = 0.33 - вероятность 0 автомобилей в системе

Вероятность более, чем k автомобилей в системе

_k+1

^{k Pn>k = (2/3)}

0 .667 <------- Это эквивалентно 1-Р₀=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.

P₀ 

_{M 1}

_{[ е}

1

¹ _{(l / m)}ⁿ _{] } ¹

_{(l / m)} ^{M Mm}

для

Mm  1

_n0 ^n!

M ! Mm  l

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

_M

_{Ls } ^{lm(l / m)}

(M  1)!(Mm  l )²

P₀ 

l / m

Среднее время единицы, проводимое в ожидании или обслуживании (а именно в системе)

_M

Ws 

m(l / m)

_{(M  1)!(Mm  l )}²

P₀  1/ m  Ls / l

Среднее число клиентов или единиц в очереди на обслуживание Lq = Ls - l/m

Среднее время единицы, проводимое в ожидании в очереди на обслуживание

Wq = Ws - 1/m = Lq/l

Пример 1.9. Модель M/M/S. Мастерская автосервиса открывает второй пункт ремонта и нанимает второго механика. Заказы, которые появляются по правилу l=2/час, будут выстрое-

ны в очередь, пока один из двух механиков не освободится. Каждый механик ремонтирует автомобили по правилу m=3/час.

Чтобы выяснить, как эта система будет конкурировать со старой одноканальной систе-

мой очередей, вычисляем ряд операционных характеристик для М=2 канала и сравниваем результаты с найденными в первом примере.

Р₀ 

¹ _{1(2 / 3)}ⁿ

_{[ е}

1

_{] } ¹ _{(2 / 3)}²

2(3)

_ ¹ _

^{1  2 / 3  1/ 2(4 / 9)(6 / 4)}

n 0

_ ¹

n! 2!

_{ 1/ 2}

2(3)  2

Тогда

1  2 / 3  1/ 3

т.е. 0.5 - вероятность 0 автомобилей в системе.

₂

_{L } ^{(2)(3)(2 / 3)}

^s 1![2(3)  2]²

_{(1/ 2)  2 / 3 } ^{8 / 3} _{(1/ 2)  2 / 3  3 / 4}

¹⁶

= .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 ²

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

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 с ограниченным источником.}