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

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

Вероятность поступления заявки за 5 мин равна , а вероятность обслуживания заявки за 5 мин – .

В начальный момент в системе

отсутствовали заявки для ,

одна заявка – для ,

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

Необходимо:

а) определить множество состояний СМО и граф состояний СМО;

б) вычислить матрицу переходных состояний;

в) найти вектор вероятностей состояний по истечении одного 1ч и 2ч;

г) найти стационарный режим работы СМО (вектор вероятностей состояния стационарного режима);

д) сравнить результаты, полученные в пунктах в и г. Сделать выводы.

Задание 2. На сортировочную станцию в среднем за сутки прибывает N составов. Среднее время обслуживания (сортировки) состава составляет t мин. В парке прибытия имеется m путей для ожидания сортировки прибывающих составов, а в случае занятости этих путей составы ожидают обслуживания на внешних путях.

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

Для расчетов принять N = 45 + k, m = 3, , руб., где номер варианта.

Задание 3. Ремонтное предприятие имеет линий ремонта и мест ожидания. Поток заявок для ремонта простейший с интенсивностью ед. в час. Среднее время ремонта заявки составляет ч. Предприятие платит штраф за ожидание заявки в очереди Z₂ руб. в час, штраф за отказ в обслуживании Z₃ руб., и имеет расходы с содержанием свободных каналов обслуживания Z₁ руб. в час. Исходные данные к заданию определяются по номеру варианта из табл. 8.1, 8.2.

Необходимо:

а) изобразить граф состояний СМО;

б) определить характеристики СМО;

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

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

Таблица 8.1

Параметр	Первая цифра номера варианта
	0	1	2	3
	5	4	3	6
	3	4	5	5
	0,005	0,007	0,004	0,006

Таблица 8.2

Параметр	Последняя цифра номера варианта
	0	1	2	3	4	5	6	7	8	9
	3	4	5	6	2	3	4	5	2	4
	0,15	0,12	0,15	0,16	0,21	0,22	0,20	0,23	0,11	0,18
Z1	35	30	38	42	33	40	44	45	32	37
Z2	58	55	60	61	59	57	62	64	62	58
Z3	62	60	65	70	71	68	66	72	73	68

Методические указания по выполнению заданий

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

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

СМО делятся на системы с отказами и системы с ожиданием (очередью).

В СМО имеются следующие основные элементы:

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

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

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

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

В зависимости от этих характеристик СМО можно разбить на два больших класса:

1) СМО с дискретным состоянием и дискретным временем;

2) СМО с дискретным состоянием и непрерывным временем.

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

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

А – среднее число заявок, обслуживаемое СМО в единицу времени, т.е. абсолютная пропускная способность СМО;

Q – вероятность обслуживания поступившей заявки, т.е. относительная пропускная способность СМО;

Р_отк – вероятность отказа, вероятность того, что поступившая в систему заявка не будет обслужена, тогда Р_отк = 1 – Q;

L – среднее число заявок в СМО (на обслуживании и в очереди);

L_o – среднее число заявок в очереди, если она есть (т.е. средняя длина очереди);

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

W_оч – среднее время пребывания заявки в очереди;

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

Выбор показателей эффективности зависит от типа СМО.

Анализ работы СМО с дискретными состояниями и дискретным временем

Задача: Пусть имеем одноканальную СМО, в которую заявки могут поступать в определенные моменты времени t₁, t₂,…t_k с вероятностью Р₁. Если в момент поступления очередной заявки канал обслуживания занят, то заявка занимает место в очереди. Если в очереди на обслуживание уже имеется две заявки, то вновь поступившая заявка в очередь не становится (все места заняты), не обслуживается и покидает систему (получает отказ). Обслуживание заявки, поступившей на обслуживание, завершается в каждый указанный момент времени с вероятностью Р₂. (В момент времени t_k в систему поступает не более одной заявки и не более чем одна заявка может покинуть систему).

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

Решение

Пусть возможные состояния рассматриваемой СМО следующие:

S₀ – в очереди на обслуживание нет ни одной заявки;

S_N – в очереди на обслуживание имеется N заявок, N = 1,2.

Данная СМО может быть исследована с помощью теории марковской цепи, изложенной в [2], так как процесс, происходящий в СМО, представляет собой марковский процесс с дискретными состояниями (S₀, S₁, S₂) и дискретным временем (t₁, t₂,…t_k,…). Находим матрицу переходных вероятностей системы из одного состояния системы S_i в другое S_j:

; (8.1)

где

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

Пусть имеем граф состояний системы

Рис. 8.1

и = 0,7; = 0,6, тогда = 0,3, = 0,4, и, использовав предыдущие формулы (8.1), получим матрицу переходных вероятностей в данной СМО:

P =

Можно найти вероятности состояний очереди после шагов по формуле

или

где – вектор вероятностей состояний в начальный момент времени, для которого выполняется

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

тогда

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

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

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

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

Решение системы: (0,5213; 0,37; 0,1064).

Заметим, что (0,515; 0,374; 0,111), а (0,5207; 0,3724; 0,1068). Таким образом, можно считать, что в момент времени t10 система работает в стационарном режиме, т.е. вероятности состояний системы не зависят от вектора вероятностей состояний в начале работы.