Курсовая работа: Имитационное моделирование системы массового обслуживания

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

Выберем шаг по времени (). Он должен быть много меньше среднего времени поступления заявки () и среднего времени ее обслуживания (), т.е.

, где (3.1.1)

Исходя из условия (3.1.1) определим шаг по времени .

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

Рассмотрим поступление заявки в СМО. Вероятность того, что на интервале  в СМО поступит заявка, равна: . Сгенерируем случайное число , и, если , то будем считать, что заявка на данном шаге в систему поступила, если , то не поступила.

В программе это осуществляет isRequested(). Интервал времени  примем постоянным и равным 0,0001, тогда отношение  будет равно 10000. Если заявка поступила, то она принимает значение «истина», в противном случае значение «ложь».

bool isRequested()

{

double r = R. NextDouble();

if (r < (timeStep * lambda))

{return true;}

return false;

}

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

double GetServiceTime()

{

double r = R. NextDouble();

return (-1/mu*Math. Log (1-r, Math.E));

}

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

Если поступила, и, при этом имеются свободные каналы, то с помощью функции GetServiceTime() генерируем время обработки заявки и ставим ее на обслуживание. Если все каналы заняты, а длина очереди меньше 4, то помещаем заявку в очередь, если же длина очереди равна 4, то заявке будет отказано в обслуживании.

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

По истечении времени Т, т.е., после моделирования работы СМО, вычисляются показатели эффективности работы системы и результаты выводятся на экран.

 

3.2 Блок-схема программы

Блок-схема программы, реализующей описанный алгоритм, приведена на рис. 5.

 

Рис. 5. Блок-схема программы

Распишем некоторые блоки более подробно.

Блок 1. Задание начальных значений параметров.

Random R; // Генератор случайных чисел

public uint maxQueueLength; // Максимальная длина очереди

public uint channelCount; // Число каналов в системе

public double lambda; // Интенсивность потока поступления заявок

public double mu; // Интенсивность потока обслуживания заявок

public double timeStep; // Шаг по времени

public double[] timeOfFinishProcessingReq; // Время окончания обслуживания заявки во всех каналах

public double[] timeInQueue; // Время пребывания СМО в состояниях с очередью

public double processingTime; // Время работы системы

public double totalProcessingTime; // Суммарное время обслуживания заявок

public uint requestEntryCount; // Число поступивших заявок

public uint declinedRequestCount; // Число отказанных заявок

public uint acceptedRequestCount; // Число обслуженных заявок

uint queueLength; // Длина очереди //

Тип, описывающий состояния СМО

enum SysCondition {S0, S1, S2, S3, S4, S5, S6};

SysCondition currentSystemCondition; // Текущее состояние системы

Задание состояний системы. Выделим у данной 2-х канальной системы 7 различных состояний: S0, S1. S6. СМО находится в состоянии S0, когда система свободна; S1 – хотя бы один канал свободен; в состоянии S2, когда все каналы заняты, и есть место в очереди; в состоянии S6 – все каналы заняты, и очередь достигла максимальной длины (queueLength = 4).

Определяем текущее состояние системы с помощью функции GetCondition()

SysCondition GetCondition()

{

SysCondition p_currentCondit = SysCondition.S0;

int k = 0;

int busyChannelCount = 0;

for (int i = 0; i < channelCount; i++)

{

if (timeOfFinishProcessingReq[i] > 0)

{

k = 1;

busyChannelCount++;

}

else

{k = 0;}

p_currentCondit += k * (i + 1);

}

if (busyChannelCount > 1)

{p_currentCondit ++;}

return p_currentCondit + (int) QueueLength;

}

Изменение времени пребывания СМО в состояниях с длиной очереди 1, 2,3,4. Это реализуется следующим программным кодом:

if (queueLength > 0)

{

timeInQueue [queueLength – 1] += timeStep;

if (queueLength > 1)

{timeInQueue [queueLength – 2] += timeStep;}

}

Присутствует такая операция, как помещение заявки на обслуживание в свободный канал. Просматриваются, начиная с первого, все каналы, когда выполняется условие timeOfFinishProcessingReq [i] <= 0 (канал свободен), в него подается заявка, т.е. генерируется время окончания обслуживания заявки.

for (int i = 0; i < channelCount; i++)

{

if (timeOfFinishProcessingReq [i] <= 0)

{

timeOfFinishProcessingReq [i] = GetServiceTime();

totalProcessingTime+= timeOfFinishProcessingReq [i];

break;

}

}

Обслуживание заявок в каналах моделируется кодом:

for (int i = 0; i < channelCount; i++)

{

if (timeOfFinishProcessingReq [i] > 0)

{

timeOfFinishProcessingReq [i] -= timeStep;

}

}

Алгоритм метода имитационного моделирования реализован на языке программирования C#.

3.3 Расчет показателей эффективности СМО на основе результатов ее имитационного моделирования

Наиболее важными являются такие показатели, как:

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

2) Относительная пропускная способность – это средняя доля поступивших заявок, обслуживаемых системой.

3) Абсолютная пропускная способность – это среднее число заявок, обслуживаемых в единицу времени.

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

5) Среднее время пребывания заявки в очереди определяется формулой Литтла

6) Среднее число занятых каналов определяется следующим образом:

7) Процент заявок, которым было отказано в обслуживании, находится по формуле

8) Процент обслуженных заявок находится по формуле

3.4 Статистическая обработка результатов и их сравнение с результатами аналитического моделирования

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

Величина  попадает в доверительный интервал, если выполняется неравенство

, где

математическое ожидание (среднее значение), находится по формуле

,

 исправленная дисперсия,

,

N=20 – число прогонов,

 – надежность. При  и N=20 .

Результат работы программы представлен на рис. 6.

Рис. 6. Вид программы

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

Таблица 2.

Показатели эффективности СМО	Результаты аналитического моделирования	Результаты имитационного моделирования (послед. шаг)	Результаты имитационного моделирования
			Нижняя граница доверительного интервала	Верхняя граница доверительного интервала
Вероятность отказа		0,174698253017626	0,158495148639101	0,246483801571923
Относительная пропускная способность		0,825301746982374	0,753516198428077	0,841504851360899
Абсолютная пропускная способность		3,96144838551539	3,61687775245477	4,03922328653232
Средняя длина очереди		1,68655313447018	1,62655862750852	2,10148609204869
Среднее время пребывания заявки в очереди	0,4242558575	0,351365236347954	0,338866380730942	0,437809602510145
Среднее число занятых каналов		1,9807241927577	1,80843887622738	2,01961164326616

Из табл. 2 видно, что результаты, полученные при аналитическом моделировании СМО, попадают в доверительный интервал, полученный по результатам имитационного моделирования. Т.е., результаты, полученные разными методами, согласуются.

 

Заключение

В данной работе рассмотрены основные методы моделирования СМО и расчета показателей их эффективности.

Проведено моделирование двухканальной СМО с максимальной длиной очереди равной 4 с помощью уравнений Колмогорова, а также, найдены финальные вероятности состояний системы. Рассчитаны показатели ее эффективности.

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

Полученные при имитационном моделировании результаты согласуются с результатами аналитического моделирования.

Литература

1.   Вентцель Е.С. Исследование операций. – М.: Дрофа, 2004. – 208 с.

2.   Волков И.К., Загоруйко Е.А. Исследование операций. – М.: Изд.-во МГТУ им. Н.Э. Баумана, 2002. – 435 с.

3.   Волков И.К., Зуев С.М., Цветкова Г.М. Случайные процессы. – М.: Изд.-во МГТУ им. Н.Э. Баумана, 2000. – 447 с.

4.   Гмурман В.Е. Руководство к решению задач по теории вероятностей и математической статистике. – М.: Высшая школа, 1979. – 400 с.

5.   Ивницкий В.Л. Теория сетей массового обслуживания. – М.: Физматлит, 2004. – 772 с.

6.   Исследование операций в экономике/ под ред. Н.Ш. Кремера. – М.: Юнити, 2004. – 407 с.

7.   Таха Х.А. Введение в исследование операций. – М.: ИД «Вильямс», 2005. – 902 с.

8.   Харин Ю.С., Малюгин В.И., Кирлица В.П. и др. Основы имитационного и статистического моделирования. – Минск: Дизайн ПРО, 1997. – 288 с.