Работа 3. Исследование моделей системы

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

1. Элементы и логическая схема

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

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

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

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

Рис. 3.1. Логическая схема многоканальной СМО

   и ее элементы.

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

Простейший поток заявок подчиняется закону распределения Пуассона, т. е. число поступивших заявок N(T) за фиксированный промежуток времени [0,T] является случайной величиной, которая принимает целочисленные значения 0, 1, 2, ... , k, …, с вероятностями

k = 0, 1, 2, ... (1)

где через P_k обозначена вероятность поступления ровно k заявок, т. е.

k = 0, 1, 2, …, (2)

Согласно формуле (1), P_o = e^-λT есть вероятность отсутствия заявок, P₁ = (λT)e^-λT - вероятность поступления одной заявки и т. д. Величина  характеризует интенсивность (или плотность) ординарного потока заявок (число поступивших заявок за единицу времени). Важной характеристикой простейшего потока является закон распределения промежутков времени между моментами поступления заявок. Пусть {t_j}, j = 1, 2, …, – последовательность моментов поступления заявок, а {τ_j}, τ_j = t_j - t_j-1, j = 1, 2, …, t₀ = 0, – последовательность промежутков времени между этими моментами. Оказывается, что величины τ_j, j = 1, 2, …, являются независимыми случайными величинами, распределенными по экспоненциальному закону

(3)

при этом функция вероятности равна F(τ) = 1 - P₀ при T = τ.

2. Аналитические модели и

характеристики СМО

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

, (4)

процесс функционирования одноканальной СМО можно описать с помощью функции вероятности P_n(t) - вероятности того, что в произвольный момент времени t > 0 в системе имеется ровно n заявок, n = 0, 1,...

В предположении, что в момент времени t = 0 в системе заявок нет, следовательно, P₀(0) = 1, для функции P_n(t) получаются дифференциальные уравнения [1, 9]

(5)

Установившееся решение можно получить из этой системы, полагая в ней = 0 при t → ∞ и ρ = λ/μ < 1. Это решение получается в виде

(6)

Выражение (6) позволяет оценить ряд важных характеристик работы одноканальной СМО, а именно:

• среднее число заявок в системе

; (7)

- средняя длина очереди (среднее число заявок в накопителе)

(8)

• среднее время обслуживания каждой заявки

Т_об = 1/μ; (9)

• среднее время пребывания заявки в системе

Т_пр = 1/(μ - λ). (10)

Основанием для формулы (10) служит тот факт, что время пребывания заявок в системе подчиняется закону распределения

f(t_пр) = (μ - λ)e^{-(μ - λ)tпр}; (11)

• среднее время ожидания заявок в очереди

Т_ож = Т_пр - Т_об = 1/( μ - λ) - 1/ μ = ρ/μ(1 - ρ) ; (12)

• коэффициент загрузки прибора (или канала)

К_з = λ/μ. (13)

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

, (14)

где – выборочная оценка величины μ, P₀ – доверительная вероятность, ε – точность оценивания. Эмпирическая оценка находится по формуле

(15)

а эмпирическая дисперсия оцениваемой величины определяется по формуле

. (16)

В этих формулах x_i – реализации случайной величины, N – количество реализаций (объем выборки).

Из теории статистических выводов известно [6], что когда распределение стандартизованной переменной далеко от нормального распределения, при построении доверительного интервала используется t – распределение Стьюдента, а (1 - α) 100% доверительный интервал для среднего значения выборки определяется с помощью формулы

, (17)

т. е. считается, что с доверительной вероятностью P₀ = 1 - α выполняется неравенство

, (18)

где – стандартизованная t - статистика (точнее, квантиль распределения) для υ = N - 1 степеней свободы, выше которой лежит (α/2)100% площади t – распределения. Таким образом, доверительный интервал составляет

. (19)

Считается, что при N ≥ 30 t – распределение тождественно нормальному закону распределения, поэтому в формулах (17) – (19) можно, вместо величины , использовать значения U_α для стандартизованного нормального распределения. Значения квантиля U_α в зависимости от уровня значимости α приведены в таблице.

Таблица значений U_α

	0,15	0,1	0,05	0,025	0,01	0,005
Uα	1,0364	1,2816	1,6449	1,9600	2,3263	2,5758

Эти значения означают, что, например, площадь справа от U_α = 1,9600 (или слева от U_α = - 1,9600) составляет α = 0,025, а площадь справа от U_α = 1,6449 - соответственно 0,05.

При N ≥ 30 соотношение (14) позволяет оценить величину N*, обеспечивающую заданную точность оценивания ε для совокупности, не являющейся нормальной. Эта связь дается формулой

(20)

и равна

.

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

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

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

Пусть, как и выше, - вероятность того, что в произвольный момент времениt в системе имеется равноnзаявок,n = 0, 1, 2, … Из теории массового обслуживания известно, что величинаподчиняется дифференциальному уравнению [1, 9]

В этих формулах m- число обслуживающих каналов.

Установившееся решение можно получить из этой системы, полагая в ней при:

Эти соотношения позволяют вывести следующие формулы для :

где . Так как сумма всех вероятностей равняется единице, дляP₀ получим:

С помощью этих формул можно рассчитать основные характеристики работы системы в установившемся режиме:

- вероятность простоя системы -;

- вероятность занятости всех каналов (вероятность наличия в системе заявок)

(21)

- вероятность наличия в очереди ровно М заявок

(22)

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

(23)

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

(24)

- коэффициент загрузки каналов (или системы)

(25)

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

(26)

- среднее число заявок в системе

(27)

где - среднее

число обслуженных заявок;

- среднее время ожидания заявок в очереди

(28)

- среднее время обслуживания заявок

(29)

- среднее время пребывания заявок в системе

(30)

где вычисляется по формуле (28)

Задание для выполнения работы

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

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

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

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

Исходные данные к заданию

Данные для выполнения пунктов 1, 2 и 3 задания приведены в таблице 1, а данные для выполнения пункта 4 – в таблице 2.

Таблица 1

Варианты	1	2	3	4	5
1/	100	120	140	150	160
1/	110	160	200	100	250
m	3	4	5	5	4

Таблица 2

Варианты	1	2	3	4	5
	100	120	140	110	130
	110	130	100	150	120
С	50	100	200	200	120
m	2	3	4	5	3

Порядок выполнения работы на ЭВМ

Произвести загрузку рабочего файла GPSS.EXE. Для выполнения пунктов 1 - 3 задания в командной строке набрать программуCMO_М_1.GPS. Текст этой программы приведен в приложении 3. БлокSTORAGE(строка с меткой 60) задает количество обслуживающих каналов; блокGENERATEустанавливает параметр 1/(среднее время обслуживания).

После введения данных осуществить генерацию и получить результаты распределения времени пребывания заявок в системе. Доступ к гистограмме осуществляется нажатием на клавиши [Аlt] и [T]. Числовые данные этой гистограммы хранятся в файлеGPPSS.REP, для загрузки которого необходимо выйти из программыCMO_М_1.GPS.

Для выполнение пункта 2 задания необходимо изменить среднее время обработки (блок ADVANCE) в диапазоне (1/2) 1/. Значения времени пребывания заявок в системе (переменнаяTIME) и в очереди ( переменнаяTQUE) доступны в окне [Аlt] + [T], далее [PgUp] и [PgDn]. Значение коэффициента загрузки можно получить в окне [Аlt] + [S] (для одноканальной СМО эта информация находиться в окне [Аlt] + [F]). Рекомендуется выбрать число заявок. После каждого прогона модели в командной строке ввести командуRESETдля обнуления имеющейся статистики.

При выполнении пункта 3 задания изменяется количество каналов в пределах . Значения параметров 1/и 1/соответствуют варианту моделирования системы.

При выполнении пункта 4 задания вызвать программу CMO_М_2.GPS, текст которой приведен в приложении 4. В ней блокSTORAGE(строка с меткой 45) задает количество каналов; блокGENERATEустанавливает фиксированный интервал; блокиADVANCE(метки строк 78, 80) устанавливают постоянную составляющую (С)и переменную составляющую (Y) времени обслуживания соответственно. Таким образом, время обслуживания является случайной величинойX = C + Y, причемY-экспоненциально распределенная величина с математическим ожиданиемМ{X} = C + .

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

Содержание отчета по работе:

- задание на лабораторную работу;

- основные аналитические соотношения;

- исходные данные к работе;

- результаты моделирования по пунктам задания;

- краткие выводы по работе.

3. Исследование смо в замкнутом режиме

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

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

Задание на выполнение работы

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

Обратная связь

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

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

Исходные данные к заданию

Исходные данные для пяти вариантов работы системы приведены в таблице 1. Величина 1/определяет средний промежуток времени между моментами поступления заявок от каждого абонента, следовательно,- это интенсивность потока заявок. Когда предыдущая заявка еще не обслужена, величинаравна нулю. Величина 1/задает среднее время обслуживания заявок. Последующая строка таблицы устанавливает пределы изменения числа абонентовN. Максимально доступное время пребывания заявок в системе равно 250 (ед. вр.).

Таблица 1

Варианты	1	2	3	4	5
1/	100	120	130	140	150
1/	80	90	100	120	130
N	2 - 6	3 - 5	2 - 6	3 - 7	2 - 7

Порядок выполнения работы

1. Вызвать программу GPSS.EXEи в командной строке набрать командуCMO_ZAM.GPS. Текст этой программы приведен в приложении 5. БлокиSTORAGE(строка 80) иGENERATE(строка 100) задают количество подключенных к системе абонентов, блокADVANCE(строка 150) устанавливает среднее время между моментами поступления заявок (величину 1/), а другой блокADVANCE(строка 210) устанавливает среднее время обслуживания заявок (величину 1/).

2. Выбрать вариант данных и ввести в программу параметры 1/и 1/. Меняя число пользователейNв пределах, указанных в варианте задания, запустить программу и получить результаты моделирования: время пребывания заявок в системе, время пребывания заявок в очереди (окно открывается клавишами [Аlt] и [F]). Рекомендуется число заявок взять не менее 10000.

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

Содержание отчет по работе

- задание на лабораторную работу;

- исходные данные для моделирования;

- результаты моделирования и исследуемые зависимости;

- краткие выводы по работе.