Лекции по "Системы массового обслуживания"

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

1. Лекция

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

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

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

Заявки поступают в СМО обычно не регулярно, а случайно, образуя так называемый случайный поток заявок (требований). 

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

Показатели эффективности СМО:

- среднее число заявок, обслуживаемых в единицу времени;

- сред­нее число заявок в очереди;

- среднее время ожидания обслужива­ния;

-  вероятность отказа в обслуживании без ожидания;

- вероят­ность того, что число заявок в очереди превысит определенное значение и т.п.

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

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

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

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

Приоритет мо­жет быть:

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

- относительным, когда более важ­ная заявка получает лишь "лучшее" место в очереди.

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

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

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

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

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

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

Пример марковского процесса: система S — счетчик в такси.

Многие процессы можно приближенно считать марковскими. 

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

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

Решение. Возможные состояния системы: S0 — оба узла исправны; S1 — первый узел ремонтируется, второй исправен; S2 — второй узел ремонтируется, первый исправен; S3 — оба узла ремонтируются.

2. Лекция

Потоки событий. Уравнения Колмогорова.

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

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

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

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

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

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

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

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

Уравнения Колмогорова. Предельные вероятности состояний

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

воздействием потока отказов первого узла, а обратный переход из состояния S1 в S0 — под воздействием потока "окончаний ремонтов" первого узла и т.п.

Граф состояний системы с проставленными у стрелок интен­сивностями называется размеченным.

Вероятностью i-го состояния называется вероятность pi(t) того, что в момент t система будет находиться в состоянии Si.

Система дифференциальных уравнений

Колмогорова для вероятностей состояний:

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

В записанной системе независимых уравнений на единицу меньше общего числа уравнений. Поэтому для решения системы необхо­димо добавить уравнение

pi(t)=1              (*)

Уравнения Колмогорова дают возможность найти все вероят­ности состояний как функции времени.

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

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

(λ01+ λ02)P0 = λ10 P1+ λ20 P2

(λ10+ λ13)P 1= λ01 P0+ λ31 P3

(λ20+ λ23)P2 = λ02 P0+ λ32 P3            

               (λ31+ λ32)P3 = λ13 P1+ λ23 P2               (**)

Систему  можно составить непосредственно по размеченному графу состояний, если руководствоваться правилом, согласно которому слева в

уравнениях стоит предельная вероятность данного состояния pi, умноженная на суммарную интенсивность всех потоков, ведущих из данного состояния, а справа — сумма произведений интенсивностей всех потоков, входящих в i-e состояние, на вероятности тех состояний, из которых эти потоки исходят.

Задача 2. Найти предельные вероятности для системы S из задачи 1,  при  λ01=l,  λ02= 2,  λ10=2,  λ13=2,  λ20=3,  λ23=1,   λ31=3,   λ32=2. 

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

3P0=2P1+3P2

4P1=P0+3P3

4P2=2P0+2P3

P0+ P1+P2+P3=1

(Здесь мы вместо одного "лишнего" уравнения системы (**) записали нормировочное условие (*)).

Решив систему, получим P0=0,40, P1=0,20, P2=0.27, P3=0,13, т.е. в предельном, стационарном режиме система S в среднем 40% времени будет находиться в состоянии S0 (оба узла исправны), 20% — в состоянии S1 (первый узел ремонтируется, второй работает), 27% — в состоянии S2 (второй узел ремонтируется, первый работает) и 13% времени — в состоянии S3 (оба узла ремонтируются).

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

Решение. Из задачи 2 следует, что в среднем первый узел исправно работает долю времени, равную P0+P2=0,40+0,27=0,67, а второй узел — P0+P1=0,40+0,20=0,60. В то же время первый узел находится в ремонте в среднем долю времени, равную P1+P3=0,20+0,13=0,33, а второй узел - P2+P3=0,27+0,13=0,40. Поэтому средний чистый доход в единицу времени от эксплуатации систе­мы, т.е. разность между доходами и затратами, равен

Д=0,67•10+0,60•6-0,33•4-0,40•2=8,18 ден.ед.

Уменьшение вдвое среднего времени ремонта каждого из узлов будет означать увеличение вдвое интенсивностей Потока "окончаний ремонтов" каждого узла, т.е. теперь λ10=4, λ20=6, λ31=6, λ32=4 система уравнений, описывающая стационарный режим системы S, вместе с нормировочным условием примет вид: