4 системы массового обслуживания icon

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


1 чел. помогло.
Смотрите также:
Лабораторная работа №3. Системы массового обслуживания...
Лекция 2 (4 часа). Моделирование вс на основе систем и сетей массового обслуживания...
5. Теория массового обслуживания При исследовании операций часто приходится сталкиваться с...
«Информационные системы в управлении предприятием»...
Рабочая программа дисциплины «сервисная деятельность» для специальности 100106 «организация...
Кафедра высшей математики повторные испытания...
Исследование систем массового обслуживания с переменными параметрами...
Концепция вс с управлением потоком данных 70 10. Закон Амдала и его следствия 71 Глава 3 72...
Рабочая программа дисциплина «Системы технического обслуживания и ремонта технологических машин...
Методические указания по курсовому проектированию по курсу «Исследование систем управления»...
Лурия А. Р. Основы нейропсихологии: Учеб. Пособие для студ. Высш учеб заведений. 3-е изд., стер...
К 50-летию основания отрасли бытового обслуживания населения...



Загрузка...
скачать

Разработано доцентом каф. ОСУ, к.т.н., О.В.Марухиной

Тема 4


СИСТЕМЫ МАССОВОГО ОБСЛУЖИВАНИЯ

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


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

  • Билетные кассы;

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

  • Торговые, транспортные, энергетические системы;

  • Системы связи;

  • И т.д.

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



Рис. 1. Основные сферы применения ТМО.

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

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

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

  2. Накопитель (очередь).

  3. Приборы (каналы обслуживания).

  4. Выходящий поток.



Рис. 2. Общая схема систем массового обслуживания.




Рис. 3. Модель работы системы

(стрелками показаны моменты поступления требований в

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

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


В зависимости от правил образования очереди различают следующие СМО:

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

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

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

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

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

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

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

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

Пуассон Симеон (1781 - 1840) - французский математик, механик и физик, профессор Политехнической школы в Париже (с 1806 г.), член института Франции и Бюро долгот (с 1812 г.), член Совета французского университета (с 1816 г.), наблюдатель за преподаванием математики во всех коллежах Франция (с 1820 г.), почетный член Петербургской академии наук (с 1826 г.); получил выдающиеся результаты в области теории рядов, теории неопределенных интегралов, вариационного исчисления, теории вероятностей, математической физики, теоретической механики; предложил (названный его именем) один из важнейших законов распределения случайных величин в теории вероятностей.

Определение 5. Интенсивностью потока заявок λ называется среднее число заявок, поступающих из потока за единицу времени.

Для стационарного потока интенсивность постоянна. Если τ – среднее значение интервала времени между двумя соседними заявками, то В случае пуассоновского потока вероятность поступления на обслуживание m заявок за промежуток времени t определяется по закону Пуассона:



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

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

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

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


^

Марковский случайный процесс


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

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

Такие процессы бывают двух типов: с дискретным или непрерывным временем.

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

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

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

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

Марков Андрей Андреевич (1856 - 1922) - известный русский математик, ординарный академик Петербургской академии наук, заслуженный профессор Петербургского университета. Основные исследования А.А. Маркова относятся к теории чисел, теории вероятностей и математическому анализу.

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

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

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

СМО с отказами


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

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

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


свободны все каналы;

занят ровно один канал;



заняты k каналов;



заняты все n каналов/


Через обозначим вероятность того, что в момент времени t система будет находиться в состоянии .

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

Для установившегося процесса обслуживания при этих условиях Эрланг получил следующие зависимости.


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

(3.1)

где k – количество занятых аппаратов,

λ – интенсивность потока заявок,

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


^ ЧАСТНЫМИ СЛУЧАЯМИ ЭТОЙ ФОРМУЛЫ БУДУТ:

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

(3.2)

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

(3.3)

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

(3.4)

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



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

(3.5)

Доля каналов, занятых обслуживанием (коэффициент загрузки):

(3.6)


ПРИМЕР

На вход трехканальной СМО с отказами поступает поток заявок с интенсивностью λ = 4 заявки в минуту. Время обслуживания заявки одним каналом мин.

Найти показатели эффективности работы системы.

Решение

Находим вероятность простоя трехканальной СМО по формуле (3.2):

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





Вероятность отказа определяем по формуле (3.3):



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



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



Среднее число занятых каналов (в ед. времени) определяем по формуле (3.5):



Доля каналов, занятых обслуживанием (формула (3.6)):



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

мин.
^

СМО с неограниченным ожиданием


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



Для СМО с неограниченной очередью накладывается ограничение .

Если это условие нарушено, то очередь растет до бесконечности, наступает явление «взрыва».

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

(3.7)

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

(3.8)

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

(3.9)

  • Вероятность наличия очереди есть вероятность того, что число требований в системе больше числа каналов:

(3.10)

  • Вероятность для заявки попасть в очередь есть вероятность занятости всех каналов, эта вероятность равна сумме вероятностей наличия очереди и занятости всех n каналов при отсутствии очереди:

(3.11)

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

(3.12)

  • Доля каналов, занятых обслуживанием:

(3.13)

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

(3.14)

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

(3.15)

  • Среднее время ожидания заявки в очереди

(3.16)

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

(3.17)

ПРИМЕР

На вход трехканальной СМО с неограниченной очередью поступает поток заявок с интенсивностью λ = 4 заявки в минуту. Среднее время обслуживания заявки ч.

Найти показатели эффективности работы системы.

Решение

Для рассматриваемой системы



Определяем вероятность простоя по формуле (3.7):



Среднее число заявок в очереди находим по формуле (3.14):



Среднее время ожидания заявки в очереди считаем по формуле (3.16):

ч.

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

ч.
^

СМО с ожиданием и ограниченной длиной очереди


Имеется n-канальная СМО с ожиданием, в которой количество заявок, стоящих в очереди, ограничено числом m, т.е. заявка, заставшая все каналы занятыми, становится в очередь, только если в ней находится менее m заявок.

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

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

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

(3.18)

  • Вероятность отказа в обслуживании равна вероятности того, что в очереди уже стоят m заявок:

(3.19)

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



(3.20)

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

(3.21)

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

(3.22)

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

(3.23)

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

(3.24)

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

(3.25)

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

(3.26)

ПРИМЕР

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

Решение

Для данной задачи



Определяем вероятность простоя по формуле (3.18):



Вероятность отказа в обслуживании определим по формуле (3.19)



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



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



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



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



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

ч.

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

.

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

ч.


^

Замкнутые СМО


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

Примеры:

  • Поликлиника, обслуживающая данную территорию.

  • Бригада рабочих, закрепленная за группой станков.

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

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

Пусть n – число каналов обслуживания, s – число потенциальных заявок, , λ –интенсивность потока заявок каждого потенциального требования,  – интенсивность обслуживания, . Поток

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

нет заявок):

(3.27)



  • Финальные вероятности состояний системы

(3.28)

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

или

(3.29)

Через находим абсолютную пропускную способность системы

(3.30)

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

(3.31)


ПРИМЕР

Рабочий обслуживает 4 станка. Каждый станок отказывает с интенсивностью λ = 0,5 отказа в час. Среднее время ремонта ч. Определить пропускную способность системы.

Решение

Эта задача рассматривает замкнутую СМО,



Вероятность простоя рабочего определяется по формуле (3.27):



Вероятность занятости рабочего

.

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

станков в час.







Скачать 136,73 Kb.
оставить комментарий
Дата04.03.2012
Размер136,73 Kb.
ТипДокументы, Образовательные материалы
Добавить документ в свой блог или на сайт

отлично
  7
Ваша оценка:
Разместите кнопку на своём сайте или блоге:
rudocs.exdat.com

Загрузка...
База данных защищена авторским правом ©exdat 2000-2017
При копировании материала укажите ссылку
обратиться к администрации
Анализ
Справочники
Сценарии
Рефераты
Курсовые работы
Авторефераты
Программы
Методички
Документы
Понятия

опубликовать
Загрузка...
Документы

Рейтинг@Mail.ru
наверх