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

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

4.3.1. Краткая характеристика систем массового обслуживания

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

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

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

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

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

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

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

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

Очередь образуется в следующих случаях.

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

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

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

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

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

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

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

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

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

4.3.2. Основные элементы систем массового обслуживания

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

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

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

В теории вероятности доказано, что если входящий поток отвечает распределению Пуассона, то вероятность Pn(t) того, что за промежуток времени от 0 до t в систему поступит n требований, равна:

п(t) и!

Математическое ожидание числа требований x(t), поступающих в систему за время t, определяется по формуле

M [x(t )]_ Xt.

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

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

р (Л_ [це"ц, если t > 0,

P°6(t) In

[0, если t < 0.

Среднее время обслуживания при достаточно большом количестве обслуживаний определяется по формуле

t06_n tP (t )dt _ I.

o ц

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

P ^об > t) = Є-Ц.

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

P (tоб > t) = 1Є-*.

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

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

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

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

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

4.3.3. Анализ системы массового обслуживания экспедиции колбасного завода

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

Данные проведенного хронометража прибытия автомашин на колбасный завод в интервале 10 мин представлены в табл. 4.13.

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

Прибытие одной автомашины не зависит от прибытия другой (независимость прибытий).

Никогда не приходят одновременно две автомашины или более.

Среднее количество прибытий не изменяется во времени.

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

n!

где Pn(t) — вероятность, что за время t произойдет n прибытий; e — основание натуральных логарифмов;

X — среднее количество прибытий за выбранную единицу времени.

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

= 15\%;

Частота прибытий равна:

15х100

для 1-й автомашины:

100

2 й 23х100

для 2-й автомашины: —Ю0— = 23\%

и т.д.

Частота прибытия для 1, 2, 3, 4, 5, 6-й автомашин представлена в табл. 4.13.

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

N = 1 х 15 + 2 х 23 + 3 х 27 + 4 х 20 + 5 х 11 + 6 х 4 = 301.

Среднее число прибытий за 1 мин:

АN -—301— -0,301 = 0,3авт./мин t 100 х 10 .

Подставляя в формулу значения n = 1, 2, ., 6, получим:

P1(t) - 0,147,

Pi(t) - Є-32х9 0,22,

P3(t) - —r^ 0,22

e"3 х33 e"S<27 3! 6

и т.д.

Вычисленные теоретические частоты прибытий автомашин для n = 1, 2, 3, 4, 5, 6 показаны в табл. 4.13 (чтобы получить результаты вычислений в процентах, умножаем вычисленные теоретические частоты на 100).

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

2 (15-14,7)2 (23-22)2 (27 -22)2

X2 - — + — + — +

А 14,7 22 22

(20-16,5)2 (11-10)2 (4 5)2

+ — + — + — 16,5 10 5

= 0,006 + 0,04 + 1,1 + 0,7 + 0,1 + 0,2 = 2,146.

С помощью таблиц значений выраженных через вероятности гипотезы и число наблюдений, можно определить вероятность правильности гипотезы. Например, для значений X2 = 2,343, n = 5 вероятность правильности гипотезы равна 0,8, а для 5С2 = 1,610, n = 5 вероятность правильности гипотезы равна 0,9. Следовательно, можно сделать вывод, что гипотеза вполне приемлема.

Из приведенного хронометража продолжительности обслуживания одной машины зафиксировано, что из 1000 наблюдений с интервалом обслуживания 0—20 мин имели место 445 случаев; с интервалом 20—25 мин — 80 случаев и т.д. Результаты наблюдений представлены в табл. 4.14.

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

_ k

i=1

где ai — значение чисел 1-й строки;

pi — получается делением значений 2-й строки табл. 4.14 на 1000;

Tf = 20 х 0,445 + 25 х 0,08 + 30 х 0,075 +...+ 100 х 0,005 = = 32,39 32 мин.

Можно построить гистограмму, используя экспериментальные данные 2-й строки табл. 4.14. Верхние точки гистограммы при их соединении образуют гиперболу, которая характеризует закон обслуживания. Насколько он близок к теоретическому, можно точно проверить, используя распределение X2.

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

рr {x >9} = 1000 e-19, (4.6)

где рr {x >9} вероятность того, что интервал x больше или равен данному значению 9; ц — среднее число обслуживаний за единицу времени; 9 — измеряется в минутах.

В нашем случае ц = — = 0,031, и формула (4.6) приобретает следующий вид:

pr {x >9}=1000e -0,0319, (4.7)

Подсчитаем теоретические вероятности согласно формуле (4.7), если 0 = 0: pr{x > 0} = 1000,

0 = 20: pr{x > 20} = 1000 e-0,031 х 20 = 548,

0 = 25: pr{x > 25} = 1000 e-0,031 х 25 = 472

и т.д.

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

2 = (445 452)2 + (80 76)2 + (75 66)2 +

452 76 66

(5 7)2 49 16 81 49 4 9 1 36 9

... + - — = + ^ + + — + — + — + ^ + — + — +

7 452 76 66 57 48 42 36 31 27

9259169 1 4 + — + 25 + — +16 + — + — + 4 = 0,1084 + 0,2105 +1,2272 + 23 20 17 14 13 11 7

+ 0,8596 + 0,0833 + 0,2142 + 0,0277 + 1,1612 + 0,3333 + 0,3913 + + 1,2500 + 0,5294 + 1,1428 + 0,6923 + 0,0909 + 0,5714 = 8,8935.

По таблицам математической статистики вероятность выбранной нами гипотезы равна 0,9.

Введем важную величину — среднее число обслуживаний одним кладовщиком (одним каналом обслуживания). Если мы имеем S кладовщиков, работающих с одинаковой производительностью, то уровень обслуживания системы равен |iS.

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

X < nS,

откуда

— <1.

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

X

Средняя длина очереди и средняя продолжительность ожидания каждой машины являются функциями у:

0,3 = <9Д6

¥ 0,31 SS

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

1

0 SSy8 л Sy S2y2 SS-V-1

S !(1 -у) 1! 2! "' (S -1)! Среднее время ожидания в очереди:

f Ц S!(1 у) 0' 9,6

при S = 10: у = 40 = 0,96,

P0 = 1 2 r = 0,0000188,

0 9,6 +. 9,6 + 9,62_ + + 9,6^

10!(1 0,96) +1 + 1 + 2! +... + 9!

19,610

7, = — 9,6 — P0 = 27,54 мин.

f 0,031 10!(1 0,96) 0

В связи с тем что у должно быть меньше единицы (у > 1), S должно быть больше 10 (S > 10).

При S = 11: у = у!6 = 0,87,

P0 = 1 2 йг = 0,000046,

0 9,6 , 9,6 9,62 9,610

11!(1 -0,87)1 2! 10!

9,6і

0,031 11! (1 0,87)

P0 =18,1 мин.

Для S < 9 |/ > 1 и, следовательно, среднее время ожидания в очереди бесконечно.

12

Для S = 12: P =

9,6

12! (1 0,8)

у = ^—= 0,8, т 12

1

9,6 9,62 9,6 +1 +1"+... + ТІ!

0,0000576,

12

1

9,6

0,031 12!(1 0,8)

P0.

Проведя вычисления, получаем t/ =11,78 мин. Сведем в таблицу полученные данные:

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

X х 60 х 8 = 0,3 х 60 х 8 = 144.

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

1441 = 144 х 32 = 4608 мин = 76,8 ч.

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

Для S = 10:

S = 11:

S = 12:

х 8 76,8 = 3,3 ч,

х 8 76,8 = 11,2 ч,

х 8 76,8 = 19,2 ч.

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

При S = 10:

S = 11:

S = 12:

144 х 27,54 = 3965,5 мин = 66,1 ч, 144 х 18,1 = 2606,4 мин = 43,4 ч, 144 х 11,78 = 1696,3 мин = 28,2 ч.

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

Общие потери в рабочий день от простоя каналов обслуживания и машин составят:

при S = 10:

S = 11:

S = 12:

3,2 х 2000 + 66,1 х 1000 = 72 500 руб., 11,2 х 2000 + 43,4 х 1000 = 65 800 руб., 19,2 х 2000 + 28,2 х 1000 = 66 600 руб.

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