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

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

Задачи теории массового обслуживания (ТМО). Типы систем массового обслуживания (СМО) в соответствии с классификацией Кендалла. Простейший поток и поток Эрланга.

Процесс обслуживания как марковский процесс. Уравнения Колмогорова. Матрица переходов. Характеристики СМО.

Аналитические модели различных типов СМО, расчет характеристик сети СМО.

Методические указания

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

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

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

Фундаментальным вероятностным понятием, используемым в ТМО, является марковский процесс. Это процесс, дальнейшее поведение которого определяется только его состоянием в данный момент времени и не зависит от предистории процесса. СМО является марковской только при простейшем входном потоке и показательном времени обслуживания. В этом случае состояние системы полностью определяется числом находящихся в системе заявок k. Марковские процессы исследуются с помощью дифференциальных уравнений в частных производных, составленных для плотностей вероятностей состояний {Pk(t)/dt} (уравнения Колмогорова). Для стационарных состояний они обращаются в систему обыкновенных линейных уравнений, решение которой затруднения не вызывает.

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

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

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

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

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

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

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

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

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

НЕКОТОРЫЕ ВОПРОСЫ ТЕОРИИ МАССОВОГО

ОБСЛУЖИВАНИЯ
1.1.Общие сведения о моделях массового обслуживания
Задачи, связанные с работой систем массового обслуживания разного вида требований, возникают в разных областях техники, в организации производства и пр. Примерами систем и требований могут служить парикмахерская и клиенты, преподаватель и студенты, телефонная станция (как совокупность линий) и вызовы на разговор, ремонтная бригада вычислительного центра и отказы обслуживаемых ею машин. Как моменты прибытия требований, так и длительности обслуживания каждой заявки являются случайными. Поэтому основным математическим аппаратом для изучения функционирования таких систем является теория вероятностей.

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

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

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

- среднее число свободных обслуживающих приборов,

- стоимость ожидания одной заявки в единицу времени,

- стоимость простоя одного обслуживающего прибора в единицу времени.

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

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

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

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

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

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

в) с отказами и без отказов (в зависимости от того, разрешается входной заявке ждать в очереди или нет, если разрешается – ограничена очередь по длине или времени либо нет),

г) многофазные и однофазные: при последовательном процессе обслуживания заявки несколькими приборами,

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

е) одиночные и сети СМО: сложные комбинации всех рассматриваемых выше СМО.

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

Модели потоков событий.

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

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

Рекуррентный поток – для которого все функции распределения интервалов между заявками совпадают.

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

Для характеристики потоков очень часто вводят в рассмотрение вероятность появления числа событий в заданном интервале времени

Где n - число событий, появляющихся на интервале.

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

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

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

Интенсивностью потока называется предел

,

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

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

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

Пуассоновским поток называется потому, что подчиняется пуассоновском закону распределения

,

Где - интенсивность потока,

k - количество событий, появляющихся за время t.

Тогда вероятность появления одного события за малое время dt равна

А вероятность того, что за малое время dt не появится ни одно событие, учитывая условия ординарности, равна

Время между двумя последовательными наступлениями событий потока имеет экспоненциальную функцию распределения

или

Для показательного распределения

Где m_t - математическое ожидание,

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

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

Контрольные вопросы.

1. Почему простейший поток занимает центральное место в ТМО?

2. Является ли простейший поток потоком Эрланга и наоборот?

3. Перечислите типы СМО.

4. Постройте граф переходов для замкнутой многоканальной СМО.

5. Как по известным вероятностям состояний системы определить среднее количество заявок в СМО?