Характеристики потока

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

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

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

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

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

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

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

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

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

Примеры:

- поток вызовов на телефонной станции;

- поток включений приборов в бытовой электросети;

- поток грузовых составов, поступающих на железнодорожную станцию;

- поток неисправностей (сбоев) вычислительной машины;

- поток выстрелов, направляемых на цель, и т. д.

Входной поток – поток заявок на обслуживание системой.

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

Входной поток заявок однозначно задается последовательностью моментов времени поступления заявок в систему t₁, t₂, . . . , t_k, . . ..

Чтобы описать случайный поток однородных событий как случайный процесс достаточно задать закон распределения, характеризующий последовательность случайных величин t₁, t₂, . . . t_k, Обычно вместо t₁, t₂, . . . t_k, . . задают случайные величины ξ₁, ξ₂, . . . , ξ_к, . . ., являющиеся длинами интервалов времени между последовательными моментами t_j:

t₁ = ξ₁,

t₂ = ξ₁ + ξ₂ ,

. . . . . . . .

t_к = ξ₁ + ξ₂ +. . . ξ_к._.

Для задания входного потока достаточно получить последовательность случайных величин ξ₁, ξ₂, . . , ξ_i, . . . с заданным законом распределения.

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

Источник – первопричина возникновения заявок независимо от их физической природы.

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

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

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

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

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

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

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

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

Для потока однородных событий получены аналитические решения оценки качества обслуживания.

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

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

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

Для решения многих прикладных задач можно ограничиваться частными случаями потоков.

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

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

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

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

Стационарность потока означает его однородность по времени; вероятностные характеристики такого потока не меняются в зависимости от времени.

Для стационарного потока характерна постоянная плотность потока λ - среднее число событий в единицу времени. Или: вероятность р_к (t, t₀) появления к событий за промежуток времени (t₀, t₀ +t) не зависит от t₀, а зависит только от t и к.

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

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

Ординарный поток – вероятность появления двух и более событий в течение элементарного интервала времени ∆t есть величина бесконечно малая по сравнению с вероятностью появления одного события на этом интервале.

Условие ординарности означает, что заявки поступают в систему поодиночке, а не парами, тройками и т.д.

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

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

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

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

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

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

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

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

Если поток событий не имеет последействия, ординарен, но не стационарен, он называется нестационарным пуассоновским потоком. В таком потоке интенсивность λ (среднее число событий в единицу времени) зависит от времени: λ = λ(t), тогда как для простейшего потока λ=const.

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

Для простейшего потока (потока Пуассона) вероятность P_k (t) наступления k событий за интервал времени длины t выражается законом распределения Пуассона (вероятность того, что за время t произойдет к событий) - поэтому часто простейший поток называют пуассоновским потоком:

с математическим ожиданием a = λt.

Здесь λ – плотность потока (количество заявок в единицу времени).

Введем состояние системы следующим образом: система находится в состоянии Е_s в момент времени t, если к этому моменту в систему поступило s заявок. Вероятность того, что в момент времени t + ∆t система останется в том же состоянии, т.е. что за интервал времени ∆t в систему не поступит ни одной заявки:

S = 0, 1, 2, …,

разлагая в ряд, имеем w_ss = 1 – λdt.

Вероятность поступления в систему хотя бы одной заявки w_ss+1 = λdt.

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

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

Матрица переходов для простейшего потока и соответствующий граф

Матрица переходов Е0 Е1 Е2 Е3 . . . Е0 1 – λdt λdt . . . Е1 1 – λdt λdt . . . Е2 1 – λdt λdt . . . Е3 1 – λdt . . . . . . . . . . . . . . . . . . . .

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

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

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

В некоторый момент времени t в систему поступает заявка. Если в этот момент времени имеются свободные каналы, заявка принимается к обслуживанию. В противном случае, т.е. когда все каналы заняты, заявка остается в систем в течение некоторого времени (τ_пр – время пребывания заявки в системе). За этот интервал времени она должна быть принята к обслуживанию, в противном случае считается потерянной – получает отказ.

Система с отказами при τ_пр = 0, система с ожиданием τ_пр = ∞, система с ограниченным ожиданием при 0 < τ_пр < ∞.

Заявка, принятая к обслуживанию занимает один из каналов в системе в течение времени обслуживания τ_з (время занятости канала). По окончании этого времени канал может приступить к обслуживанию новой заявки.

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

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

Чаще всего встречается показательный закон обслуживания.

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

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

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

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

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

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

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

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

(t)=e^-, (1)

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

Если вывод системы S из какого-то ее состояния s_i происходит под воздействием нескольких простейших потоков, то непрерывная случайная величина T, представляющая собой время пребывания системы (подряд) в данном состоянии s_i, также распределена по показательному закону, в котором  - суммарная интенсивность всех потоков, выводящих систему S из данного состояния s_i.