Понятие марковского случайного процесса

Глава 15

ЭЛЕМЕНТЫ ТЕОРИИ МАССОВОГО ОБСЛУЖИВАНИЯ

Основные понятия. Классификация СМО

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

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

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

Глава 15

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

 

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

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

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

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

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

¹ Здесь и в дальнейшем средние величины понимаются как математи­ческие ожидания соответствующих случайных величин.

Понятие марковского случайного процесса

Процесс работы СМО представляет собой случайный процесс.

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

Процесс называется процессом с дискретными состояниями, ес­ли его возможные состояния S\, S₂, S3... можно заранее перечис­лить, а переход системы из состояния в состояние происходит мгновенно (скачком). Процесс называется процессом с непрерыв­ным временем, если моменты возможных переходов системы из состояния в состояние не фиксированы заранее, а случайны.

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

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

Пример марковского процесса: система S — счетчик в такси. Состояние системы в момент / характеризуется числом километ­ров (десятых долей километров), пройденных автомобилем до данного момента. Пусть в момент /q счетчик показывает Sq. Веро­ятность того, что в момент / > % счетчик покажет то или иное число километров (точнее, соответствующее число рублей) S\, зависит от Sq, но не зависит от того, в какие моменты времени изменялись показания счетчика до момента t₀.

Многие процессы можно приближенно считать марковскими. Например, процесс игры в шахматы; система S — группа шахмат­ных фигур. Состояние системы характеризуется числом фигур противника, сохранившихся на доске в момент /₀- Вероятность того, что в момент / > /₀ материальный перевес будет на стороне одного из противников, зависит в первую очередь от того, в ка-

Глава 15

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

 

ком состоянии находится система в данный момент /₀, а не от того, когда и в какой последовательности исчезли фигуры с доски до момента /q-

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

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

15Л. Построить граф состояний следующего случайного процесса: устройство S состоит из двух узлов, каждый из которых в случай­ный момент времени может выйти из строя, после чего мгновен­но начинается ремонт узла, продолжающийся заранее неизвестное случайное время.

Решение. Возможные состояния системы: Sq — оба узла исправны; S_} — первый узел ремонтируется, второй исправен; 5*2 — второй узел ремонтируется, первый исправен; S$ — оба узла ремонтируются. Граф системы приведен на рис. 15.1.

Рис. 15.1

Стрелка, направленная, например, из So в.Si, означает переход системы в момент отказа первого узла, из S\ в S₀ — переход в момент окончания ремонта этого узла.

На графе отсутствуют стрелки из So в S^ и из S[ в 62. Это объ­ясняется тем, что выходы узлов из строя предполагаются незави­симыми друг от друга и, например, вероятностью одновременного выхода из строя двух узлов (переход из Sq в 5₃) или одновремен­ного окончания ремонтов двух узлов (переход из Sj в Sq) можно пренебречь. ►

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

Потоки событий

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

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

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

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

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

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

■ Поток событий называется потоком без последействия, если для

■ любых двух непересекающихся участков времени i\ и тг ^— число

■ событий, попадающих на один из них, не зависит от числа собы-

■ тий, попадающих на другие. Например, поток пассажиров, вхо-
Ш дящих в метро, практически не имеет последействия. А, скажем,

Глава 15

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

 

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

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

Поток событий называется простейшим (или стационарным пуассоновским), если он одновременно стационарен, ординарен и не имеет последействия. Название "простейший" объясняется. тем, что СМО с простейшими потоками имеет наиболее про­стое математическое описание. Заметим, что регулярный поток не является "простейшим", так как он обладает последействи­ем: моменты появления событий в таком потоке жестко зафик­сированы.

Простейший поток в качестве предельного возникает в тео­рии случайных процессов столь же естественно, как в теории вероятностей нормальное распределение получается в качестве предельного для суммы случайных величин: при наложении (суперпозиции) достаточно большого числа п независимых, стацио­нарных и ординарных потоков (сравнимых между собой по интен-сивностям Xj (i=J,2,..., п) получается поток, близкий к простей­шему с интенсивностью X, равной сумме интенсивностей входящих потоков, т.е.

1=1

Рассмотрим на оси времени Ot (рис. 15.2) простейший поток событий как неограниченную последовательность случайных то­чек.

Т ,т

_____ i______ Г Z^j_____ ШШПШШШ ______ *,

О t

Рис. 15.2

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

PJd=^-e~^x\ (15.1)

m\

для которого математическое ожидание случайной величины рав­но ее дисперсии: а = а² = Хт.

В частности, вероятность того, что за время т не произойдет ни одного события (/я=0), равна

ад = е~"^т- (15.2)

Найдем распределение интервала времени Т между произволь­ными двумя соседними событиями простейшего потока.

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

Р(Т >t) = e~^x', (15.3)

а вероятность противоположного события, т.е. функция рас­пределения случайной величины Т, есть

F(t) = Р(Т < /) = 1 - e"^w. (15.4)

Плотность вероятности слу­чайной величины есть произ­водная ее функции распреде­ления (рис. 15.3), т.е.

_ф(/) = F\t) = Хе'^к'. (15.5)

Рис. 15.3

Распределение, задаваемое плотностью вероятности (15.5) или функцией распределения (15.4), называется показатель­ным (или экспоненциальным). Таким образом, интервал вре­мени между двумя соседними произвольными событиями имеет показательное распре­деление, для которого матема-

Глава 15

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

 

тическое ожидание равно среднему квадратическому отклонению случайной величины

а = о = ± (15.6)

и обратно по величине интенсивности потока X.

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

Другими словами, для интервала времени Т между двумя по­следовательными соседними событиями потока, имеющего пока­зательное распределение, любые сведения о том, сколько времени протекал этот интервал, не влияют на закон распределения ос­тавшейся части. Это свойство показательного закона представляет собой, в сущности, другую формулировку для "отсутствия после­действия" — основного свойства простейшего потока.

Для простейшего потока с интенсивностью X вероятность по­падания на элементарный (малый) отрезок времени At хотя бы одного события потока равна согласно (15.4)

Рь, = Р(Т < At) = 1 - е~^ш * X&t. (15.7)

(Заметим, что эта приближенная формула, получаемая заменой

функции е~^УЛ{ лишь двумя первыми членами ее разложения в ряд по степеням At, тем точнее, чем меньше At).

1234Следующая ⇒

Поделиться:

Воспользуйтесь поиском по сайту: