85634 (612533), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

SIRO (service in random order)  очередная заявка выбирается наудачу.

Для обозначения простых процессов обслуживания используются обозначения, предложенные Кендалом:

А/B/n/N.

Буква А характеризует поток требований: например, А=М - пуассоновский поток. Буква B характеризует случайные последовательности длительностей обслуживания на отдельных приборах: B=M - экспоненциальное обслуживание (с одинаковой интенсивностью для разных приборов). Буква n означает количество обслуживающих приборов, буква N - количество мест для ожидания заявок в очереди.

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

К марковским системам относятся системы, поведение которых в момент времени t может быть описано марковским процессом . В частности, сюда относятся все системы вида M/M/n/N, где . Действительно, пусть обозначает число заявок в системе в момент t. Вероятностное распределение после момента t определяются:

1) числом заявок в системе в момент t;

2) моментами поступления заявок после момента t;

3) моментами окончаний обслуживания заявок после момента t.

В силу того, что входной поток простейший, моменты поступления заявок после момента t не зависят от предыстории системы до момента t. Аналогично, поскольку времена обслуживания показательно распределены, из-за “отсутствия памяти” у показательного распределения моменты окончания обслуживания заявок после момента t не зависят от предыстории системы до момента t. Поэтому вероятностное поведение после момента t зависит только от и не зависит от поведения до момента t. Значит - марковский процесс с конечным или счетным числом состояний. Поэтому для нахождения зависящих от времени вероятностей состояний следует решить систему уравнений Колмогорова для безусловных вероятностей. Если интерес представляет стационарные вероятности, то следует решить систему уравнений равновесия. Для получения уравнений Колмогорова используется предельный переход при t, который называется t -методом.

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

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

Под состоянием сети в момент времени t будем понимать вектор:

где - число заявок в i-ой СМО (на обслуживание и в очереди).

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

Традиционный подход в описании моделей сетей массового обслуживания зависит от ряда предположений из теории стохастических процессов, например:

Переходы заявок между СМО сети описываются неприводимой цепью Маркова.

Заявки стохастически независимы.

Существует стационарный режим, работа сети может быть описана стационарным стохастическими процессами.

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

1.7 Нахождение стационарных вероятностей состояний открытой марковской сети массового обслуживания

Пусть входящий в открытую марковскую сеть массового обслуживания поток заявок описывается чистым процессом размножения с интенсивностью , причем в i-ую систему массового обслуживания входящая заявка поступает с вероятностью . Времена обслуживания заявок в i-той системе массового обслуживания распределены по показательному закону , зависящим от текущего числа заявок в i-той системе i=1,...,n.

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

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

,

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

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

Поэтому (2).

Из (2) получим (3).

Соотношение (2) иногда называют законом сохранения потока заявок. Оно говорит о том, что интенсивность входящего потока заявок в i-тую СМО, i=1,...,n, в стационарном режиме равна интенсивности входящего потока заявок из этой системы.

Теорема1. (Джексона) Стационарное распределение может быть найдено в виде:

1.8 Нахождение решения для немарковского случая

Составив и решив систему дифференциально-разностных уравнений, найдется вид функции распределения

для случайного процесса . Тогда можно найти и .

Так что нахождение функций

решит поставленную задачу.

2. Марковский случай

2.1 Описание модели

1

2.2 Сеть массового обслуживания

Дана открытая марковская сеть массового обслуживания, состоящая из трех подсистем. Состояние сети в момент времени t определяется вектором

число заявок в i-ой подсистеме в момент времени t. Входящий поток является пуассоновским потоком с параметром . Времена обслуживания заявок в i-ой системе массового обслуживания распределены по показательному закону с параметром , зависящим от текущего числа заявок в i-ой системе, i=1,2,3.

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

2.3 Уравнения равновесия

Предположим, что существует стационарное распределение . Составим уравнение равновесия.

P

P + P +

+ P + P +

+ P + P +

+ P

2.4 Нахождение стационарных вероятностей

Для того, чтобы найти решение уравнения равновесия , воспользуемся теоремой 1 из 1.7 из которой получим, что

,

-вероятность поступления заявок в i-ую подсистему.

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

Из системы получим

где -вероятности перехода

Матрица перехода имеет вид:

Тогда, получим

где Io - нулевой вектор.

Итак, стационарное распределение найдено с точностью до постоянного множителя P (Io).

2.5 Условия эргодичности

Для исследования эргодичности применим эргодическую теорему Фостера (теорема 1 из 1.1)

Теорема (Эргодическая теорема Фостера).

Регулярная Марковская цепь с непрерывным временем и счетным числом состояний эргодична, если она неприводима и система уравнений

имеет нетривиальное решение такое, что

При этом существует единственное стационарное распределение, которое совпадает с эргодическим.

Рассмотрим условия этой теоремы.

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

В качестве нетривиального решения системы уравнений из теоремы Фостера возьмем . Тогда для эргодичности потребуется, чтобы

Тогда получим,

Условие (1) и есть искомое условие эргодичности. Если это условие будет выполнятся, то будет существовать единственное стационарное распределение, совпадающее с эргодическим.

3. Немарковский случай

3.1 Описание модели

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

.

Состояние сети в момент времени t определяется вектором

, где

Характеристики

Список файлов курсовой работы