Санкт-Петербургский государственный университет
Факультет прикладной математики — процессов управления
Кафедра информационных систем
Гусев Сергей Михайлович
Выпускная квалификационная работа бакалавра
Нестационарная система обслуживания с
конечным источником заявок с
относительными приоритетами
Направление 010400
Прикладная математика, фундаментальная информатика и
программирование
Заведующий кафедрой,
доктор физ.-мат. наук,
профессор
Олемской И. В.
Научный руководитель,
кандидат физ.-мат. наук,
доцент
Ерёмин А. С.
Рецензент,
доктор физ.-мат. наук,
профессор
Буре В. М.
Санкт-Петербург
2016
Содержание
Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
Простая нестационарная система обслуживания . . . . . . . . . . . .
4
Нестационарные системы обслуживания с относительными приоритетами . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
Постановка задачи . . . . . . . . . . . . . . . . . . . . . . . . . .
5
Теория . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
Алгоритм составления матрицы A . . . . . . . . . . . . . . . . .
9
Сравнение результатов с имитационной моделью . . . . . . . . .
11
Заключение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
14
Список литературы . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15
2
Введение
Нестационарные системы обслуживания (НСО) — это системы массового обслуживания [1] с конечным количеством заявок и, следовательно,
состояний, каждое из которых определяется числом поступивших и числом
обслуженных заявок [2]. Бо́льшая часть работ по теории массового обслуживания посвящена стационарному режиму систем с неограниченными заявками и его характеристикам, таким как пропускная способность, среднее
количество заявок в очереди и т. д. Но он существует только у тех систем,
у которых задания обслуживаются в среднем быстрее, чем поступают. Потому для многих задач практический интерес представляет исследование
нестационарных систем. Поскольку они завершают обслуживание за конечное время, то вместо стационарного режима рассматривают переходный процесс и его характеристики, такие как вероятность того, что длина
очереди превысит заданное число, вероятность нахождения в свободном
состоянии, математическое ожидание времени, за которое будет обработано некое количество заявок, вероятность завершения обслуживания за
фиксированное время и т. д.
Вероятности нахождения системы в том или ином состоянии есть
функции от времени, которые являются решением обратного уравнения
Чепмена — Колмогорова [3]:
dP (t)
= AP (t),
dt
(1)
P (0) = (1, 0, . . . , 0)T ,
(2)
с начальным условием:
где P (t) — вектор-функция, i-й элемент которой равен вероятности нахождения системы в i-м состоянии в момент t, а A — матрица интенсивностей,
где Aij — интенсивность перехода из j-го состояния в i-е при i ̸= j, Aii —
суммарная интенсивность переходов из i-го состояния.
3
Простая нестационарная система обслуживания
Рассмотрим одноканальную нестационарную систему обслуживания,
на вход которой поступает N заявок с интенсивностями поступления и
обработки, зависящими от номера заявки. Дисциплина обслуживания —
FIFO (First in first out), что значит, что заявки обслуживаются в порядке их
поступления. Интервалы времени между поступлением заявок, случайны
и подчиняются экспоненциальному закону распределения. Интенсивности
поступления обозначим вектором λ, обработки — µ, p-е компоненты векторов относятся к p-й заявке. Интенсивность потока равна среднему количеству
событий,
происходящих
в
единицу
времени.
Данной системе можно сопоставить граф,
изображенный на рис. 1, вершины которого соответствуют состояниям системы, а
стрелки — возможным переходам. У вершин указано число поступивших и обработанных заявок, у стрелок — интенсивности
переходов. Общее количество состояний будет равно
(N +1)(N +2)
.
2
Значение вероятности
нахождения в состоянии с i поступившими
и j обработанными заявками можно найти
Рис. 1
из уравнения:
dPi,j (t)
= θ(i) × (Pi−1,j (t)λi+j − Pi,j (t)µj+1 ) + θ(j) × Pi+1,j−1 (t) × µj −
dt
−θ(N − i − j) × Pi,j (t)λi+j+1 ,
1, x > 0;
1, i + j = 0;
где θ(x) =
Pi,j (0) =
0, x 6 0,
0, i + j ̸= 0.
4
Нестационарные системы обслуживания с
относительными приоритетами
В данной работе рассматриваются нестационарные системы обслуживания с относительными приоритетами [4], это значит, что в НСО поступает несколько независимых пуассоновских потоков заявок. Заявки более
высокого приоритета обрабатываются в первую очередь, но уже начатое обслуживание заявки, пусть даже более низкого приоритета не прерывается.
Время обработки заявок, так же как и поступления, опять же, подчиняется
экспоненциальному закону распределения с различными интенсивностями
для каждой заявки. То есть если обозначить за λ интенсивность поступления заявки, то время, через которое она поступит, есть случайная величина
с плотностью распределения равной λe−λt , t > 0.
Постановка задачи
Системы с приоритетами также описываются системой уравнений вида (1). Для расчета характеристик переходного процесса НСО с известными интенсивностями поступления и обработки заявок требуется построить
матрицу A, соответствующую возможным переходам между состояниями.
Систему (1) можно решить аналитически, если известны собственные
числа матрицы A. Поскольку система не имеет возвратных состояний, существует возможность упорядочить состояния таким образом, чтобы матрица A была треугольной. В таком случае собственные числа будут в явном
виде представлены на её диагонали.
К сожалению, граф, соответствующий НСО с приоритетами, в общем случае, не обладает свойством планарности, потому наглядно изобразить его возможно только для самых простых случаев. Так, например, на
рис. 2 изображен граф, соответствующий НСО с всего лишь двумя заявками разных приоритетов. В вершинах обозначения даны следующим образом: в первой строке обозначено количество поступивших, но не обслуженных и обслуженных заявок высокого приоритета, во второй — то же самое
5
для заявок низкого приоритета. Простыми стрелками обозначены переходы, соответствующие поступлению заявки, пунктирными —обслуживанию.
Пример приведен для того, чтобы обозначить важное свойство НСО с относительными приоритетами — наличие состояний, отличающихся только
лишь номером приоритета заявки, обслуживаемой в данный момент. Данная особенность значительно увеличивает количество состояний системы.
Рис. 2: Граф, соответствующий простейшей НСО с двумя приоритетами
6
Теория
Введем следующие обозначения:
• r — количество потоков заявок с различными приоритетами, заявки из
потока с бо́льшим номером, имеют более высокий приоритет,
• N — вектор количества заявок каждого приоритета N = (N1 , . . . , Nr ),
• i — вектор количества поступивших, но не обработанных заявок каждого приоритета, i = (i1 , . . . , ir ),
• j — вектор количества обработанных заявок каждого приоритета,
j = (j1 , . . . , jr ),
• λ1 , . . . , λr — векторы интенсивностей поступления заявок,
λp = (λp,1 , . . . , λp,Np ),
• µ1 , . . . , µr — векторы интенсивностей обработки заявок,
µp = (µp,1 , . . . , µp,Np ),
• d — приоритет заявки, обрабатываемой в текущий момент (для определенности будем считать, что d = 0 при i = (0, . . . , 0)),
• k(i, j, d) — функция, отображающая параметры состояния в его номер.
Таким образом, НСО с относительными приоритетами описывается
векторами λ1 ,. . . , λr , µ1 ,. . . , µr , а каждое её состояние можно обозначить
вектором (i1 , . . . , ir , j1 , . . . , jr , d), или, короче, (i, j, d), где 0 6 ip + jp 6 Np ,
p = 1, . . . , r, d = 0, 1, . . . , r.
В начальный момент времени система находится в нулевом состоянии, то есть без поступивших и обработанных заявок.
Из каждого состояния система может перейти в не более чем r + 1
состояний, где r возможных переходов — поступление новой заявки и ещё
один — обработка. То есть возможны следующие переходы:
• (i1 , . . . , ir , j1 , . . . , jr , d) → (i1 , . . . , ip +1, . . . , ir , j1 , . . . , jr , d), если ip +jp <
Np , p = 1, . . . , r, причем интенсивность перехода будет равна λp,ip +jp +1 .
Этот переход соответствует поступлению заявки приоритета p.
7
• (i1 , . . . , ir , j1 , . . . , jr , d) → (i1 , . . . , id − 1, . . . , ir , j1 , . . . , jd + 1, . . . , jr , m),
если d ̸= 0, интенсивность перехода — µd,jd , m равен наибольшему
индексу среди ненулевых элементов вектора i нового состояния.
Этот переход соответствует обработке заявки приоритета d.
Следовательно, при использовании следующих замен:
r
∑
k̂(i, j, d, p) = k(i1 , . . . , ip − 1, . . . , ir , j1 , . . . , jr , d × θ( il − 1)),
l=1
k̄(i, j, d) = k(i1 , . . . , ip + 1, . . . , ir , j1 , . . . , jp − 1, . . . , jr , d),
k-e уравнение системы (1) примет следующий вид:
Ṗk(i,j,d)(t) =
r [
∑
p=1
]
θ(ip) × λp,ip+jp × Pk̂(i,j,d,p)(t) +
r [
]
∑
+θ(d − max(p) + 1) ×
θ(jp) × µp,jp × Pk̄(i,j,p)(t) −
ip >0
p=1
( r
)
]
∑[
−
θ(Np − ip − jp)λp,ip+jp+1 + θ(d)µd,jd+1 × Pk(i,j,d)(t)
p=1
Рано или поздно НСО заканчивает обработку всех заявок и остается
в состоянии (0, N, 0), дальнейшие переходы невозможны.
8
Алгоритм составления матрицы A
Для того чтобы матрица A была нижнетреугольной, требуется чтобы
состояния с меньшим номером не зависели от состояний с бо́льшим. Для
этого нужно разбить множество состояний на подмножества с одинаковым числом обработанных заявок наивысшего приоритета и упорядочить
их по его возрастанию, затем каждое подмножество аналогичным образом разбить на подмножества и упорядочить их относительно количества
поступивших, но ещё не обработанных заявок с наивысшим приоритетом.
Затем следует повторять данную операцию для каждого приоритета, в порядке его убывания. Также, для определенности, будем считать, что состояния, отличающиеся лишь параметром d, будут также упорядочены по
его возрастанию. То есть упорядочивание состояний идет по возрастанию
параметров в следующем порядке: jr , ir , jr−1 , ir−1 ,. . . , j1 , i1 , d.
Алгоритм формирования матрицы A последовательно пробегает по
всем состояниям системы и заполняет соответствующие им столбцы матрицы интенсивностями переходов в другие состояния в соответствии с принятой нумерацией.
Данный алгоритм был реализован на языке C#.
k
1
2
3
4
5
6
7
8
9
10
i1
0
1
0
0
1
1
0
0
1
0
i2
0
0
0
1
1
1
1
0
0
0
j1
0
0
1
0
0
0
1
0
0
1
j2
0
0
0
0
0
0
0
1
1
1
d
0
1
0
2
1
2
2
0
1
0
Таблица 1: Порядок состояний простейшей НСО с двумя приоритетами
Так, в табл. 1 приведен порядок состояний НСО с двумя поступающими заявками разных приоритетов, а матрица A примет следующий вид:
9
−(λ1 + λ2 )
0
0
0
0
0
0
0
0
λ1
−(λ2 + µ1 ) 0
0
0
0
0
0
0
0
µ1
−λ2
0
0
0
0
0
0
λ2
0
0 −(λ1 + µ2 ) 0
0
0
0
0
0
λ2
0
0
−µ1
0
0
0
0
A=
0
0
0
λ1
0 −µ2
0
0
0
0
0
λ2
0
µ1
0 −µ2
0
0
0
0
0
µ2
0
0
0 −λ1
0
0
0
0
0
0
µ2
0
λ1 −µ1
0
0
0
0
0
0
µ2
0
µ1
0
0
0
0
0
0
0
0
0
0
Также стоит заметить, что нижнетреугольная матрица позволяет находить вероятность нахождения системы в состоянии с номером k не решая
систему дифференциальных уравнений полностью, а лишь меньшую систему из не более чем k первых уравнений.
10
Сравнение результатов с имитационной моделью
В пакете MatLab была написана функция, имитирующая поведение
НСО c девятью поступающими заявками, пять из которых имеют высокий
приоритет. Параметры данной НСО: λ1 = (0.6, 0.8, 2, 1.5), µ1 = (0.5, 0.7, 3, 1.2),
λ2 = (1, 1.1, 1.5, 1.3, 0.7), µ2 = (0.7, 1.2, 0.8, 1, 0.8). Имитационная модель
запускается много раз, и значения вероятностей нахождения в определённых состояниях в каждый момент времени находятся отношением количества попаданий в эти состояния к общему числу запусков.
Для той же НСО при помощи реализации описанного алгоритма была найдена матрица A. Затем система (1) была решена методом, описанным в статье [5]. На рис. 3 представлено сравнение решения с результатами
100-кратной имитации на промежутке времени от 0 до 30 c. Сравниваются графики вероятности нахождения системы в свободном состоянии, то
есть без заявок, которые ждут обработки. Пунктирная линия — решение
системы (1), непрерывная — результаты имитации. Максимальная разница
между значениями на рассматриваемом промежутке — 0.0734.
Рис. 3: Вероятность свободного состояния, максимальная разница между 100-кратной
имитацией и решением системы ОДУ — 0.0734.
11
Для получения более точных результатов следующие сравнения проводились уже с результатами 100000-кратной имитации. Визуально решение и результаты имитации становятся неразличимы (см. рис. 4–6).
Рис. 4: Вероятность свободного состояния, максимальная разница — 0.0033
Рис. 5: Вероятность того, что суммарное количество заявок в очереди превысит три,
максимальная разница — 0.0022
12
Так например, матожидание времени, за которое будут обслужены
все заявки, вычисленное через решение системы (1), составило 11.7172 с, а
среднее время обработки всех заявок по результатам имитации — 11.7203 c.
Таким образом, абсолютная разница этих двух значений составляет менее
0.003 с, а относительная — менее 0.03%, что свидетельствует о правильности формирования матрицы A.
Рис. 6: Вероятность обработки всех заявок, максимальная разница — 0.0027
13
Заключение
В рамках данной работы был разработан алгоритм составления уравнений уравнений Чепмена — Колмогорова и написана его программная реализация, которая, в совокупности с реализацией метода, описанного в [5],
может быть использована для расчета надежности и пропускной способности аппаратно-программных комплексов, у которых множество выполняемых заданий можно разделить на группы с разными приоритетами. В рассмотренном примере для простоты были использованы заявки только двух
приоритетов, но сконструированный алгоритм применим к системам с любым количеством приоритетов. В будущем возможно расширение метода
для применения к многоканальным системам и/или системам с неэкспоненциальными законами распределения времен поступления и обработки
заявок.
14
Список литературы
[1] Клейнрок Л. Теория массового обслуживания; пер. с анг. И. И. Грушко,
ред. В. И. Нейман. М.: Машиностроение, 1979. 432 c.
[2] Бубнов В. П., Сафонов В. И. Разработка динамических моделей нестационарных систем обслуживания. СПб.: Издательство «Лань», 1999.
64 c.
[3] Бубнов В. П., Тырва А. В., Еремин А. С. Комплекс моделей нестационарных систем обслуживания с распределениями фазового типа // Труды СПИИРАН. 2014. Вып. 37. C. 61–71.
[4] Матвеев В. Ф., Ушаков В. Г. Системы массового обслуживания. М.: Издво МГУ, 1984. 240 c.
[5] Бубнов В. П., Еремин А. С., Сергеев С. А. Особенности программной
реализации численно-аналитического метода расчёта моделей нестационарных систем обслуживания // Труды СПИИРАН. 2015. Вып. 38.
C. 218–232.
15
Отзывы:
Авторизуйтесь, чтобы оставить отзыв