А) Краткое теоретическое введение

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

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

входной выходной

поток поток

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

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

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

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

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

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

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

Согласно формуле (2.1), P_o = e^-λT есть вероятность отсутствия заявок, P₁ = (λT)e^-λT - вероятность поступления одной заявки и т.д. Величина l характеризует интенсивность (плотность) ординарного потока заявок (число заявок, поступивших за единицу времени).

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

(3.3)

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

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

, (3.4)

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

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

(3.5)

Стационарное решение можно получить из системы (3.5), полагая в ней = 0 при t → ∞ и ρ = λ/μ < 1. Оно равно

(3.6)

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

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

; (3.7)

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

(3.8)

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

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

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

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

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

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

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

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

- коэффициент загрузки обслуживающего прибора (канала)

К_з = λ/μ.. (3.13)

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

, (3.14)

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

(3.15)

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

. (3.16)

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

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

, (3.17)

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

, (3.18)

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

. (3.19)

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

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

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

. (3.20)

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

и выражается в виде

. (3.21)