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

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

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

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

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

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

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

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

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

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

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

1) ординарностью,

2) стационарностью и

3) отсутствием после­действия.

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

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

Отсутствие последействия означает, что число требований, по­ступивших в систему до момента t, не определяет того, сколько требований поступит в систему за промежуток времени от t до t + Dt

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

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

т.е. вероятность того, что время обслуживания не превзойдет неко­торой величины t, определяется формулой (5.2), где µ — параметр экспоненциального закона распределения времени обслуживания требований в системе, т.е. величина, обратная среднему времени обслуживания

Системы массового обслуживания классифицируются:

1. В зависимости от условий ожидания начала обслуживания:

· СМО с потерями (отказами)

· СМО с ожиданием

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

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

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

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

2. По числу каналов обслуживания СМО делятся на:

• одноканальные;

• многоканальные.

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

• разомкнутые, когда источник требования находится вне сис­темы;

замкнутые, когда источник находится в самой системе.

19.7. Задачи анализа замкнутых и разомкнутых систем массового обслуживания

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

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

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

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

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

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

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

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

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

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

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

(5.14)

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

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

(5.16)

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

(5.17)

5. Вероятность отказа

(5.18)

6. Средняя длина очереди

7. Среднее число свободных от обслуживания каналов

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

Требуется определить характеристики работы фирмы.

Решение. Данная система относится к типу СМО с ожида­нием и ограниченной длиной очереди. Найдем параметры системы, приняв за единицу времени один час:

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

Вероятность того, что в се машины заняты, определяется по формуле (5.17) и составляет

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

, а средняя длина очереди в соответствии с формулой (5.19) составит

Тогда вероятность отказа в принятии заказа на перевозку, рас­считываемая по формуле (5.18), будет равна

а средняя длина очереди в соответствии с формулой (5.19) составит

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

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

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

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

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

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

1. Параметр α=α/µ. - показатель загрузки системы, т.е. мате­матическое ожидание числа требований, поступающих в систему за время, равное средней длительности обслуживания

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

(5.21)

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

(5.22)

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

Величину Р₀можно получить также путем подстановки в равенство значений Р₁ P_2, .--, Р_т, в которые P_овходитсомножителем. Подставляя их, получаем следующее уравнение для опреде­ления Р₀

откуда

(5.23)

5. Среднее число требований, ожидающих начала обслуживания (средняя длина очереди),

или

(5.24)

6. Коэффициент простоя в очереди обслуживаемого требования (объекта)

(5.25)

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

или

(5.26)

8. Среднее число свободных обслуживающих каналов

(5.27)

9. Коэффициент простоя обслуживающего канала

(5.28)

Рассмотрим примеры расчетов характеристик замкнутых СМО в задаче организации труда.

Пример 3.Рабочий обслуживает группу автоматов, состоя­щую из трех станков. Поток поступающих требований на обслужи­вание станков пуассоновский с параметром λ = 2 ст./ч. Обслужива­ние одного станка занимает у рабочего в среднем 12 минут, а время обслуживания подчинено экспоненциальному закону.

Тогда 1/µ = = 0,2 ч/ст., т.е.µ = 5 ст./ч, а α = λ/µ = 0,4.

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

Решение. Обслуживающим каналом здесь является рабо­чий. Так как станки обслуживает один рабочий, то п = 1. Общее число требований не может превзойти числа станков, т.е. т = 3.

Система может находиться в четырех различных состоя­ниях:

1) все станки работают;

2) один станок простаивает и обслуживается рабочим, а два ра­ботают;

3) два станка простаивают, один обслуживается, один ждет об­служивания;

4) три станка простаивают, из них один обслуживается, а два ждут очереди.

Для ответа на поставленные вопросы можно воспользоваться формулами

(5.21) и (5.22):

В табл. 5.1 первой вычисляется третья графа, т.е. отношения Рк/Ро

при к = 0, 1, 2, 3. Затем, суммируя величины по графе и учитывая, что

получаем :

откуда P₀=0,2822.

Умножая величины третьей графы на Р₀, полу­чаем четвертую графу. Величина Р_о = 0,2822, равная вероятности того, что все автоматы работают, может быть истолкована как веро­ятность того, что рабочий будет свободен. Получается, что в рас­сматриваемом случае рабочий будет свободен более 1/4 всего рабо­чего времени. Однако это не означает, что «очередь» станков, ожи­дающих обслуживания, всегда будет отсутствовать. Математическое ожидание числа автоматов, стоящих в очереди,

, т.к. n=1

Суммируя пятую графу получим математическое ожидание =0,4875 . Следовательно , в среднем 0,49 станкова будет простаивать в ожидании , пока освободится рабочий.

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

т.е. в среднем 1,2 станка не будут выдавать продукцию. Коэффици­ент простоя станка

т.е. каждый станок простаивает примерно 0,16 часть рабочего вре­мени в ожидании, пока рабочий освободится. Коэффициент простоя рабочего в данном случае совпадает с Р_о, так как n = 1, поэтому