Структура СМО и ее основные характеристики

ЗАДАЧИ И МОДЕЛИ ТМО

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

Например: АТС, магазины, различные технические системы, системы военного назначения и т.п.

Такие системы обычно рассматривают как Системы Массового Обслуживания (СМО).

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

По числу каналов обслуживания СМО могут быть одноканальными и многоканальными.

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

Например:

1. АТС – многоканальная система, в которую поступают вызовы от абонентов на обслуживание (соединение с другим абонентом). Если каналы (линии связи) занят, то при наборе первых [трех] цифр возникает сигнал «занято» и заявка получает отказ. Очередь на обслуживание отсутствует.

2. Обслуживание M станков-автоматов N рабочими (N≤ M). В их обязанности входит контроль, наладка станков, заправка их сырьем, устранение неисправностей и т.п. Каждый рабочий одновременно может обслуживать только один станок. Если число отказавших станков больше числа рабочих (каналов обслуживания), то образуется очередь на обслуживание.

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

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

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

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

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

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

*) А.А. Марков (1856-1922) – профессор Петербургского университета, ученик П.Л.Чебышева, один из крупнейших представителей петербургской школы теории вероятностей. Основные работы Маркова по теории вероятностей посвящены предельным теоремам для сумм независимых величин, в том числе связанных в цепь.

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

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

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

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

 

 

СТРУКТУРА СМО И ЕЕ ОСНОВНЫЕ ХАРАКТЕРИСТИКИ

В общем виде СМО можно представить как:

 

Система обслуживания

Входной поток   требований

Выходной поток   требований

 

 

Входной поток требований –случайная исследовательность требований,поступающих на обслуживание. Его основные характеристики:

· распределение числа требований в единицу времени;

· распределение времени между двумя соседними требованиями;

· ограниченность потока (ограничен, неограничен).

Система обслуживания характеризуется:

· механизмом обслуживания и дисциплиной обслуживания.

Механизм обслуживания задается:

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

· пропускной способностью (число каналов обслуживания);

· доступностью для обслуживания (полнодоступные – возможны всегда и неполнодоступные – обслуживание лишь в определенные периоды).

Дисциплина обслуживания – регламентирует порядок поступления требований на обслуживание из очереди:

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

- с приоритетами, - когда порядок обслуживания определяется не местом в очереди, а рангом требования. При этом приоритеты бывают:

· абсолютные – требование более высокого ранга исключает из идущего обслуживания требования меньшего ранга;

· относительные - начинает обслуживаться раньше требований низкого ранга.

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

Системы с потерями (отказами) или системы без ожидания. В них требование, поступившее в систему в момент, когда все каналы заняты, покидает систему.

Эффективность функционирования таких систем характеризуется:

· -вероятностью потери требования (отказа);

· -среднее число отказов за заданный временной интервал;

· -среднее число занятых каналов;

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

Такие системы характеризуются:

· -средней длиной очереди;

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

· -средним числом занятых каналов.

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

· -среднее число требований, покинувших систему до начала обслуживания;

· -среднее число требований, покинувших систему во время обслуживания;

· -время обслуживания требований, покинувших систему во время обслуживания.

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

Схематически СМО можно представить в виде

 

Для удобства в 1953 году Д.Г.Кендалл предложил классифицировать СМО по совокупности трех основных признаков для подобных СМО. А именно

A/b/n,

где:

a - характер входящего потока, а конкретнее закон распределение интервала между требованиями;

b - закон распределения времени обслуживания одного требования;

n - число одновременно обслуживаемых требований (число каналов СМО).

Для обозначения вида закона распределения входного потока (a) и потока обслуживания (b) обычно используют следующие обозначения:

- М – марковское – ‘экспоненциальный закон распределения интервалов времени между требованиями входными и обслуженными;

- D – детерминированные интервалы времени между требованиями;

- Е_к - распределение Эрланга К-ого порядка;

- N – нормальное распределение;

G – произвольный закон распределения.

Кроме этого часто дополнительно указывают:

m – максимальную длину очереди (максимальное число требований в системе);

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

Так, например, М/М/3 /m=0 обозначает трехканальную СМО без очереди с простейшим потоком на входе и экспоненциальным распределением времени обслуживания, а Е/D/1/m обозначает одноканальную СМО с Эрланговским потоком, постоянным временем обслуживания и ограниченной очередью.    

 

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