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

Определение 1. Пусть имеется некоторая физическая система S, которая с течением времени меняет своё состояние (переходит из одного состояния в другое), причём заранее неизвестным, случайным образом. Тогда мы будем говорить, что в системе S протекает случайный процесс.

Под «физической системой» можно понимать что угодно: техническое устройство, предприятие, живой организм и т.д.

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

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

Пусть в настоящий момент t₀ система находится в определённом состоянии S₀. Мы наблюдаем процесс со стороны и в момент t₀ знаем состояние системы S₀ и всю предысторию процесса, все, что было при t<t₀. Нас, естественно, интересует будущее: t>t₀. Можем ли мы его предугадать? В точности – нет. Наш процесс случайный, следовательно – непредсказуемый. Но какие-то вероятностные характеристики процесса в будущем мы найти можем. Например, вероятность того, что через некоторое время t система S окажется в состоянии S₁ или сохранит состояние S₀ и т.д.

Если процесс марковский, то предсказывать можно, только учитывая настоящее состояние системы S₀ и забыв о его «предыстории» (поведение системы при t<t₀). Само состояние S₀, разумеется, зависит от прошлого, но как только оно достигнуто, о прошлом можно забыть. Т.е. в марковском процессе «будущее зависит от прошлого только через настоящее».

Пример.Система S – счётчик Гейгера, на который время от времени попадают космические частицы; состояние системы в момент времени t характеризуется показаниями счётчика – числом частиц, пришедших до данного момента. Пусть в момент t₀ счётчик показывает S₀. Вероятность того, что в момент t>t₀ счётчик покажет то или другое число частиц S₁ (или менее S₁) зависит от S₀, но не зависит от того, в какие именно моменты приходили частицы до момента t₀.

На практике часто встречаются процессы, которые если не в точности марковские, то могут быть в каком-то приближении рассмотрены как марковские. Например, S – группа самолётов, участвующих в воздушном бою. Состояние системы характеризуется числом самолётов «красных» – x и «синих» – y, сохранившихся (не сбитых) к какому-то моменту. В момент t₀ нам известны численности сторон x₀ и y₀. Нас интересует вероятность того, что в какой-то момент времени t₀+t численный перевес будет на стороне «красных». От чего зависит эта вероятность? В первую очередь от того, в каком состоянии находится система в данный момент времени t₀, а не от того, когда и в какой последовательности погибали сбитые до момента времени t₀ самолёты.

В сущности, любой процесс можно рассматривать как марковский, если все параметры из «прошлого», от которых зависит "будущее", перенести в "настоящее". Например, пусть речь идёт о работе какого-то технического устройства; в какой-то момент времени t₀ оно ещё исправно, и нас интересует вероятность того, что оно проработает ещё время t. Если за настоящее время считать просто «система исправна», то процесс, безусловно, не марковский, потому что вероятность, что она не откажет за время t, зависит, в общем случае, от того, сколько времени она уже проработала и когда был последний ремонт. Если оба эти параметра (общее время работы и время после ремонта) включить в настоящее состояние системы. То процесс можно будет считать марковским.

Определение 3. Процесс называется с дискретными состояниями, если его возможные состояния S₁, S₂,... можно заранее перечислить (перенумеровать), и переход системы из состояния в состояние происходит "скачком", практически мгновенно.

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

Мы будем рассматривать только процессы с дискретными состояниями.

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

Рис.3.1

Возможные состояния системы (Рис.3.1):

S₀ – оба узла исправны;

S₁ – первый узел ремонтируется, второй исправен;

S₂ – второй узел ремонтируется, первый исправен;

S₃ – оба узла ремонтируются.

Стрелка, направленная из S₀ в S₁ означает момент отказа первого узла и т.д. На рисунке нет стрелки из состояния S₀ в состояние S₃, поскольку вероятность того, что два прибора откажут одновременно, стремится к нулю.

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

Важнейшей характеристикой потока событий является его интенсивность l – среднее число событий, приходящееся на единицу времени. Интенсивность потока может быть постоянной (l = const), так и переменной, зависящей от времени. Например, поток автомашин, движущихся по улице, днём интенсивнее, чем ночью, а поток автомашин с 14-ти до 15-ти часов дня можно считать постоянным.

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

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

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

Например, поток вызовов, поступающих на АТС между 13 и 14 часами. Практически стационарен, но тот же поток в течение суток уже не стационарен.

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

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

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

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

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

Для описания случайного процесса, протекающего в системе с дискретными состояниями S₁, S₂, ..., S_n часто пользуются вероятностями состояний p₁(t), ..., p_n(t), где p_k(t) – вероятность того, что в момент времени t система находится в состоянии S_k. Вероятности p_k(t) удовлетворяют условию: .

Определение 11. Марковский случайный процесс с дискретными множествами возможных значений (состояний цепи) S₁, S₂,..., S_n и соответствующие им моменты времени t₁, t₂,..., t_n, называется цепью Маркова.

Если число возможных состояний n конечно, то цепь называется
конечной.

Вместо значений моментов времени можно указывать их номер. Разность между двумя соседними значениями аргумента t_k+i – t_k называется
шагом.

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

· вероятности состояний p₁(t),...,p_n(t), где p_k(t) – вероятность того, что в момент времени t система находится в состоянии S_k. Вероятности p_k(t) удовлетворяют условию: .

· вероятности p_ij перехода из состояния i в состояние j. Вероятности p_i,j(t) удовлетворяют условию: .

Дата добавления: 2015-01-19; просмотров: 176; Нарушение авторских прав

Мы поможем в написании ваших работ!