Ячейка памяти компьютера состоит из. Логическое строение оперативной памяти в графическом виде. Устройство и принцип работы оперативной памяти

4 – Основы теории массового обслуживания.

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

Под «физической системой» можно понимать что угодно: техническое устройство, предприятие, живой организм и т.д.

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

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

Пусть в настоящий момент t 0 система находится в определенном состоянии S 0 . Мы наблюдаем процесс со стороны и в момент t 0 знаем состояние системы S 0 и всю предысторию процесса, все, что было при t < t 0 . Нас, естественно. Интересует будущее: t > t 0 . Можем ли мы его предугадать? В точности – нет. Наш процесс случайный, следовательно – непредсказуемый. Но какие-то вероятностные характеристики процесса в будущем мы найти можем. Например, вероятность того, что через некоторое время t система S окажется в состоянии S 1 или сохранит состояние S 0 и т.д.

Если процесс марковский, то предсказывать можно, только учитывая настоящее состояние системы S 0 и забыв о его «предыстории» (поведение системы при t < t 0 ). Само состояние S 0 , разумеется, зависит от прошлого, но как только оно достигнуто, о прошлом можно забыть. Т.е. в марковском процессе «будущее зависит от прошлого только через настоящее» .

Пример. Система S – счетчик Гейгера, на который время от времени попадают космические частицы; состояние системы в момент времени t характеризуется показаниями счетчика – числом частиц, пришедших до данного момента. Пусть в момент t 0 счетчик показывает S 0 . Вероятность того, что в в момент t > t 0 счетчик покажет то или другое число частиц S 1 (или менее S 1 ) зависит от S 0 , но не зависит от того, в какие именно моменты приходили частицы до момента t 0 .

На практике часто встречаются процессы, которые если не в точности марковские, то могут быть в каком-то приближении рассмотрены как марковские. Например, S ­ – группа самолетов, участвующих в воздушном бою. Состояние системы характеризуется числом самолетов «красных» – x и «синих» – y , сохранившихся (не сбитых) к какому-то моменту. В момент t 0 нам известны численности сторон x 0 и y 0 . Нас интересует вероятность того, что в какой-то момент времени t 0 + t численный перевес будет на стороне «красных». От чего зависит эта вероятность? В первую очередь от того, в каком состоянии находится система в данный момент времени t 0 , а не от того, когда и в какой последовательности погибали сбитые до момента времени t 0 самолеты.

В сущности любой процесс можно рассматривать как марковский, если все параметры из «прошлого», от которых зависит «будущее», перенести в «настоящее». Например, пусть речь идет о работе какого-то технического устройства; в какой-то момент времени t 0 оно ещё исправно, и нас интересует вероятность того, что оно проработает ещё время t . Если за настоящее время считать просто «система исправна», то процесс безусловно не марковский, потому что вероятность, что она не откажет за время t , зависит, в общем случае, от того, сколько времени она уже проработала и когда был последний ремонт. Если оба эти параметра (общее время работы и время после ремонта) включить в настоящее состояние системы. То процесс можно будет считать марковским.

Определение 3. Процесс называется с дискретными состояниями, если его возможные состояния S 1 , S 2 ,... можно заранее перечислить (перенумеровать), и переход системы из состояния в состояние происходит «скачком», практически мгновенно.

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

Мы будем рассматривать только процессы с дискретными состояниями.

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

Рис.4.1

Возможные состояния системы:

S 0 – оба узла исправны;

S 1 – первый узел ремонтируется, второй исправен;

S 2 – второй узел ремонтируется, первый исправен;

S 3 – оба узла ремонтируются.

Стрелка, направленная из S 0 в S 1 означает момент отказа первого узла и т. д. На рисунке нет стрелки из состояния S 0 в состояние S 3 , поскольку вероятность того, что два прибора откажут одновременно, стремится к нулю.

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

Важнейшей характеристикой потока событий является его интенсивность l – среднее число событий, приходящееся на единицу времени. интенсивность потока может быть постоянной (l = const ), так и переменной, зависящей от времени. Например, поток автомашин, движущихся по улице, днем интенсивнее, чем ночью, а поток автомашин с 14-ти до 15-ти часов дня можно считать постоянным.

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

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

Например, поток вызовов, поступающих на АТС между 13 и 14 часами. Практически стационарен, но тот же поток в течение суток уже не стационарен.

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

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

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

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

Определение 10. Поток событий называется простейшим (или стационарным Пуассоновским), если он обладает сразу тремя свойствами: стационарен, ординарен и не имеет последействия, а сам входной поток распределен по закону Пуассона ().

Для описания случайного процесса, протекающего в системе с дискретными состояниями S 1 , S 2 , ..., S n часто пользуются вероятностями состояний p 1 ( t ),..., p n ( t ) , где p k ( t ) – вероятность того, что в момент времени t система находится в состоянии S k . Вероятности p k ( t ) удовлетворяют условию: .

Если процесс, протекающий в системе с дискретными состояниями и непрерывным временем является марковским, то для вероятностей состояний p 1 ( t ), ..., p n ( t ) можно составить систему линейных дифференциальных уравнений. При составлении этих уравнений удобно пользоваться графом состояний системы, на котором против каждой стрелки, ведущей из состояния в состояние, проставлена интенсивность потока событий, переводящего систему по стрелке (рис.4.2):

Рис.4.2 l ij – интенсивность потока событий, переводящего систему из состояния S i в состояние S j . Правило создания системы линейных дифференциальный уравнений для нахождения вероятностей состояний. Для каждого состояния выписывается собственное уравнение. В левой части каждого уравнения стоит производная , а в правой – столько членов, сколько стрелок связано непосредственно с данным состоянием; если стрелка ведет в данное состояние, то член имеет знак «+», иначе - знак «–». Каждый член равен интенсивности потока событий, переводящего систему по данной стрелке, умноженной на вероятность того состояния, из которого стрелка выходит. Т.о. система линейных дифференциальных уравнений в нашем случае имеет вид:

Начальные условия для интегрирования такой системы отражают состояние системы в начальный момент времени. Если, например, система при t =0 была в состоянии S k , то . Эти уравнения можно решать аналитически, но это удобно только тогда, когда число уравнений не превышает двух (иногда трех). В случае, когда уравнений оказывается больше, применяют численные методы.

Что будет происходить с вероятностями состояний при ? Будут ли p 1 ( t ), ..., p n ( t ) стремиться к каким-то пределам? Если эти пределы существуют и не зависят от начального состояния системы, то они называются финальными вероятностями состояний: . p i – среднее относительное время пребывания системы в i -ом состоянии.

Как найти финальные вероятности? Поскольку все p i = const , то производные, стоящие в левой части каждого уравнения равны нулю. Т.о. мы получили систему линейных алгебраических уравнений. Поскольку ни одно уравнение в этой системе не имеет свободного члена, то система является вырожденной (т.е. все переменные будут выражены через одну). Чтобы этот избежать, необходимо воспользоваться нормировочным условием (), при этом любое уравнение можно отбросить.

Классификация систем массового обслуживания

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

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

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

Одноканальная СМО с неограниченной очередью

Рис.4.3

Найдем вероятности p k :

Для состояния S 0 : , отсюда ;

Для состояния S 1 n : , подставляем полученное значение для p 1 : . Аналогично, .

Вероятность p 0 найдем из нормировочного условия :

, – геометрическая прогрессия, при r <1 сходится. – вероятность того, что нет заявок.

– вероятность того, что прибор занят обслуживанием заявки. r = l / m – мера загрузки одноканальной СМО.

В текущий момент времени в системе может быть 0, 1, 2, ..., k , ... заявок с вероятностями p 0 , p 1 p 2 , ... Математическое ожидание количества заявок:

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

Средняя длина очереди равна разности между средним числом заявок в системе и средним числом заявок, находящихся под обслуживанием: .

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

Рис.4.4

Первая формула Литтла позволяет определить время реакции СМО (время пребывания заявки в системе).

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

.

Интеграл равен площади ступенчатой фигуры, ограниченной функциями X ( t ) и Y ( t ) , эта сумма состоит из прямоугольников, ширина которых равна единице, а длина – времени пребывания i -ой заявки в системе. Сумма распространяется на все заявки, поступившие в систему за время T . Правую часть домножим и разделим на l : . T l – среднее количество заявок, пришедших за время T . Поделив сумму всех времен t i на среднее число заявок, получим среднее время пребывания заявки в системе: .

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

Многоканальная СМО с неограниченной очередью

Рис.4.5

Найдем вероятности p k :

Для состояния S 0 : ;

Для состояний S 1 – S n : ;

Для S n +1 : ; ...

Для S n+s-1 : ;

Для S n+s : .

Из первых n +1 уравнений получаем:

Из последнего уравнения выражаем: и подставляем в предпоследнее: , . Тогда .

Продолжая аналогию: .

Теперь найдем p 0 , подставив полученные выражения в нормировочное условие (): . Отсюда .

Показатели эффективности СМО

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

– Вероятность того, что обслуживанием требований в системе занято k приборов, равна p k .

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

– Среднее число свободных от обслуживания приборов:.

– Коэффициент простоя приборов: .

– Коэффициент занятости оборудования: .

– Средняя длина очереди: , p k - вероятность того, что в системе находится k требований.

– Среднее число заявок, находящихся в сфере обслуживания: .

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

Кроме перечисленных критериев при оценке эффективности СМО могут быть использованы стоимостные показатели:

q об – стоимость обслуживания каждого требования в системе;

q ож – стоимость потерь, связанных с простаиванием заявок в очереди в единицу времени;

q у – убытки, связанные с уходом из системы заявки;

q k – стоимость эксплуатации каждого прибора в единицу времени;

q k пр – стоимость простоя единицы времени k -го прибора системы.

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

Для СМО с отказами: .

Для смешанных: .

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

СМО замкнутого типа

Пример. С1, С2, С3 – станки; НЦ – центральный накопитель; B – манипулятор. Транспортная тележка (манипулятор) транспортирует отработанную деталь от станка к накопителю и укладывает ее там, забирает новую деталь (заготовку), транспортирует ее к станку и устанавливает в рабочую позицию для зажима. Во время всего периода, необходимого для выгрузки–загрузки, станок простаивает. Время T з смены заготовки и есть время обслуживания.

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

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

В станочной системе число заявок на обслуживание может быть равно 0, 1, 2, ... m , где m – общее число станков. Тогда возможны следующие состояния:

S 0 – все станки работают, манипулятор стоит.

S 1 – все станки, кроме одного, работают, манипулятор обслуживает станок, от которого поступила заявка на смену заготовок.

S 2 – работают m -2 станка, на одном станке идет смена заготовки, другой ожидает.

S 3 – работают m -2 станка, один станок обслуживается манипулятором, два станка ожидают в очереди.

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

Рис.4.6.

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

p 0 – вероятность того, что все станки работают.

Манипулятор работает при состояниях системы от S 1 до S m ­ . Тогда вероятность его загрузки равна: .

Число станков, находящихся в очереди связано с состояниями S 2 , – S m , при этом один станок обслуживается, а (k -1) – ожидают. Тогда, среднее число станков в очереди: .

Коэффициент простоя одного станка (из-за ожидания при многостаночном обслуживании): .

Среднее использование одного станка:

Применение метода Монте-Карло для решения задач,

связанных с теорией массового обслуживания

Для того, чтобы описать поток однородных событий, достаточно знать закон распределения моментов времени t 1 , t 2 , ..., t k , ..., в которые поступают события.

Для удобства дальнейших рассмотрений целесообразно от величин t 1 , t 2 , ..., перейти к случайным величинам z 1 , z 2 , ..., z m , ... , таким образом, что:

Случайные величины z k являются длинами интервалов времени между последовательными моментами t k .

Совокупность случайных величин z i считается заданной, если определена совместная функция распределения: . Обычно рассматриваются только непрерывные случайные величины z k , поэтому часто пользуются соответствующей функцией плотности f ( z 1 , z 2 ,..., z k ) .

Обычно в теории СМО рассматриваются потоки однородных событий без последействия, для которых случайные величины z k независимы. Поэтому . Функции f i ( z i ) при i >1 представляют собой условные функции плотности при условии, что в начальный момент интервала z k ( i >1) поступила заявка. В отличие от этого функция f 1 ( z 1 ) является безусловной функцией плотности, т.к. относительно появления или непоявления заявки в начальный момент времени не делается никаких предположений.

Широкое применение имеют так называемые стационарные потоки, для которых вероятностный режим их во времени не изменяется (т.е. вероятность появления k заявок за промежуток времени (t 0 , t 0 + t ) не зависит от t 0 , а зависит только от t и k ). Для стационарных потоков без последействия имеют место соотношения:

где l – плотность стационарного потока.

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

а) линии занимаются в порядке их номеров. Линия с большим номером не может быть привлечена к обслуживанию заявки, если имеется свободная линии с меньшим номером;

б) линии занимаются в порядке очереди. Освободившаяся линия поступает в очередь и не начинает обслуживания заявок до израсходования всех ранее освободившихся линий;

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

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

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

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

в) заявки принимаются к обслуживанию в случайном порядке в соответствии с заданными вероятностями. Если в момент освобождения линии имеется m заявок в очереди, то в простейшем случае вероятность выбрать для обслуживания некоторую определенную заявку может быть принята равной q =1/ m . В более сложных случаях вероятности q 1 , q 2 ,..., q m считаются зависящими от времени пребывания заявки в системе, времени, остающегося до получения отказа и других параметров.

· Для решения ряда прикладных задач оказывается необходимым учитывать такой важный фактор, как надежность элементов обслуживающей системы. Будем предполагать, что с точки зрения надежности каждая линия в данный момент времени может быть либо исправной, либо неисправной. Надежность линии определяется вероятностью безотказной работы R = R ( t ) , задаваемой как функция времени. Будем также предполагать, что линия, вышедшая из строя по причине неполной надежности, может быть введена в строй (отремонтирована), для чего требуется затратить время t p . Величину t p будем считать случайной величиной с заданным законом распределения.

Относительно судьбы заявки, при обслуживании которой линия выходит из строя, могут быть сделаны различные предположения: заявка получает отказ; заявка остается в системе (с общим временем пребывания в системе не более t n ) как претендент на обслуживание вне очереди; заявка поступает в очередь и обслуживается на общих основаниях и т.д.

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

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

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

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

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

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

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

· Структура алгоритма, моделирующего

процесс обслуживания заявок

Рассмотрим однофазную СМО, имеющую n линий, на которые поступают заявки в случайные моменты времени t i . Если вмомент поступления заявки оказываются в наличии свободные линии (их число n св ), заявка занимает одну из них на время t p . В противном случае заявка находится в системе до момента t n , ожидая обслудивания. В т t чение времени ожидания некоторые линии могут освободиться (их число m ), и в этом случае будет возможность обслужить заявку. Если до момента времени t n ни одна из линий не освобождается (m =0 ), заявка получает отказ.

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

Для исследования качества обслуживания заявок предусматривается N * кратное моделирование процесса функционирования системы в интервале (0, T ) . В процессе моделирования число обследованных реализаций обозначим через N .

Алгоритм:

1. Определяется момент t i поступления очередной заявки в систему.

2. Если t i < T , то переход на шаг 3, иначе – на шаг 11.

3. Проверка возможности обслужить поступившую заявку: если n св >0 , то переход на шаг 4, иначе – на шаг 12. (Значение времени поступления заявки t i сравнивается с t осв для всех линий, т.о. выявляются свободные линии.)

4.Если n св >1 , то переход на шаг 5, иначе – на шаг 6.

5. Выбирается номер свободной линии по специальным правилам.

6. Назначается выбранная линия.

7. Проверка: имеет ли место срыв обслуживания по причине недостаточной надежности? Если да, то переход на шаг 8, иначе – на шаг 10.

8. Определение времени t рем ремонта линии, вышедшей из строя (t рем имеет определенный закон распределения).

9. N отк = N отк +1 . Переход на шаг 1.

10. Определение времени занятости t з линии, которая назначена обслуживать заявку (некая случайная величина с определенным законом распределения) и времени освобождения линии: t осв = t i + t з . Переход к очередной заявке (шаг 1).

11. Проверка: если N < N * , то N = N +1 и переход на шаг 1, иначе – обработка результатов опыта и конец.

12. Определить:

А) времени t n пребывания заявки в системе;

Б) число освободившихся каналов m за время t n .

13. Если m >0 , то переход на шаг 14, иначе – на шаг 9.

14. Если m >1 , то переход на шаг 15, иначе – на шаг 6.

15. Выбирается определенная линия в соответствии с принятыми правилами и переход на шаг 6.

(Теория очередей)

1. Элементы теории массового обслуживания

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

1.1 Компоненты и классификация моделей массового обслуживания

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

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

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

Примерами систем массового обслуживания могут служить:

· магазины;

· ремонтные мастерские;

· почтовые отделения;

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

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

· аудиторские фирмы;

· отделы налоговых инспекций, занимающиеся приемкой и проверкой текущей отчетности предприятий;

· телефонные станции и т.д.

Основными компонентами системы массового обслуживания любого вида являются:

· входной поток поступающих требований или заявок на обслуживание;

· дисциплина очереди;

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

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

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

Первым пришел - первый обслуживаешься;

Пришел последним - обслуживаешься первым;

Случайный отбор заявок;

Отбор заявок по критерию приоритетности;

Ограничение времени ожидания момента наступления обслужи вания (имеет место очередь с ограниченным временем ожидания обслуживания, что ассоциируется с понятием «допустимая дли на очереди»).

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

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

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

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

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

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

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

· конфигурацией обслуживающей системы (параллельное, последовательное или параллельно-последовательное обслуживание);

· количеством и производительностью обслуживающих каналов;

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

· мощностью источника требований.

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

· вероятность немедленного обслуживания поступившей заявки;

· вероятность отказа в обслуживании поступившей заявки;

· относительная и абсолютная пропускная способность системы;

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

· среднее время ожидания в очереди;

· средняя длина очереди;

· средний доход от функционирования системы в единицу времени и т.п.

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

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

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

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

Системы массового обслуживания с ожиданием делятся на системы с ограниченным ожиданием и системы с неограниченным ожиданием.

В системах с ограниченным ожиданием может ограничиваться:

Длина очереди;

Время пребывания в очереди.

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

Все системы массового обслуживания различают по числу каналов обслуживания:

Одноканальные системы;

Многоканальные системы.

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

Определим характеристики систем массового обслуживания.

1.2. Одноканальная СМО с отказами

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

Плотность распределения длительностей обслуживания:

где – интенсивность обслуживания, tоб – среднее время обслуживания одного клиента.

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

Абсолютная пропускная способность (А) - среднее число заявок, которое может обслужить система массового обслуживания в единицу времени: Вероятность отказа в обслуживании заявки будет равна вероятности состояния «канал обслуживания занят»:

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

Пример. Пусть одноканальная СМО с отказами представляет собой один пост ежедневного обслуживания для мойки автомобилей. Заявка - автомобиль, прибывший в момент, когда пост занят, - получает отказ в обслуживании. Интенсивность потока автомобилей λ 1,0 (автомобиль в час). Средняя продолжительность обслуживания - tоб=1,8 часа.

Требуется определить в установившемся режиме предельные значения:

a) относительной пропускной способности q;

b) абсолютной пропускной способности А;

c) вероятности отказа Ротк;

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

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

Абсолютную пропускную способность определим по формуле: А=λ×q=1×0,356=0,356.

Это означает, что система способна осуществить в среднем 0,356 обслуживания автомобилей в час.

Вероятность отказа:

Ротк=1-q=1-0,356=0,644.

Это означает, что около 65% прибывших автомобилей на пост ЕО получат отказ в обслуживании.

Определим номинальную пропускную способность системы:

Аном= (автомобилей в час). Оказывается, что Аном в раза больше, чем фактическая пропускная способность, вычисленная с учетом случайного характера потока заявок и времени обслуживания.

1.3 . Одноканальная СМО с ожиданием и ограниченной очередью

Рассмотрим теперь одноканальную СМО с ожиданием.

Система массового обслуживания имеет один канал. Входящий поток заявок на обслуживание поток имеет интенсивность λ. Интенсивность потока обслуживания равна μ (т. е. в среднем непрерывно занятый канал будет выдавать μ обслуженных заявок). Длительность обслуживания - случайная величина, подчиненная показательному закону распределения. Заявка, поступившая в момент, когда канал занят, становится в очередь и ожидает обслуживания.

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

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

Здесь - приведенная интенсивность потока. Тогда вероятность того, что канал обслуживания свободен и в системе нет ни одного клиента, равна: .

С учетом этого можно обозначить

Определим характеристики одноканальной СМО с ожиданием и ограниченной длиной очереди, равной (N-1):

· вероятность отказа в обслуживании заявки: Pотк=РN=

· относительная пропускная способность системы:

· абсолютная пропускная способность:

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

среднее время пребывания заявки в системе:

средняя продолжительность пребывания клиента (заявки) в очереди:

среднее число заявок (клиентов) в очереди (длина очереди):

Рассмотрим пример одноканальной СМО с ожиданием.

Пример. Специализированный пост диагностики представляет собой одноканальную СМО. Число стоянок для автомобилей, ожидающих проведения диагностики, ограниченно и равно 3, то есть (N- 1)=3. Если все стоянки заняты, т. е. в очереди уже находится три автомобиля, то очередной автомобиль, прибывший на диагностику, в очередь на обслуживание не становится. Поток автомобилей, прибывающих на диагностику имеет интенсивность λ=0,85 (автомобиля в час). Время диагностики автомобиля распределено по показательному закону и в среднем равно =1,05 час.

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

Интенсивность потока обслуживаний автомобилей:

Приведенная интенсивность потока автомобилей определяется как отношение интенсивностей λ и μ, т.е.

Вычислим вероятности нахождения п заявок в системе:

P1=r∙P0=0,893∙0,248=0,221;

P2=r2∙P0=0,8932∙0,248=0,198;

P3=r3∙P0=0,8933∙0,248=0,177;

P4=r4∙P0=0,8934∙0,248=0,158.

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

Pотк=Р4=r4∙P0≈0,158.

Относительная пропускная способность поста диагностики:

q=1–Pотк=1-0,158=0,842.

Абсолютная пропускная способность поста диагностики

А=λ∙q=0,85∙0,842=0,716 (автомобиля в час).

Среднее число автомобилей, находящихся на обслуживании и в очереди (т.е. в системе массового обслуживания):

Среднее время пребывания автомобиля в системе:

Средняя продолжительность пребывания заявки в очереди на обслуживание:

Wq=Ws-1/μ=2,473-1/0,952=1,423 часа.

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

Lq=λ∙(1-PN)∙Wq=0,85∙(1-0,158)∙1,423=1,02.

Работу рассмотренного поста диагностики можно считать удовлетворительной, так как пост диагностики не обнаруживает автомобили в среднем в 15,8% случаев (Ротк=0,158).

1.4. Одноканальная СМО с ожиданием и неограниченной очередью

Перейдем теперь к рассмотрению одноканальной СМО с ожиданием без ограничения на вместимость блока ожидания (т.е. Ν → ∞). Остальные условия функционирования СМО остаются без изменений.

Устойчивое решение в такой системе существует только тогда, когда λ<μ, то есть заявки должны обслуживаться с большей скоростью, чем поступают, в противном случае очередь может разрастись до бесконечности.

Вероятность того, что в системе находится п заявок, вычисляется по формуле

Pn=(1-r)rn, n=0,1,2,…,

где r = λ/μ <1.

Характеристики одноканальной СМО с ожиданием, без ограничения на длину очереди, следующие:

среднее число находящихся в системе клиентов (заявок) на обслуживание:

средняя продолжительность пребывания клиента в системе:

среднее число клиентов в очереди на обслуживание:

средняя продолжительность пребывания клиента в очереди:

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

Требуется определить финальные значения следующих вероятностных характеристик:

вероятности состояний системы (поста диагностики);

среднее число автомобилей, находящихся в системе (на обслуживании и в очереди);

среднюю продолжительность пребывания автомобиля в системе

(на обслуживании и в очереди);

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

среднюю продолжительность пребывания автомобиля в очереди.

Решение. Параметр потока обслуживания и приведенная интенсивность потока автомобилей ρ определены в предыдущем примере:

μ=0,952; ρ=0,893.

Вычислим предельные вероятности системы по формулам

P0=1-r=1-0,893=0,107;

P1=(1-r)·r=(1-0,893)·0,893=0,096;

P2=(1-r)·r2=(1-0,893)·0,8932=0,085;

P3=(1-r)·r3=(1-0,893)·0,8933=0,076;

P4=(1-r)·r4=(1-0,893)·0,8934=0,068;

P5=(1-r)·r5=(1-0,893)·0,8935=0,061 и т.д.

Следует отметить, что Р0 определяет долю времени, в течение которого пост диагностики вынужденно бездействует (простаивает). В нашем примере она составляет 10, 7%, так как Р0=0,107.

Среднее число автомобилей, находящихся в системе (на обслуживании и в очереди):

ед.

Средняя продолжительность пребывания клиента в системе:

Среднее число автомобилей в очереди на обслуживание:

Средняя продолжительность пребывания автомобиля в очереди:

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

Абсолютная пропускная способность:

A=λ∙q=0,85∙1=0,85.

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

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

В нашем примере при N=3+1=4 и r=0,893,

m=λ∙P0∙ r4=0,85∙0,248∙0,8934=0,134 автомобиля в час.

При 12-часовом режиме работы поста диагностики это эквивалентно тому, что пост диагностики в среднем за смену (день) будет терять 12∙0,134=1,6 автомобиля.

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

1.5. Многоканальная СМО с отказами

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

Процесс массового обслуживания, описываемый данной моделью, характеризуется интенсивностью входного потока λ, при этом параллельно может обслуживаться не более n клиентов (заявок). Средняя продолжительность обслуживания одной заявки равняется 1/μ. Режим функционирования того или иного обслуживающего канала не влияет на режим функционирования других обслуживающих каналов системы, при чем длительность процедуры обслуживания каждым из каналов является случайной величиной, починенной экспоненциальному закону распределения. Конечная цель использования параллельно включенных обслуживающих каналов заключается в повышение (по сравнению с одноканальной системой) скорости обслуживания требований за счет обслуживания одновременно n клиентов.

Стационарное решение системы имеет вид:

,где ,

Формулы для вычисления вероятностей называются формулами Эрланга.

Определим вероятностные характеристики функционирования многоканальной СМО с отказами в стационарном режиме:

вероятность отказа:

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

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

абсолютная пропускная способность

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

Величина характеризует степень загрузки СМО.

Пример. Пусть n-канальная СМО представляет собой вычислительный центр (ВЦ) с тремя (n=3) взаимозаменяемыми ПЭВМ для решения поступающих задач. Поток задач, поступающих на ВЦ, имеет интенсивность λ=1 задача в час. Средняя продолжительность обслуживания tоб=1,8 час.

Требуется вычислить значения:

Вероятности числа занятых каналов ВЦ;

Вероятности отказа в обслуживании заявки;

Относительной пропускной способности ВЦ;

Абсолютной пропускной способности ВЦ;

Среднего числа занятых ПЭВМ на ВЦ.

Определите, сколько дополнительно надо приобрести ПЭВМ, чтобы увеличить пропускную способность ВЦ в 2 раза.

Определим параметр μ потока обслуживаний:

Предельные вероятности состояний найдем по формулам Эрланга:

Вероятность отказа в обслуживании заявки

Относительная пропускная способность ВЦ

Абсолютная пропускная способность ВЦ:

Среднее число занятых каналов – ПЭВМ

Таким образом, при установившемся режиме работы СМО в среднем будет занято 1,5 компьютера из трех – остальные полтора будут простаивать. Работу рассмотренного ВЦ вряд ли можно считать удовлетворительной, так как центр не обслуживает заявки в среднем в 18% случаев (Р3= 0,180). Очевидно, что пропускную способность ВЦ при данных λ и μ можно увеличить только за счет увеличения числа ПЭВМ.

Определим, сколько нужно использовать ПЭВМ, чтобы сократить число не обслуженных заявок, поступающих на ВЦ, в 10 раз, т.е. чтобы вероятность отказа в решении задач не превосходила 0,0180. Для этого используем формулу вероятности отказа:

Составим следующую таблицу:

n
P0	0,357	0,226	0,186	0,172	0,167
Pотк	0,673	0,367	0,18	0,075	0,026

Анализируя данные таблицы, следует отметить, что расширение числа каналов ВЦ при данных значениях λ и μ до 6 единиц ПЭВМ позволит обеспечить удовлетворение заявок на решение задач на 99,22%, так как при n = 6 вероятность отказа в обслуживании (Ротк) составляет 0,0078.

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

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

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

Решение будет действительным, если выполняется следующее условие:

Остальные вероятностные характеристики функционирования в стационарном режиме многоканальной СМО с ожиданием и неограниченной очередью определяется по следующим формулам:

среднее число клиентов в очереди на обслуживание

;

среднее число находящихся в системе клиентов (заявок на обслуживание и в очереди)

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

средняя продолжительность пребывания клиента в системе

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

Пример. Механическая мастерская завода с тремя постами (каналами) выполняет ремонт малой механизации. Поток неисправных механизмов, прибывающих в мастерскую, - пуассоновский и имеет интенсивность λ=2,5 механизма в сутки, среднее время ремонта одного механизма распределено по показательному закону и равно tоб=0,5 сут. Предположим, что другой мастерской на заводе нет, и, значит, очередь механизмов перед мастерской может расти практически неограниченно.

Требуется вычислить следующие предельные значения вероятностных характеристик системы:

Вероятность состояний системы;

Среднее число заявок в очереди на обслуживание;

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

Среднюю продолжительность пребывания заявки в очереди;

Среднюю продолжительность пребывания заявки в системе.

Определим параметр потока обслуживаний

Приведенная интенсивность потока заявок

ρ=λ/μ=2,5/2,0=1,25,

при этом λ/μ ∙с=2,5/2∙3=0,41<1.

Поскольку λ/μ∙с<1, то очередь не растет безгранично и в системе наступает предельный стационарный режим работы.

Вычислим вероятности состояний системы:

Вероятность отсутствия очереди у мастерской

Ротк≈Р0+Р1+Р2+Р3≈0,279+0,394+0,218+0,091=0,937.

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

Ls=Lq+ =0,111+1,25=1,361.

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

Средняя продолжительность пребывания механизма в мастерской (в системе)

суток.

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

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

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

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

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

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

Рассмотрим следующий пример.

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

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

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

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

1.Входящий поток требований.

2.Дисциплину очереди.

3.Механизм обслуживания.

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

Рис. 9.1. Модель теории массового обслуживания

В некоторых системах «очередь» отсутствует.

СМО делится на классы по ряду признаков, например СМО с отказами (как в телефонии) и СМО с очередью. На практике чаще встречаются и имеют большее значение СМО с очередью: недаром ТМО иногда называют «теория очередей». В СМО с очередью длина очереди и (или) время ожидания могут быть ограничены или не иметь ограничений; обслуживание может быть с приоритетом или без него, в порядке поступления или случайным.

Приоритет может быть абсолютным или относительным.

СМО могут быть открытыми и закрытыми. В первой - поток заявок не зависит от состояния самой СМО (сколько каналов занято), во

второй - зависит. Пример - наладка группы станков одним рабочим. Здесь интенсивность «требований» со стороны станков зависит от того, сколько их уже неисправно.

Классификация СМО не ограничивается приведенными разновидностями.

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

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

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

ность может быть как постоянной, так и зависящей от t. Например, поток машин ночью не так интенсивен, как днем.

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

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

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

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

ний, поступивших в систему за, не зависит от того, сколько требований поступило за промежуток.

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

Пусть случайная величинаобозначает число требований на интервале .

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

Заметим, что

где

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

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

Можно показать, что для простейшего потока число требований в промежутке времени длиной t распределено по закону Пуассона с параметром(см. п. 7.2.1), т. е.

Стационарность и отсутствие последействия налицо, ординарность (т. е. условие (9.1)) вытекает из равенства

которое можно проверить по правилу Лопиталя.

Параметр X здесь характеризует интенсивность потока. Действительно,

Простейший поток еще называют стационарным пуассоновским.

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

Решение. Пусть интенсивностьполомки/ч. По формуле (9.2)

прии t =1 найдем вероятность k поломок в течение часа

Составим табл. 9.1. Таблица 9.1

k

....

p k (1)

0,05

0,15

0,22

0,22

0,17

0,05

....

Следующее важное понятие ТМО - это время обслуживания.

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

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

Параметр(аналогично параметрувходящего потока) определяет интенсивность обслуживания; величина является средним временем обслуживания t одной заявки:

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

Далее коротко опишем я-канальную систему массового обслуживания с отказами. Это «классическая» задача ТМО, возникшая из практических нужд телефонии и решенная в начале ХХ века датским математиком Эрлангом. Задача ставится так.

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

ленно приступает к обслуживанию. В противном случае заявка получает отказ и покидает систему.

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

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

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

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

. Р отк - вероятность отказа, или того, что заявка покинет СМО необслуженной;

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

. - вероятность того, что занято ровно k каналов, и, в частности, Р 0 - вероятность простоя системы;

. - коэффициент занятости каналов в процентах (%);

.
- коэффициент простоя каналов

в процентах (%). Обозначим

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

а вероятностиприимеют вид

Формулы (9.6), (9.7) для вероятностей Р к называются формулами Эрланга - в честь основателя ТМО. С их помощью можно вычислить остальные интересующие нас характеристики СМО. Так, вероятность Действительно, для того чтобы пришедшая заявка получила отказ, необходимо, чтобы все я каналов были заняты. Итак,

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

Абсолютную пропускную способность получим, умножая интенсивность потока заявок на Q:

Среднее число занятых каналовпо определению математического ожидания с учетом формул (9.6) и (9.7) равно

Отметим, что, зная вероятность отказав обслуживании

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

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

Отсюда заключаем, что на АТС в среднем занято 2 линии из 5, каждая линия загружена всего на 39 %, теряется приблизительно 4 вызова из 100. Таким образом, АТС работает не слишком эффективно, и вполне можно сократить общее число линий и (или) увеличить интенсивность потока заявок.

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

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

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

Таким образом, загрузка каждого из двух оставшихся продавцов немного вырастет (с 0,53 до 1/2 . 1,2 = 0,6 рабочего дня), зато «коэффициент полезного действия» аптеки упадет с 0,79 до 0,6, поскольку в сложившейся ситуации будет обслужено лишь 60 % ((1 - 0,4) . 100 %) потенциальных клиентов, а не 79 % как ранее при трех продавцах.

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

Каждая система массового обслуживания состоит из определенного числа обслуживающих единиц, в том числе приборов, при-

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

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

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

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

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

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

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

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

В качестве показателей эффективности систем массового обслуживания могут использоваться следующие:

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

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

Вероятность отказа в обслуживании без ожидания;

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

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

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

В качестве показателей эффективности системы массового обслуживания с отказами применяются следующие:

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

где - интенсивность потока заявок;

Интенсивность потока обслуживания.

При этом интенсивность потока обслуживания является обратной величиной к среднему времени обслуживания ():

2. Относительная пропускная способность (Q) - показатель, характеризующий среднюю долю заявок, которая поступила и обслуживается системой. Вычисляется по формуле

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

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

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

В многоканальных системах массового обслуживания с предельными вероятностями используют формулы для предельных вероятностей состояния, которые получили название формул Эрланга в честь А.К. Эрланга (конец XIX - начало XX в.) - Датского инженера, математика, основателя теории массового обслуживания.

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

;

, ..., ...,.

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

.

Абсолютная пропускная способность рассчитывается:

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

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

1. Определить показатели эффективности работы системы массового обслуживания (переговорного пункта) при наличии одного телефонного номера.

2. Определить оптимальное количество телефонных номеров на переговорном пункте, если условием оптимальности считать

удовольствие в среднем из каждых 100 заявок не менее 80 заявок на переговоры.

1. Рассчитаем интенсивность потока обслуживания:

.

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

.

Это означает, что в среднем только 20% заявок, поступающих будут удовлетворены за ними будут предоставлены услуги, то есть осуществятся переговоры по телефону.

3. Вероятность отказа в обслуживании () составит:

.

Итак, в среднем 80% заявок, которые поступят на переговоры, получат отказ в обслуживании.

4. Абсолютная пропускная способность системы массового обслуживания - переговорного пункта равно

.

Таким образом, в среднем за час будут обслужены 16 заявок на переговоры.

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

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

5. Вычислим интенсивность нагрузки канала:

.

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

6. Для получения характеристик системы (переговорного пункта) и выбора оптимального варианта количества номеров следует постепенно увеличивать число каналов (телефонных номеров) n = 2,3,4, ..., превращая таким образом имеющуюся систему массового обслуживания с одноканальной в многоканальную. Тогда относительная пропускная способность составит:

;

;

за;.

Абсолютная пропускная способность равна:

Аналогично рассчитаем основные характеристики системы массового обслуживания для 3, 4, 5, 6 каналов обслуживания (номеров телефонов) и сведем их в табл. 13.5.

Таблица 13.5. Основные характеристики обслуживания заявок на переговоры переговорным пунктом в зависимости от количества номеров

Итак, по условиям оптимальности Q 3 = 0,8, поэтому на переговорном пункте необходимо установить 3 телефонных номера (в этом случае Q = 0,80). Это означает, что за час будут обслуживаться в среднем 64 заявки (А = 64), а среднее число занятых номеров (каналов) равна

.

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

Введение

Теория случайных процессов (случайных функций) - это раздел математической науки, изучающий закономерности случайных явлений в динамике их развития.

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

Теория массового обслуживания опирается на теорию вероятностей и математическую статистику. Первоначальное развитие теории массового обслуживания связано с именем датского ученого А.К. Эрланга (1878-1929), с его трудами в области проектирования и эксплуатации телефонных станций.

Теория массового обслуживания - область прикладной математики, занимающаяся анализом процессов в системах производства, обслуживания, управления, в которых однородные события повторяются многократно, например, на предприятиях бытового обслуживания; в системах приема, переработки и передачи информации; автоматических линиях производства и др. Большой вклад в развитие этой теории внесли российские математики А.Я. Хинчин, Б.В. Гнеденко, А.Н. Колмогоров, Е.С. Вентцель и др.

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

В коммерческой деятельности применение теории массового обслуживания пока не нашло желаемого распространения.

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

1. Определение случайного процесса и его характеристики

Случайным процессом X(t) называется процесс, значение которого при любом значении аргумента t является случайной величиной.

Другими словами, случайный процесс представляет собой функцию, которая в результате испытания может принять тот или иной конкретный вид, неизвестный заранее. При фиксированном t = to X(to) представляет собой обычную случайную величину, т.е. сечение случайного процесса в момент tо.

Реализацией случайного процесса X (t, w) называется неслучайная функция x(t), в которую превращается случайный процесс X(t) в результате испытания (при фиксированном w), т.е. конкретный вид, принимаемый случайным процессом X(t), его траектория.

Таким образом, случайный процесс X (t, w) совмещает в себе черты случайной величины и функции. Если зафиксировать значение аргумента t, случайный процесс превращается в обычную случайную величину, если зафиксировать w, то в результате каждого испытания он превращается в обычную неслучайную Функцию.

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

Математическим ожиданием случайного процесса X(t) называется неслучайная функция ax(t), которая при любом значении переменной t равна математическому ожиданию соответствующего сечения случайного процесса X(t), т.е. ax(t) = M .

Дисперсией случайного процесса X(t) называется неслучайная функция. Dx(t), при любом значении переменной t равная дисперсии соответствующего сечения случайного процесса X(t), т.е. Dx(t) = D .

Средним квадратическим отклонением случайного процесса X(t) называется арифметическое значение корня квадратного из его дисперсии, т.е.

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

Корреляционной функцией случайного процесса X(t) называется неслучайная функция

двух переменных t1 и t2, которая при каждой паре переменных t1и t2 равна ковариации соответствующих сечений X(t1) и X(t2) случайного процесса.

Нормированной корреляционной функцией случайного процесса X(t) называется функция

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

2. Основные понятия теории массового обслуживания

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

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

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

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

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

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

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

3. Понятие марковского случайного процесса

Процесс работы СМО представляет собой случайный процесс.

Процесс называется процессом с дискретными состояниям, если его возможные состояния S1, S2, S3… можно заранее перечислить, а переход системы из состояния в состояние происходит мгновенно (скачком). Процесс называется процессом с непрерывным временем, если моменты возможных переходов системы из состояния в состояние не фиксированы заранее, а случайны.

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

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

Пример марковского процесса: система S - счетчик в такси. Состояние системы в момент t характеризуется числом километров (десятых долей километров), пройденных автомобилем до данного момента. Пусть в момент to счетчик показывает So. Вероятность того, что в момент t > to счетчик покажет то или иное число километров (точнее, соответствующее число рублей) S1, зависит от So, но не зависит от того, в какие моменты времени изменялись показания счетчика до момента to.

Многие процессы можно приближенно считать марковскими. Например, процесс игры в шахматы; система S - группа шахматных фигур. Состояние системы характеризуется числом фигур противника, сохранившихся на доске в момент to. Вероятность того, что в момент t > to материальный перевес будет на стороне одного из противников, зависит в первую очередь от того, в каком состояний находится система в данный момент to, а не от того, когда и в какой последовательности исчезли фигуры с доски до момента to.

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

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

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

. Потоки событий

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

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

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

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

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

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

Поток событий называется простейшим (или стационарным пуассоновским ), если он одновременно стационарен, ординарен и не имеет последействия. Название «простейший» объясняется тем, что СМО с простейшими потоками имеет наиболее простое математическое описание. Регулярный поток не является простейшим, так как обладает последействием: моменты появления событий в таком потоке жестко зафиксированы.

Простейший поток в качестве предельного возникает в теории случайных процессов столь же естественно, как в теории вероятностей нормальное распределение получается в качестве предельного для суммы случайных величин: при наложении (суперпозиции) достаточно большого числа п независимых, стационарных и ординарных потоков (сравнимых между собой по интенсивностям Аi (i=1,2…п)) получается поток, близкий к простейшему с интенсивностью X, равной сумме интенсивностей входящих потоков, т.е.:

Биномиальный закон распределения:

с параметрами

Биномиальное распределение стремится к распределению Пуассона с параметром

для которого математическое ожидание случайной величины равно ее дисперсии:

В частности, вероятность того, что за время т не произойдет ни одного события (т = 0), равна

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

и обратно по величине интенсивности потока

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

Другими словами, для интервала времени Т между двумя последовательными соседними событиями потока, имеющего показательное распределение, любые сведения о том, сколько времени протекал этот интервал, не влияют на закон распределения оставшейся части. Это свойство показательного закона представляет собой, в сущности, другую формулировку для «отсутствия последействия» - основного свойства простейшего потока.

Для простейшего потока с интенсивностью вероятность попадания на элементарный (малый) отрезок времени At хотя бы одного события потока равна:

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

5. Уравнения Колмогорова. Предельные вероятности состояний

Соответствующий граф состояний процесса изображен на рис. к задаче. Будем полагать, что все переходы системы из состояния Si в Sj происходят под воздействием простейших потоков событий с интенсивностями (i, j =0, 1, 2,3); так, переход системы из состояния S0 вS1 будет происходить под воздействием потока отказов первого узла, а обратный переход из состояния S0 в S1 - под воздействием потока «окончаний ремонтов» первого узла и т.п.

Граф состояний системы с проставленными у стрелок интенсивностями будем называть размеченным (см. рис. выше). Рассматриваемая система S имеет четыре возможных состояния: S0, S1 S2, S3. Вероятностью i-го состояния называется вероятность pi(t) того, что в момент t система будет находиться в состоянии Si. Очевидно, что для любого момента t сумма вероятностей всех состояний равна единице:

Рассмотрим систему в момент t и, задав малый промежуток At, найдем вероятность po (t + At) того, что система в момент t+At будет находиться в состоянии S0. Это достигается разными способами.

1.Система в момент t с вероятностью po (t) находилась в состоянии S0, а за время At не вышла из него.

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

А вероятность того, что система не выйдет из состояния S0, равна . Вероятность того, что система будет находиться в состоянии S0 и не выйдет из него за время At, равна по теореме умножения вероятностей:

Система в момент t с вероятностью p1 (t) (или p2 (t)) находилась в состоянии S1 или S2 и за время At перешла в состояние

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

Применяя теорему сложения вероятностей, получим:

Переходя к пределу при At 0 (приближенные равенстваперейдут в точные), получим в левой части уравнения производную (обозначим ее для простоты ):

Получено дифференциальное уравнение первого порядка, т.е. уравнение, содержащее как саму неизвестную функцию, так и ее производную первого порядка.

Рассуждая аналогично для других состояний системы S, можно получить систему дифференциальных уравнений Колмогорова для вероятностей состояний:

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

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

Особенность решения дифференциальных уравнений вообще состоит в том, что требуется задавать так называемые начальные условия, в данном случае - вероятности состояний системы в начальный момент t = 0. Так, например, систему уравнений естественно решать при условии, что в начальный момент оба узда исправны и система находилась в состоянии So, т.е. при начальных условиях

Уравнения Колмогорова дают возможность найти все вероятности состояний как функции времени. Особый интерес представляют вероятности системы pi(t) в предельном стационарном режиме, т.е. при , которые называются предельными (финальными) вероятностями состояний.

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

Предельная вероятность состояния Si имеет четкий смысл: она показывает среднее относительное время пребывания системы в этом состоянии. Например, если предельная вероятность состояния So, т.е. р0=0,5, то это означает, что в среднем половину времени система находится в состоянии S0.

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

Процессы гибели и размножения

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

Рассмотрим упорядоченное множество состояний системы S0, S1, S2,…, Sk. Переходы могут осуществляться из любого состояния только в состояния с соседними номерами, т.е. из состояния Sk-1 возможны переходы либо в состояние либо в состояние S k+11.

В соответствии с правилом составления таких уравнений (уравнением Колмогорова) получим: для состояния S0

Заключение

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

Использованная литература

случайный массовый марковский колмогоров

1. Н.Ш. Кремер «Теория вероятностей и математическая статистика» Юнити, г. Москва, 2003 г.

Репетиторство

Нужна помощь по изучению какой-либы темы?

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