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

Система.

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

Элемент, система, комплекс — понятия относительные, т.к. любой элемент, если его расчленить, если его не рассматривать как  неделимый объект, то он становится системой, и наоборот любой комплекс становится системой, если входящие в  его состав системы рассматривать  как элементы.

Структура и  функции.

Для описания системы  необходимо определить ее структурную  и функциональную организацию.

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

Для описания структуры  системы используются способы:

а) графический  — в форме графа, где вершины  графа соответствуют элементам  системы, а дуги — связям между  элементами (частный случай графического задания структуры системы —  это форма схем);

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

Функциональная  организация (функции) системы —  это правила достижения поставленной цели, правила, описывающие поведение  системы на пути к цели её назначения.

Способами описания функций системы являются:

а) алгоритмический  — в виде последовательности шагов, которые должна выполнять система;

б) аналитический  — в виде математических зависимостей;

в) графический  — в виде временных диаграмм;

г) табличный  — в виде таблиц, отображающих основные функциональные зависимости.

Понятие состояния  системы.

Свойства системы, значения переменных, описывающих систему, в конкретные моменты времени  называются состояниями системы.

Процесс (продвижение – лат.) функционирования системы можно рассматривать как последовательную смену её состояний во времени, другими словами, процесс функционирования системы — это переход её из одного состояния в другое.

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

 Действия:                                    События:                

"поход (ходьба) в кассу"                      "прибытие";                           

"ожидание"                              "уход из очереди",                                                                        

"начало обслуживания";                       

"обслуживание"                  "окончание обслуживания",                                    

                                         "уход из системы".

Понятия "система" и "процесс функционирования" тесно взаимосвязаны и часто  рассматриваются как эквивалентные  понятия

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

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

Процесс функционирования СМО включает в общем случае следующие  этапы:

1)    приход (поступление) требования;

2)    ожидание (при необходимости) в очереди;

3)    обслуживание в приборе;

4)    уход требования из системы.

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

Для формализации любой СМО необходимо описать:

1)    процесс поступления заявок в систему;

2)    процесс обслуживания заявок в системе;

3)    дисциплину обслуживания.

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

 
Пусть t₁, t₂, t₃, ... , t_k, ... — моменты поступления в систему 1-го, 2-го, 3-го, ..., k-го, ... требований:

Обозначим через  t_k = t_k– t_k-1 промежуток времени между моментами прихода (k–1)-го и k-го требований, который называется интервалом прихода k-го требования (k = 1, 2, 3, ...).

Если интервалы  прихода всех заявок являются постоянными, т.е. , то такой поток называется  детерминированным или регулярным. Однако, как правило, интервалы прихода t_k являются случайными величинами, и соответствующий поток заявок называется стохастическим или случайным. Очевидно, что регулярный поток является частным случаем случайного потока.

Для описания стохастического  потока (стохастического процесса поступления) заявок необходимо задать функцию распределения  случайного в общем случае интервала  прихода для каждой заявки:

 .

Поток заявок, для  которого функции распределения  интервалов прихода всех заявок одинаковы, т.е.

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

Важная характеристика любого потока — это его интенсивность, которая обозначается через l(t) и определяет среднее число заявок, поступающих в систему в единицу времени. Если интенсивность поступления l(t) не зависит от времени, т.е. l(t) є l, то такой поток называется стационарным.

Величина а, обратная интенсивности l (а=1/l), определяет среднее значение интервалов прихода или средний интервал поступления заявок.  

Если в каждый момент времени t₁, t₂, t₃, ... поступает только одна заявка, то такой поток называется ординарным, в противном случае — групповым (могут приходить одновременно две или более заявок). В дальнейшем рассматриваются только рекуррентные, стационарные и ординарные потоки.

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

При анализе  СМО важное место занимает так  называемый простейший поток. Простейшим называется поток, в котором интервалы  поступления заявок распределены по экспоненциальному закону:

.

Очевидно, что  параметр l данного экспоненциального  распределения является интенсивностью соответствующего простейшего потока.

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

Простейший поток  обладает следующими свойствами.

1)    Сумма (слияние) двух или более простейших потоков образует простейший поток, интенсивность которого равна сумме интенсивностей составляющих его простейших потоков.

2) Если из  простейшего потока интенсивности  l исключить каждую заявку с  вероятностью р (а с вероятностью 1–р оставить), то как поток исключенных, так и поток оставшихся заявок, окажутся простейшими с интенсивностями рl и (1–р)l соответственно:

 
          3) Число заявок N(t) простейшего потока, поступающих в СМО за время t, будучи случайной целочисленной дискретной величиной, распределено по закону Пуассона:

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

Таким образом, для описания рекуррентного, стационарного  и ординарного процесса поступления  заявок необходимо в общем случае задать функцию распределения интервалов их поступления. Однако не всегда бывает известной функция распределения. В таких случаях вместо неизвестной  функции распределения для описания входного потока задаются интенсивность l (или средний интервал а=1/l) и коэффициент вариации (КВ) n_а интервалов поступления, что оказывается достаточным для многих теоретических и практических приложений. Более того, в большинстве аналитических исследований в качестве входного потока заявок рассматривается простейший поток, ибо только в этом случае удается получать сколько-нибудь содержательные результаты анализа СМО. А для описания простейшего потока достаточно задать интенсивность l, т.к. при этом КВ n_ає1 в силу экспоненциального характера распределения интервалов поступления заявок.

Процесс обслуживания

По аналогии с процессами поступления заявок в систему для описания процессов  обслуживания необходимо задать функцию  распределения B_k(t) длительности обслуживания для каждой k-й заявки (k = 1, 2, 3, ...), которая в общем случае является случайной величиной. При этом под длительностью обслуживания t_в понимается промежуток времени, в течение которого заявка находится в обслуживающем приборе. Далее будем считать, что все заявки создают статистически однородную нагрузку, т.е. длительности обслуживания всех заявок распределены по одному и тому же закону:

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

Величина b, обратная интенсивности m (b=1/m), определяет среднее время обслуживания одной заявки.

Как и в случае интервалов поступления, если функция  распределения B(t) неизвестно, то для многих приложений (теоретических и практических) оказывается достаточным определить интенсивность обслуживания m (или среднее время обслуживания b)и КВ n_в длительности обслуживания. Если длительность обслуживания распределено по экспоненциальному закону, то достаточно задать интенсивность обслуживания m (или среднее время обслуживания b). Следует отметить, что, в отличие от интервалов поступления заявок, отказ от экспоненциального характера распределения длительности их обслуживания не столь усложняет задачу аналитического исследования СМО, и многие содержательные результаты получены при произвольном характере распределения времени обслуживания.

1.3 Потоки событий. Простейший поток и его свойства. ²

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