Формула литтла

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

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

Обозначим: X(t)—число заявок, прибывших в СМО до момента t, Y(t) — число заявок, покинувших СМО до момента t. И та, и другая функции являются случайными и меняются скачком (увеличиваются на единицу) в моменты приходов заявок (X(t)) и уходов заявок (Y(t)). Для любого момента t их разность Z(t) = X(t) - Y(t) — это число заявок, находящихся в СМО.

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

(2)

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

, (3)

где сумма распространяется на все заявки, пришедшие за время Т.

Разделим правую и левую часть (3) на длину интервала Т. Получим, с учетом (2):

(4)

Разделим и умножим правую часть (4) на интенсивность :

(5)

Величина T — это среднее число заявок, пришедших за время Т. Если мы разделим сумму всех времен t_i на среднее число заявок, то получим среднее время пребывания заявки в системе W_сист .

Итак,

(6)

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

Точно таким же образом выводится вторая формула Литтла, связывающая среднее время пребывания заявки в очереди W_оч и среднее число заявок в очереди L_оч.

СХЕМА РАЗМНОЖЕНИЯ И ГИБЕЛИ

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

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

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

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

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

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

Процесс (или схема) размножения и гибели опи­сывается графом состояний, приведенным на рис. 1.

Рис. 1. Граф состояний схемы размножения и гибели

Число состояний равно m+1. Из каждого состояния w_k, k = 1,2,…, m-1, возможны переходы только в со­седние состояния w_k-1 и w_k+1. Переход w_k→w_k+1 (k = 0, 1, 2, …, m-1) означает рождение некоторого объекта, а переход w_k→w_k-1 (k = 1, 2, …, m) – его ги­бель. Таким образом, индекс k в обозначении w_k пока­зывает число объектов, находящихся в системе.

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

ОПИСАНИЕ С ПОМОЩЬЮ МАРКОВСКОГО ПРОЦЕССА

Марковский процесс относится к случайным процес­сам с дискретными состояниями и непрерывным вре­менем, то есть нахождение в состояниях и переходы между ними происходят в непрерывном времени. Пе­реход из состояния w_i в состояние w_j за достаточно ма­лый промежуток времени описывается вероятностью:

,

где – параметр, называемый интенсивностью пере­хода w_i→w_i-1 в непрерывном времени, –беско­нечно малая величина более высокого порядка малости по сравнению с при . Если интенсивности не зависят от времени, то процесс будет однородным, а вероятности будут зависеть только от w_i, w_j и дли­ны и не будут зависеть от положения промежутка на оси времени. Для однородного марковского процес­са время нахождения в каждом состоянии распределе­но по показательному закону.

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

,, (1)

, ,

где – параметр, равный отношению интенсивности переходак интенсивности перехода.

Можно сформулировать правило вычисления пре­дельной вероятности состояния w_k (k = 1, 2, …, m): ве­роятность состояния равна произведению парамет­ров для всех переходов левее состояния, умноженному на вероятность крайнего левого состоя­ния. Следует отметить, что при имеет место процесс чистого размножения.

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