5. Классификация и характеристики смо. Понятие системы массового обслуживания

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

1) входящий поток;

2) очередь;

3) каналы обслуживания;

4) выход. поток обслуженных заявок.

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

Характеристики эффективности СМО:

1. Показатели эффективности использования СМО

• Абсолютная ПС— среднее число заявок, кот. м обслужить СМО в 1 времени.

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

• Средняя продолжительность периода занятости СМО.

• Коэффициент использования СМО — средняя доля времени, в течение которого СМО занята обслуживанием заявок, и т.п.

2. Показатели качества обслуживания заявок

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

• Среднее время пребывания заявки в СМО.

• Вероятность отказа заявке в обслуживании без ожидания.

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

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

• Закон распределения времени пребывания заявки в СМО.

• Среднее число заявок, находящихся в очереди.

• Среднее число заявок, находящихся в СМО, и т.п.

3. Показатели эффективности функционирования пары «СМО — потребитель» (вся совокупность заявок/ их источник). Используется, если доход от обслуживания заявок, и затраты на обслуживание измеряются в одних и тех же единицах.

Поток событий и его свойства

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

• Стационарный или нестационарный; Стационарный – в разные интервалы времени в среднем получаем одни и те же характеристики.

• С последействием и без последействия; Если вероятность появления события не зависит на определенном интервале от предыдущих, интервалов, то без последействия.

• Ординарный и неординарный. Если вероятность, что на элементарном интервале времени произойдет больше 1 события равно 0, то ординарный.

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

- функция распределения; - плотность вероятности

λ –интенсивность потока (λ=const – стационарный поток); m-число событий.

Потоки Пальма –потоки, в которых интервал времени является независимым и с одинаковым распределением. Их подмножество– потоки Эрланга. Его получают, просеивая простейший поток. Если после просеивания остается каждое k-е событие, то получаем поток Эрланга k-го порядка.

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

Уравнения Холмогорова

Условие наступления предельного стационарного режима: если система имеет конечное число состояний, из каждого можно попасть в другое за конечное число шагов – предельные вероятности не зависят от начального состояния. При предельных вероятностях их производные равны 0.

Процессы гибели и размножения

6. Графы и показатели СМО с простейшими потоками.

Одноканальная система с отказами

Известны λ и μ одного канала.

λ – интенсивность входного потока заявок (среднее число заявок в единицу времени)

μ – интенсивность обслуживания (1/ среднее время обслуживания заявки)

2 состояния: канал занят или свободен.

; ; ;

- относительная ПС; - абсолютная ПС

Многоканальная система с отказами

Все каналы идентичны. Поток ординарный. S₀ – все каналы свободны. S₁ – 1 занят, остальные свободны. S₂ – 2 канала заняты, остальные свободны. … S_n – все n каналов заняты. - приведенная интенсивность

;

… ; ; ; ; … ; ; ; ; ; ; - среднее число занятых каналов.

Одноканальная система с ожиданием

m – число мест в очереди. S₀ – канал свободен, очереди нет.

S₁ – канал занят, очереди нет. S₂ –канал занят, одна заявка в очереди.

S₃ –канал занят, 2 заявки в очереди. … S_m+1 – канал занят, все места в очереди заняты.

… ; ; ; ;… ;

; ;

; ; ;

; ; ;

Если ,то:

• Если , то в системе наступает установившийся режим.

• Если , то система не придет никогда в установившееся состояние, будет неограниченно расти очередь.

n-канальная система с ожиданием

; ; …; ; ; ; …;

; ; ; ; ;

Если ,то при в системе наступает установившийся режим.

Многоканальная система с ограниченным временем ожидания

λ_у(у нас в лекциях ν -ню) – интенсивность ухода.

; ; ;

;

Замкнутые СМО

Входящий поток зависит от состояния системы. Пример: офис, где n комп-в. 1 человек отвечает за их ремонт. λ – интенсивность выхода из строя 1 компа. S₀ – все компы исправны. S₁ – 1 компьютер не исправен, остальные исправны.

; ; … ; ; ; ;

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

; ; ; ;

7. Примеры задач ЛП: игра 2 лиц как з. ЛП, транспортная задача.

Игра двух лиц с нулевой суммой как задача линейного программирования

Рассмотрим платежную матрицу игры двух лиц, не имеющую седловых точек,

	B1	B2	…	Bn
A1	U11	U12	…	U1n
A2	U21	U22	…	U2n
…	…	…	…	…
Am	Um1	Um2	…	Umn

где платежи U_ij - выигрыши игрока A.

Р ешение в области смешанных стратегий. Пусть X=(x₁,x₂,…,x_m) – распределение вероятностей на стратегиях игрока A. По принципу гарантированного результата будет выбрано такое распределение X ^*, которое макс-ет наименьший ожидаемый выигрыш Обозначим через  минимальный ожидаемый выигрыш;  не больше каждого ожидаемого выигрыша, цель – максимальный выигрыш, то приходим к следующей эквивалентной задаче

L=→max при ограничениях , х_i0. ...

Это обычная линейная задача, оптимальное значение критерия которой L^*=^* есть цена игры. Ее решение определяет оптимальное поведение игрока А.

Для игрока B линейная модель строится аналогично, но тот же критерий минимизируется, так как  уже имеет смысл максимального проигрыша, а ограничения на вероятности y_j соответствуют строкам платежной матрицы и записываются как неравенства “меньше или равно”.