Главная Обратная связь

Дисциплины:

Архитектура (936)
Биология (6393)
География (744)
История (25)
Компьютеры (1497)
Кулинария (2184)
Культура (3938)
Литература (5778)
Математика (5918)
Медицина (9278)
Механика (2776)
Образование (13883)
Политика (26404)
Правоведение (321)
Психология (56518)
Религия (1833)
Социология (23400)
Спорт (2350)
Строительство (17942)
Технология (5741)
Транспорт (14634)
Физика (1043)
Философия (440)
Финансы (17336)
Химия (4931)
Экология (6055)
Экономика (9200)
Электроника (7621)






Классификация систем массового обслуживания



 

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

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

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

,

где l > 0 – постоянное число, характеризующее интенсивность потока (см. разд. 5.3).

Попытки указать достаточно общие условия, при выполнении которых такой поток действительно имеет место, были предприняты давно. В монографии А.Я. Хинчина “Работы по математической теории массового обслуживания” эти условия были сведены к трем:

- стационарность;

- отсутствие последействия;

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

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

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

Стационарность потока означает его однородность по времени: вероятностные характеристики такого потока не должны меняться в зависимости от времени. В частности, вероятность появления требований в промежутке времени (t, t+t) не зависит от t и является функцией только переменных k и t.

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

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

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



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

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

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

Ординарность потока означает, что требования в потоке приходят по одиночке, а не парами, тройками и т.д.

Ординарность потока требований выражает собой условие практической невозможности появления двух или нескольких требований в один и тот же момент времени. Чтобы точнее сформулировать это условие, обозначим через Р > 1(t) вероятность появления в промежутке длины t двух или более требований. Условие ординарности потока состоит в том, что при t ® 0

или, как мы будем записывать в дальнейшем,

Р > 1(t) = О(t).

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

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

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



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

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

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

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

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

Рассмотрим на оси Оt простейший поток событий и сохраним в нем не все точки, а только каждую вторую, остальные выбросим (рисунок 12).

 

 

Рисунок 12. Поток Эрланга второго порядка

 

В результате такой операции “прореживания” или “просеивания” образуется снова поток событий, он называется потоком Эрланга второго порядка.

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

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

 

 

Рисунок 13. Поток Эрланга четвертого порядка

 

Очевидно, простейший поток представляет собой частный случай потока Эрланга, а именно, поток Эрланга 1-го порядка Э1.

Интервал времени Т между соседними событиями в потоке Эрланга k-го порядка представляет собой сумму k независимых случайных величин – расстояний между событиями в исходном простейшем потоке

Т = Т1 + Т2 + … Тк = .

Каждая их этих случайных величин распределена по показательному закону

Р1(t) = lе-lt (t > 0).

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

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

Конкретную реализацию случайного процесса обозначим через х(t).

В качестве примера рассмотрим работу автомата по продаже газированной воды. В некоторые промежутки времени автомат будет свободен, а в другие – занят. Условимся для определенности считать, что если автомат в момент t свободен, то x(t) = 0, а если занят, то x(t) = 1. Одна из возможных реализаций случайного процесса х(t) показана на рисунке 14.

 

 

Рисунок 14. Один из вариантов реализации случайного процесса х(t)

 

В данном примере работа автомата характеризуется одной случайной величиной x(t), которая в любой момент t равна либо 0, либо 1 (автомат свободен, автомат занят). При этом, если в момент t0 = 0 автомат был свободен, то, вообще говоря, нельзя предсказать заранее, когда его займут первый раз (t1), когда он после этого освободится (t2), когда его займут вторично (t3) и т.д.

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

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

Пусть имеется в системе x дискретный случайный процесс, протекающий в системе с возможными состояниями х0, х1, х2, …, хi, …, хj, … .

Обозначим условную вероятность того, что в момент t = t0 + t система будет в состоянии хj, если она была в момент t0 в состоянии хi, через Рij(t0,t).

Другими словами, все вероятностные характеристики марковского процесса в будущем (при
t > t0) зависят лишь от того, в каком состоянии этот процесс находится в настоящий момент времени t0, и не зависят от того, каким образом этот процесс протекает до момента t0 (в прошлом). Короче, можно сказать так: для марковского процесса “будущее зависит от прошлого только через настоящее”.

Различают два типа марковских случайных процессов: с дискретным временем и с непрерывным временем. Марковским случайным процессом с дискретным временем называется процесс, у которого переходы из одного состояния в другое возможны в строго определенные заранее моменты времени t1, t2, …, tk, … .

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

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

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

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

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

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

Таким образом, для исследования процесса нужно:

1) указать все состояния, в которых может находиться система;

2) составить граф состояний, т.е. указать пути возможных непосредственных переходов системы из состояния в состояние;

3) для каждого возможного перехода указать соответствующую интенсивность lij(t) потока событий, переводящего систему из состояния хi непосредственно в состояние хj;

4) указать, в каком состоянии находится система в начальный момент времени (при t = 0).

Рассмотрение марковских случайных процессов, протекающих в системах со счетным множеством состояний, будем начинать всегда с описания самих состояний и составления графа состояний, на котором из каждой строчки проставляется интенсивность соответствующего пуассоновского потока событий. Граф состояний с интенсивностями пуассоновских потоков событий полностью определяет процесс, протекающий в системе, если указано начальное состояние (или начальные состояния) системы. На рисунке 15 показан граф системы с двумя состояниями х0, х1: переход системы из состояния х0 в х1 происходит под воздействием пуассоновского потока событий с интенсивностью l0,1(t), из х1 в х0 – с интенсивностью l10(t).

 

 

Рисунок 15. Граф системы с двумя состояниями х0 и х1

По числу каналов СМО могут быть одноканальными и многоканальными.

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

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

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

1. Системы с отказами. В таких системах заявка, поступившая в момент, когда все каналы заняты, получает “отказ”, покидает СМО и в дальнейшем процессе не участвует.

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

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

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

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

 

 


Эта страница нарушает авторские права

allrefrs.ru - 2018 год. Все права принадлежат их авторам!