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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Возможны и другие признаки классификации СМО, например по дисциплине обслуживания, однофазные и многофазные СМО и др.

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

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

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

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

(8.43)

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

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

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

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

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

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

(8.44)

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

(8.45)

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

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

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

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

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

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

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

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

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

1. Введем в рассмотрение параметр α = l/m. Заметим, что если α/n < 1, то очередь не может расти безгранично. Это условие имеет следующий смысл: l - среднее число требований, поступающих за единицу времени, 1/m - среднее время обслуживания одним каналом одного требования, тогда α = l · 1/m - среднее число каналов, которое необходимо иметь, чтобы обслуживать в единицу времени все поступающие требования. Поэтому условие α/n < 1 означает, что число обслуживающих каналов должно быть больше среднего числа каналов, необходимых для того, чтобы за единицу времени обслужить все поступившие требования. Важнейшие характеристики работы СМО:

(8.46)

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

при (8.47)

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

при (8.48)

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

(8.49)

5. Среднее время ожидания требованием начала обслуживания в системе:

(8.50)

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

(8.51)

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

(8.52)

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

(8.53)

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

(8.54)

10. Коэффициент загрузки каналов:

(8.55)

Пример 8.6. Пусть филиал фирмы по ремонту радиоаппаратуры имеет п = 5 опытных мастеров. В среднем в течение рабочего дня от населения поступает в ремонт l = 10 радиоаппаратов. Общее число радиоаппаратов, находящихся в эксплуатации у населения, очень велико, и они независимо друг от друга в различное время выходят из строя. Поэтому есть все основания полагать, что поток заявок на ремонт аппаратуры является случайным, пуассоновским. В свою очередь каждый аппарат в зависимости от характера неисправности также требует различного случайного времени на ремонт. Время на проведение ремонта зависит во многом от серьезности полученного повреждения, квалификации мастера и множества других причин. Пусть статистика показала, что время ремонта подчиняется экспоненциальному закону; при этом в среднем в течение рабочего дня каждый из мастеров успевает отремонтировать m = 2,5 радиоаппарата. Требуется оценить работу филиала фирмы по ремонту радиоаппаратуры, рассчитав ряд основных характеристик данной СМО.

За единицу времени принимаем 1 рабочий день (7 часов).

1. Определим параметр:

так как α < п, то очередь не может расти безгранично.

2. Вероятность того, что все мастера свободны от ремонта аппаратуры, равна согласно (8.46):

3. Вероятность того, что все мастера заняты ремонтом, находим по (8.49):

Это означает, что 55,4% времени мастера полностью загружены работой.

4. Среднее время обслуживания (ремонта) одного аппарата согласно (8.45):

(при условии семичасового рабочего дня).

5. В среднем время ожидания каждого неисправного аппарата начала ремонта равно по (8.50):

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

аппарата.

7. Определим среднее число мастеров, свободных от работы, по (8.52):

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

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

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

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

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

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

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

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

(8.56)

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

(8.57)

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

откуда

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

(8.58)

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

или

(8.59)

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

(8.60)

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

(8.61)

или

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

(8.62)

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

(8.63)

Рассмотрим пример расчета характеристик замкнутой СМО.

Пример 8.7. Рабочий обслуживает группу автоматов, состоящую из 3 станков. Поток поступающих требований на обслуживание станков пуассоновский с параметром l = 2 ст./ч. Обслуживание одного станка занимает у рабочего в среднем 12 мин, а время обслуживания подчинено экспоненциальному закону. Тогда 1/m = 0,2 ч/ст., т.е. m = 5 ст./ч, а α = l/m = 0,4.

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

Система может находиться в четырех различных состояниях: 1) все станки работают; 2) один стоит и обслуживается рабочим, а два работают; 3) два стоят, один обслуживается, один ждет обслуживания; 4) три стоят, из них один обслуживается, а два ждут очереди.

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

Сведем вычисления в табл. 8.2.

Таблица 8.2

k	k - п	Р_k/Р₀	Р_k	(k -п) Р_k	kР_k
1	2	3	4	5	6
0	0	1.0000	0,2822	0	0
1	0	1.2000	0,3386	0	0,3386
2	1	0,9600	0,2709	0,2709	0,5418
3	2	0,3840	0,1083	0,2166	0,3249
	2	3,5440	1,0000	0,4875	1,2053

В этой таблице первой вычисляется третья графа, т.е. отношения P_k/P₀ при k = 0, 1, 2, 3. Затем, суммируя величины по графе и учитывая, что , получаем

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

(так как п = 1).

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

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

т.е. в среднем 1,2 станка не будет выдавать продукцию. Коэффициент простоя станка равен К_пр.об = М_оч/3 = 0,1625, т.е. каждый станок простаивает примерно 0,16 своего рабочего времени в ожидании, пока рабочий освободится.

Коэффициент простоя рабочего в данном случае совпадает с Р₀, так как п = 1, поэтому .