Глава 4. Элементы системы массового обслуживания (смо)

 

Формулировка задачи и характеристики СМО

 

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

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

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

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

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

СМО можно разбить на две группы:

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

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

Дисциплина очереди. Это описательная характеристика. Требование, поступившее в систему обслуживается в порядке очереди – дисциплина очереди: «первым пришел – первым обслужен». Другая дисциплина очереди: «последним пришел – первым обслужен»- это обслуживание по приоритету. Наконец, обслуживание требований может быть случайным.

Механизм обслуживания. Характеризуется продолжительностью и характером процедур обслуживания. Обслуживание может осуществляться по принципу: «на одно требование – один обслуживающий прибор». Если в системе несколько приборов, то параллельно могут обслуживаться несколько требований. Часто используют групповое обслуживание, то есть требование обслуживается одновременно несколькими приборами. В некоторых случаях требование обслуживается последовательно несколькими приборами – это многофазовое обслуживание.

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

 

Рис. 4.1

Функционирование СМО представляется в виде связного графа ее состояний С_i, . Переход системы из состояния С_i в состояние С_j графически осуществляется по направленным отрезкам с заданными интенсивностями переходов . Если переход невозможен, то .

В стационарном (установившемся) режиме действует принцип равновесия: сумма «входов» в любое состояние равна сумме «выходов» из него. Это позволяет записать уравнения равновесия по каждому из состояний (принцип декомпозиции).

Рис. 4.2

 

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

 

4.2. Входящий поток требований

 

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

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

Рис. 4.3

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

Наиболее изучены потоки, которые обладают следующими свойствами:

а) стационарности – все его вероятностные характеристики не меняются со временем;

б) отсутствия последействия – для любых непересекающихся временных интервалов на временной оси, число событий находящихся на одном интервале, не зависит от того, сколько их и как они оказались на другом интервале;

в) ординарности – практическая невозможность на достаточно малом временном интервале появиться двум и более событиям.

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

а) выбрать интервал времени, в течение которого поток требований практически стационарный;

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

в) построить гистограмму и найти эмпирическую функцию распределения;

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

д) используя критерий (Пирсона) и/или Колмогорова сделать вывод о соответствии или несоответствии выдвинутой гипотезы данной выборке;

е) в случае отрицательного результата либо проверяется репрезентативность выборки, или отвергается гипотеза.

 

1. Пуассоновский поток

В подавляющем большинстве работ по ТМО рассматривается пуассоновский поток требований

, ,

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

Основание:

а) количественная оценка качества функционирования СМО выражается в простых, относительно других видов потоков, аналитических зависимостях;

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

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

 

2. Рекуррентный поток

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

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

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

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

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

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

 

3. Потоки Эрланга

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

,

называется потоком Эрланга порядка k, .

В частности, поток Эрланга 1-го порядка является простейшим потоком, то есть,

.

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

.

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

Рис. 4.4

С помощью потоков Эрланга можно моделировать потоки Пальма с различным последействием.

В самом деле, при получаем простейший поток (у него нет последействия). При увеличении k (до 10¸20) получаем поток Пальма с интервалами между поступлениями требований (как показывают многочисленные эксперименты) распределенными практически нормально. При получаем регулярный (не случайный) поток.

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

 

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

 

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

.

В практических приложениях наиболее распространен экспоненциальный закон обслуживания требований

,

где интенсивность .

Время обслуживания требования числено равно математическому ожиданию времени обслуживания.

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

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

,

где .

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

,

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

Это свойство справедливо только для экспоненциального распределения.

Более общим, является эрланговская функция распределения времени обслуживания , ,

Для стационарного режима функционирования СМО с отказами справедливы формулы Эрланга для любых функций распределения времени обслуживания требований.

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

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

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

 

Показатели эффективности

 

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

При анализе функционирования и определении оптимального варианта в качестве параметров используются:

n – число приборов (обслуживающих устройств);

a - интенсивность входящего потока;

b - интенсивность обслуживания требований;

l - интенсивность отказов обслуживающего устройства;

m - интенсивность восстановления отказавшего устройства;

m – число восстанавливающих устройств в системе и др.

 

1. Показатели эффективности, дающие количественную оценку СМО:

- вероятность того, что в системе нет требований;

- вероятность того, что в системе обслуживанием занято k из n приборов;

Õ - вероятность того, что в системе все приборы заняты обслуживанием;

- среднее время, в течение которого любое требование, находящееся в очереди, ждет начала обслуживания;

A - средняя длина очереди;

B - среднее число обслуживаемых требований;

À₀ – среднее число свободных приборов;

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

R - среднее число требований в системе;

- вероятность очереди;

- вероятность «потери» требования;

- среднее время пребывания требования в системе, где t_ср – среднее время обслуживания требования одним прибором;

- коэффициент простоя приборов;

- коэффициент загрузки системы.

 

2. Экономические показатели:

- стоимость обслуживания каждого требования в системе в единицу времени;

- стоимость потерь, связанных с простаиванием требований в очереди в единицу времени;

- стоимость потерь, связанных с уходом требования из системы, в единицу времени;

- стоимость эксплуатации каждого обслуживающего устройства в единицу времени;

- стоимость простоя обслуживающего устройства в единицу времени.

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

Можно использовать функцию потерь за определенный временной промежуток T (например, месяц):

а) для систем с ожиданием

,

где A – средняя длина очереди, - среднее число свободных приборов, - среднее число занятых приборов;

б) для систем с отказами (ограничения на длину очереди)

;

в) для смешанных систем

.

Можно применить показатель экономической эффективности системы

,

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

 

Примеры моделей СМО