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

Партнерка на США и Канаду по недвижимости, выплаты в крипто

30% recurring commission
Выплаты в USDT
Вывод каждую неделю
Комиссия до 5 лет за каждого referral

Санкт-Петербургский Государственный Университет Информационных Технологий Механики и Оптики

Курсовая работа:

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

Выполнил:

Непряхин Егор

Проверила:

Муравьева-

2013 год

1. Постановка задачи:

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

2. Исходные данные:

Структурные параметры и количество заявок в ЗСеМО

К-во узлов n	Кол-во приборов в узлах	К-во заявок М	Номер узла	Тип модели	К-во Состояний
У1	У2
2	1	4	8	1	М1	9

Для неэкспоненциальной модели СеМО распределение длительности обслуживания заменяется на гиперэкспоненциальное с коэффициентом вариации 2.

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

Вероятности передач	Средние длительности обслуживания, с
p10	p12	b1	b2
0,2	0,8	1,5	0,5

Тип модели

3. Разработка моделей и проведение над ними экспериментов

3.1. Разработка аналитических моделей замкнутой СеМО (ЗСеМО) и разомкнутой СеМО (РСеМО)

Разработка аналитических моделей ЗСеМО и РСеМО заключается в подготовке

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

1) количество узлов СеМО;

НЕ нашли? Не то? Что вы ищете?

N = 2

2) количество обслуживающих приборов в узлах СеМО;

К1 = 1, К2 = 4

3) матрица вероятностей передач и рассчитанные по этой матрице коэффициенты

передач;

0	1	2
0	0	1	0
1	0,2	0	0,8
2	0	1	0

Коэффициенты передач: α0= 1, α1= 5, α2= 4

4) для замкнутой СеМО - число заявок, циркулирующих в сети, М=8

для разомкнутой СеМО - интенсивность входящего потока заявок, поступающих в сеть (определяется после расчета характеристик замкнутой СеМО и принимается равной производительности ЗСеМО);

5) средние длительности обслуживания заявок в узлах СеМО.

b1 =1,5, b2 = 0,5

Результаты аналитического моделирования

Характеристики СеМО	Замкнутая СеМО	Разомкнутая СеМО
Узел 1	Узел 2	Сеть	Узел 1	Узел 2	Сеть
Загрузка	1	0,06	1,06	0,97	0,06	1,03
Длина очереди	6,73332	0,00001	6,73333	38,02494	0,00001	38,02495
Число заявок	7,73332	0,26668	8	38,99994	0,26001	39,25995
Время ожидания	10,09998	0,00002	50,5	58,49992	0,00002	292,49966
Время пребывания	11,59998	0,50002	60	59,99992	0,50002	301,99966
Производительность	0,1333	0,13

Определим критическое число заявок, начиная с которого производительность ЗСеМО не изменяется и (прирост производительности не превосходит 1-5%). Так же, определим предельную интенсивность поступления заявок в РСеМО, при которой в сети существует стационарный режим.

Хар-ки СеМо	(критическое число = 3) Число заявок в ЗСеМо	(Предельная инт.= 0,132) Интенсивн. потока в РСеМО
1	2	3	4	5	0,03	0,055	0,08	0,105	0,130
Длина очереди	0	0,7679	1,7364	2,7335	3,7333	0,0653	0,2896	0,9	2,9184	38,025
Число заявок	1	2	3	4	5	0,3503	0,8121	1,66	3,9159	39,26
Время ожидания	0	5,9211	13,0546	20,5048	28,0004	2,1774	5,266	11,25	27,7941	292,4997
Время пребывания	9,5	15,4211	22,5546	30,0048	37,5004	11,6774	14,766	20,75	37,2941	301,4997
Производительность	0,1053	0,1297	0,1330	0,1333	0,1333	0,03	0,055	0,08	0,105	0,130

График зависимости сетевых характеристик ЗСеМО при изменении числа заявок

«Узким местом» является узел 1, для его устранения уменьшаем время обслуживания заявок с 1,5 до 0,25.

Характеристики	(критическое число = 9) Число заявок в ЗСеМо
5	6	7	8	9	10
Длина очереди	2,4574	3,4228	4,4091	5,4036	6,4014	7,4006
Число заявок	5	6	7	8	9	10
Время ожидания	3,1412	4,3163	5,5307	6,7640	8,0063	9,2528
Время пребывания	6,3912	7,5663	8,7807	10,0140	11,2563	12,5028
Производительность	0,7823	0,7930	0,7972	0,7989	0,7996	0,7998

Сравнение характеристик СеМо с «узким местом» и СеМО с устраненным наболее нагруженным узлом

Графики зависимости сетевых характеристик РСеМО при изменении интенсивности потока

3.2. Разработка Марковских моделей ЗСеМО

Экспоненциальная ЗСеМО

1) Перечень состояний Марковского процесса

Состояние	E0	E1	E2	E3	E4	E5	E6	E7	E8
(К1, К2)	(8,0)	(7,1)	(6,2)	(5,3)	(4,4)	(3,5)	(2,6)	(1,7)	(0,8)

2) Размеченный граф переходов случайного процесса

3) Матрица интенсивностей переходов

0	1	2	3	4	5	6	7	8
0	- p12μ1	p12μ1
1	μ2	-p12μ1-μ2	p12μ1
2	2μ2	-p12μ1-2μ2	p12μ1
3	3μ2	-p12μ1-3μ2	p12μ1
4	4μ2	-p12μ1-4μ2	p12μ1
5	4μ2	-p12μ1-4μ2	p12μ1
6	4μ2	-p12μ1-4μ2	p12μ1
7	4μ2	-p12μ1-4μ2	p12μ1
8	4μ2	-p12μ1-4μ2

4) Стационарные вероятности состояний

Состояние	E0	E1	E2	E3	E4	E5	E6	E7	E8
Вероятности	p0	p1	p2	p3	p4	p5	p6	p7	p8
0,7659	0,2042	0,0272	0,0024	0,0002	0,0000	0,0000	0,0000	0,0000

5) Расчет характеристик

Характеристика	Прибор	Расчетная формула	Результат
Загрузка	Уз.1	с1=p0+p1+p2+p3+p4+p5+p6+p7	1
Уз. 2	с2=1/4p1+1/2p2+3/4p3+p4+p5+p6+p7+p8	0,0667
Сеть	R=с1+с2	1,0667
Длина очереди	Уз.1	l1= 7p0+6p1+5p2+4p3+3p4+2p5+p6	6,7333
Уз. 2	l2= p5+2p6+3p7+4p8	0,0000
Сеть	L=l1+l2	6,7334
Число заявок	Уз.1	m1= 8p0+7p1+6p2+5p3+4p4+3p5+2p6+p7	7,7333
Уз. 2	m2=p1+2p2+3p3+4p4+5p5+6p6+7p7+8p8	0,2667
Сеть	M=m1+m2	8
Время ожидания	Уз.1	щ1=l1/л1	10,1025
Уз. 2	щ2=l2/л2	0,0000
Сеть	W=α1щ1+ α2щ2	50,5128
Время пребывания	Уз.1	u1=m1/л1	11,6029
Уз. 2	u2=m2/л2	0,5001
Сеть	U=α1u1+ α2u2	60,0150
Производительность	Уз.1	л1= α1л0	0,6665
Уз. 2	л2=α2л0	0,5332
Сеть	л0=с1/(α1b1)	0,1333

Неэкспоненциальная ЗСеМО

1) Перечень состояний Марковского процесса

Состояние	E0	E1	E2	E3	E4	E5	E6	E7	E8
(К1, К2)	(81,0)	(82,0)	(71,1)	(72,1)	(61,2)	(62,2)	(51,3)	(52,3)	(41,4)
Состояние	E9	E10	E11	E12	E13	E14	E15	E16
(К1, К2)	(42,4)	(31,5)	(32,5)	(21,6)	(22,6)	(11,7)	(12,7)	(0,8)

2) Размеченный граф переходов случайного процесса

3) Матрица интенсивностей переходов

qp12μ’1

(1-q)p12μ”1

μ2

qp12μ’1

μ2

(1-q)p12μ”1

μ2

qp12μ’1

μ2

(1-q)p12μ”1

μ2

qp12μ’1

μ2

(1-q)p12μ”1

μ2

qp12μ’1

μ2

(1-q)p12μ”1

μ2

qp12μ’1

μ2

(1-q)p12μ”1

μ2

qp12μ’1

μ2

(1-q)p12μ”1

μ2

p12μ’1

μ2

p12μ”1

qμ2

(1-q)μ2

g1=(1-q)(1-p12)μ’1 g3=q(1-p12)μ”1

g2=(1-q)p12μ’1 g4= qp12μ”1

Примем q=0,1. b’=6, b”=1.

0,1*6+0,9*1=1,5

4) Стационарные вероятности состояний

Состояние	E0	E1	E2	E3	E4	E5	E6	E7	E8
Вероятности	p0	p1	p2	p3	p4	p5	p6	p7	p8
0,3604	0,3729	0,0257	0,1475	0,0090	0,0517	0,0032	0,0181	0,0011
Состояние	E9	E10	E11	E12	E13	E14	E15	E16
Вероятности	p0	p1	p2	p3	p4	p5	p6	p7
0,0064	0,0004	0,0022	0,0001	0,0008	0,0000	0,0003	0,0001

5) Расчет характеристик

Характеристика	Прибор	Расчетная формула	Результат
Загрузка	Уз.1	с1=p0+p1+p2+p3+p4+p5+p6+p7+p8+p9+p10+p11+p12+p13+p14+p15	0,9999
Уз. 2	с2= 1/4p2+1/4p3+1/2p4+1/2p5+3/4p6+3/4p7+ +p8+p9+p10+p11+p12+p13+p14+p15+p16	0,1011
Сеть	R=с1+с2	1,1009
Длина очереди	Уз.1	l1= 7(p0+p1)+6(p2+p3)+5(p4+p5)+4(p6+p7)+ +3(p8+p9)+2(p10+p11)+p12+p13	6,5900
Уз. 2	l2= p10+p11+2(p12+p13)+3(p14+p15)+4p16	0,0059
Сеть	L=l1+l2	6,5959
Число заявок	Уз.1	m1= 8(p0+p1)+7(p2+p3)+6(p4+p5)+5(p6+p7)+ +4(p8+p9)+3(p10+p11)+2(p12+p13)+p14+p15	7,5899
Уз. 2	m2=p2+p3+2(p4+p5)+3(p6+p7)+ +4(p8+p9)+5(p10+p11)+6(p12+p13)+7(p14+p15)+8p16	0,4101
Сеть	M=m1+m2	8
Время ожидания	Уз.1	щ1=l1/л1	9,8875
Уз. 2	щ2=l2/л2	0,0110
Сеть	W=α1щ1+ α2щ2	49,4817
Время пребывания	Уз.1	u1=m1/л1	11,3877
Уз. 2	u2=m2/л2	0,7691
Сеть	U=α1u1+ α2u2	60,0150
Производительность	Уз.1	л1= α1л0	0,6665
Уз. 2	л2=α2л0	0,5332
Сеть	л0=с1/(α1b1)	0,1333

Сравнительная таблица характеристик экспоненциальной и неэкспоненциальной ЗСеМО

Хар-киСеМО	Экспоненциальная ЗCеМО	Неэкспоненциальная ЗCеМО
1	2	Сеть	1	2	Сеть
Загрузка	1	0,0667	1,0667	0,9999	0,1011	1,1009
Длина очереди	6,7333	0	6,7333	6,5900	0,0059	6,5959
Число заявок	7,7333	0,2667	8	7,5899	0,4101	8
Время ожид.	10,1025	0	50,5128	9,8875	0,0110	49,4817
Время преб.	11,6029	0,5001	60,0150	11,3877	0,7691	60,0150
Произв-ть	0,6665	0,5332	0,1333	0,6665	0,5332	0,1333

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

Хар-киСеМО	Численное моделирование	Аналитическое моделирование
Уз. 1	Уз. 2	Сеть	Уз. 1	Уз. 2	Сеть
Загрузка	1	0,0667	1,0667	1	0,0600	1,0600
Длина очереди	6,7333	0	6,7333	6,7333	0	6,7333
Число заявок	7,7333	0,2667	8	7,7333	0,2667	8
Время ожид.	10,1025	0	50,5128	10,1000	0	50,5000
Время преб.	11,6029	0,5001	60,0150	11,6000	0,5000	60,0000
Произв-ть	0,6665	0,5332	0,1333	0,6665	0,5332	0,1333

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

3.3. Разработка имитационных моделей РСеМО

Для РСеМО1:

Uz_2 STORAGE 4; задание числа приборов в узле 2

Tw_1 QTABLE 1,0,1,20; время ожидания в узле 1

Tw_2 QTABLE 2,50,50,20; время ожидания в узле 2

TU TABLE M1,150,150,20; времени пребывания в сети *

GENERATE (Exponential(920,0,7.5075))

Met_1 QUEUE 1

SEIZE Uz_1

DEPART 1

ADVANCE (Exponential(920,0,1.5))

RELEASE Uz_1

TRANSFER .8,,Met_2; передача транзакта с вероятностью 0,8 в узел 2

TABULATE TU

TERMINATE 1

Met_2 QUEUE 2

ENTER Uz_2

DEPART 2

ADVANCE (Exponential(920,0,0.5))

LEAVE Uz_2

TRANSFER ,Met_1

Для РСеМО2:

Uz_2 STORAGE 4; задание числа приборов в узле 2

Tw_1 QTABLE 1,0,1,20; время ожидания в узле 1

Tw_2 QTABLE 2,50,50,20; время ожидания в узле 2

TU TABLE M1,150,150,20; времени пребывания в сети

GENERATE 7.5075

Met_1 QUEUE 1

SEIZE Uz_1

DEPART 1

ADVANCE (Exponential(920,0,1.5))

RELEASE Uz_1

TRANSFER .8,,Met_2; передача транзакта с вероятностью 0,8 в узел 2

TABULATE TU

TERMINATE 1

Met_2 QUEUE 2

ENTER Uz_2

DEPART 2

ADVANCE (Exponential(920,0,0.5))

LEAVE Uz_2

TRANSFER ,Met_1

Для РСеМО3:

Uz_2 STORAGE 4; задание числа приборов в узле 2

Tw_1 QTABLE 1,0,1,20; время ожидания в узле 1

Tw_2 QTABLE 2,50,50,20; время ожидания в узле 2

TU TABLE M1,150,150,20; времени пребывания в сети

GENERATE 7.5075

Met_1 QUEUE 1

SEIZE Uz_1

DEPART 1

TRANSFER .1,,B_1; передача транзакта с вероятностью 0,1 в 1 фазу

ADVANCE (Exponential(920,0,1))

Rel RELEASE Uz_1

TRANSFER .8,,Met_2; передача транзакта с вероятностью 0,8 в узел 2

TABULATE TU

TERMINATE 1

B_1 ADVANCE (Exponential(920,0,6))

TRANSFER ,Rel

Met_2 QUEUE 2

ENTER Uz_2

DEPART 2

ADVANCE (Exponential(920,0,0.5))

LEAVE Uz_2

TRANSFER ,Met_1

Характе-ристики СеМО	РСеМО-1	РСеМО-2	РСеМО-3
Узловые	Сетевые	Узловые	Сетевые	Узловые	Сетевые
У1	У2	У1	У2	У1	У2
Загрузка	0,987	0,066	1,053	0,971	0,064	1,035	0,981	0,066	1,047
Длина очереди	42,136	0	42,136	12,961	0	12,961	11,969	0	11,969
Число заявок	64,846	0,149	65,036	20,909	0,060	20,969	18,964	0,038	19,002
Время ожидания	64,089	0,190	321,395	19,982	0	101,39	18,30	0	18,30
Время Пребывания	66,346	5,69	328,296	21,482	4,005	106,887	19,829	3,987	99,581

Хар-киСеМО	Численное моделирование	Аналитическое моделирование
Уз. 1	Уз. 2	Сеть	Уз. 1	Уз. 2	Сеть
Загрузка	0,581	0,039	0,62	0,6	0,04	0,64
Длина очереди	0,884	0	0,884	0,9	0	0,9
Число заявок	1,318	0	1,318	1,5	0,16	1,66
Время ожид.	2,266	0	11,33	2,25	0	11,25
Время преб.	4,093	0	20,469	3,75	0,5	20,75
Произв-ть	0,4	0,32	0,08	0,4	0,32	0,08

После проведенного имитационного моделирования, можно сделать вывод о том, что из выбранных РСеМО лучше всего оказалась РСеМО-3. Это объясняется тем, что интервалы между поступающими заявками распределены по детерминированному закону, в котором коэффициент вариации равен 0, и время обслуживания в обоих узлах распределено по гиперэкспоненциальному закону с коэффициентом вариации 2. Детерминированное значение интервала между заявками снижает вероятность появления очередей, поэтому уменьшаются и времена ожидания и пребывания.

Следующая – РсеМО-2, которая отличается от РСеМО-3 тем, что время обслуживания заявок в ней распределено по экспоненциальному закону.

Худшие результаты показала РСеМО-1, так как и заявки в ней поступают по экспоненциальному закону, и время пребывания заявок изменяется в соответствии с ним.

4. Выводы

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

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

Партнерка на США и Канаду по недвижимости, выплаты в крипто

Домашний очаг

Справочная информация

Техника

Общество

Образование и наука

Мир

Бизнес и финансы