МС лекции (1086519), страница 5

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

Текст из файла (страница 5)

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

,

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

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

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

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

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

или

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

,

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

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

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

1.3.Обзор методов решения задач массового обслуживания

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

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

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

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

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

Для сокращенного наименования систем массового обслуживания будем использовать обозначения вида А/В/n/m, где А указывает распределение интервалов между событиями, В – распределение времени обслуживания, n – число каналов, m – количество мест в очереди. Показательное распределение обозначим - М, Эрланговского порядка , постоянное время обслуживания или регулярный поток – D, распределение обслуживания общего, не конкретизируемого типа – G.

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

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

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

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

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

1. Процесс обслуживания как марковский случайный процесс.

Пусть система может находиться в состояниях , где n = 0,1,2 … - в системе находиться n заявок. Обозначим вероятность нахождения системы в конкретном состоянии в момент времени t через . Очевидно, что для каждого t

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

Каждый паре состояний можно поставить в соответствие условную вероятность того, что система находится в состоянии в момент t+1 при условии, что в момент t она находилась в состоянии n.

Очевидно, что для вероятности можно написать

, (*)

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

Если равна нулю, то переход из состояния n в невозможен.

Соотношение (*) может быть записано в векторной форме

(**)

где квадратная матрица J образована из элементов , удовлетворяющих условиям

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

Матрица, удовлетворяющая этим условиям, матрицей перехода, вероятности - вероятности перехода. Из (**) следует, что для однородной последовательности Маркова, определяемой как последовательность, для которой значения элементов матрицы J постоянны (не зависят от номеров состояний), имеем:

в частности

т.е. марковская последовательность целиком определяется матрицей перехода J и начальными условиями .

1. Расчет основных характеристик для различных типов СМО

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

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

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

Более компактно матрицу перехода можно представить в виде графа переходов, в котором вершины означают состояния системы, а дуги - вероятности переходов:

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

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

Построим по этому правилу систему дифференциальных уравнений

…

После преобразований получим

…

…

Эти уравнения могут быть решены при начальных условиях

n=n₀

Частотными методами с использованием преобразования Лапласа.

Чаще интересуются установившимися или стационарным режимом, для которого справедливо

В этом случае система дифференциальных уравнений преобразуется в систему линейных уравнений

Отсюда ,

Учитывая, что получаем

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

Установившийся режим не зависит от начальных условий. Получим некоторые числовые характеристики установившегося режима.

Среднее число заявок в системе

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

Среднее число заявок в очереди

или

Характеристики

Список файлов лекций