Графы СМО с простейшими потоками

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

Дисциплина очереди (или принцип построения очереди) определяет порядок, в соответствии с которым выбираются клиенты из очереди для обслуживания. Наиболее распространенный принцип построения очереди основан на правиле " первым пришел - первым обслуживаешься" (FIFO - First-In-First-Out). Среди других правил, определяющих принципы построения очередей, укажем правило " последним пришел - первым обслуживаешься" (LIFO - Last-In-First-Out) и дисциплину очереди, определяемую случайным правилом отбора клиентов (SIRO - Service-In-Random-Out). Кроме того, клиенты могут выбираться из очереди в соответствии с заданным приоритетом.

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

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

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

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

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

Обозначения для характеристики СМО имеют следующую структуру: 1/2/3, где 1 – закон распределения входящего потока, 2 – закон распределения потока обслуживания, 3 – число средств обслуживания (каналов). Пр: M/G/3, где М – простейший поток (пуассоновский), G – поток без конкретного закона распределения.

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

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

- интенсивность перехода из состояния i в состояние j, - вероятность нахождения в состоянии .

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

Марковская цепь описывается уравнением Колмогорова (система диф-ых уравнений 1 порядка):

(равно 0, т.к. процесс стационарный и вероятностные хар-ки не меняются со временем).

и т.д.

.

1.Одноканальная система с отказами: М/М/1

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

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

Возможны 2 состояния: - канал свободен, - канал занят.

2. Многоканальная система с отказами: М/М/n

n – число каналов

- интенсивность обслуживания 1 канала (все каналы одинаковы)

- все каналы свободны, - 1 канал занят, остальные свободны, - все n каналов заняты.

3.Одноканальная система с ожиданием: М/М/1

m – число мест в очереди

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

4. Многоканальная система с ожиданием: М/М/n

- канал свободен, - все n каналов заняты, нет заявок в очереди, - все n каналов заняты, 1 заявка в очереди, - все n каналов заняты и заняты все m мест в очереди.

5. Многоканальная система с ограниченным временем ожидания: М/М/n

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