где i - номер i-го требования в начальной очереди; требования поступают в моменты времени a, 2a, ...; b = na (n = 1, 2, ...).

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

Рис. 3.1. Схема СМО.

Поступающие на вход СМО однородные заявки в зависимости от порождающей причины делятся на типы, интенсивность потока заявок типа i (i=1…M) обозначено  i . Совокупность заявок всех типов - входящий поток СМО.

Обслуживание заявок выполняется m каналами. Различают универсальные и специализированные каналы обслуживания. Для универсального канала типа j считается известными функции распределения F ji () длительности обслуживания заявок произвольного типа. Для специализированных каналов функции распределения длительности обслуживания каналов заявок некоторых типов являются неопределёнными, назначение этих заявок на данный канал.

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

Q - схемы можно исследовать аналитически и имитационными моделями. Последнее обеспечивает большую универсальность.

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

В любом элементарном акте обслуживания можно выделить две основные составляющие: ожидание обслуживания заявкой и собственно обслуживание заявки. Это можно отобразить в виде некоторого i-ого прибора обслуживания П i , состоящего из накопителя заявок, в котором может находится одновременно l i =0…L i H заявок, где L i H - ёмкость i-ого накопителя, и канала обслуживания заявок, k i .

Рис. 3.2. Схема прибора СМО

На каждый элемент прибора обслуживания П i поступают потоки событий: в накопитель H i поток заявок w i , на канал k i - поток обслуживания u i .

Потоком событий (ПС) называется последовательность событий, происходящих одно за другим в какие-то случайные моменты времени. Различают потоки однородных и неоднородных событий. Однородный ПС характеризуется только моментами поступления этих событий (вызывающими моментами) и задаётся последовательностью {t n }={0t 1 t 2 …t n …}, где t n - момент поступления n- ого события - неотрицательное вещественное число. ОПС может быть также задан в виде последовательности промежутков времени между n-ым и n-1-ым событиями { n }.

Неоднородным ПС называется последовательность {t n , f n } , где t n - вызывающие моменты; f n - набор признаков события. Например, может быть задана принадлежность к тому или иному источнику заявок, наличие приоритета, возможность обслуживания тем или иным типом канала и т.п.

Рассмотрим ОПС, для которого  i { n }- случайные величины, независимые между собой. Тогда ПС называется потоком с ограниченным последействием.

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

Если для любого интервала t событие P 0 (t, t) + P 1 (t, t) + Р  1 (t, t)=1, P 1 (t, t) - вероятность попадания на интервал t ровно одного события. Как сумма вероятностей событий, образующих полную группу и несовместных, то для ординарного потока событий P 0 (t, t) + P 1 (t, t)  1, Р  1 (t, t)=(t), где (t)- величина, порядок малости который выше, чем t, т.е. lim((t))=0 при t0.

Стационарным ПС называется поток, для которого вероятность появления того или иного числа событий на интервале времени  зависит от длины этого участка и не зависит от того, где на оси времени 0 - t взят этот участок. Для ОПС справедливо 0*P 0 (t, t) + 1*P 1 (t, t)= P 1 (t, t) - среднее число событий на интервале t. Среднее число событий, наступающих на участке t в единицу времени составляет P 1 (t, t)/t. Рассмотрим предел этого выражения при t0

lim P 1 (t, t)/t=(t)*(1/един.вр.).

Если этот предел существует, то он называется интенсивностью (плотностью) ОПС. Для стандартного ПС (t)==const.

Применительно к элементарному каналу обслуживания k i можно считать что поток заявок w i W, т.е. интервалы времени между моментами появления заявок на входе k i образуют подмножество неуправляемых переменных, а поток обслуживания u i U, т.е. интервалы времени между началом и окончанием обслуживания заявки образуют подмножество управляемых переменных.

Заявки, обслуженные каналом k i и заявки, покинувшие прибор П i по различным причинам не обслуженными, образуют выходной поток y i Y.

Процесс функционирования прибора обслуживания П i можно представить как процесс изменения состояний его элементов во времени Z i (t). Переход в новое состояние для П i означает изменение кол-ва заявок, которые в нём находятся (в канале k i и накопителе H i). Т.о. вектор состояний для П i имеет вид: , где- состояния накопителя, (=0 - накопитель пуст,=1- в накопителе одна заявка…,=- накопитель занят полностью;- состояние каналаk i (=0 - канал свободен,=1 канал занят).

Q-схемы реальных объектов образуются композицией многих элементарных приборов обслуживания П i . Если k i различных приборов обслуживания соединены параллельно, то имеет место многоканальное обслуживание (многоканальная Q-схема), а если приборы П i и их параллельные композиции соединены последовательно, то имеет место многофазное обслуживание (многофазная Q-схема).

Т.о. для задания Q-схемы необходимо оператор сопряжения R, отражающий взаимосвязь элементов структуры.

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

Собственными (внутренними) параметрами Q-схемы будут являться кол-во фаз L Ф, количество каналов в каждой фазе, L kj , j=1… L Ф, количество накопителей каждой фазы L kj , k=1… L Ф, ёмкость i-ого накопителя L i H . Следует отметить, что в теории массового обслуживания в зависимости от ёмкости накопителя применяют следующую терминологию:

системы с потерями (L i H =0, накопитель отсутствует);

системы с ожиданием (L i H );

системы с ограниченной ёмкостью накопителя Н i (смешанные).

Обозначим всю совокупность собственных параметров Q-схемы как подмножество Н.

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

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

В зависимости от динамики приоритетов Q-схемы различают статические и динамические. Статические приоритеты назначаются заранее и не зависят от состояний Q-схемы, т.е. они являются фиксированными в пределах решения конкретной задачи моделирования. Динамические приоритеты возникают при моделировании. Исходя из правил выбора заявок из накопитель Н i на обслуживание каналом k i можно выделить относительные и абсолютные приоритеты. Относительный приоритет означает, что заявка с более высоким приоритетом, поступившая в накопитель Н, ожидает окончания обслуживания представляющей заявки каналом k i и только после этого занимает канал. Абсолютный приоритет означает, что заявка с более высоким приоритетом, поступившая в накопитель, прерывает обслуживание каналом k i заявки с более низким приоритетом и сами занимает канал (при этом вытесненная из k i заявка может либо покинуть систему, либо может быть снова записана на какое-то место в Н i).

Необходимо также знать набор правил, по которым заявки покидают Н i и k i: для Н i – либо правила переполнения, либо правила ухода, связанные с истечением времени ожидания заявки в Н i ­ ; для k i – правила выбора маршрутов или направлений ухода. Кроме того, для заявок необходимо задать правила, по которым они остаются в канале k i , т.е. правила блокировок канала. При этом различают блокировки k i по выходу и по входу. Такие блокировки отражают наличие управляющих связей в Q‑схеме, регулирующих поток заявок в зависимости от состояний Q‑схемы. Набор возможных алгоритмов поведения заявок в Q‑схеме можно представить в виде некоторого оператора алгоритмов поведения заявок А.

Т.о. Q‑схема, описывающая процесс функционирования СМО любой сложности однозначно задаётся в виде набора множеств: Q = .

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

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

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

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

Рис. 8.6.

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

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

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

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

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

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

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

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

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

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

где Хх = а - математическое ожидание количества событий на участке т; X - параметр, характеризующий плотность потока (к > 0);

Рщ СО - вероятность того, что за время X произойдет т событий.

В частности, при т = 0

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

т. е. вероятность того, что за время т произойдет хотя бы одно событие.

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

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

t o6 - среднее время обслуживания требования.

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

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

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

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

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

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

Кратко рассмотрим подход к решению одной из классических задач теории массового обслуживания. Пусть имеется п станков и бригада из т человек, обслуживающая эти станки. Станок, работающий в момент времени t, отказывает к моменту t + т с вероятностью Р(т) = - 1 - е~ кх, где е~ кХ есть вероятность того, что за время t не произойдет ни одного отказа. Время ремонта станка - случайная величина г). Для такой системы можно вычислить среднее число простаивающих рабочих. Эта характеристика используется в дальнейшем для оптимального выбора соотношения между пит исходя из экономических критериев.

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

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

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

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

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

где А - плотность потока заявок;

п - число аппаратов (линий, приборов и т. д.); т - параметр обслуживания.

Чаще всего в формулах используется параметр а = А/p, тогда предыдущую формулу запишем так:

Частными случаями этой формулы будут:

Вероятность того, что все обслуживающие аппараты свободны:

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

На практике необходимо часто определять:

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

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

Среднее число аппаратов, свободных от обслуживания:

Коэффициент простоя аппаратов:

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

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

Рассмотрим несколько примеров.

Пример 1. Необходимо оценить работу автоматизированной телефонной станции (АТС), которая имеет п = 5 линий связи. К услугам станции обращаются абоненты с требованиями на ведение разговоров. Естественно, что моменты поступления требований на станцию случайны и независимы друг от друга.

Задачу решим на примере простейшего потока требований. Пусть средняя плотность потока вызовов в единицу времени X = 2. Продолжительность каждого разговора - также величина случайная. Можно принять, что продолжительность разговоров различных абонентов подчинена показательному закону распределения. Пусть среднее время, необходимое для ведения каждого разговора, равно t o6 = 1 ед. времени. Может возникнуть сомнение в правомочности принятия показательного закона распределения времени ведения разговоров абонентов. Но, как уже говорилось выше, формулами Эрланга можно пользоваться при любых законах распределения времени разговоров абонентов.

В итоге в предлагаемом примере необходимо оценить функционирование АТС.

Решение

Находим параметр

Вероятность того, что все линии будут свободны при работе АТС, может быть определена по формуле (8.24):

Вероятность того, что абоненту будет отказано в обслуживании, рассчитывается по формуле (8.25):

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

Для проведения необходимых расчетов составим таблицу 8.3.

Таблица для расчета параметров задачи

По результатам расчетов получено:

Коэффициент простоя линий равен:

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

Пример 2. Необходимо спроектировать АТС с пропускной способностью, при которой вероятность получения абонентом отказа в обслуживании не превосходила Р п X = 0,5 вызова в минуту. Считается, что средняя продолжительность разговора равна f o6 -2 мин. Определить необходимое число линий связи.

Значит, коэффициент загрузки линий связи равен:

Среднее число свободных линий связи равно:

Решение

Определяем параметр

Для составления расчетной таблицы воспользуемся таблицей 4 приложения 5 к работе .

Таблица 8.4

Определение вероятностей

Из данных таблицы 8.4 следует, что АТС нужно проектировать на 5 линий связи. При этом будет обеспечена связь одного абонента с другими с вероятностью Р = 0,997.

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

• Вывод приводимых ниже формул можно найти в работе .