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

Лекции 3-4

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

Определение 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 ) удовлетворяют условию: .

Моделирование цепей Маркова

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

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

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

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

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

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

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

Для рассмотренного примера граф состояния имеет вид, представленный на рис. 3.2. Стрелка, направленная из S₀ в S₁, означает переход в момент отказа первого узла; стрелка, направленная обратно, из S₁в S₀, – переход в момент окончания ремонта этого узла. Аналогично вычисляются интенсивности потоков событий, переводящих систему по всем стрелкам графа.

Рис. 3.2. Граф состояния

Рассмотрим простейший поток событий с интенсивностью λ и произвольный элементарный (очень маленький) участок времени Δt.

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

Элемент вероятности (с точностью до малых величин более высокого порядка по сравнению с Δt) равен

p_Δt ₌ λ Δt ,

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

Найдем все интенсивности потоков событий, переводящих систему из состояния в состояние. Пусть система находится в состоянии S₀. Какой поток событий переводит ее в состояние S₁? Очевидно, поток отказов первого узла. Его интенсивность λ₁равна единице, деленной на среднее время безотказной работы первого узла. Какой поток событий переводит систему обратно из S₁в S₀? Очевидно, поток "окончаний ремонтов" первого узла. Его интенсивность μ₁равна единице, деленной на среднее время ремонта первого узла. Аналогично вычисляются интенсивности потоков событий, переводящих систему по всем стрелкам графа рис. 3.2.

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

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

Сформулируем общее правило составления уравнений Колмогорова.

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

Пользуясь этим правилом, запишем уравнения Колмогорова для системы S, размеченный граф состояний которой дан на рис. 3.2:

(3.1)

Чтобы решить эту систему уравнений найти вероятности состояний, прежде всего надо задать начальные условия. Начальные условия отражают состояние системы в начальный момент времени. Если, например, система при t = 0 была в состоянии S_k, то p_k(0) = 1, p_i(0) = 0 при i = 1, n и i ≠ k. Эти уравнения можно решать аналитически, но это удобно только тогда, когда число уравнений не превышает двух (иногда трёх). В случае, когда уравнений оказывается больше, применяют численные методы.

Что будет происходить с вероятностями состояний при ? Будут ли p₁(t), ..., p_n(t) стремиться к каким-то пределам?

Если эти пределы существуют и не зависят от начального состояния системы, то они называются финальными вероятностями состояний: . p_i – среднее относительное время пребывания системы в i-ом состоянии.

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

Финальную вероятность состояния S_i можно истолковать как среднее относи тельное время пребывания системы в этом состоянии.

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

Для рассматриваемого примера из системы дифференциальных уравнений (3.1) получим:

(3.2)

Зададимся численными значениями интенсивностей

λ₁ = 1, λ₂ = 2, μ₁ = 2, μ₂ = 3

и решим систему (3.2). Пожертвуем четвертым уравнением, добавив вместо него нормировочное условие:

Решая эту систему алгебраических уравнений, получим:

р₀ = 0.4; р₁ = 0.2; р₂ ≈ 0.27; p₃ ≈ 0.13.

т.е. в предельном, стационарном режиме система S в среднем 40% времени будет проводить в состоянии S₀ (оба узла исправны), 20% – в состоянии S₁ (первый узел ремонтируется, второй работает), 27% – в состоянии S₂ (второй узел ремонтируется, первый работает) и 13% – в состоянии S₃ полной негодности (оба узла ремонтируются). Знание этих финальных вероятностей может помочь оценить среднюю эффективность работы системы и загрузку ремонтных органов.

Предположим, что система S в состоянии S₀ (полностью исправная) приносит в единицу времени доход 8 (условных единиц), в состоянии S₁ – доход 3, в состоянии S₂ – доход 5, в состоянии S₃ – вообще не приносит дохода. Тогда в предельном, стационарном режиме средний доход в единицу времени будет

W = 0.4*8 + 0.2*3 + 0.27*5 = 5.15

Теперь оценим загрузку ремонтных органов (рабочих), занятых ремонтом узлов 1 и 2.

Узел 1 ремонтируется долю времени, равную р₁ + p₃= 0.2 + 0.13 = 0.33.

Узел 2 ремонтируется долю времени р₂ + p₃= 0.4.

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

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

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

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

Устройства, удовлетворяющие запросу на обслуживание, называются обслуживающими устройствами (аппаратами, приборами).

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

Канал – обслуживающее устройство в цехе, пропускающее через себя требование.

Время обслуживания – период времени, в течение которого обслуживается требование.

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

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

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

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

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

Дата добавления: 2018-10-26; просмотров: 290; Мы поможем в написании вашей работы!

Поделиться с друзьями:

12 3 4 Следующая ⇒

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