Системы массового обслуживания

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

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

Первые задачи теории массового обслуживания были рассмотрены датским ученым, сотрудником Копенгагенской телефонной компании, А.К.Эрлангом в период между 1908 и 1922 гг. Эти задачи возникли в процессе разработки методов, позволяющих повысить эффективность работы телефонной сети. Оказалось, что ситуации, возникающие на телефонных станциях, являются типичными не только для телефонной связи [24].

Значительный вклад в разработку общей теории массового обслуживания внес выдающийся советский математик А.Я.Хинчин. Им предложен термин «теория массового обслуживания». Чаще в зарубежной литературе используется название «теория очередей» [8].

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

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

Рис. 6.2.1. Структура СМО.

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

· входящий поток заявок,

· очередь,

· поток необслуженных (покинувших очередь) заявок,

· каналы обслуживания,

· выходящий поток обслуженных заявок.

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

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

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

Переходы СМО из одного состояния в другое происходят под воздействием вполне определенных событий — поступления заявок и их обслуживания.

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

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

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

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

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

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

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

Для простейшего потока частота поступления требований в систему подчиняется закону Пуассона, то есть вероятность поступления за время t ровно k требований задается формулой:

. (6.2.1)

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

, (6.2.2)

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

. (6.2.3)

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

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

· среднее количество требований, которые может обслужить СМО в единицу времени;

· вероятность того, что все каналы свободны или заняты;

· вероятность отказа в обслуживании поступившей заявке;

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

· среднее время ожидания в очереди;

· коэффициенты занятости и простоя каналов обслуживания и др.

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

Таблица 6.2.1

Классификация моделей СМО

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

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

3. В зависимости от возможности образования очереди СМО подразделяются на два основных типа: СМО с отказами обслу­живания и СМО с ожиданием (очередью) обслуживания.

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

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

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

4. По месту нахождения источника требований СМО делятся на разомкнутые и замкнутые.

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

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

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

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