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

Варанкин Игорь Игоревич

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

Рассматривается одноканальная нестационарная система массового обслуживания с абсолютным приоритетом. На вход подаются заявки разных групп. Для каждой группы известно число заявок, интенсивности их поступления и обработки. Распределения временных интервалов поступления и обработки заявок подчиняются экспоненциальным законам. Причем заявки первой группы (первого приоритета) имеют преимущество над заявками второй группы, а те, в свою очередь, над заявками третьей группы, и так далее. При поступлении более приоритетной заявки, обработка менее приоритетной прекращается, и возобновляется, лишь после обработки всех заявок более важных заявок. В статье описывается алгоритма формирования системы уравнений Чепмена-Колмогорова с треугольной матрицей, на основе вышеописанной системы. Проводится сравнение решения полученной системы с результатами имитационного моделирования.

Общественные науки в целом

Дипломы

Вуз: Санкт-Петербургский государственный университет (СПбГУ)

ID: 587d36555f1be77c40d58ce6

UUID: 5361e2bb-1934-4b6c-bc8b-8df21f323061

Язык: Русский

Опубликовано: почти 8 лет назад

Просмотры: 85

Варанкин Игорь Игоревич

Источник: Санкт-Петербургский государственный университет

Комментировать 0

Рецензировать 0

Скачать - 517331 bytes

Поделиться работой

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ КАФЕДРА ИНФОРМАЦИОННЫХ СИСТЕМ Варанкин Игорь Игоревич Выпускная квалификационная работа бакалавра Нестационарная система обслуживания с конечным источником заявок с абсолютными приоритетами Направление 010400 Прикладная математика и информатика Научный руководитель, кандидат физ.-мат. наук, доцент Еремин А. С. Санкт-Петербург 2016

Содержание Введение ........................................................................................................ 3 Постановка задачи ........................................................................................5 Обзор литературы .........................................................................................6 Глава 1. Аналитическая модель НСО.......................................................... 8 1.1. Модель НСО .....................................................................................8 1.2. Модель НСО с абсолютными приоритетами...............................12 Глава 2. Описание алгоритма..................................................................... 16 2.1. Формирование списка возможных состояний.............................16 2.2. Заполнение матрицы коэффициентов ..........................................20 2.3. Реализация решения ......................................................................21 2.4. Реализация имитационного моделирования ...............................23 Глава 3. Практический пример ..................................................................25 ..................................................................................................................................... Заключение ..................................................................................................33 Список литературы .....................................................................................34 2

Введение Теория массового обслуживания (ТМО) является относительно новым разделом теории вероятности. Целью изучения ТМО является выбор структуры системы обслуживания и процесса обслуживания на основе изучения потоков требований на обслуживание, поступающих в систему и выходящие из неё, длительности ожидания и длины очередей. Большинство авторов используют модели ТМО в предположении, что очередь заявок бесконечна, существует стационарный режим. Это позволяет оценить эффективность системы обслуживания на длительном интервале времени, получить характеристики «в среднем». Какой в среднем процент заявок будет теряться, какая средняя длительность ожидания обслуживания, какая в среднем нагрузка на один канал и т.д. В то же время большой практический и теоретический интерес представляют модели нестационарных систем обслуживания (НСО). Изучению таких систем посвящено сравнительно мало работ. Под моделью НСО понимается модель системы обслуживания с переменными во времени вероятностями состояний, каждое из которых определяет вероятность числа находящихся в НСО заявок и числа получивших обслуживание заявок. Число заявок, поступающих на обслуживание в рассматриваемых моделях, конечно. Стационарный режим не выделяется и основным предметом исследования является переходный процесс. Соответственно и важными характеристиками системы являются совсем другие: например среднее время обработки всех или некоторого числа заявок или вероятность не уложиться в требуемые сроки, вероятность превышения критической длины очереди, вероятность отказа в обслуживании критического числа заявок и т.д. Для иллюстрации важности моделирования НСО можно рассмотреть работу приемной комиссии университета. Заявления на поступление, приходят концентрированно в течение небольшого 3

промежутка времени. Кроме того нас не интересует сколько из них мы можем потерять ведь важно обработать их все. Поэтому одной из важных характеристик будет являться количество людей (каналов обслуживания) необходимых для обработки заявлений в срок. Имеется большое число реальных ситуаций, когда в потоке требований могут содержаться требования нескольких типов, причем требования первого типа обслуживаются вне всякой очереди, если только в очереди нет требований того же типа. По отношению к требованиям третьего и следующих типов правом преимущества пользуются требования второго типа и т.д. В качестве хорошего примера можно привести обслуживание на телеграфе, где срочные телеграммы передаются раньше обычных, даже когда простые телеграммы сданы ранее срочных. Далее будут рассматриваться системы с так называемыми абсолютными приоритетами, в которых обслуживание заявки меньшего приоритета в случае прихода более «важной» заявки прерывается, и возобновляется лишь после обработки всех более приоритетных заявок. Вероятности нахождения системы в том или ином состоянии есть функции от времени, которые являются решением обратного уравнения Чепмена – Колмогорова. Однако его составление даже для одноканальной НСО с абсолютными приоритетами представляется проблематичным. В данной работе предст авлен а лгоритм формирования нижнетреугольной матрицы коэффициентов линейной стационарной системы обыкновенных дифференциальных уравнений (ОДУ) для вышеуказанных систем без вывода общего уравнения системы. Для проверки корректности составления матрицы, проводится сравнение решения системы ОДУ с указанной матрицей коэффициентов, и результатами имитационного моделирования. Так же приведены графики, отображающие наиболее интересные характеристики исследуемой системы. 4

Постановка задачи Рассматривается одноканальная нестационарная система массового обслуживания с абсолютными приоритетами. На вход системы поступают N заявок K типов (приоритетов) (K ≤ N). Известно сколько заявок каждого типа может прийти. Распределения временных интервалов между моментами поступления заявок описывается экспоненциальными законами с интенсивностями, зависящими от номера типа заявок. Закон распределения времён обслуживания – экспоненциальный с интенсивностями, так же зависящими от номера типа заявок. Вычислительную систему представим в виде одноканальной нестационарной системы обслуживания без потерь. Необходимо сформулировать правила формирования списка состояний, а так же способ генерации нижнетреугольной матрицы коэффициентов системы однородных дифференциальных уравнений, описывающих вышеуказанную систему. 5

Обзор литературы Изучение нестационарных систем обслуживания на практике, как впрочем и всей теории массового обслуживания, невозможно без должного освоения теоретической литературы. В книге Дж. Кемени и Дж. Снелла [6] изложены основы теории цепей Маркова. Основные теоремы даны в простой и понятной форме, не требующей глубоких математических познаний. В последнем разделе учебника Е. С. Венцель [4], даются основные определения и теоремы ТМО. Автор учебника ставил задачу изложить предмет наиболее просто и наглядно. Книга снабжена большим количеством примеров, в ряде случаев расчетного характера, в которых применение излагаемых методов иллюстрируется на конкретном практическом материале и доводится до численного результата. Для более подробного и целостного изучения ТМО следует обратиться к труду А. Я. Хинчина [10], а так же к работе Л. Клейнрока [7]. В книге Б. В. Гнеденко, И. Н. Коваленко [5] помимо рассмотрения задач теории массового обслуживания в целом и методов их решений, уделено внимание интересующим нас нестационарным системам обслуживания. В учебнике В. Ф. Матвеева и В. Г. Ушакова [8] рассматриваются приоритетные НСО, в частности системы с абсолютными приоритетами. Методическое издание В. П. Бубнова и В. И. Сафонова [2] содержит рассмотрение основных моделей НСО с различными типами поступления и обработки заявок. Приводятся диаграммы переходов, а так же характеристики этих моделей. Статья В. П. Бубнова, А. С. Еремина и С. А. Сергеева [1] содержит описание численно-аналитического метода решения уравнения Чепмена6

Колмогорова. Показано преимущество данного метода над “классическим” методом Рунге-Кутты четвертого порядка с постоянным шагом, а так же м е т о д о м ode4 5 п а к е т а Matlab, использующимися при решении вышеуказанных уравнений. Глава 1. Аналитическая модель НСО 7

1.1. Модель НСО Рассмотрим систему обслуживания, на вход которой последовательно поступает N заявок. Распределения временных интервалов между моментами поступления заявок описываются экспоненциальными законами с интенсивностями, зависящими от номера заявки, { λ1 , λ2 , … , λN } соответственно. Закон распределения времени обслуживания – экспоненциальный с интенсивностями, зависящими от номера заявок, { µ1 , µ2 , … , µ N } соответственно. Представим такую систему обслуживания вложенной марковской цепью с дискретным множеством состояний и непрерывным временем без потерь. [2] Марковская цепь – процесс, в котором для каждого момента времени вероятность любого состояния системы в будущем зависит только от состояния системы в настоящий момент времени и не зависит от того, каким образом система пришла в это состояние. [4] Система обслуживания без потерь – система, в которой заявки поступающие, в момент обработки какой либо другой заявки, не теряются. [7] Состояния системы в каждый момент времени будем характеризовать числом находящихся в системе запросов i (i = 0,N) и числом обработанных запросов j (i = 0,N-i) . Вероятности пребывания системы в этих состояниях будем обозначать P i , j (t ) . В таком представлении система будет иметь суммарное число состояний равное N c= ( N +1 ) (N +2)/ 2 . Все состояния невозвратные, иначе говоря, из них можно выйти, но вернуться уже нельзя. Конечное состояние – поглощающее, то есть, попав в него, выйти уже нельзя. Процесс однородный, не эргодический, для него не существует стационарного режима. 8

Однородный процесс – процесс, при котором в любой фиксированный интервал времени с вероятностью 1 система находится в одном из состояний. [5] Эргодический процесс – процесс, в котором из каждого состояния можно попасть в другое за конечное число шагов. [6] Под переходом из одного состояния в другое понимается поступление новой заявки на обслуживание, либо обработка заявки, которая в исходном состоянии обрабатывалась. Диаграмма переходов между состояниями системы представлена на рис.1и подробно рассмотрена в [9]. Рис. 1. Диаграмма переходов между состояниями НСО 9

Для того чтобы определить значения вероятностей нахождения системы в каждом из состояний необходимо решать относительно P i , j (t) систему дифференциальных уравнений i,j-тое уравнение которой в общем виде можно записать в виде d Pi , j ( t ) =H ( i ) ( Pi−1 , j ( t ) λ i+ j− Pi , j ( t ) µ j+1 ) +¿ dt + H ( j ) P i+1 , j−1 ( t ) µ j− H (N c −i− j) P i , j ( t ) λ i+ j+1 j (1) = 0,N, i = 0,N-j где H (k ) – функция Хевисайда: если k >0 {1,0,если k ≤0 H(k) = В качестве начальных условий выберем нахождение в состоянии (0,0), т о е с т ь P i , j ( 0 )=1− H (i+ j) . Для каждого момента времени должно выполняться условие вида N N −i ∑ ∑ P i , j ( t )=1 . [3] i=0 j=0 Рассмотренная выше линейная однородная система уравнений (1) представляет собой обратное уравнение Чепмена–Колмогорова и может быть представлена в матричной форме: Ṕ ( t )= AP(t ) г д е P(t ) – вектор неизвестных функций размерности N c , (2) аA – квадратная матрица. Для системы (2) существует явное аналитическое решение, если только известны собственные числа матрицы A. Очевидным является тот факт, что в с л у ч а е т р еу гол ь н о го в и д а м ат р и ц ы A ( для определенно сти – нижнетреугольного), её собственные числа выписаны в явном виде на диагонали. [1] 10

Если пронумеровать состояния по возрастанию числа обработанных заявок, а внутри этих групп по возрастанию числа поступивших заявок, то ни одно из состояний не будет иметь зависимости от последующих. Соответственно, полученная матрица будет нижнетреугольной. На графе это будет выглядеть как нумерация сверху вниз с перемещением по столбцам слева направо. [1] Рассмотрим простой пример заполнения матрицы A. Пусть может прийти 2 заявки с интенсивностями распределения времени (ИРВ) { λ1 , λ2 } соот вет ст вен н о. ИР В об раб от ки воз ьм ем равным и { µ1 , µ2 } соответственно. Количество состояний N c = 6. Тогда матрица A будет заполняться следующим образом. Диагональные элементы A[i,i] , i 0, ´N c = заполняются суммой интенсивностей выхода из i-го состояния, со знаком минус. Недиагональные элементы A[i,j], i = 0, N c−1 , j = 0, N c−i заполняются ИРВ перехода из j-го состояния в i-ое. Матрица A в этом маленьком примере выглядит так: - λ1 0 - λ2 - 0 0 0 0 λ1 µ1 0 0 0 0 0 λ2 0 0 0 0 µ1 0 - λ1 0 0 0 0 µ1 λ1 - µ2 0 0 0 0 0 µ2 0 - µ1 Значение вероятности нахождения в НСО i заявок в каждый момент времени определяется из формулы: N −i P i ( t )=∑ P i , j (t) j=0 Значение вероятности обслуживания j заявок в каждый момент времени определяется из: 11

N− j P j ( t )= ∑ P i , j (t) i=0 Значение вероятности обслуживания не менее q запросов может быть определено из выражения: N P q ( t )=∑ P j (t) i=q 1.2. Модель НСО с абсолютными приоритетами От рассмотрения простейшей одноканальной модели нестационарной системы обслуживания перейдем к одноканальной нестационарной системе с абсолютными приоритетами. На вход системы поступают N заявок K типов (приоритетов) (K ≤ N). Известно сколько заявок каждого типа может прийти. Распределения временных интервалов между моментами поступления заявок описывается экспоненциальными законами с интенсивностями, зависящими от номера типа заявок. Закон распределения времён обслуживания – экспоненциальный с интенсивностями, так же зависящими от номера типа заявок. Вычислительную систему представим в виде одноканальной нестационарной системы обслуживания без потерь. Введем некоторые обозначения:  – максимальное число заявок каждого приоритета n1 ,n2 , … , nk k (N = ∑ nz ) z=1  i1 ,i 2 ,… , ik – число поступивших в систему заявок соответствующего приоритета (обработанных и не обработанных) i1 = 0,n1 , … , i k =  0, nk , j1 , j2 , … , jk – число обработанных заявок соответствующего приоритета j1 = 0, n1 , … , j k = 0, nk , 12

 λ1 , λ 2 , …, λ k – интенсивности поступления заявок соответствующего типа  µ1 , µ2 ,… , µk – интенсивности обработки заявок соответствующего типа Таким образом, НСО с K приоритетами описывается K векторами (n1 , λ1 , µ1 ) , (n2 , λ 2 , µ 2) , … , (nk , λk , µ k ) .А любое состояние описывается вектором (i1 , j1 ,i 2 , j 2 , … , ik , jk ) . Граф переходов между со стояниями НСО с абсолютными приоритетами в общем случае является многомерным, и к тому же не обладает свойством планарности, а значит, не может быть изображен на плоскости без пересечения ребер. Вероятности нахождения системы в том или ином состоянии есть функции от времени, которые являются решением стационарной системы однородных дифференциальных уравнений: Ṕ ( t )= AP(t ) гд е P(t) – вектор функция, i-й компонент которой есть вероятность нахождения в i-ом состоянии в момент времени t, а A – квадратная матрица. В матрице A каждый недиагональный элемент A[i,j] содержит интенсивность перехода из j-го со стояния в i-ое, а диагональные A[i,i] – сумму интенсивностей обработки i-ой заявки, со знаком минус. В качестве начальных данных выберем нахождение системы в начальный момент времени в состоянии (0,0,0,0,…,0,0), то есть P 0 =P ( 0 ) =(1, 0 ,… , 0) . Стоит подчеркнуть основную особенность НСО с абсолютными приоритетами. Мы не можем приступить к обработке и даже продолжить обработку заявки с определенным приоритетом, если в очереди находится заявка более высокого приоритета. К примеру, рассмотрим систему, в которую может прийти три заявки первого приоритета и две второго. Пусть система находится в состоянии (2,1,1,0), то есть пришло две заявки первого 13

типа и одна из них уже обработана, а так же в очереди находится одна заявка второго типа. Рис.2 Возможные переходы из состояния (2,1,1,0) Как можно увидеть из рис.2 из состояния (2,1,1,0) можно получить заявку первого типа или второго типа, чему соответствуют первый и второй переходы на рис.2. Так же мы можем обработать заявку первого приоритета и перейти в состояние (2,2,1,0) , однако переход из (2,1,1,0) в (2,1,1,1) невозможен, так как в очереди есть еще необработанная заявка более высокого приоритета. Стоит отметить также, что возобновление обработки заявки, обработка которой была прервана приходом более приоритетной, начинается заново, то есть без учета того, сколько она обрабатывалась до этого. Поскольку система не имеет возвратных состояний, можно упорядочить состояния таким образом, чтобы матрица A была треугольной. В таком случае собственные числа будут находиться на её диагонали. Найти аналитическое решение системы в явном виде, зная собственные числа, не составит большого труда. Однако использовать стандартные методы решения систем дифференциальных уравнений с большими матрицами коэффициентов, даже зная собственные числа, не всегда рационально. Основными недостатками традиционных численных методов являются накапливаемая на каждом шаге интегрирования погрешность и время работы 14

алгоритма. Причем, вычислительная погрешность может привести и к отсутствию физического смысла получаемого решения. Поэтому рекомендуется использовать метод, описанный в статье [1]. Глава 2. Описание алгоритма В данном разделе будет описан алгоритм, принимающий на вход параметры нестационарной системы обслуживания с абсолютными приоритетами, и выдающий на выход нумерованный список возможных 15

состояний системы, а так же нижнетреугольную матрицу коэффициентов обратного уравнения Чепмена-Колмогорова. Алгоритм реализован на объектно-ориентированном языке C#. Программа принимает на вход данные вида: n1 : λ1 ; µ1 n2 : λ2 ; µ2 … nk : λ k ; µk 2.1. Формирование списка всех возможных состояний ИРВ поступления и обработки заявок нас интересовать пока не будут. Для формирования списка состояний нам потребуется лишь количество заявок каждого типа. Основной принцип алгоритма заключается в том, что все возможные состояния разбиваются на уровни. Каждый уровень фактически есть множество состояний, с одинаковым числом переходов. Любое состояние можно представить в виде ( i1 , j 1 , i2 , j2 , … , ik , j k ). Таким образом, номер уровня для любого из состояний может быть найден как: k nx L (i1 , j 1 , i2 , j2 , … ,i k , j k )=∑ ∑ (i y + j y ) x=1 y=0 Номер последнего уровня находится из формулы: k lastL=2∗∑ nx x =1 16

Очевидно, что нулевой и последний уровни будут состоять лишь из одного состояния (0,0, … ,0,0), (n1 , n1 , n2 , n2 , … , nk , nk ) соответственно. Алгоритм последовательно генерирует каждый уровень, начиная с нулевого. Каждая итерация получает на вход уровень. По окончании итерации производится очистка полученного уровня от одинаковых состояний, оставляя состояния лишь в единственном экземпляре. Итерации продолжаются, пока не будет сформирован последний уровень. Рассмотрим процесс формирования уровней подробнее. Начало итерации. Исследуем каждое состояние уровня. Просматриваем каждый четный (0-ую позицию считаем четной) элемент вектора (i1 , j1 ,i 2 , j 2 , … , ik , jk ) , другими словами смотрим на элементы i. Если i x <n x , x=1,k то в генерируемый уровень добавляем новое состояние, отличающееся от исходного, лишь тем, что i x увеличен на 1. То есть мы добавляем состояние, в котором пришла еще одна заявка x-го приоритета. Да л ее рассмат ри ваем каж дый нечетный элемент вектора (i1 , j1 ,i 2 , j 2 , … , ik , jk ) , то есть элементы j. Если j x <i x , x=1,k, то в генерируемый уровень добавляем новое состояние, отличающееся от исходного лишь тем, что j x увеличен на 1. Если мы создаем такое состояние, то прекращаем рассмотрение нечетных элементов вектора. Это позволит нам не рассматривать обработки системой заявок, при наличии в очереди заявки с более высоким приоритетом. Очищаем полученный уровень от дубликатов. Конец итерации. В итоговый список состояний добавляем сформированный уровень. 17

Переход между состояниями внутри уровня невозможен. Из любого уровня (кроме последнего) система может перейти только в следующий уровень. Если пронумеровать состояния, в том порядке, в котором они добавлялись итоговый список состояний, то получится что состояния с большим номером не зависят от состояний с меньшим. Это гарантирует нам нижнетреугольный вид матрицы коэффициентов обратного уравнения Чепмена-Колмогорова. Ниже представлены блок-схемы алгоритма. 18

X[i] возвращает i-й элемент структуры X. Метод X.Length возвращает количество элементов в X. Метод X.Add(Y) добавляет в конец структуры X структуру Y. Метод sum(X) возвращает сумму элементов вектора X. Метод X.ClearLevel – удаляет дубликаты из структуры X. 2.2. Заполнение матрицы коэффициентов Для начала создадим квадратную матрицу из нулей размерностью Nc×Nc , г д е Nc число состояний, которое мы получим после их генерации. Так же имеем список всех состояний. Структура хранения всех состояний выглядит следующим образом: список содержащий множество уровней от нулевого до последнего. Каждый уровень представляется списком состояний. Состояния представлены в виде векторов вида ( i1 , j 1 , j2 , … , ik , i2 , j k ). Каждому состоянию присваиваем номер, равный его порядковому, при расположении состояний в порядке возрастания уровней Так же нам потребуется максимальное число заявок каждого приоритета { n1 , n2 , … , nk }, и ИРВ поступления и обработки заявок каждого типа { λ1 , λ2 , … , λk } и { µ1 , µ2 , … , µk }. Нумеруем состояния, в том порядке, в котором они добавлялись итоговый список состояний. Алгоритм заполнения матрицы A просматривает все уровни, и каждое из состояний внутри уровней. Рассмотрение одного состояния будем называть одной итерацией. Начало итерации. Находим номер рассматриваемого состояния index1. 20

Просматриваем каждый четный (0-ую позицию считаем четной) элемент вектора ( i1 , j 1 , i2 , j2 , … , смотрим на i-e элементы. Если i x ik , j k ), другими словами < n x , x=1,k, то находим номер состояния в следующем уровне, отличающегося от исходного, лишь увеличенным на единицу i x . Номер найденного состояния index2. Это состояние, в которое мы можем перейти, получив заявку x-го приоритета. Далее в матрице A к значению ячейки [index2, index1] прибавляем значение λ x , а из значения ячейки [index1, index1] вычитаем λx . Далее рассматриваем каждый нечетный элемент вектора ( i1 , j 1 , i2 , j2 , … , ik , j k ), то есть j-e элементы. Если jx < i x , x=1,k, то находим номер состояния в следующем уровне, отличающегося от исходного, лишь увеличенным на единицу j x . Номер найденного состояния index2. Если мы находим такое состояние, то прекращаем рассмотрение нечетных элементов вектора. Это состояние, в которое мы можем попасть, обработав заявку x-го приоритета. В матрице A к значению ячейки [index2 , index1] прибавляем значение µ x , а из значения ячейки [index1 , index1] вычитаем µx . Конец итерации. 2.3. Реализация решения Рассматриваем обратное уравнение Чепмена – Колмогорова вида: (2) Ṕ ( t )= AP(t ) гд е P(t) – вектор функция, i-й компонент которой есть вероятность нахождения в i-ом состоянии в момент времени t, а A – найденная квадратная матрица. Решение системы было найдено методом матричной экспоненты. 21

В качестве начальных данных выберем вектор нахождения в состоянии (0,0,0,0, … ,0,0), то есть в нулевом состоянии: P 0 =P ( 0 ) =(1, 0 ,… , 0) Решение уравнения (2) можно выписать в явном виде: tA P ( t )=e P 0 Матричная экспонента etA находится как сумма ряда: ∞ e =E+∑ tA k =1 k t A k! k где E – единичная матрица. Суммирование заканчивается если очередное k-е слагаемое по норме мало: ‖ ‖ t k Ak <ɛ k! В качестве нормы матрицы выбрана норма Фробениуса: ‖Q‖= 2 Q[i , j] ∑ √ i, j Находим решение системы (2) во временном отрезке [0, maxT] с шагом step. Матрица решения Solve будет иметь размерность N c × ⌈ maxT /step ⌉ , где каждый столбец Solve[i,j] , i=1, N c−1 , для любого фиксированного j содержит вероятности нахождения системы в состояниях i в момент времени j×step. 22

2.4. Реализация имитационного моделирования При имитационном моделировании алгоритм, реализующий модель, воспроизводит процесс функционирования системы во времени. Имитируется процесс получения и обработки заявок, с сохранением логической структуры объекта и последовательности протекания процесса во времени. Это позволяет по исходным данным получить сведения о состоянии процесса в определенные моменты времени. Результаты, полученные имитационной моделью, являются реализацией случайных величин и функций, поэтому для нахождения характеристик процесса функциональной системы производится его многократное воспроизведение с последующей статистической обработкой. Пусть моделирование проводится N ℑ раз. Назовем один этап имитационного моделирования малой имитацией. Каждая малая имитация начинается из нулевого состояния и выполняется, пока система не окажется в последнем состоянии либо будет достигнут временной предел maxT. Изначально время имитации Time = 0. Матрица малой имитации smallImit имеет размерность N c × ⌈ maxT / step⌉ . ⌈ q⌉ – округление q до целого в большую сторону. ⌊ q ⌋ – округление q до целого в меньшую сторону. Рассмотрим один шаг малой имитации. Предположим, система находится в состоянии с номером p. Формируем множество состояний, в которое мы можем перейти из p-го состояния. Это множество будет состоять из состояний, в которое система может перейти, получив заявку каждого приоритета, или обработав наиболее приоритетную заявку. Каждому из возможных переходов соответствует ИРВ, с которой мы можем в него попасть. Генерируем экспоненциально распределенную 23

псевдослучайную величину - время перехода в каждое из состояний (параметром распределения служат ИРВ переходов). Выбираем состояние, в которое можем перейти за наименьшее время minTime В матрице имитации элементам smallImit[p,x] присвоить 1, где x=⌈ maxT /step ⌉ , ⌊(Time+minTime)/step ⌋ К суммарному времени имитации Time прибавляем minTime. Конец шага малой имитации. По окончании малой имитации элементы smallImit[i,j] равные 1 будут говорить о том, что в момент времени j×step система находилась в состоянии i. Проведя N ℑ малых имитаций, сложим все матрицы этих имитаций, и разделим каждый элемент этой суммы на N ℑ . В результате получим матрицу Imit. Смысл матрицы Imit такой же, как и у матрицы Solve. Анализ матриц Imit и Solve позволяет нам судить о правильности или не правильности работы алгоритма нумерации состояний и формировании матрицы коэффициентов обратного уравнения Чепмена-Колмогорова для НСО с абсолютными приоритетами. 24

Глава 3. Практический пример Рассмотрим конкретный пример НСО с абсолютными приоритетами. На вход программы подаются следующие данные: 2:0.5;0.3 5:0.4;0.25 3:0.6;0.5 Это интерпретируется так: n1 =2 , n2=5 , n3 =3 λ1=0.5 , µ1 =¿ 0.3 λ2=0.4 , µ2 =¿ 0.25 λ3=0.6 , µ3 =¿ 0.5 Суммарное число заявок N ¿ 10 . Число состояний после их генерации N c=1260 . Матрица A является нижнетреугольной и имеет размерность 1260×1260. Найдем матрицу решения обратного уравнения Чепмена-Колмогорова на отрезке [0,70] шагом step=0.5. Имитационное моделирование выполним на том же отрезке, то есть с параметром maxT=70 и step = 0.5. В результате работы программы получаем две матрицы одинаковой размерности 1260 × 141. Первая матрица – матрица решения уравнения Чепмена – Колмогорова, а вторая – результатов имитационного моделирования. i-я строка этих матриц содержит значения вероятностей 25

нахождения в i-ом сотоянии на протяжении всего временного интервала с выбранным шагом. На основании этих матриц c помощью пакета прикладных программ MATLAB были построены графики интересующих нас характеристик рассматриваемой системы. На рис. 2 изображены кривые вероятностей пребывания системы в последнем состоянии на рассматриваемом промежутке времени. Имитации проводились 200 раз. Сплошная кривая – кривая имитации, пунктирная – решения. Максимальная разница между значениями на указанном промежутке maxDiff = 0.0339. Рис.2 26

Кривые вероятностей нахождения системы в последнем состоянии уже при 1000 имитаций на исследуемом промежутке времени изображены на Рис. 3. maxDiff = 0.0144. Рис. 3 27

А на рис. 4 изображены кривые вероятностей нахождения в последнем состоянии при 100 000 имитаций. maxDiff=0.0015. Визуально графики сливаются. Рис. 4 Не трудно заметить тенденцию к уменьшению разницы между решением и результатом имитации при увеличении количества имитаций. Дальнейшие графики приводятся для числа имитаций равного 100 000. 28

График вероятностей того, что система находится в свободном состоянии, приводится на рис. 5. Свободное состояние системы – состояние, при котором в системе отсутствуют необработанные заявки. Рис. 5 На рисунках 6, 7 и 8 приведены графики вероятности того что в системе обработаны все заявки первого, второго и третьего типов соответственно. Сплошной линией, как и прежде, обозначается кривая, полученная в результате имитационного моделирования, а пунктирной – в результате решения. Визуально кривые практически не различимы, и максимальная разница между значениями на рассматриваемом промежутке указана ниже: maxDiff =0.0034 для рис. 6. maxDiff =0.0021 для рис. 7. maxDiff =0.0014 для рис. 8. 29

Рис. 6 Рис. 7 30

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

На рис. 9 приведены кривые вероятности того, что в системе находится в очереди более чем 2, 3 и 4 заявки. График построен основываясь на решении системы. Сплошной линией указана кривая, соответствующая вероятности нахождения в системе более 2-х необработанных заявок в очереди, пунктирной – более 3-х, штрихпунктирной – более 4-х. Рис. 9 32

Заключение В данной работе описан алгоритм формирования списка состояний для НСО с абсолютными приоритетами таким образом, чтобы матрица A коэффициентов уравнения Чепмена – Колмогорова, описывающего данную систему, имела нижнетреугольный вид. Правильность выполнения поставленной задачи показана, путем сравнения решения уравнения с ре зульт ат ами имит ационного моделирования. Для решения уравнения Чепмена – Колмогорова был реализован метод матричной экспоненты, имеющий очевидные недостатки. Одним из них является накапливающаяся величина погрешности округления, растущая вместе с увеличением рассматриваемого отрезка времени. Так же, в связи с разреженностью матрицы A, выбранный метод выполняет множество ненужных операций, что значительно увеличивает время работы программы. Чтобы максимально избежать описанных проблем, планируется использовать численно-аналитический метод, описанный в статье [1]. В дальнейшем планируется так же рассмотрение НСО с абсолютными приоритетами с несколькими каналами обслуживания, а так же с распределениями временных интервалов между моментами поступления и обработки заявок подчиняющимися гипер экспоненциальному распределению, а так же распределениям Эрланга и Кокса. Рост количества входных заявок увеличивает рассматриваемую систему на порядки, делая её крайне неудобной для исследования. В связи с этим возникает потребность в объединении состояний в группы по некоторому принципу, тем самым аппроксимируя исходную громоздкую систему. Выбор таких принципов так же входит в планы дальнейшего рассмотрения НСО с приоритетами. 33

Список литературы 1. Бубнов В. П., Еремин А. С., Сергеев С. А. Особенности программной реализации численно-аналитического метода расчета моделей нестационарных систем обслуживания // Труды СПИИРАН 2015. Вып. 38. С. 218-232. 2. Бубнов В. П., Сафонов В.И. Разработка динамических моделей нестационарных систем обслуживания. СПб.: Издательство «Лань». 1999. 64 с. 3. Бубнов В. П., Тырва А. В., Еремин А. С. Комплекс моделей нестационарных систем обслуживания с распределениями фазового типа // Труды СПИИРАН. 2014. Вып. 37. С. 61-71. 4. Вентцель Е.С. Теория вероятностей: Учебник для вузов. 6-е изд. стер. М.: Высш. шк., 1999. 576 c. 5. Гнеденко Б.В., Коваленко И.Н. Введение в теорию массового обслуживания. Изд. 5-е, испр. М.: Издательство ЛКИ, 2011. 400с. 6. Кемени Д. Дж., Снелл Дж. Л. Конечные цепи Маркова. М.: Наука, 1970, 271 с. 7. Клейнрок Л. Теория массового обслуживания. Пер. с англ./ Пер. И. И. Грушко; ред. В. И. Нейман. М.:Машиностроение, 1979. 432с. 8. Матвеев В. Ф., Ушаков В. Г. Системы массового обслуживания. М.: Изд-во МГУ, 1984. 240 c. 9. Сафонов В. И. Моделирование систем обслуживания с изменяющейся интенсивностью поступления запросов. Деп. в войсковой части 11520 № В 216 // УПИМ. 1987. Вып. 3, сер, Б. 10. Хинчин А. Я. Работы по математической теории массового обслуживания / Под редакцией Б. В. Гнеденко. М.: Физматгиз, 1963. 236 с. 34

Рецензии:

Авторизуйтесь, чтобы добавить рецензию

- у работы пока нет рецензий -

Отзывы:

Авторизуйтесь, чтобы оставить отзыв