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

Непрерывно-стохастические модели (Q - схемы).

Числовой пример

Пример У-детерминированного автомата

Таблица переходов.

	z₁	z₂	…	z_K-1	z_K
z₁	p₁₁	p₁₂	…	p_1,K-1	p_1K
z₂	p₂₁	p₂₂	…	p_2,K-1	p_2K
…	…	…	…	…	…
z_K	p_K,1	p_K,2	…	P_K,K-1	p_KK

Таблица выходов.

z	z₁	z₂	…	z_K-1	z_K
y	y_i₁	y_i2	…	y_i,K-1	y_i,K

Начальное распределение вероятностей:

z		z₁	z₂		z_K-1	z_K
d		d₁	d₂		d_K-1	d_K

Лекция №5.

К ним относятся системы массового обслуживания ( англ. queuing system), которые называют Q- схемами.

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

Поступающие на вход СМО однородные заявки в зависимости от порождающей причины делятся на типы, интенсивность потока заявок типа i (i=1…M) обозначено l_i. Совокупность заявок всех типов - входящий поток СМО.

Обслуживание заявок выполняется n каналами. Различают универсальные и специализированные каналы обслуживания. Для универсального канала типа j считается известными функции распределения F_ji(t) длительности обслуживания заявок произвольного типа.

Типичные примеры операций обслуживания:

— обслуживание потока вызовов телефонной станцией

— обслуживание потока посетителей в парикмахерской

— обслуживание потока автомобилей перекрестком,

— обслуживание потока прерываний процессором,

— обслуживание потока пакетов маршрутизатором,

— обслуживание потока целей системой ПВО и т. д.

Q - схемы можно исследовать аналитически и имитационными моделями. Последнее обеспечивает большую универсальность.

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

В любом элементарном акте обслуживания можно выделить две основные составляющие: ожидание обслуживания заявкой и собственно обслуживание заявки. Это можно отобразить в виде некоторого i-ого прибора обслуживания П_i, состоящего из накопителя заявок, в котором может находится одновременно l_i=0…L_i^H заявок, где L_i^H - ёмкость i-ого накопителя, и канала обслуживания заявок, k_i.

l_i=0…L_i^H

Рис. 3.2. Схема прибора СМО

{t_n}={0£t₁£t₂…£t_n£…}, где t_n - момент поступления n- ого события

{t_n, f_n} , где t_n- вызывающие моменты; f_n- набор признаков события.

t_iÎ{t_n} => поток с ограниченным последействием

На каждый элемент прибора обслуживания П_i поступают потоки событий: в накопитель H_i поток заявок w_i , на канал k_i - поток обслуживания u_i.

Потоком событий (ПС) называется последовательность событий, происходящих одно за другим в какие-то случайные моменты времени. Различают потоки однородных и неоднородных событий. Однородный ПС характеризуется только моментами поступления этих событий (вызывающими моментами) и задаётся последовательностью {t_n}={0£t₁£t₂…£t_n£…}, где t_n - момент поступления n- ого события - неотрицательное вещественное число. ОПС может быть также задан в виде последовательности промежутков времени между n-ым и n-1-ым событиями {t_n}.

Неоднородным ПС называется последовательность {t_n, f_n} , где t_n- вызывающие моменты; f_n- набор признаков события. Например, может быть задана принадлежность к тому или иному источнику заявок, наличие приоритета, возможность обслуживания тем или иным типом канала и т.п.

Рассмотрим ОПС, для которого t_iÎ{t_n}- случайные величины, независимые между собой. Тогда ПС называется потоком с ограниченным последействием.

ПС называется ординарным, если вероятность того, что на малый интервал времени Dt, примыкающий к моменту времени t попадает больше одного события Р_³1(t, Dt) пренебрежительно мала.

Если для любого интервала Dt событие P₀(t, Dt) + P₁(t, Dt) + Р_³1(t, Dt)=1, P₁(t, Dt) - вероятность попадания на интервал Dt ровно одного события. Как сумма вероятностей событий, образующих полную группу и несовместных, то для ординарного потока событий P₀(t, Dt) + P₁(t, Dt) » 1, Р_³1(t, Dt)=Q(Dt), где Q(Dt)- величина, порядок малости который выше, чем Dt, т.е. lim(Q(Dt))=0 при Dt®0.

Стационарным ПС называется поток, для которого вероятность появления того или иного числа событий на интервале времени t зависит от длины этого участка и не зависит от того, где на оси времени 0 - t взят этот участок. Для ОПС справедливо 0*P₀(t, Dt) + 1*P₁(t, Dt)= P₁(t, Dt) - среднее число событий на интервале Dt. Среднее число событий, наступающих на участке Dt в единицу времени составляет P₁(t, Dt)/Dt. Рассмотрим предел этого выражения при Dt®0

lim P₁(t, Dt)/Dt=l(t)*(1/един.вр.).

Если этот предел существует, то он называется интенсивностью (плотностью) ОПС. Для стандартного ПС l(t)=l=const.

Применительно к элементарному каналу обслуживания k_i можно считать что поток заявок w_iÎW, т.е. интервалы времени между моментами появления заявок на входе k_i образуют подмножество неуправляемых переменных, а поток обслуживания u_iÎU, т.е. интервалы времени между началом и окончанием обслуживания заявки образуют подмножество управляемых переменных.

Заявки, обслуженные каналом k_i и заявки, покинувшие прибор П_i по различным причинам необслуженными, образуют выходной поток y_iÎY.

Процесс функционирования прибора обслуживания П_i можно представить как процесс изменения состояний его элементов во времени Z_i(t). Переход в новое состояние для П_i означает изменение кол-ва заявок, которые в нём находятся (в канале k_i и накопителе H_i). Т.о. вектор состояний для П_i имеет вид : , где - состояния накопителя, (=0 - накопитель пуст, =1- в накопителе одна заявка…, =- накопитель занят полностью; - состояние канала k_i (=0 - канал свободен, =1 канал занят).

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

1. По входному потоку:

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

— со случайным потоком (random input). Если время поступления отдельных заявок заранее предсказать невозможно, используется модель случайного потока с теми или иными вероятностными характеристиками.

2. По количеству приборов:

—одноканальная (one-channel) система,

—многоканальная (multi-channel) система.

3. По возможности ожидания:

— с отказами в обслуживании (denial of service), т. е., с потерями заявок при занятости всех приборов;

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

4. По дисциплине очереди:

— заявки обслуживаются в порядке поступления (First-In-First-Out — FIFO);

— заявки обслуживаются в обратном порядке (Last-In-First- Out — LIFO);

— заявки обслуживаются с учетом приоритетов (priorities);

— полнодоступная или неполнодоступная (full or limited availability) очередь. В полнодоступном случае (общая очередь) очередной клиент может быть обслужен любым освободившимся прибором, в неполнодоступном прибор обслуживает только «своих» клиентов.

5. По дисциплине ожидания:

— с терпеливыми клиентами (готовыми ждать до бесконечности);

— с нетерпеливыми клиентами (impatient customers): с ограниченным временем ожидания либо покидающими очередь с вероятностью, возрастающей по мере ожидания

6. По времени обслуживания:

— детерминированное время обслуживания (deterministic service time);

— случайное время обслуживание (random service time) с тем или иным законом распределения, например экспоненциальным или равномерным.

7. По виду обслуживания:

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

— многофазная модель. Выполнив первую фазу, прибор передает заявку другому, который выполняет вторую фазу и т. д.;

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

8. По общему количеству заявок:

— открытая система, когда число клиентов в системе не ограничено. Пример — общедоступная станция технического обслуживания, куда автомобили приходят из потенциально бесконечного внешнего мира;

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

Пример системы массового обслуживания: СМО (Q - схема) M/M/1

В начальный момент времени заявок нет