Что такое входной поток. Смотреть страницы где упоминается термин входной поток

12.37 Руководство по входной/выходной информации ПО Руководство по входной/выходной информации ПО объясняет пользователю как представить, ввести входную информацию и как интерпретировать выходную информацию, в каком режиме (пакетном или интерактивном) работает система

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

В качестве критерия эффективности могут быть использованы различные функции и величины:

• среднее время простоя системы;
• среднее время ожидания в очереди;
• закон распределения длительности ожидания требования в очереди;
• средний % заявок, получивших отказ; и т.д.

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

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

2. Математические модели потоков событий.

2.1. Регулярный и случайный потоки.

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

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

1. все заявки потока с точки зрения обслуживания являются равноправными;

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

Определение: Регулярным называются поток, если события в потоке следуют один за другим через строгие интервалы времени.

Функция f (х) плотности распределения вероятности случайной величины Т – интервала времени между событиями имеет при этом вид:

Где - дельта функция, М т - математическое ожидание, причем М т =Т, дисперсия D т =0 и интенсивность наступления событий в поток =1/M т =1/T.

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

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

Где, zi - значения Ti(i=1,n), В этом случае моменты наступления событий могут быть вычислены следующим образом

t 1 =t 0 +z1

t 2 =t 1 +z2

………,

2.2. Простейший пуассоновский поток.

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

Определение: Поток называется стационарным, если вероятность появления n событий на интервале времени (t,t+T) зависит от его расположения на временной оси t.

Определение: Поток событий называется ординарным, если вероятность появления двух или более событий в течении элементарного интервала времени D t есть величина бесконечно малая по сравнению с вероятностью появления одного события на этом интервале, т.е. при n=2,3,…

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

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

Доказано, что для простейшего потока число n событий попадающих на любой интервал z распределено по закону Пуассона:

(1)

Вероятность того, что на интервале времени z не появится ни одного события равна:

(2)

тогда вероятность противоположного события:

где по определению P(T это функция распределения вероятности Т. Отсюда получим, что случайная величина Т распределена по показательному закону:

(3)

параметр называют плотностью потока. Причем,

2.3.1. Введем величину a= х. В соответствии со свойствами Пуассоновского распределения при оно стремится к нормальному. Поэтому для больших а для вычисления Р{Х(а)меньше, либо равно n}, где Х(а) – случайная величина распределенная по Пуассону с матожиданием а можно воспользоваться следующим приближенным равенством:

Доказательство: пусть Т распределено по показательному закону: Предположим, что промежуток а уже длился некоторое время а< Т. Найдем условный закон распределения оставшейся части промежутка Т 1 =Т-а

Отсюда,

равносильно событию а, для которого P(а; с другой стороны

P(T>a)=1-F(a), таким образом

По характеру входной поток требований разделяется на детерминированный поток требований и стохастический (рис.2).

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

Рис.2. Классификация входного потока

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

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

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

Входной поток называется рекуррентным, если он характеризуется следующими свойствами:

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

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

• продолжительность интервалов между поступлениями требований статистически независимы;
• продолжительность интервалов описывается одной и той же плотностью распределения;
• вероятность поступления требований на достаточно малом интервале Δt зависит только лишь от величины Δt (это свойство называется стационарностью или однородностью прихода);
• вероятность поступления требований на интервале Δt не зависит от предыстории процесса;
• характер потока требований таков, что в любой момент времени может поступить только одно требование.

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

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

(1.1)

где λ - интенсивность поступления заявок в систему.

Если интервалы распределены по экспоненциальному закону, то процесс пуассоновский. Такие процессы называются М-процессами (Марковскими).

Кроме закона Пуассона часто применяется закон распределения Эрланга.

(1.2)

СМО с отказами

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

Состояние СМО характеризуется простаиванием или занятостью ее канала, т.е. двумя состояниями: S 0 - канал свободен и простаивает, S 1 - канал занят. Переход системы из состояния S 0 в состояние S 1 осуществляется под воздействием входящего потока заявок П вх, а из состояния S 1 в состояние S 0 систему переводит поток обслуживании П об: если в данный момент времени система находится в некотором состоянии, то с наступлением первого после данного момента времени СМО переходит в другое состояние. Плотности вероятностей перехода из состояния S 0 в S 1 и обратно равны соответственно λ и µ. Граф состояний подобной СМО с двумя возможными состояниями приведен на рис.3.

Рис.3. Граф состояний одноканальной СМО с отказами.

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

Таким образом, подобная СМО может находиться в одном из следующих (n+1) состояний: s 0 - все n каналов свободны; s 1 - занят только один из каналов, остальные (n-1) каналов свободны; s i - заняты i - каналов, (n-i) каналов свободны; s n - заняты все n каналов. Граф состояний такой СМО приведен на рис.4.

Рис.4. Граф состояний многоканальной СМО с отказами.

При этом имеет место а

Пользуясь общим правилом составления дифференциальных уравнений Колмогорова, можно для приведенных на рис.2 и рис.3 графов состояний составить системы дифференциальных уравнений:

например, для одноканальной СМО (рис.2) имеем:

для многоканальной СМО (рис.3) соответственно имеем:

Решив первую систему уравнений, можно найти значения p 0 (t) и p 1 (t) для одноканальной СМО и построить графики при трех случаях:

СМО с ожиданием

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

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

Рис.6. Граф состояний одноканальной СМО с ожиданием

Состояния СМО имеют следующую интерпретацию:

S 0 - канал свободен;

S 1 - канал занят (очереди нет);

S 2 - канал занят (одна заявка стоит в очереди);

S n - канал занят (n-1 заявок стоит в очереди);

S N - канал занят (N-1 заявок стоит в очереди).

Стационарный процесс в данной системе будет описываться следующей системой алгебраических уравнений:

(1.11)

где ρ=λ/µ; n - номер состояния.

Решение приведенной выше системы уравнений (1.10) для нашей модели СМО имеет вид:

(1.12)

(1.13)

Следует отметить, что выполнение условия стационарности для данной СМО необязательно, поскольку число допускаемых в обслуживающую систему заявок контролируется путем введения ограничения на длину очереди (которая не может превышать N-1), а не соотношением между интенсивностями входного потока, т.е. не отношением λ/µ=ρ. Определим характеристики одноканальной СМО с ожиданием и ограниченной длиной очереди, равной (N-1): вероятность отказа в обслуживании заявки:

(1.14)

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

(1.15)

абсолютная пропускная способность:

среднее число находящихся в системе заявок:

(1.17)

среднее время пребывания заявки в системе:

средняя продолжительность пребывания клиента (заявки) в очереди:

(1.19)

среднее число заявок (клиентов) в очереди (длина очереди):

. (1.20) .

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

Система может находиться в одном состоянии S 0 , S 1 , S 2 ,…,S k ,…,S n ,…, нумеруемых по числу заявок, находящихся в СМО: S0 - в системе нет заявок (все каналы свободны); S 1 - занят один канал, остальные свободны; S 2 - заняты два канала, остальные свободны; …, S k - занято k каналов, остальные свободны; …, S n - заняты все n каналов (очереди нет); S n +1 - заняты все n каналов, в очереди одна заявка; …, S n + r - заняты все n каналов, r заявок стоит в очереди, ….

среднее число заявок в очереди:

(1.32)

среднее число заявок в системе:

(1.31) .

24. Входящий поток требований

24.1 Структура СМО

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

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

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

где Т - среднее значение интервала между поступлением очередных требований.

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

Простейший поток обладает такими важными свойствами:

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

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

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

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

Практически любой поток требований, поступающий в систему обслуживания, является случайным процессом. Действительно, если мы примем t =0 за начальный момент, то во многих потоках (кроме того случая, когда требования поступают строго по расписанию) либо нельзя, либо довольно трудно точно предсказать момент поступления очередного требования, а также моменты поступления последующих требований. Например, нельзя точно указать моменты прихода клиентов в ателье, пациентов в больницу, поступления вызовов на АТС, оборудования в ремонтную мастерскую и т. д.

Следовательно, моменты поступления заявок, равно и интервалы между ними, есть, вообще говоря, независимые случайные величины. Тогда процесс поступления требований в систему массового обслуживания следуя рассматривать как вероятностный или случайный процесс. Обозначим такой процесс через Х(t ). Эта функция определяет число требований, поступивших в систему за промежуток времени . Для каждого фиксированного t функция Х(t ) есть случайная величина. Действительно, если выбрать промежутки времени даже одинаковой продолжительности, то в этом случае нельзя быть уверенным в том, что в каждый из этих промежутков поступит одно и то же число требований.

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

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

1. При всяком фиксированном t функция Х(t ), принимает целые неотрицательные значения 0, 1, 2,...,R,... и с возрастанием не убывает.

2. Число требований, поступивших за промежуток вре­мени , зависит от длины этого промежутка, т. е. от значе­ния t.

3. Реализации процесса представляют собой ступенчатые линии, чем-то непохожие одна на другую. Из теории случайных процессов известно, что процесс будет полностью определен с вероятностной точки зрения, если будут известны все его много­мерные законы распределения:

Однако отыскание такой функции в общем случае является весьма трудной, а иногда неразрешимой задачей. Поэтому на прак­тике стараются использовать процессы, которые обладают свой­ствами, позволяющими найти более простые способы их описания. К таким свойствам относятся:

Стационарность (лучше однородность во времени);

Отсутствие последействия (марковость), иногда говорят об отсутствии памяти;

Ординарность.

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

Поток требований называется стационарным или однородным во времени, если вероятность поступления определенного количе­ства требований в течение определенного промежутка времени за­висит только от длины промежутка, а не от его временного положения (иначе говоря, не зависит от начала отсчета). Таким обра­зом, для стационарного потока вероятность того, что за промежу­ток поступит ровно R требований, равна вероятности поступле­ния R требований за промежуток [а, а + t ] , где а>0 , т. е.

Это означает, что вероятностные характеристики потока (парамет­ры закона распределения) не должны изменяться во времени.

Свойством стационарности обладают многие реальные потоки требований, если рассматривать их в течение непродолжительных периодов. К таким потокам можно отнести: поток вызовов на АТС в определенные промежутки времени, поток покупателей в магазин, поток радиоаппаратуры, нуждающейся в ремонте, интенсивность движения пассажиров и т. п. Однако некоторые из перечисленных потоков изменяются в течение дня (вероятность вызовов в ночное время меньше чем днем, часы «пик» в работе городского транс­порта).

В некоторых потоках число требований, поступивших в систему после произвольного момента времени, не зависит от числа ранее поступивших требований и моментов их поступления, т. е. интер­валы между поступлениями требований считаются независимыми величинами и между ними нет связи. Будущее состояние системы не зависит от прошлого ее состояния. Поток, обладающий таким свойством, называют потоком без последействия или марковским. Свойство отсутствия последействия (отсутствия памяти) присуще многим реальным потокам. Например, поток вызовов на АТС является потоком без последействия, поскольку, как правило, оче­редной вызов поступает независимо от того, когда и сколько было вызовов до этого момента.

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

Если Р R >2 (h ) -вероятность появления за промежуток h более одного требования, то для ординарного потока должно быть:

,

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

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

Случайный процесс X (t ) (0≤ t <∞) целочисленными значениями называется процессом Пуассона, если он является процессом с независимыми приращениями или если любое приращение процесса за промежуток времени h распределено по закону Пуассона с параметром λ h , где λ>0 т.е.

В частности, если t =0, X(0)=0 , то (3) переписывается сле­дующим образом:

(4)

Здесь V r (h) означает вероятность того, что интересующее нас событие произойдет ровно R раз за промежуток времени h (с точки зрения теории массового обслуживания V r (h) опреде­ляет вероятность того, что за промежуток времени h в систему обслуживания поступит ровно R требований).

Смысл параметра X легко выяснить, если найти математиче­ское ожидание пуассоновского процесса: М [Х(t )]=М. При t = 1 получаем М[Х(1)]=1. Следовательно, есть среднее число заявок за единицу времени. Поэтому величину λ часто называют интенсивностью или плотностью потока.

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

1) Независимость приращений. В независимости приращений для процесса Пуассона заключается отсутствие последействия- марковость процесса.

2) Однородность во времени. Это означает, что вероятности V r (h) не зависят от начального момента t рассматриваемого промежутка , а зависят только от длины промежутка h :

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

Итак, одновременное поступление двух и более требований за малый промежуток времени h маловероятно, поэтому

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

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