Теория очередей. Модель теории очередей, или модель массового обслуживания

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

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

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

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

Основные элементы системы следующие:

1. Входящий поток требований (интенсивность входящего потока );

2. Каналы обслуживания (число каналов n , среднее число занятыхk , производительность );

3. Очередь требований (среднее число заявок z , среднее время пребывания одной заявкиt );

4. Выходящий поток требований (интенсивность входящего потока  ).

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

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

 открытые – вне системы и не оказывает влияния.

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

 однофазные – один этап обслуживания,

 многофазные – два и более этапов.

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

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

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

1. по принципу «первый пришел – первый обслужен»;

2. по принципу «первый пришел – последним обслужен» (например, отгрузка однородной продукции со склада).

3. случайно;

4. с приоритетом. При этом приоритет может быть абсолютным (более важная заявка вытесняет обычную) иотносительным (важная заявка получает лишь «лучшее» место в очереди).

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

Пример . УстройствоS состоит из двух узлов,

каждый из которых в случайный момент времени может выйти из строя, после чего мгновенно начинается ремонт узла, продолжающийся заранее неизвестное случайное время. Возможные состояния системы: S 0 – оба узла исправны;S 1 – первый узел ремонтируется, второй исправен;S 2 – первый узел исправен, второй ремонтируется;S 3 – оба узла ремонтируются.

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

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

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

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

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

Поток событий называетсястационарным , если его вероятностные характеристики не зависят от времени. В частности у стационарного потока λ(i )= λ (поток автомобилей на проспекте в часы пик).

Поток событий называетсяпотоком без последствий , если для любых два непересекающихся участков времени –τ 1 иτ 2 – число событий, попадающих на один из них, не зависит от числа событий, попадающих на другие(поток людей, входящих в метро или поток покупателей, отходящих от кассы).

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

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

Ординарный поток заявок без последствий описывается распределением (законом) Пуассона.

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

Каждому событию соответствует момент t , в который это событие произошло. Т – интервал между двумя моментами времени. Поток событий – независимая последовательность моментов t .

Для простейшего потока с интенсивностью λ вероятность попадания на элементарный (малый) отрезок времени Δt хотя бы одного события потока равна.

Ординарный поток заявок без последствий описывается распределением (законом) Пуассона с параметром λτ :

, (1)

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

В частности, вероятность того, что за время τ не произойдет ни одного события (m =0), равна

. (2)

Пример. На автоматическую телефонную линию поступает простейший поток вызовов с интенсивностью λ =1,2 вызовов в минуту. Найти вероятность того, что за две минуты: а) не придет ни одного вызова; б) придет ровно один вызов; в) придет хотя бы один вызов.

Решение. а) Случайная величина Х – число вызовов за две минуты – распределена по закону Пуассона с параметром λτ =1,2·2=2,4. Вероятность того, что вызовов не будет (m =0), по формуле (2):

б) Вероятность одного вызова (m =1):

в) Вероятность хотя бы одного вызова:

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

Рассмотрим математическое описание Марковского процесса с дискретными состояниями и непрерывным временем на примере процесса, граф которого изображен на рис. 1. Будем полагать, что все переходы системы из состояния S i в S j происходят под воздействием простейших потоков событий с интенсивностями состояний λ ij (i , j =0,.1,2,3).

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

Граф состояний системы с проставленными у стрелок интенсивностями будем называтьразмеченным . Рассматриваемая система имеет четыре возможных состояния:S 0 ,S 1 ,S 2 ,S 3 . Назовем вероятностьюi -го состояния вероятностьp i (t ) того, что в моментt система будет находиться в состоянииS i . Очевидно, что для любого моментаt сумма вероятностей всех состояний равна единице:
.

Предельная вероятность состояния S i имеет – показывает среднее относительное время пребывания системы в этом состоянии(если предельная вероятность состояния S 0 , т.е. p 0 =0,5, то это означает, что в среднем половину времени система находится в состоянии S 0 ).

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

(3)

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

Пример . Найти предельные вероятности для системы, граф состояний которого изображен на рис. выше. при λ 01 =1, λ 02 =2, λ 10 =2, λ 13 =2, λ 20 =3, λ 23 =1, λ 31 =3, λ 32 =2 .

Система алгебраических уравнений для этого случая согласно (3) имеет вид:

Решив линейную систему уравнений, получим p 0 = 0,4, p 1 = 0,2, p 2 = 0,27, p 3 = 0,13; т.е. в предельном стационарном режиме система S в среднем 40% времени будет находиться в состоянии S 0 (оба узла исправны), 13% в состоянии S 1 (первый узел ремонтируется, второй работает), 27% - в состоянии S 2 (второй узел ремонтируется, первый работает) и 13% в состоянии S 3 (оба узла ремонтируются).

Определим чистый доход от эксплуатации в стационарном режиме рассмотренной системы S в условиях, что в единицу времени исправная работа узла один и узла два приносит доход соответственно 10 и 6 денежных единиц, а их ремонт требует соответственно затрат 4 и 2 денежных единицы. Оценим экономическую эффективность имеющейся возможности уменьшения вдвое среднего времени ремонта каждого из двух узлов, если при этом придется вдвое увеличить затраты на ремонт каждого узла (в единицу времени).

Для решения этой задачи с учетом полученных значений p 0 , p 1 , p 2 , p 3 определим долю времени исправной работы первого узла, т.е. p 0 + p 2 = 0,4+0,27 = 0,67 и долю времени исправной работы второго узла p 0 + p 1 = 0,4+0,2 = 0,6. В то же время первый узел находится в ремонте в среднем долю времени равную p 1 + p 3 = 0,2+0,13 = 0,33, а второй узел p 2 + p 3 = 0,27+0,13 = 0,40. Поэтому средний чистый доход в единицу времени от эксплуатации системы равен Д =0,67·10+0,6·6–0,33·4–0,4·2=8,18 ден.ед. уменьшение вдвое среднего времени ремонта каждого узла будет означать увеличение вдвое интенсивностей потока «окончания ремонтов» каждого узла, т.е. теперь λ 10 =4, λ 20 =6, λ 31 =6, λ 32 =4 и система уравнений, описывающая стационарный режим системы S , будет иметь вид:

Решив систему получим p 0 = 0,6, p 1 = 0,15, p 2 = 0,2, p 3 = 0,05. Учитывая, что p 0 + p 2 = 0,6+0,2 = 0,8,

p 0 + p 1 = 0,6+0,15 = 0,75, p 1 + p 3 = 0,15+0,05 = 0,2, p 2 + p 3 = 0,2+0,05 = 0,25, а затраты на ремонт первого и второго узла составляют соответственно 8 и 4 ден.ед., вычислим чистый средний доход в единицу времени: Д1 =0,8·10+0,75·6–0,2·8–0,25·4=9,99 ден.ед.

Так как Д1 больше Д (примерно на 20%), то экономическая целесообразность ускорения ремонта узлов очевидна.

5. Процесс размножения и гибели Рассматриваемый в СМО процесс размножения и гибели характеризуется тем, что если все состояния системы пронумероватьS 1 ,S 2 ,… ,S n то из состоянияS k (k < n ) можно попасть либо в состояниеS k -1 , либо в состояниеS k +1 .

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

(4)

к которой добавляется условие:

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

, (6)

,
, …,
. (7)

Пример. Процесс гибели и размножения представлен графом. (рис).

Найти предельные вероятности состояний.

Решение. По формуле (6) найдем
,

по (7)
,
,

т.е. в установившемся стационарном режиме в среднем 70,6% времени система будет находиться в состоянии S 0 , 17,6% – в состоянии S 1 и 11,8% – в состоянии S 2 .

6. Системы с отказами В качестве показателей эффективности СМО с отказами будем рассматривать:

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

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

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

– среднее число занятых каналов (для многоканальной системы).

Очередей теория

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

Пример. Пусть имеется один обслуживающий прибор, на который поступает случайный поток требований. Если в момент поступления требования прибор свободен, то оно сразу начинает обслуживаться. В противном случае оно становится в очередь и прибор обслуживает требования одно за другим в порядке их поступления. Пусть а - среднее число требований, поступающих за время одного обслуживания, а Т - длительность периода занятости, то есть промежутка времени от момента занятия прибора каким-либо требованием, заставшим прибор свободным, до первого момента полного освобождения прибора. О. т. показывает, что при естественных допущениях математическое ожидание Т равно m = 1/(1 - а), а дисперсия равна (1 + a ) m 3 (так, при а = 0,8 соответствующие значения равны 5 и 225). Таким образом, для «хорошо загруженного» обслуживающего прибора (то есть при а, близких к 1) среднее значение m случайной величины Т является весьма ненадёжной характеристикой Т.

Лит.: Гнеденко Б. В., Коваленко И. Н., Введение в теорию массового обслуживания, М., 1966; Приоритетные системы обслуживания, М., 1973.

Ю. В. Прохоров.

Большая советская энциклопедия. - М.: Советская энциклопедия . 1969-1978 .

Очанка
Очередные задачи советской власти

Смотреть что такое "Очередей теория" в других словарях:

ОЧЕРЕДЕЙ ТЕОРИЯ - в математике раздел теории массового обслуживания, где изучаются системы, в которых требования, застающие систему занятой, не теряются, а ожидают ее освобождения и затем обслуживаются в том или ином порядке … Большой Энциклопедический словарь

очередей теория - (матем.), раздел теории массового обслуживания, где изучаются системы, в которых требования, застающие систему занятой, не теряются, а ожидают её освобождения и затем обслуживаются в том или ином порядке. * * * ОЧЕРЕДЕЙ ТЕОРИЯ ОЧЕРЕДЕЙ ТЕОРИЯ, в… … Энциклопедический словарь

ОЧЕРЕДЕЙ ТЕОРИЯ - см. Массового обслуживания теория … Большой энциклопедический политехнический словарь

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

ОЧЕРЕДЕЙ ТЕОРИЯ - (матем.), раздел теории массового обслуживания, где изучаются системы, в к рых требования, застающие систему занятой, не теряются, а ожидают её освобождения и затем обслуживаются в том или ином порядке … Естествознание. Энциклопедический словарь

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

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

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

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

Теория очередей - см. Теория массового обслуживания … Экономико-математический словарь

Книги

Логистика и теория очередей
Логистика и теория очередей , Рыжиков Ю.И.. В учебном пособии рассматривается современное состояние теории логистики, обсуждаются элементы математической модели управления запасами и основы численных методов теории очередей;…

Этот метод, предложенный Данцигом, Кестеном и Ранненбергом (метод коллективных меток - method of collective marks) и развитый затем Г.П. Климовым (метод «катастроф»), позволяет легко получить аналитические результаты в ситуациях, когда другие известные методы приводят к трудоемким выкладкам. Особенно эффективен он оказался при анализе ненадежных и приоритетных систем массового обслуживания.

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

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

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

Считаем, что выполняется условие:

гарантирующее существование стационарного распределения длины периода занятости рассматриваемой СМО.

Утверждение 13.

Преобразование Лапласа - Стилтьеса распределения длины периода занятости рассматриваемой СМО удовлетворяет следующему функциональному уравнению:

Доказательство. Легко видеть, что распределение длины периода занятости системы не зависит от того, в каком порядке обслуживаются запросы. Для облегчения анализа структуры периода занятости предположим, что запросы обслуживаются в инверсионном порядке, то есть на обслуживание всегда выбирается запрос, пришедший в систему последним. Такая дисциплина выбора из очереди кодируется как LIFO (Last In - First Out) или LCFS (Last Came - First Served). При такой дисциплине выбора из очереди каждый запрос как бы порождает период занятости системы запросами, пришедшими в систему после него. Причем структура и, следовательно, распределение длины периода занятости, порожденного некоторым запросом, такие же, как структура и распределение длины периода занятости системы. Используя эти рассуждения, мы приходим к пониманию того, что период занятости системы состоит из времени обслуживания первого запроса, с которого начался период занятости, и случайного числа периодов занятости, порожденных запросами, пришедшими в систему за время обслуживания первого запроса.

Теперь предположим, что независимо от функционирования данной системы поступает простейший поток катастроф интенсивности s. Введем в рассмотрение (дополнительное) событие А, состоящее в том, что за данный период занятости не поступили катастрофы.

Напомним, что согласно вероятностной трактовке преобразования Лапласа - Стилтьеса, величина есть вероятность того, что не произойдет ни одной катастрофы за случайное время, имеющее функцию распределения H(t). Поэтому легко понять, что вероятность события А определяется следующим образом:

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

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

Таким образом, используя еще раз вероятностную трактовку преобразования Лапласа - Стилтьеса мы получаем следующую формулу для вероятности события :

Сравнивая выражения (1.83) и (1.84), мы убеждаемся в справедливости формулы (1.82). Утверждение 13 доказано.

Уравнение (1.82), полученное Дж. Кендаллом в 1951 году, имеет единственное решение в области Res > 0, такое, что

В случае, если распределение времени обслуживания показательное, рассматриваемая система есть М|М|1 и преобразование Лапласа - Стилтьеса распределения времени обслуживания имеет вид: При этом функциональное уравнение (1.82) переходит в квадратное уравнение для неизвестного преобразования Лапласа - Стилтьеса

Решая уравнение (1.85), получаем:

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

где функция есть модифицированная функция Бесселя первого рода.

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

Кроме того, путем последовательного дифференцирования уравнения (1.82) с последующей подстановкой аргумента и учета свойства 5 преобразования Лапласа - Стилтьеса, можно получить рекуррентную последовательность формул для вычисления начальных моментов распределения длины периода занятости. Так, среднее значение длины периода занятости и второй начальный момент ее распределения определяются формулой:

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

Рассмотрим теперь другую характеристику функционирования системы M\G\1 - число запросов, обслуженных за период занятости. Обозначим

Утверждение 14. Производящая функция удовлетворяет следующему функциональному уравнению:

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

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

Так как поток запросов - простейший с параметром , а произвольный запрос является темно-красным с вероятностью , то поток нетемно-красных вызовов (как это следует из Утверждения 6) является простейшим с параметром Вспоминая вероятностную интерпретацию преобразования Лапласа - Стилтьеса, из приведенных рассуждений выводим следующую альтернативную формулу для вероятности события

Сравнивая формулы (1.90) и (1.91), убеждаемся в справедливости (1.89). Утверждение 14 доказано.

Уравнение (1.89) определяет единственную аналитическую в области функцию, такую, что

Следствие. Среднее число запросов, обслуженных в системе M\G\1 за один период занятости, задается формулой:

Приведем еще одно доказательство формулы Поллячека-Хинчина для производящей функции распределения вероятностей числа запросов в системе M\G\1 в моменты окончания обслуживания. Каждый из запросов, приходящих в систему, независимо от других назовем красным с вероятностью 2 и синим с дополнительной вероятностью. Введем событие А, состоящее в том что запрос, уходящий в данный момент окончания обслуживания из системы, сам красный и все запросы, остающиеся в системе в этот момент, тоже красные.

Из вероятностной интерпретации производящей функции очевидно следует, что:

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

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

Из этих рассуждений следует, что:

Из соотношений этого соотношения и (1.92) очевидным образом следует формула Поллячека - Хинчина:

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

В заключение подраздела найдем характеристики системы M\G\1 с дисциплиной LIFO.

Выше отмечалось, что распределение периода занятости системы M|G|1 не зависит от дисциплины обслуживания. Поэтому уравнение (1.82) определяет преобразование Лапласа - Стилтьеса распределения периода занятости для всех дисциплин. Кроме того, несложно видеть, что и распределения числа запросов в системе M\G\1 при дисциплинах FIFO и LIFO совпадают и задаются формулой (1.81).

Распределение времени ожидания запроса при дисциплинах FIFO и LIFO различно. При дисциплине FIFO преобразование Лапласа - Стилтьеса стационарного распределения времени ожидания задается формулой (1.52).

Утверждение 15. При дисциплине LIFO преобразование Лапласа - Стилтьеса имеет следующий вид:

где функция является решением уравнения (1.82).

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

Учитывая сущность дисциплины LIFO и рассуждения, использованные при доказательстве Утверждения 13, получаем формулу:

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

Министерство образования и науки Российской Федерации

Федеральное агентство по образованию

ГОУ ВПО «Уральский Государственный Технический Университет – УПИ»

Теория очередей. Закономерности образования очередей и способы предсказания среднего размера очереди.

По дисциплине: Теория информационных процессов и систем

Екатеринбург, 2007г.

ВВЕДЕНИЕ
1. КЛАССИЧЕСКАЯ ЗАДАЧА ЭРЛАНГА
1.1. Составление уравнений
1.2. Определение стационарного решения
1.3. Некоторые подготовительные результаты
1.4. Определение функции распределения длительности ожидания
1.5. Средняя длительность ожидания
2. ПОСТАНОВКА ЗАДАЧИ
2.1. Математическая модель
2.2. Решение поставленной задачи
2.3. Анализ результатов

СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ

Введение.

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

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

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

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

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

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

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

Это можно изобразить так:

https://pandia.ru/text/78/375/images/image001_340.jpg" width="61" height="19">Входящий поток Очередь

Обслуживающие устройства Выходящий поток

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

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

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

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

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

Простейший поток обладает такими важными свойствами:

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

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

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

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

1. Классическая задача Эрланга.

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

Длительность обслуживания представляет собой случайную величину с одним и тем же распределением вероятностей F(x) .

За x берем время (часы, минуты и т. д.).

Предполагается, что при x ³ 0

F(x) = 1 - e- m x

где m > 0 - постоянная.

Эрланг решил эту задачу, имея в виду постановки вопросов возникших к тому времени в телефонном деле.

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

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

Действительно, пусть fa(t) означает вероятность того, что обслуживание, которое уже продолжается время a , продлится еще не менее чем t . В предположении, что длительность обслуживания распределена показательно, f0(t)=e- m t .

f 0 (a )= e - m a и f 0 (a + t )= e - m (a +1) .

А так как всегда

f0(a+t) = f0(a) fa(t), то e- m (a+t) = e- m a f0(t)

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

fa(t) = e- m t = fo(t).

Требуемое доказано.

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

где, m > 0, а k - целое положительное число.

Распределение Эрланга представляет собой распределение суммы k независимых слагаемых, каждое из которых имеет распределение вероятностей F(x)

Обозначим для случая распределения вероятностей F(x) через h время обслуживания требования. Тогда средняя длительность обслуживания равна

Это равенство дает нам способ оценки параметра m по опытным данным. Как легко вычислить, дисперсия длительности обслуживания равна

1. Составление уравнений.

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

Найдём те уравнения, которым удовлетворяют вероятности Pk(t). Одно из уравнений очевидно, а именно для каждого t

Найдем сначала вероятность того, что в момент t+h все приборы свободны. Это может произойти следующими способами:

В момент t все приборы были свободны и за время h новых требований не поступало;

В момент t один прибор был занят обслуживанием требования, все остальные приборы свободны; за время h обслуживание требования было завершено и новых требований не поступило.

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

Вероятность первого из указанных событий равна

вероятность второго события

Таким образом,

Отсюда очевидным образом приходим к уравнению

Перейдем теперь к составлению уравнений для Pk(t) при k ³ 1. Рассмотрим отдельно два различных случая:

1) Пусть вначале 1 £ k < m . Перечислим только существенные состояния, из которых можно прийти в состояние Ek в момент t+h . Эти состояния таковы:

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

В момент t система находилась в состоянии Ek-1 , за время h поступило новое требование, но ни одно ранее находившееся требование не было закончено обслуживанием. Вероятность этого события равна

В момент t система находилась в состоянии Ek+1 , за время h новых требований не поступило, но одно требование было обслужено. Вероятность этого равна

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

Собрав воедино найденные вероятности, получаем следующее

равенство:

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

для 1 £ k < m:

2) Подобные же рассуждения для k ³ m приводят к уравнению

Для определения вероятностей Pk(t) мы получили бесконечную систему дифференциальных уравнений. Ее решение представляет несомненные технические трудности.

2. Определение стационарного решения.

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

Сказанное позволяет заключить, что уравнения

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

при 1 £ k < m

при k ³ m

К этим уравнениям добавляется нормирующее условие

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

при 1 £ k < m

при k ³ m

Система уравнений в этих обозначениях принимает такой вид:

z1 = 0, zk - zk+1 = 0 при k ³ 1

Отсюда заключается, что при всех k ³ 1 zk = 0

т. е. при 1 £ k < m

k m Pk = l Pk-1

и при k ³ m

m m Pk= l Pk-1

Введем для удобства записи обозначение

r = l / m .

Уравнение k m Pk = l Pk-1 позволяет заключить, что при 1 £ k < m

При k ³ m из уравнения m m Pk= l Pk-1 находим, что

и следовательно, при k ³ m

Остается найти P0. Для этого в подставляем выражения полученного Pk.

В результате

Так бесконечная сумма, стоящая в квадратных скобках, находится только при условии, что

r < m

то при этом положении находим равенство

Если условие r < m не выполнено, т. е. если r ³ m, то ряд, стоящий в квадратной скобке уравнения для определения P0 , расходится и, значит, P0 должно быть равно 0..gif" width="71" height="44 src=">при всех k ³ 1 оказывается Pk = 0.

Методы теории цепей Маркова позволяют заключить, что при r ³ m с течением времени очередь стремится к ¥ по вероятности.

3. Некоторые подготовительные результаты.

Для задачи с ожиданием основной характеристикой качества обслуживания является длительность ожидания требованием начала обслуживания. Длительность ожидания представляет собой случайную величину, которую обозначим буквой g . Рассмотрим сейчас только задачу определения распределения вероятностей длительности ожидания в уже установившемся процессе обслуживания. Обозначим далее через P { g > t } вероятность того, что длительность ожидания превзойдет t, и через Pk { g > t } вероятность неравенства, указанного в скобке, при условии, что в момент поступления требования, в очереди уже находится k требований. В силу формулы полной вероятности имеем равенство

P { g > t } = .

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

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

4. Определение функции распределения длительности ожидания.

Если в момент поступления требования в очереди уже находились k - m требований, то поскольку обслуживание происходит в порядке очередности, вновь поступившее требование должно ожидать, когда будут обслужены

k – m + 1 требований.

Пусть qs(t) означает вероятность того, что за промежуток времени длительности t после поступления интересующего нас требования закончилось обслуживание ровно S требований. Ясно, что k ³ m имеет место равенство

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

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

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

Но вероятности Pk известны:

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

Из формул и следует, что , поэтому при t>0

Само собой разумеется, что при t<0 .

Функция имеет в точке t = 0 разрыв непрерывности, равный вероятности застать все приборы занятыми.

5. Средняя длительность ожидания.

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

Несложные вычисления приводят к формуле

Дисперсия величины g равна

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

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

При т=1 в силу (20)

При р = 0,1; 0,3; 0,5; 0,9 значение приблизительно равно 0,011; 0,267; 0,500; 1,633; 8,100.

При m = 2 в силу (24)

При = 0,1; 1,0; 1,5; 1,9 значение приблизительно равно 00003; 0,333; 1,350; 17,537.

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

Постановка задачи.

На станции технического обслуживания (СТО) легковых автомобилей имеется 7 рабочих мест по обслуживанию клиентов. По статистическим данным в час поступает 2 заявки на обслуживания легковых автомобилей. Среднее время обслуживания 1 заявки составляет 3 часа 24 минуты.

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

Каждый мастер, в любой момент времени, может обслуживать не более одного клиента. Обслуженный клиент покидает СТО.

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

1. Математическая модель.

Имеем систему массового обслуживания, из n = 7 идентичных приборов, на которую поступает поток требований α = 2, интенсивностью β = 0,29411(1/ч).

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

вероятность DIV_ADBLOCK171">

где https://pandia.ru/text/78/375/images/image057_47.gif" width="231 height=25" height="25">

где https://pandia.ru/text/78/375/images/image059_45.gif" width="15 height=28" height="28">.gif" width="716 height=299" height="299">

Рис.1. Требование в системе.

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

Вероятность того, что в СМО за время Dt поступит одно требование:

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

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

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

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

Https://pandia.ru/text/78/375/images/image069_37.gif" width="381 height=48" height="48">;

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

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

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

Выделяют четыре основных типа очередей, схемы которых приведены на рис. 6.15.

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

Ожидание у кассы в продовольственном магазине - типичный пример многоканальной однофазовой очереди.

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

Рис. 6.15.

а - одноканальная; б - многоканальная однофазовая очередь; в - одноканальная многофазовая очередь; г - многоканальная многофазовая очередь

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

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

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

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

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

Администратор универсама должен обеспечить работу необходимого количества кассиров. Это количество определяется двумя факторами:

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

Задача администратора сводится к тому, чтобы минимизировать

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

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

Таблица 6.5

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