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

Национальный исследовательский ядерный университет «МИФИ»

 

Е.А. Елтаренко

 

Конспект лекций по разделу

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

 

 

Москва 2013

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

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

Основные понятия СМО

Рассмотрим основные понятия СМО, их характеристики, классификацию. Ниже представлена структурная схема СМО.

Источник заявок

®

Очередь заявок

®

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

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

обслуживания

а) характеристики (параметры) входного потока заявок:

– плотность функции распределения интервала между поступлениями заявок;

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

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

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

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

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

в) характеристики (параметры) очереди:

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

– дисциплина очереди:

- первым пришел – первым ушел (FIFO);

- последним пришел – первым ушел (LIFO);

- с приоритетами;

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

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

Классификация СМО

Если (см. п.1.2.), то такие СМО называются пуассоновскими.

– одноканальные СМО;

– многоканальные СМО;

– системы без очередей;

– системы с бесконечной очередью;

(произвольное конечное число) – системы с ограниченной очередью.

– сети СМО, узлами сети являются отдельные СМО. Выделяют ациклические сети (рис. 1.1) и циклические сети (рис. 1.2).

0,3

		СМО1	®	СМО2
Источник		0,7 ¯	0,7	­1,0
		СМО3	®	СМО4

0,3 – вероятность

Рис. 1.1. Топология ациклической сети СМО

0,3

		СМО1	®	СМО2
Источник		0,7 ¯­0,2	0,5	­1,0
		СМО3	®	СМО4

0,3

Рис. 1.2. Топология циклической сети СМО

Характеристики СМО

Основные характеристики

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

– среднее время пребывания заявок в СМО;

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

– среднее время ожидания заявок в очереди;

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

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

Производные характеристики

– среднее число свободных мест в очереди;

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

– среднее число свободных (простаивающих) каналов;

– эффективный (реальный) поток заявок, который обслуживается.

Связи между основными характеристиками (формулы Литтла)

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

Обозначим через , –время наблюдения.

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

n(t)

 

 

 

0 t₁ t₂ t

Рис. 1.3. График изменения числа заявок в СМО во времени

 

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

. (1.1)

Аналогично для средней длины очереди получим:

. (1.2)

иотличаются временем обслуживания.

, (1.3)

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

Таким образом, вычислив и ,можно, используя (1.1), (1.2), (1.3), вычислить все основные характеристики:

.

Отметим также следующие соотношения:

;

;

.

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

.

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

Потоки заявок

Остановимся на общем случае, когда для его описания требуется задать – плотность функции распределения интервала между поступлением заявок, и –… Простейший (пуассоновский) поток Свойства потока:

Марковские процессы

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

Вопросы и задачи

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

	S1	S2	S3
S1	0,3	0,3	0,4
S2	0,0	1,0	0,0
S3	0,0	0,0	1,0

2. Управляемый объект имеет 4 возможных состояния. Через каждый час производится снятие информации и перевод объекта из одного состояния в другое в соответствии со следующей матрицей вероятностей переходов:

	S1	S2	S3	S4
S1	0,3	0,4	0,0	0,3
S2	0,2	0,2	0,4	0,2
S3	0,4	0,3	0,2	0,1
S4	0,2	0,3	0,4	0,1

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

3. По заданным коэффициентам системы уравнений Колмогорова составить размеченный граф состояний. Определить коэффициенты А, В, С, Д в уравнениях:

-А Р1 + 4 Р2 + 5 Р3 = 0

-В Р2 + 4 Р1 + 2 Р4 = 0

-С Р3 + 2 Р2 + 6 Р1 = 0

-Д Р4 + 7 Р1 + 2 Р3 = 0.

4. Физическая система имеет 4 состояния. Размеченный граф состояний приведен ниже.

6

S₁ S₂

4 5 3

 

S₃ S₄

Определить предельные вероятности состояний системы.

 

Пуассоновские СМО

1.4.1. Одноканальные пуассоновские СМО СМО без очереди (N=0). Используем теорию процессов гибели и размножения для…    

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

       

Пуассоновские сети СМО

      Рис. 1.20. Топология сети СМО  

Оптимизация параметров СМО

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

потери от низкого затраты на

уровня функционирование

обслуживания СМО

 

оптимальный уровень качество

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

Рис. 1.31. Определение оптимального уровня качества СМО

 

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

Задача оптимальной интенсивности обслуживания в одноканальной СМО с бесконечной очередью

Класс СМО.

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

С учетом того, что , получим целевую функцию: . Для определения минимума целевой функции найдем производную:

.

Искомая оптимальная интенсивность находится из уравнения:

,

.

Задача оптимальной интенсивности в одноканальной СМО без очереди

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

Поскольку , , то

,

,

откуда получим:

.

Задачи оптимизации параметров многоканальной СМО

Определение оптимального числа каналов. Сформируем целевую функцию: , где – затраты в единицу времени на функционирование одного канала, – то же,…   Класс СМО.

Задачи оптимизации СМО по нескольким параметрам

Класс СМО .

Рассмотрим задачу определения оптимального количества каналов m и числа мест в очереди N в многоканальных СМО.

Целевая функция имеет вид:

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

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

Вопросы и задачи

1. Для каких классов СМО справедливы формулы Литтла?

2. Информационная система технологии "клиент-сервер" обслуживает клиентов. Поток запросов в систему пуассоновский, интенсивностью 20/мин. Время обработки запроса сервером (поиск и передача по каналам связи) распределено по экспоненциальному закону. Интенсивность обработки сервером запросов равна 30/мин.

Определить: а) какую часть времени сервер простаивает; б) среднее время реакции (время ответа) информационной системы.

3.В парикмахерской клиентов обслуживают 4 мастера. Время обслуживания распределено по экспоненциальному закону. Среднее время обслуживания одного клиента 30/мин. Поток клиентов пуассоновский – 6 чел./ч.

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

4. Задана циклическая пуассоновская сеть СМО. Входной поток интенсивностью − 10 заявок/ч, интенсивность обслуживания в СМО₁ − 20 заявок/ч, в СМО₂ − 16 заявок/ч, в СМО₃ – 18 заявок/ч.

СМО1

			Выход из сети

0,3

Источник заявок

0,4

0,5

 

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

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

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