Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

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




 

 


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

 

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

 

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

1) системы массового обслуживания с потерями (отказами);

2) системы массового обслуживания с ожиданием;

3) системы массового обслуживания с ограниченной длиной очереди;

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

 

Источник требований:

1. Бесконечный

2. Конечный

 

Входной поток:

1. Пуасона

2. Эрланга

3. Регулярный

По числу каналов обслуживания делятся на одноканальные и многоканальные.

 

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

 

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

А – тип распределения входящего потока требований,

В – тип распределения времени обслуживания,

C – число каналов обслуживания.

D – количество мест в очереди.

Также

Запись М | М | 3 означает, что входящий поток требований пуассоновский (простейший), время обслуживания распределено по экспоненциальному закону, в системе имеется три канала обслуживания.

 

 

Лекция № 8 (27.09.2013)

 

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

Состояние системы – связано с числом заявок системы.

 

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

 

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

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

 

Вершины – состояния системы. Дуги – переходы с соответствующих вершин.

– система дифф. Уравнения Колмагорова.

- уравнение нормировки.

 

 


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

 

 

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

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

 

 

Пример:

 

 

;

Пусть , тогда

 

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

Система рождения и гибели:

 


Используя уравнения Колмагорова получили:

 

 

Многофункциональная СМО с отказами (задача Эрланга)

 

 


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

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

- интенсивность обслуживания;

- колличество каналов;

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

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

- абсолютная пропускная способность (интенсивность потока на выхода);

– вероятность потерь;

 

1. Введем множество состояний

– cистема пуста;

– один канал занят;

– все каналы заняты;

 

2. Нарисуем граф

 

3. Используя формулу гибели и рождения получим

– загрузка СМО (вероятность того, что систма находиться в занятом состоянии)

;

;

;

; где

;

;

;

 

 

Лекция № 9 (01.10.13)

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

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

;

;


<я не знаю откуда и к чему эта таблица, скорее всего расчетов, но как что считалось он не писал>

 
  0.294 0.159 0.116 0.1 0.094 0.092
  0.706 0.847 0.677 0.406 0.195 0.024
  0.294 0.153 0.323 0.594 0.805 0.976
            2.342

 

Видимо расчет таблицы:

;

 

=;

 

 

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

 


1. Введем множество возможных состояний

– cистема пуста;

– система обслуживает заявку;

 

2. Нарисуем граф состояний

 

 
 

 


3. Запишем дифференциальное уравнение Колмогорова.

;

 

– Вероятность того, что СМО находиться в состоянии ;

– Вероятность того, что СМО находиться в состоянии ;

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

- вероятность отказа ()

 

 

Всегда ли существуют финальные вероятности?

1. Финальные вероятности существуют в том случае, если загрузка системы меньше для одноканальной СМО.

2. Число состояний СМО – должно быть конечно и из каждого состояния можно попасть в любое другое состояние за конечное число шагов.

Если выполняются оба условия, то можно составить систему Колмогорова.

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

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

 

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

Определить характеристики СМО и оценить эффективность работы.

;

;

 

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

M/M/3/m

3 – число каналов; m – длина очереди;

 

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

 
 

 

 


1. Введем множество состояний

– cистема пуста;

– система обслуживает заявку;

– канал занят заявкой + одна заявка в очереди;

– канал занят заявкой + m заявок в очереди;

2. Зарисуем граф состояний.

 

 


3. Используя формулы гибели и размножения, имеем:

;

;

;

;

При условии, что , получим систему без очереди

;

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

;

;

; – размер очереди.) – количество каналов;

Очередь будет отдичаться от общего числа заявок в системе на величину звгрузки ;

Временные характеристики определяются по формуле Литтла:

;

;

Формула Литтла связывает 3 величины:

 

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

 

 

1. Введем множество состояний

– cистема пуста;

– система обслуживает заявку;

– n заявка;

– канал занят заявкой + n заявок в очереди;

 

 

2. Зарисуем граф состояний.

 

 

3. Используя формулы гибели и размножения, имеем:

;

;

;

;

 

Лекция № 10 (4.10.2013)

 

;

;

– длина очереди.

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

– среднее время, которое заявка проводит в очереди.

– время пребывания, с момента захода до выхода – время ответа.

Вывод формулы Литтла.

 


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

- случайный процесс ухода заявок.

Система простаивает в момент времени, где ступни кривых совпадают.

;

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

;

;

Следовательно:

– первая формула Литтла.

- вторая формула Литтла.

 

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

 

 

1. Множество состояний

– cистема пуста;

– один канал занят;

– n каналов заняты;

– n каналов заняты + 1 заявка в очереди ;

– n каналов заняты + m заявок в очереди (в этом состоянии происходят потери);

2. Граф состояний

 

 
 

 

 


3. Используя формулы рождения и гибели получим:

;

;

;

;

;

Вероятность возникновения очереди:

;

;

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

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

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

;

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

;

;

По формуле Литла определяем:

;

;

 

 

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

 

1. Множество состояний.

– cистема пуста;

– один канал занят;

– n каналов заняты;

– n каналов заняты + 1 заявка в очереди ;

– n каналов заняты + 2 заявок в очереди ;

2. Граф состояний

 

 

3. Используя формулы рождения и гибели получим:

;

;

;

;

;

Вероятность образования очереди:

;

;

;

Средняя длина очереди.

;

;

 

 

Пример:

На замок демонов в среднем нападают 3 отряда немцев в час. Замок обороняют колдуна 2-го уровня. Среднее время уничтожения отрядов – час. В очереди подраться могут стоять не более 4 отрядов.

 
 

 


Рещение:

, , .

,,

Вероятность отсутствия машин на складе:

;

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

;

;

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

;

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

;

И это намного меньше 4х

 

Пример:

Интенсивность потока посетителей столовой составляет 150 человек в час () есть кассира () каждый из которых обслуживает человека в минуту . Нацти характеристики СМО.

 

Решение:

, , .

.

Вероятность отсутствия посетителей в столовой

;

Т.е. работники столовой почти всегда заняты

Вероятность образования очереди:

;

Среднее число посетителей:

человека

А среднее число обслуженных посетителей равно:

человек

Значит

;

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

мин

Можно сделать вывод, что работа в столовой организована эффективно.

 

Лекция № 11 (08.10.2013)

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

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

- предельно допустимое время ожидания.

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

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

 

 
 

 


1. Введем множество состояний

– cистема пуста;

– одна заявка;

– n заявок;

;

– n заявок + m заявок в очереди ;

2. Граф состояний

 


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

 

 

3. Используя формулы рождения и гибели получим:

;

;

;

;

;

 

;

;

 

Вероятность образования очереди:

;

Отказ системы происходит в состоянии

;

 

;

;

 

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

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

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

 

 

 

 


1. Введем множество состояний

– cистема пуста;

– 1 элемент сломался и ремонтируется;

– 2 элемента сломались, 1 ремонтируется, 1 в очереди;

– n элементов сломались, 1 ремонтируется, в очереди;

 

2. Граф состояний

 
 

 


3. Используя формулы рождения и гибели получим:

 

;

;

;

;

;

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

 

Системы типа M//1, M/D/1, M/G/1.

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

;

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

– среднеквадратическое отклонение.

– среднее время обслуживания.

– коэффициент вариации времени обслуживания.

– время пребывания;

– время ожидания;

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

1. Система типа M/D/1 с постоянным обслуживанием.

;

4. Система типа M/M/1 с экспоненциальным обслуживанием.

; ;

5. Система типа M//1 с эрланговским обслуживанием.

; – показатель закона Эрланга.

;

 

 


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

 

 

Лекция № 12 (11.10.2013)

 

Системы с неограниченными потоками.

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

 

 

Дисциплина обслуживания(ДО) – порядок выбора заявок из очереди на обслужмвание. Можно предположить множество ДО.

 

FIFO – первым пришел, первым обслужился.

LIFO – последним пришел, первым обслужился.

RANDOM – случайный выбор из очереди.

Все потоки равноправны – время ожидания в очереди у них одинаково.

 

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

– коэффициент вариации времени обслуживания. (отношение времени обслуживания к среднему математическому ожиданию времени обслуживания).

– среднее время ожидания в очереди для заявок k-го потока.

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

;

;

Где ;

 

 

При выводе формулы применяются следущие допущения:

1. Один обслуживающий прибор;

2. Бесконечная очередь;

3. Заявки поступают независимо друг от друга;

4. ДО подчинена произвольному закону и не зависят друг от друга;

5. Прибор обслуживания не простаивает если накопителе имеется хотя бы одна заявка любого класса;

6. Выбор на обслуживание производится мгновенно;

 

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

- суммарная загрузка по всем потокам. ;

 

Свойство ДО без приоритетов:

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

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

3. Среднее время ожидания минимальнл когда имеется постоянное, детерминированное время обслуживания и увеличивается с ростом коэффициент вариации.

4. Среднее время ожидания нелинейно зависит от коэффициента вариации

().

При получаем ;

При получаем двухкратное увеличение;

При получаем 5 пятикратное увеличение;

5. Среднее время ожидания хаявок зависит от суммарной загрузки систем

 

 

 


, – это превышение относительно равно времени обслуживания.

( – различно, - одинаково) длины очередей будут различны. Длины очередей равны если

6. Показано, что если обслуживание производится в обратном порядке(LIFO?) средние времена будут одинаковы, но дисперсия .

 

Циклическая ДО.

       
 
 
   

 


Сперва выбираются заявки из первого потока, далее из второго и так по циклу.

 

Дисциплины с относительным приоритетом.

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

 

 

6 – обслуживается, 1,2,5,4 – в очереди, 1- только прибыла в очередь.

;

Заявки в очереди не мешают обслуживанию заявки . После того как ушла, то меняются приоритеты и выбирается 1. Если в процессе обслуживания пришла еще , то она берется после освобождения. Этот цикл без прерывания.

;

Где ;

;

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

;

;

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

; ;

;

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

 

 

 


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

 

     
 
 
 

 

 


Лекция №13 (15.10.2013)

ДО с абсолютным приоритетом.

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

 

 
 

 


;

– сумма загрузок до k-го

;

;

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

– Среднее время ожидания в прерванном состоянии (время в очереди прерываний );

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

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

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

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

На рисунке изображена зависимость среднего времени k-го класса от номера приоритета.

       
   
 

 

 


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

 

Закон сохранения времени ожидания.

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

;

;

;

 

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

1. Система работает без потерь;

2. Система простаивает лишь в том случае, если нет заявок;

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

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

Закон сохранения для времени пребывания:

;

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

– времена обработки всех заявок одинаковые. Тогда :

;

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

 

Стохоастические сети СМО.

1. Разомкнутые – есть поток из вне.

2. Замкнутые

 

Первое предположение: разомкнутая сеть содержит узлов (СМО)

Второе предположение: после завершения обслуживания в узле k-я заявка переходит в другой узел.

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

Четвертое предположение: В любомканале есть накопитель бесконечного объема

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

Шестое предположение: Длительность обслуживания экспоненциальная величина распределенная по случайному закону.

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

Задается:

1. – Сколько узлов в сети;

2. – Количество каналов;

3. – Интенсивность обслуживаия СМО

4. Интнсивность входного потока.

5. Матрица-вероятности переходов

 

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







Дата добавления: 2015-03-11; просмотров: 1540. Нарушение авторских прав

codlug.info - Студопедия - 2014-2017 год . (0.069 сек.) русская версия | украинская версия