СМО с ограниченным временем ожидания. Замкнутые СМО

  Итак, на систему, находящуюся в состоянии  , действует простейший поток событий. Как только появится первое событие этого потока, происходит «перескок» системы из состояния  в состояние  (на графе состояний по стрелке  ).

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

  

  Рис. 3. Размеченный  граф состояний системы

  На этом рисунке   - интенсивности потока отказов;   - интенсивности потока восстановлений.

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

  Пусть система  находится в состоянии S₀. В состояние S₁ ее переводит поток отказов первого станка. Его интенсивность равна:

  

  где   - среднее время безотказной работы первого станка.

  Из состояния S₁ в S₀ систему переводит поток «окончаний ремонтов» первого станка. Его интенсивность равна:

  

  где   - среднее время ремонта первого станка.

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

  Пусть рассматриваемая  система S имеет  -возможных состояний  . Вероятность  -го состояния   - это вероятность того, что в момент времени  , система будет находиться в состоянии  . Очевидно, что для любого момента времени сумма всех вероятностей состояний равна единице:

  

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

  Что будет  происходить с вероятностями  состояний при  ? Будут ли   стремиться к каким-либо пределам? Если эти пределы существуют и не зависят от начального состояния системы, то они называются финальными вероятностями состояний.

  

  где   - конечное число состояний системы.

  Финальные вероятности состояний – это уже не переменные величины (функции времени), а постоянные числа. Очевидно, что:

     

  Финальная вероятность состояния   – это по–существу среднее относительное время пребывания системы в этом состоянии.

  Например, система S имеет три состояния S₁, S₂ и S₃. Их финальные вероятности равны соответственно 0,2; 0,3 и 0,5. Это значит, что система в предельном стационарном состоянии в среднем 2/10 времени проводит в состоянии S₁, 3/10 – в состоянии S₂ и 5/10 – в состоянии S₃.

  Правило составления системы уравнений Колмогорова: в каждом уравнении системы в левой его части стоит финальная вероятность данного состояния  , умноженная на суммарную интенсивность всех потоков, ведущих из данного состояния, а в правой его части – сумма произведений интенсивностей всех потоков, входящих в  -е состояние, на вероятности тех состояний, из которых эти потоки исходят.

  Пользуясь этим правилом, напишем систему уравнений для нашего примера:

   .

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

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

  Четвертое уравнение отбрасываем, добавляя вместо него нормировочное условие:

   .

   .

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

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

  Станок 1 ремонтируется  долю времени, равную:  . Станок 2 ремонтируется долю времени, равную:  . Возникает задача оптимизации. Пусть мы можем уменьшить среднее время ремонта первого или второго станка (или обоих), но это нам обойдется в определенную сумму. Спрашивается, окупит ли увеличение дохода, связанное с ускорением ремонта, повышенные расходы на ремонт? Нужно будет решить систему четырех уравнений с четырьмя неизвестными.

  1.5 Задачи теории массового обслуживания

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

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

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

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

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

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

  1.6 Классификация систем массового  обслуживания

  Первое деление (по наличию очередей):

  1.         СМО с отказами;

  2.         СМО с очередью.

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

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

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

  Итак, например, рассматриваются следующие СМО:

  ·           СМО с нетерпеливыми заявками (длина очереди и время обслуживания ограничено);

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

  Кроме этого  СМО делятся на открытые СМО и  замкнутые СМО.

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

  Классификация СМО далеко не ограничивается приведенными разновидностями, но этого достаточно. 

  2. Системы массового обслуживания с ожиданием  

  2.1 Одноканальная СМО  с ожиданием  

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

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

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

    — канал свободен;

    — канал занят, очереди нет;

    — канал занят, одна заявка стоит в очереди;

    — канал занят, k-1 заявок стоят в  очереди;

    — канал занят, т-заявок стоят в  очереди.

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

  

  Рис. 4. Одноканальная  СМО с ожиданием

  Изображенная  на рис. 4 схема представляет собой  схему размножения и гибели. Напишем выражения для предельных вероятностей состояний:

    (5)

  или с использованием:  :

    (6)

  Последняя строка в (6) содержит геометрическую прогрессию с первым членом 1 и знаменателем р, откуда получаем:

    (7)

  в связи  с чем предельные вероятности  принимают вид:

   (8).

  Выражение (7) справедливо только при  < 1 (при  = 1 она дает неопределенность вида 0/0). Сумма геометрической прогрессии со знаменателем  = 1 равна m+2, и в этом случае:

   .

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

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

    (9).

  Относительная пропускная способность:

    (10).

  Абсолютная  пропускная способность:

   .

  Средняя длина  очереди. Найдем среднее число  -заявок, находящихся в очереди, как математическое ожидание дискретной случайной величины R—числа заявок, находящихся в очереди: