Обнинский Институт Атомной Энергетики

МОДЕЛИРОВАНИЕИНФОРМАЦИОННЫХСИСТЕМ Гулина Ольга Михайловна Сopyright © 2001 by Nataly Pashkova

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

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

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

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

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

Классификация СМО СМО с отказами и СМО с очередью Однофазное или многофазное обслуживание «Открытые» или «замкнутые» СМО

Терминология ТМО (по Кендаллу) Для обозначения той или иной модели используют 3 символа: | | первый характеризует входной поток требований, второй – распределение длительностей обслуживания, третий - число приборов в обслуживающей системе

Распределения вероятностей

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

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

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

Стационарность Поток событий называется стационарным, если вероятность попадания того или иного числа событий на участок времени длиной зависит только от длины участка и не зависит от того, где именно на оси (0,t) расположен этот участок. λ - интенсивность потока событий – - среднее число событий в единицу времени λ=const

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

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

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

Пуассоновский поток Вероятность попадания на участок длиной ровно m событий (m=0,1,…) где а - среднее число событий, приходящееся на участок

Распределение времени между событиями в простейшем потоке

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

Ординарность P 0 ( t) - вероятность того, что на участке t не будет ни одного события, P 1 ( t) - вероятность того, что на нем появится одно событие P 1 ( t) t.

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

Уравнения Колмогорова

Придадим t малое приращение t и найдем вероятность того, что в момент (t+ t) система будет находиться в состоянии S 1. Как это событие может произойти? 1) в момент t система уже была в состоянии S 1, а за время t не вышла из этого состояния, 2) в момент t система была в состоянии S 3, а за время t перешла из него в S 1.

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