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

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. Входной поток требований или заявок на обслуживание. Этот элемент является основным. Изучение входящего потока требований и его описание необходимо при организации любой системы массового обслуживания.
2. Очередь. В тех случаях, когда поступающие в систему массового обслуживания требования не могут быть удовлетворены немедленно, возникает очередь. В такой ситуации интерес может представлять длина этой очереди, порядок, по которому ожидающие требования направляются на обслуживание (как говорят, дисциплина очереди), время ожидания.

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

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

Рис. 1

Системы массового обслуживания классифицируются по разным признакам.

1. На группы в зависимости от состава и от времени пребывания в очереди до начала обслуживания, и от дисциплины обслуживания требований.

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

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

с неограниченным временем ожидания (с ожиданием),

с отказами;

смешанного типа.

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

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

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

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

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

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

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

В таком случае используется имитационное моделирование, которое состоит в компьютерном моделировании реальной производственной ситуации.

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

Для простейшего потока частота поступления требований в систему подчиняется закону Пуассона, то есть вероятность поступления за время t ровно k требований задается формулой

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

Простейший поток обладает тремя основными свойствами:

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

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

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

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

Функция распределения для этого закона имеет вид

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

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

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

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

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

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

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

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

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

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

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

Вычислим относительную пропускную способность:

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

Абсолютную пропускную способность определим по формуле:

А=лЧq=1Ч0,356=0,356.

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

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

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

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

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

Аном= (автомобилей в час).

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

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

Специализированный пост диагностики представляет собой одноканальную СМО. Число стоянок для автомобилей, ожидающих проведения диагностики, ограниченно и равно 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).

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

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

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

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

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

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

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

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

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

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

м=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 ч. работы) пост диагностики. Ясно, что решение относительно расширения площади для стоянки автомобиля, прибывающих на пост диагностики, должно основываться на оценке экономического ущерба, который обусловлен потерей клиентов при наличие всего трех мест для стоянки этих автомобилей.

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

Примером является задание № 4

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

Механическая мастерская завода с тремя постами (каналами) выполняет ремонт малой механизации. Поток неисправных механизмов, прибывающих в мастерскую, - пуассоновский и имеет интенсивность л=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.

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

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

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

1. Основные положения к выполнению лабораторной работы

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

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

Оценка математического ожидания числа занятых каналов:

здесь - число занятых каналов в момент времени t в j-й реализации; N - число реализаций (прогонов модели);

Оценка вероятности того, что в системе в момент времени t:

здесь - число реализаций, в которых на момент времени t в системе было k требований;

Оценка вероятности, что требование получит отказ:

где - общее число требований, появившихся к моменту времени t в j-й реализации; - число требований, получивших отказ к моменту времени t;

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

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

Для математического ожидания числа занятых каналов

Здесь tb находится из распределения Стьюдента при (N-1) степенях свободы. При больших N (N>30) вместо распределения Стьюдента можно пользоваться нормальным законом. В этом случае

где Ф(х) - интеграл вероятностей:

2. Для вероятностей

При больших N приближенно

где - С.К.О. оценки вероятности:

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

2. Для заданного (базового) варианта СМО получить результаты моделирования СМО. Величину t ож время ожидания в очереди принять неслучайной t ож > T мод. T мод брать по результатам счета лабораторной работы №1 (время окончания переходного процесса умноженное на 2). Число реализаций N=50. Построить графики изменения m L , a n , P обсл и их доверительных интервалов от времени. Величину доверительной вероятности принять равной ?=0,9

Решаем систему дифференциальных уравнений методом Рунге-Кутта (правые части уравнений записаны в векторе D, начальные условия - в векторе x):

Моделирование

Время моделирования Tмод = 3 (время окончания переходного процесса по результатам лабораторной работы равно 1.3 с).

Время ожидания выбираем из условия Tожид > Tмод, отсюда Tожид = 4 с.

Параметры модели:

Входной поток (интервал времени между заявками):

Интенсивность: 7

Очередь:

Длина очереди: 3

Время ухода из очереди:

Закон распределения: Детерминированный

Величина: 4

Каналы обслуживания:

Число каналов: 3

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

Закон распределения: Экспоненциальный

Интенсивность: 2

Результаты работы программы:

Оценки математических ожиданий:

| 1,00 | 6,940 | 0,320 | 0,000 | 3,500 | 0,720 | 0,029 | 2,400 |

| 2,00 | 14,060 | 1,640 | 0,000 | 8,540 | 1,280 | 0,107 | 2,600 |

| 3,00 | 21,040 | 3,480 | 0,000 | 13,500 | 1,440 | 0,169 | 2,620 |

| 4,00 | 28,220 | 5,560 | 0,000 | 18,620 | 1,300 | 0,213 | 2,740 |

| 5,00 | 35,060 | 7,060 | 0,000 | 24,200 | 1,080 | 0,235 | 2,720 |

| 6,00 | 42,460 | 8,860 | 0,000 | 29,240 | 1,660 | 0,244 | 2,700 |

| 7,00 | 49,440 | 10,620 | 0,000 | 35,000 | 1,180 | 0,252 | 2,640 |

| 8,00 | 56,300 | 11,960 | 0,000 | 40,680 | 1,060 | 0,258 | 2,600 |

| 9,00 | 63,040 | 13,480 | 0,000 | 45,720 | 1,220 | 0,264 | 2,620 |

| 10,00 | 69,920 | 14,940 | 0,000 | 50,940 | 1,300 | 0,269 | 2,740 |

| 11,00 | 76,800 | 16,220 | 0,000 | 56,640 | 1,220 | 0,273 | 2,720 |

| 12,00 | 83,780 | 17,500 | 0,000 | 62,380 | 1,300 | 0,274 | 2,600 |

| 13,00 | 90,720 | 19,640 | 0,000 | 67,240 | 1,300 | 0,276 | 2,540 |

| 14,00 | 98,060 | 21,320 | 0,000 | 72,700 | 1,340 | 0,280 | 2,700 |

| 15,00 | 105,420 | 22,960 | 0,000 | 78,400 | 1,360 | 0,283 | 2,700 |

| 16,00 | 112,620 | 24,640 | 0,000 | 84,280 | 1,080 | 0,284 | 2,620 |

| 17,00 | 120,200 | 25,880 | 0,000 | 90,300 | 1,460 | 0,284 | 2,560 |

| 18,00 | 126,640 | 27,500 | 0,000 | 95,300 | 1,260 | 0,287 | 2,580 |

| 19,00 | 133,680 | 28,920 | 0,000 | 100,840 | 1,180 | 0,290 | 2,740 |

| 20,00 | 140,340 | 30,300 | 0,000 | 106,260 | 1,180 | 0,291 | 2,600 |

Оценки среднеквадратических отклонений:

| 1,00 | 2,745 | 0,785 | 0,000 | 1,941 | 1,000 | 0,046 | 0,916 |

| 2,00 | 3,722 | 2,197 | 0,000 | 3,054 | 1,200 | 0,086 | 0,774 |

| 3,00 | 4,906 | 3,067 | 0,000 | 3,822 | 1,235 | 0,105 | 0,718 |

| 4,00 | 5,231 | 4,176 | 0,000 | 4,151 | 1,204 | 0,100 | 0,558 |

| 5,00 | 5,984 | 5,131 | 0,000 | 4,507 | 1,110 | 0,097 | 0,530 |

| 6,00 | 6,548 | 5,830 | 0,000 | 4,773 | 1,210 | 0,088 | 0,670 |

| 7,00 | 7,518 | 6,495 | 0,000 | 5,355 | 1,125 | 0,085 | 0,624 |

| 8,00 | 7,759 | 6,971 | 0,000 | 5,773 | 1,173 | 0,082 | 0,692 |

| 9,00 | 7,725 | 7,278 | 0,000 | 6,000 | 1,237 | 0,080 | 0,718 |

| 10,00 | 8,143 | 7,882 | 0,000 | 6,077 | 1,100 | 0,080 | 0,558 |

| 11,00 | 9,361 | 8,367 | 0,000 | 6,802 | 1,118 | 0,076 | 0,722 |

| 12,00 | 10,286 | 8,690 | 0,000 | 6,831 | 1,268 | 0,075 | 0,824 |

| 13,00 | 10,438 | 8,885 | 0,000 | 6,553 | 1,204 | 0,070 | 0,780 |

| 14,00 | 10,887 | 9,321 | 0,000 | 6,394 | 1,193 | 0,067 | 0,670 |

| 15,00 | 10,398 | 8,991 | 0,000 | 6,587 | 1,179 | 0,065 | 0,670 |

| 16,00 | 10,805 | 9,333 | 0,000 | 6,600 | 1,110 | 0,063 | 0,745 |

| 17,00 | 11,144 | 9,704 | 0,000 | 7,108 | 1,152 | 0,063 | 0,875 |

| 18,00 | 11,704 | 10,425 | 0,000 | 7,566 | 1,261 | 0,062 | 0,776 |

| 19,00 | 11,853 | 10,665 | 0,000 | 7,606 | 1,089 | 0,061 | 0,521 |

| 20,00 | 11,969 | 10,562 | 0,000 | 8,009 | 1,107 | 0,059 | 0,800 |

Так какN = 50, то для построения доверительных интервалов, учитывая, что значение доверительной вероятности ? = 0.9, то t?рассчитывается с использованием нормального закона:

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

Mn - из Л.Р. 1

а - моделирование

Математическое ожидание средней длины очереди:

Вычисление доверительного интервала:

Для средней длины очереди:

Lm - из Л.Р. 1

m - моделирование

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

Вероятность обслуживания равна вероятности того, что в системе ещё не находится n+m требований, т.е. Po = 1 - Pn+m = 1 - P6

Вычисление доверительного интервала:

Для вероятности обслуживания:

Po1 - из Л.Р. 1

Po - моделирование

3. Для заданного (базового) варианта СМО исследовать влияние t ожид на характеристики системы в стационарном режиме

a) H(t) - детерминированный, tожид=Tожидания_среднее

b) H(t) подчинено экспоненциальному закону распределения. Математическое ожидание tожид равно Tожидания_среднее*{0,25; 0,5; 1; 2}.

Выводы

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

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

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

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

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

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

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

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

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

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

Рис. 8.6.

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

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

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

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

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

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

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

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

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

Ординарный стационарный поток без последствия называется простейшим (или стационарным пуассоновским). Термин «пуассоновский поток» употребляется потому, что, как известно из теории вероятностей, для ординарного потока без последствия число событий, попадающих на участок t, распределено по закону Пуассона:

где Хх = а - математическое ожидание количества событий на участке т; X - параметр, характеризующий плотность потока (к > 0);

Рщ СО - вероятность того, что за время X произойдет т событий.

В частности, при т = 0

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

т. е. вероятность того, что за время т произойдет хотя бы одно событие.

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

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

t o6 - среднее время обслуживания требования.

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

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

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

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

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

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

Кратко рассмотрим подход к решению одной из классических задач теории массового обслуживания. Пусть имеется п станков и бригада из т человек, обслуживающая эти станки. Станок, работающий в момент времени t, отказывает к моменту t + т с вероятностью Р(т) = - 1 - е~ кх, где е~ кХ есть вероятность того, что за время t не произойдет ни одного отказа. Время ремонта станка - случайная величина г). Для такой системы можно вычислить среднее число простаивающих рабочих. Эта характеристика используется в дальнейшем для оптимального выбора соотношения между пит исходя из экономических критериев.

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

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

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

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

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

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

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

Чаще всего в формулах используется параметр а = А/p, тогда предыдущую формулу запишем так:

Частными случаями этой формулы будут:

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

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

На практике необходимо часто определять:

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

Это будет и доля загруженных аппаратов за время обслуживания:

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

Коэффициент простоя аппаратов:

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

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

Рассмотрим несколько примеров.

Пример 1. Необходимо оценить работу автоматизированной телефонной станции (АТС), которая имеет п = 5 линий связи. К услугам станции обращаются абоненты с требованиями на ведение разговоров. Естественно, что моменты поступления требований на станцию случайны и независимы друг от друга.

Задачу решим на примере простейшего потока требований. Пусть средняя плотность потока вызовов в единицу времени X = 2. Продолжительность каждого разговора - также величина случайная. Можно принять, что продолжительность разговоров различных абонентов подчинена показательному закону распределения. Пусть среднее время, необходимое для ведения каждого разговора, равно t o6 = 1 ед. времени. Может возникнуть сомнение в правомочности принятия показательного закона распределения времени ведения разговоров абонентов. Но, как уже говорилось выше, формулами Эрланга можно пользоваться при любых законах распределения времени разговоров абонентов.

В итоге в предлагаемом примере необходимо оценить функционирование АТС.

Решение

Находим параметр

Вероятность того, что все линии будут свободны при работе АТС, может быть определена по формуле (8.24):

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

Определяем среднее число занятых линий связи во время работы АТС.

Для проведения необходимых расчетов составим таблицу 8.3.

Таблица для расчета параметров задачи

По результатам расчетов получено:

Коэффициент простоя линий равен:

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

Пример 2. Необходимо спроектировать АТС с пропускной способностью, при которой вероятность получения абонентом отказа в обслуживании не превосходила Р п X = 0,5 вызова в минуту. Считается, что средняя продолжительность разговора равна f o6 -2 мин. Определить необходимое число линий связи.

Значит, коэффициент загрузки линий связи равен:

Среднее число свободных линий связи равно:

Решение

Определяем параметр

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

Таблица 8.4

Определение вероятностей

Из данных таблицы 8.4 следует, что АТС нужно проектировать на 5 линий связи. При этом будет обеспечена связь одного абонента с другими с вероятностью Р = 0,997.

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

Вывод приводимых ниже формул можно найти в работе .

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

2. Постановка задачи теории очередей.

3. Подходы решения задач теории очередей.

Краткое содержание темы

Любая система массового обслуживания может включать в себя следующие элементы:

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

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

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

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

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

Основными компонентами модели очереди являются:

описание входящего потока требований;

описание способа, которым выполняется обслуживание (т.е. описание дисциплины обслуживания);

описание дисциплины очереди (т.е. каким образом из очереди выбираются клиенты на обслуживание: “первый пришел - первый обслужен”, “последний пришел - первый обслужен”, “по указанным приоритетам” и т.п.).

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

Принципиальными характеристиками очереди являются:

длина очереди в различные моменты времени;

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

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

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

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

1. Требования поступают через одинаковые интервалы времени. Каждый интервал имеет длину a единиц.

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

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

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

Поведение системы зависит от того, как связаны между собой величины a и b. Возможны три случая: 1) b > a; 2) b = a; 3) b < a. Рассмотрим каждый из этих случаев.

1) Случай b > a. Это значит, что скорость обслуживания 1/b меньше, чем скорость поступления требований 1/a, т.е. требования обслуживаются и покидают систему медленнее, чем прибывают. Следовательно, в этом случае будет образовываться очередь и она будет постоянно возрастать.

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

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

3) Случай b < a. Это значит, что скорость обслуживания больше, чем скорость поступления требований. Следовательно, какое бы ни было начальное число ожидающих обслуживания требований, длина очереди будет сокращаться до 1 или 0.

Пусть в начале процесса число требований в очереди r 2 (если первоначально есть только одно требование (r = 1), то оно будет обслужено прежде, чем поступят на обслуживание следующие требования, и очередь будет пустой).

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

где обозначение [x] означает целую часть числа x. Действительно, очередь будет отсутствовать, если через обслуживающее устройство полностью пройдет N+r требований. Для этого потребуется (N+r)b единиц времени. За это время на обслуживание поступит N требований, так что к поступлению (N+1)-го требования обслуживающее устройство будет свободно и готово обслужить его сразу без всякой очереди. Но (N+1)-е требование поступит на обслуживание через (N+1)a единиц времени, при этом будет выполнено соотношение:

Докажем, что в полученном соотношении N больше правой части не более чем на 1. Действительно, первое стоящее в очереди требование будет уже обслужено, а первое вновь поступающее на обслуживание требование еще не появится в очереди (a > b). Поэтому справедливо соотношение:

aN (N+r-1)b или.

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

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

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

В теории очередей важной функцией является функция времени ожидания обслуживания. Обозначим ее через W(t). Определим W(t) как время, которое необходимо затратить на ожидание обслуживания требования, поступившего в момент времени t (считаем, что t = 0 соответствует началу процесса обслуживания).

Определим формулу для W(t). Легко видеть, что требование, поступившее на обслуживание в момент t T-b (величина T определяется с использованием формулы (10.3)), найдет систему обслуживания пустой или только что освободившейся. Такому требованию не придется стоять в очереди. Требование, поступившее в момент времени tT-b, найдет впереди себя требований, стоящих в очереди, причем первое из них в этот же момент поступит на обслуживающее устройство. Эта величина получается следующим образом:

(начальная (число требований, обслужен- (число поступ-

очередь) - ных к моменту времени t) + лений)

Таким образом, время ожидания W(t) для рассматриваемого требования может быть выражено формулой:

Рассмотрим i-е требование в начальной очереди (0

Обобщая полученные результаты относительно функции W(t), получим для нее следующее выражение:

где i - номер i-го требования в начальной очереди; требования поступают в моменты времени a, 2a, ...; b = na (n = 1, 2, ...).