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

для расчетa времени ожидания

Рассмотрим многоканальную СМО с каналами обслуживания. Все предыдущие обозначения сохраняются. Обозначим через время ожидания - ой заявкой начала обслуживания, . Рассмотрим функционирование -го канала в отдельности. Будем считать, что входящий поток для него – тот же, что и для всей СМО, а длительность обслуживания - ой заявки равна , где = в случае, сели данная заявка действительно поступила на этот канал, = 0 в противном случае. Введем случайную величину - время с момента до момента освобождения -го канала от заявок, поступивших ранее , или 0, если все они обслужены до момента . Тогда для выполняется рекуррентное соотношение, аналогичное случаю одноканальной СМО, а именно:

= ,0).

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

= , ,

= 0, = ,

В том случае, если среди чисел лишь одно минимально. Если же, скажем, = , а все остальные , то необходимо определить правило выбора среди номеров . Так как на распределение это правило не влияет, будем считать, что из множества ( ) выбирается по равновероятному закону то , для которого = ; для всех остальных из этого множества полагается = 0. Это завершает получение необходимых рекуррентных процедур, так как случайные вектора = ( ) полностью определяют - мерное случайное блуждание.

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

Рассмотрим многолинейную систему массового обслуживания с ожиданием с обслуживающими приборами. Входящий поток является рекуррентным. В начальный момент система свободна. Требования поступают в моменты , величины = независимы в совокупности и обладают одним и тем же законом распределения . Длительности обслуживания требований - независимые в совокупности случайные величины с распределением . Предполагаем, что последовательности ( ) и ( ) взаимно независимы. Обозначим через число требований в системе в момент - 0, - число поступивших требований в систему до момента и - число обслужившихся требований системой до момента .

Пусть в момент =0 = 0. Легко видеть, что здесь также = - . Всегда . С поступлением первого требования в момент становится больше 0. Обозначим через первый момент времени, когда снова обратится в нуль. Интервал ( , ) также называется периодом занятости системы, периоды времени, когда = 0, являются свободными периодами. За свободным периодом следует период занятости, затем снова свободный период, затем период занятости и т.д.

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

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

Однако далее идет уже более сложный процесс моделирования. Обозначим через моменты времени, когда процесс претерпевает скачки. Осуществим моделирования перехода состояния процесса из момента времени в . Для этого введем векторный марковский процесс = ( , , где - время с момента до момента поступления следующего требования, - время с момента до момента окончания обслуживания требования на - ом канале, которое обслуживалось на нем в момент времени , . Величина = 0, если - ый канал в момент времени был свободен. Для моделирования поведения процесса отводим + 2 ячеек для хранения в них значений компонент процесса , т.е. , . Изменения процесса рассматриваем только в моменты времени .

Пусть в момент времени имеем = ( , . Опишем процедуру перехода к процессу в момент времени , т.е. процедуру нахождения значения процесса в момент времени , а именно, = ( , Имеет место следующий алгоритм.

1. Находим ( .

2. Если ( = то модельное время увеличивается на величину в ячейку для заносится величина интервала до момента поступления следующего требования , в ячейку для заносится величина +1, если все величины больше 0, т.е. , то они уменьшаются на величину . Модельное время увеличивается на величину . Таким образом, = ( , будет равен ( = +1 , …, = - ). Если , то генерируется случайная величина , которая будет помещена в ячейке, в которой находился 0, как символ свободности канала обслуживания. В счетчик длительностей интервалов заносится пара ( ,

3. Если ( = , то модельное время увеличивается на величину в ячейку для заносится величина - в ячейку для заносится величина -1, величины уменьшаются на величину в ячейку для заносится величина времени обслуживания следующего требования, которое является первым требованием в очереди, если , и 0 в противном случае. Таким образом, = ( , будет равен ( = -1 , - …, - )+0 (1- )), = - …, = - ). В счетчик длительностей интервалов заносится пара ( , .

4. В счетчике числа скачков прибавляется 1 и по циклу переходим к п. 1.

Кончается период занятости уменьшением до 0.

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

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

Рассмотрим сеть массового обслуживания, состоящую из многолинейных систем (узлов) с ожиданием. В - ом узле имеется обслуживающих приборов, . Входящий поток является рекуррентным. В начальный момент сеть свободна. Требования поступают в моменты , величины = независимы в совокупности и обладают одним и тем же законом распределения . При поступлении требования в сеть оно с вероятностью направляется на обслуживание в - ый узел, =1. Длительности обслуживания требований в - ом узле - независимые в совокупности случайные величины с распределением . После окончания обслуживания требования - ом узле оно с вероятностью направляется на обслуживание в - ый узел и с вероятностью покидает сеть, = 1. Предполагаем, что последовательности ( ) и ( ), , взаимно независимы. Обозначим через число требований в - ом узле в момент . Необходимо найти нестационарное распределение вектора = ( , …, ), т.е. = , …, = = .

Пусть в момент =0 = (0,…,0). С поступлением первого требования в момент становится ненулевым вектором. Обозначим через первый момент времени, когда снова станет нулевым вектором. Интервал ( , ) также называется периодом занятости сети, периоды времени, когда = (0,…,0), являются свободными периодами. За свободным периодом следует период занятости, затем снова свободный период, затем период занятости и т.д.

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

Начинается период занятости с периода увеличения вектора , к = (0,…,0) , например, к - ой компоненте прибавляется 1. Реализуется время обслуживания . Реализуются также случайные величины . Обозначим вектор (0,…,0, ,0,…, 0) через . Если , то в счетчик длительностей интервалов записывается вектор ( = (0,…, 0) + , ), где - длина интервала, на котором = 1, и ) = . На этом период увеличения заканчивается.

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

Осуществим моделирования перехода состояния векторного процесса из момента времени в . Для этого введем векторный марковский процесс = ( , , где - время с момента до момента поступления следующего требования, - время с момента до момента окончания обслуживания требования на - ом канале в - ом узле, которое обслуживалось на нем в момент времени , . Величина = 0, если - ый канал в - ом узле в момент времени был свободен.

Для моделирования поведения процесса отводим + 1 + ячеек для хранения в них значений компонент процесса , т.е. , . Изменения процесса рассматриваем только в моменты времени .

Пусть в момент времени имеем

= ( , . .

Опишем процедуру перехода к состоянию процесса в момент времени , т.е. процедуру нахождения значения процесса в момент времени , а именно,

= ( , .

Имеет место следующий алгоритм перехода к состоянию процесса в момент времени .

1. Находим ( . .

2. Если ( . = то модельное время увеличивается на величину в ячейку для заносится величина интервала до момента поступления следующего требования , с вероятностями , , разыгрывается номер узла, куда направляется следующее поступившее требование. Пусть, для примера это будет узел . Тогда в ячейку для заносится величина +1, величины ,…, уменьшаются на величину . Если , то в канал с номером +1 заносится длительность обслуживания для нового требования, которое сразу начинает обслуживаться. Таким образом,

= ( ,

будет равен = ( = + , , . Кроме того, в - ом узле в канал с номером +1 заносится длительность обслуживания для нового требования. В счетчик длительностей интервалов заносится пара ( ,

3. Если ( . = , то модельное время увеличивается на величину в ячейку для заносится величина - в ячейку для заносится величина -1, величины ,…, уменьшаются на величину в ячейку для заносится величина времени обслуживания следующего требования, которое является первым требованием в очереди, если , и 0 в противном случае. С вероятностями , , разыгрывается номер узла, куда направляется обслужившееся в - ом узле требование и с вероятностью оно покидает сеть, = 1. Таким образом,

= ( ,

будет равен = ( = - + ), - …, …, )+0 (1- )), ) )). В счетчик длительностей интервалов заносится пара ( , .

4. В счетчике числа скачков прибавляется 1 и по циклу переходим к п. 1.

Кончается период занятости уменьшением до (0,...,0).

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