Теория очередей. закономерности образования очередей и способы предсказания среднего размера очереди. Основы теории очередей Теория очередей математические модели очереди

Теория массового обслуживания (англоязычное название - queueing theory - теория очередей) возникла в начале 20 века. Ее основоположником считается датский ученый А.К. Эрланг, работавший в шведской телефонной компании и занимавшийся вопросами проектирования телефонных сетей. В дальнейшем теория получила интенсивное развитие и применение в различных областях науки, техники, экономики, производства. Это объясняется тем, что эта теория изучает широко распространенные в человеческой практике ситуации, когда имеется некоторый ограниченный ресурс и множество (поток) запросов на его использование, следствием чего являются задержки или отказы в обслуживании некоторых запросов. Стремление понять объективные причины этих задержек или отказов и по возможности уменьшить их воздействие является побудительным мотивом развития теории массового обслуживания.

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

Что, в свою очередь, лишает автора математического результата «обратной связи», важной для правильного выбора направления для дальнейшего обобщения результатов и объектов исследования. Эта серьезная проблема подмечена в обзоре известного специалиста Р. Сиски, отмечающего опасность возможности распада единой теории массового обслуживания на абстрактную и инженерную. Прямым следствием этой проблемы при написании книги обычно является вопрос выбора языка и соответствующего уровня строгости изложения результатов. Данная книга ориентирована как на специалистов в области теории массового обслуживания, так и на специалистов в области ее приложения к исследованию реальных объектов (в первую очередь, компьютерных сетей). Поэтому в данной главе приведем краткий обзор методов анализа систем массового обслуживания на среднем уровне строгости. Предполагается знакомство читателя с теорией вероятностей в рамках курса для технического вуза. При необходимости, некоторые сведения приводятся непосредственно в тексте.

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

Входящий поток запросов (заявок, требований, сообщений, вызовов);

Количество и типы обслуживающих устройств (приборов);

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

Времена обслуживания запросов на приборах;

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

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

История

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

Поток

Однородный поток

Поток заявок однороден , если:

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

Поток без последействия

Поток без последействия , если число событий любого интервала времени ( t {\displaystyle t} , ) не зависит от числа событий на любом другом не пересекающемся с нашим ( t {\displaystyle t} , t + x {\displaystyle t+x} ) интервале времени.

Стационарный поток

Поток заявок стационарен , если вероятность появления n событий на интервале времени ( t {\displaystyle t} , t + x {\displaystyle t+x} ) не зависит от времени t {\displaystyle t} , а зависит только от длины x {\displaystyle x} этого участка.

Простейший поток

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

Число n {\displaystyle n} событий такого потока, выпадающих на интервал длины x {\displaystyle x} , распределено по Закону Пуассона :

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

Нормальный поток

Cтационарный поток без последействий, для которого интервалы между событиями распределены по нормальному закону, называется нормальным потоком : f (t) = 1 2 π σ t exp ⁡ − 1 2 (t − m t σ t) 2 {\displaystyle f(t)={\frac {1}{{\sqrt {2\pi }}\sigma _{t}}}\exp {-{\frac {1}{2}}\left({\frac {t-m_{t}}{\sigma _{t}}}\right)^{2}}} .

Поток Эрланга

Потоком Эрланга k {\displaystyle k} -го порядка называется стационарный поток без последействий, у которого интервалы между событиями представляют собой сумму k + 1 {\displaystyle k+1} независимых случайных величин, распределенных одинаково по экспоненциальному закону с параметром λ {\displaystyle \lambda } . При k = 0 {\displaystyle k=0} поток Эрланга является простейшим потоком.

Плотность распределения случайной величины T-интервала между двумя соседними событиями в потоке Эрланга k {\displaystyle k} -го порядка равна: f k (t) = λ (λ t) k Γ (α) exp ⁡ − β t {\displaystyle f_{k}(t)={\frac {\lambda (\lambda t)^{k}}{\Gamma (\alpha)}}\exp {-\beta t}} , t > 0 , α ⩾ 1 {\displaystyle t>0,\alpha \geqslant 1} .

Гамма-поток

Гамма-потоком называется стационарный поток без последействий, у которого интервалы между событиями представляют собой случайные величины, подчиненные гамма-распределению с параметрами α {\displaystyle \alpha } и β {\displaystyle \beta } : f (t) = β α t α − 1 k ! exp ⁡ − λ t {\displaystyle f(t)={\frac {\beta ^{\alpha }t^{\alpha -1}}{k!}}\exp {-\lambda t}} , t > 0 {\displaystyle t>0} , где Γ (α) = ∫ 0 ∞ x α − 1 exp ⁡ − x d x {\displaystyle \Gamma (\alpha)=\int _{0}^{\infty }x^{\alpha -1}\exp {-x}dx} .

При α = k + 1 {\displaystyle \alpha =k+1} гамма-поток является потоком Эрланга k {\displaystyle k} -го порядка.

Мгновенная плотность

Мгновенная плотность (интенсивность ) потока равна пределу отношения среднего числа событий, приходящихся на элементарный интервал времени ( t {\displaystyle t} , t + x {\displaystyle t+x} ) к длине интервала ( x {\displaystyle x} ), когда последний стремится к нулю.

или, для простейшего потока,

где M (x) {\displaystyle M(x)} равно

Очередей теория

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

Пример. Пусть имеется один обслуживающий прибор, на который поступает случайный поток требований. Если в момент поступления требования прибор свободен, то оно сразу начинает обслуживаться. В противном случае оно становится в очередь и прибор обслуживает требования одно за другим в порядке их поступления. Пусть а - среднее число требований, поступающих за время одного обслуживания, а Т - длительность периода занятости, то есть промежутка времени от момента занятия прибора каким-либо требованием, заставшим прибор свободным, до первого момента полного освобождения прибора. О. т. показывает, что при естественных допущениях математическое ожидание Т равно m = 1/(1 - а), а дисперсия равна (1 + a ) m 3 (так, при а = 0,8 соответствующие значения равны 5 и 225). Таким образом, для «хорошо загруженного» обслуживающего прибора (то есть при а, близких к 1) среднее значение m случайной величины Т является весьма ненадёжной характеристикой Т.

Лит.: Гнеденко Б. В., Коваленко И. Н., Введение в теорию массового обслуживания, М., 1966; Приоритетные системы обслуживания, М., 1973.

Ю. В. Прохоров.

Большая советская энциклопедия. - М.: Советская энциклопедия . 1969-1978 .

• Очанка
• Очередные задачи советской власти

Смотреть что такое "Очередей теория" в других словарях:

ОЧЕРЕДЕЙ ТЕОРИЯ - в математике раздел теории массового обслуживания, где изучаются системы, в которых требования, застающие систему занятой, не теряются, а ожидают ее освобождения и затем обслуживаются в том или ином порядке … Большой Энциклопедический словарь

очередей теория - (матем.), раздел теории массового обслуживания, где изучаются системы, в которых требования, застающие систему занятой, не теряются, а ожидают её освобождения и затем обслуживаются в том или ином порядке. * * * ОЧЕРЕДЕЙ ТЕОРИЯ ОЧЕРЕДЕЙ ТЕОРИЯ, в… … Энциклопедический словарь

ОЧЕРЕДЕЙ ТЕОРИЯ - см. Массового обслуживания теория … Большой энциклопедический политехнический словарь

ОЧЕРЕДЕЙ ТЕОРИЯ - раздел массового обслуживания теории. О. т. изучает системы, в к рых требования, застающие систему занятой, не теряются, а ожидают ее освобождения и затем обслуживаются в том или ином порядке (часто с предоставлением приоритета определенным… … Математическая энциклопедия

ОЧЕРЕДЕЙ ТЕОРИЯ - (матем.), раздел теории массового обслуживания, где изучаются системы, в к рых требования, застающие систему занятой, не теряются, а ожидают её освобождения и затем обслуживаются в том или ином порядке … Естествознание. Энциклопедический словарь

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

теория массового обслуживания - — теория массового обслуживания Раздел исследования операций, который рассматривает разнообразные процессы в экономике, а также в телефонной связи, здравоохранении и других… … Справочник технического переводчика

Теория массового обслуживания

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

Теория очередей - см. Теория массового обслуживания … Экономико-математический словарь

Книги

• Логистика и теория очередей
• Логистика и теория очередей , Рыжиков Ю.И.. В учебном пособии рассматривается современное состояние теории логистики, обсуждаются элементы математической модели управления запасами и основы численных методов теории очередей;…

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

Теория игр - это метод, используемый для оценки влияния какого-либо действия на конкурентов. Моделями теории очередей можно пользоваться в соответствии со спросом на них. Модели управления запасами помогают руководителю синхронизировать размещение заказов на ресурсы и оптимизировать их объемы, а также определять оптимальное для склада количество готовой продукции . Модели линейного программирования позволяют установить оптимальный способ распределения дефицитных ресурсов между конкурирующими потребностями в них. Имитационное моделирование - это использование устройства, которое имитирует реальный мир. В экономическом анализе используется ряд методов для определения экономического положения организации или осуществимости действия с экономической точки зрения.  

Настоятельная потребность маркетинга и. предпринимательства в целом в полном и объективном освещении рыночных процессов , в достоверном предсказании возможного развития рынка. Понятие маркетингового исследования , его роль в бизнесе и удовлетворении информационно-аналитических потребностей маркетинга. Место маркетингового исследования в разработке стратегии маркетинга , планировании маркетинга и его контроллинге. Предмет и объекты маркетингового исследования . Цели маркетингового исследования . Принципы маркетингового исследования . Два направления маркетингового исследования формализация и качественные оценки. Достоинства и недостатки каждого из них. Возможности их консолидации. Основы методологии маркетингового исследования . Особая роль статистики и эконометрики в маркетинговых исследованиях . Теория массового обслуживания (теория очередей). Понятие статистического банка (набора статистических приемов обработки информации).  

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

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

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

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

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

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

Читатель найдет здесь доступное описание основных экономико-математических методов , построенных как на традиционном аппарате математики и логики, известном из школьных программ (дроби, проценты, уравнения, прогрессии, геометрические и логические задачи), так и на основе методов исследования операций - современном математическом аппарате , специально созданном для решения тех задач, с которыми элементарная математика не справляется. Это методы оптимизации (линейное, нелинейное и динамическое программирование), теория вероятностей и математическая статистика , теория массового обслуживания (теория очередей), метод статистических испытаний (Монте-Карло), теория игр и статистических решений, сетевое планирование.  

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

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

Центральным понятием теории очередей является функция стоимости, равная  

Если величина N больше 1, вычисления приобретают более сложный характер. Общая формула приведена в Приложении 1, где также обсуждаются другие проблемы теории очередей. Для JV, равных 2 и 3, формулы выглядят следующим образом  

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

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

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

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

Рыжиков Ю.И. Теория очередей и управление запасами . -СПб. Питер, 2001.-384 с.  

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

Часто бывает, что запросы на обслуживание отдельных клиентов или заказы индивидуальных покупателей продукции поступают в систему случайным образом. Это так называемая проблема случайных клиентов. Единственный путь, который позволяет удовлетворять таких заказчиков, если накопление продукции и ожидание клиентов исключается, это составление внешнеориентированного расписания в сочетании с общим избытком мощности системы (избытком всех ее ресурсов). На практике такое расточительное резервирование встречается редко и поэтому части заказчиков, обращающихся в систему, приходится либо предлагать ожидание, либо отказывать, неся при этом определенные экономические             Управление качеством (1974) -- [

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

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

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

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

Основные элементы системы следующие:

1. Входящий поток требований (интенсивность входящего потока );

2. Каналы обслуживания (число каналов n , среднее число занятыхk , производительность );

3. Очередь требований (среднее число заявок z , среднее время пребывания одной заявкиt );

4. Выходящий поток требований (интенсивность входящего потока  ).

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

 закрытые – источник в системе и оказывает на нее влияние;

 открытые – вне системы и не оказывает влияния.

По фазам обслуживания СМО можно разделить на:

 однофазные – один этап обслуживания,

 многофазные – два и более этапов.

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

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

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

1. по принципу «первый пришел – первый обслужен»;

2. по принципу «первый пришел – последним обслужен» (например, отгрузка однородной продукции со склада).

3. случайно;

4. с приоритетом. При этом приоритет может быть абсолютным (более важная заявка вытесняет обычную) иотносительным (важная заявка получает лишь «лучшее» место в очереди).

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

Пример . УстройствоS состоит из двух узлов,

каждый из которых в случайный момент времени может выйти из строя, после чего мгновенно начинается ремонт узла, продолжающийся заранее неизвестное случайное время. Возможные состояния системы: S 0 – оба узла исправны;S 1 – первый узел ремонтируется, второй исправен;S 2 – первый узел исправен, второй ремонтируется;S 3 – оба узла ремонтируются.

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

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

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

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

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

Поток событий называетсястационарным , если его вероятностные характеристики не зависят от времени. В частности у стационарного потока λ(i )= λ (поток автомобилей на проспекте в часы пик).

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

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

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

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

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

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

Для простейшего потока с интенсивностью λ вероятность попадания на элементарный (малый) отрезок времени Δt хотя бы одного события потока равна.

Ординарный поток заявок без последствий описывается распределением (законом) Пуассона с параметром λτ :

, (1)

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

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

. (2)

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

Решение. а) Случайная величина Х – число вызовов за две минуты – распределена по закону Пуассона с параметром λτ =1,2·2=2,4. Вероятность того, что вызовов не будет (m =0), по формуле (2):

б) Вероятность одного вызова (m =1):

в) Вероятность хотя бы одного вызова:

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

Рассмотрим математическое описание Марковского процесса с дискретными состояниями и непрерывным временем на примере процесса, граф которого изображен на рис. 1. Будем полагать, что все переходы системы из состояния S i в S j происходят под воздействием простейших потоков событий с интенсивностями состояний λ ij (i , j =0,.1,2,3).

Так как переход системы из состояния S 0 в S 1 будет происходить под воздействием потока отказов первого узла, а обратный переход из состояния S 1 в S 0 – под воздействием потока и событий, связанных с окончанием ремонтов первого узла и т.д.

Граф состояний системы с проставленными у стрелок интенсивностями будем называтьразмеченным . Рассматриваемая система имеет четыре возможных состояния:S 0 ,S 1 ,S 2 ,S 3 . Назовем вероятностьюi -го состояния вероятностьp i (t ) того, что в моментt система будет находиться в состоянииS i . Очевидно, что для любого моментаt сумма вероятностей всех состояний равна единице:
.

Предельная вероятность состояния S i имеет – показывает среднее относительное время пребывания системы в этом состоянии(если предельная вероятность состояния S 0 , т.е. p 0 =0,5, то это означает, что в среднем половину времени система находится в состоянии S 0 ).

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

(3)

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

Пример . Найти предельные вероятности для системы, граф состояний которого изображен на рис. выше. при λ 01 =1, λ 02 =2, λ 10 =2, λ 13 =2, λ 20 =3, λ 23 =1, λ 31 =3, λ 32 =2 .

Система алгебраических уравнений для этого случая согласно (3) имеет вид:

Решив линейную систему уравнений, получим p 0 = 0,4, p 1 = 0,2, p 2 = 0,27, p 3 = 0,13; т.е. в предельном стационарном режиме система S в среднем 40% времени будет находиться в состоянии S 0 (оба узла исправны), 13% в состоянии S 1 (первый узел ремонтируется, второй работает), 27% - в состоянии S 2 (второй узел ремонтируется, первый работает) и 13% в состоянии S 3 (оба узла ремонтируются).

Определим чистый доход от эксплуатации в стационарном режиме рассмотренной системы S в условиях, что в единицу времени исправная работа узла один и узла два приносит доход соответственно 10 и 6 денежных единиц, а их ремонт требует соответственно затрат 4 и 2 денежных единицы. Оценим экономическую эффективность имеющейся возможности уменьшения вдвое среднего времени ремонта каждого из двух узлов, если при этом придется вдвое увеличить затраты на ремонт каждого узла (в единицу времени).

Для решения этой задачи с учетом полученных значений p 0 , p 1 , p 2 , p 3 определим долю времени исправной работы первого узла, т.е. p 0 + p 2 = 0,4+0,27 = 0,67 и долю времени исправной работы второго узла p 0 + p 1 = 0,4+0,2 = 0,6. В то же время первый узел находится в ремонте в среднем долю времени равную p 1 + p 3 = 0,2+0,13 = 0,33, а второй узел p 2 + p 3 = 0,27+0,13 = 0,40. Поэтому средний чистый доход в единицу времени от эксплуатации системы равен Д =0,67·10+0,6·6–0,33·4–0,4·2=8,18 ден.ед. уменьшение вдвое среднего времени ремонта каждого узла будет означать увеличение вдвое интенсивностей потока «окончания ремонтов» каждого узла, т.е. теперь λ 10 =4, λ 20 =6, λ 31 =6, λ 32 =4 и система уравнений, описывающая стационарный режим системы S , будет иметь вид:

.

Решив систему получим p 0 = 0,6, p 1 = 0,15, p 2 = 0,2, p 3 = 0,05. Учитывая, что p 0 + p 2 = 0,6+0,2 = 0,8,

p 0 + p 1 = 0,6+0,15 = 0,75, p 1 + p 3 = 0,15+0,05 = 0,2, p 2 + p 3 = 0,2+0,05 = 0,25, а затраты на ремонт первого и второго узла составляют соответственно 8 и 4 ден.ед., вычислим чистый средний доход в единицу времени: Д1 =0,8·10+0,75·6–0,2·8–0,25·4=9,99 ден.ед.

Так как Д1 больше Д (примерно на 20%), то экономическая целесообразность ускорения ремонта узлов очевидна.

5. Процесс размножения и гибели Рассматриваемый в СМО процесс размножения и гибели характеризуется тем, что если все состояния системы пронумероватьS 1 ,S 2 ,… ,S n то из состоянияS k (k < n ) можно попасть либо в состояниеS k -1 , либо в состояниеS k +1 .

Для предельных вероятностей характерна следующая система уравнений:

(4)

к которой добавляется условие:

Из этой системы можно найти предельные вероятности. Получим:

, (6)

,
, …,
. (7)

Пример. Процесс гибели и размножения представлен графом. (рис).

Найти предельные вероятности состояний.

Решение. По формуле (6) найдем
,

по (7)
,
,

т.е. в установившемся стационарном режиме в среднем 70,6% времени система будет находиться в состоянии S 0 , 17,6% – в состоянии S 1 и 11,8% – в состоянии S 2 .

6. Системы с отказами В качестве показателей эффективности СМО с отказами будем рассматривать:

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

Q – относительную пропускную способность, т.е. среднюю долю пришедших заявок, обслуживаемых системой;

– вероятность отказа, т.е. того, что заявка покинет СМО необслуженной;

– среднее число занятых каналов (для многоканальной системы).