Содержание к диссертации
Введение
1 Стационарные характеристики системы массового обслуживания SM/MSP/n/r 13
1.1. Описание системы 13
1.2. Система SM/MSP/n/r с конечным накопителем 15
1.3. Система SM/MSP/n/oo с бесконечным накопителем . 23
1.4. Система G/MSP/n/r 29
1.4.1. Система G/MSP/n/r с конечным накопителем . 29
1.4.2. Система G/MSP/n/oo с бесконечным накопителем . 32
1.5. Система массового обслуживания SM/MSP/1/r 34
1.5.1. Система SM/MSP/1/r с конечным накопителем . 35
1.5.2. Система SM/MSP/1/r с бесконечным накопителем 39
2 Стационарные характеристики системы массового обслу живания G/BMSP/1/r 43
2.1. Описание системы 43
2.2. Конечный накопитель 44
2.3. Бесконечный накопитель 48
3 Стационарные характеристики СМО G/MSP/n/r с пото ком отрицательных заявок 51
3.1. Описание системы 51
3.2. Конечный накопитель 55
3.3. Бесконечный накопитель 62
4 Алгоритмы расчета СМО 67
4.1. Алгоритмы расчета системы SM/MSP/n/r 67
4.2. Алгоритмы расчета системы G/MSP/n/r 72
4.3. Алгоритмы расчета системы SM/MSP/1/r. 74
4.4. Алгоритмы расчета системы G/BMSP/1/r. 75
4.5. Алгоритмы расчета системы G/MSP/n/r с потоком отрицательных заявок 76
5 Описание программного комплекса. Примеры расчета моделей систем массового обслуживания 81
Заключение 94
Список литературы
- Система SM/MSP/n/r с конечным накопителем
- Система G/MSP/n/r с конечным накопителем
- Бесконечный накопитель
- Конечный накопитель
Введение к работе
С момента появления первых телефонных сетей возникла необходимость решения задач расчета вероятностно-временных характеристик, среди которых основными являются стационарное распределение числа заявок в системе (для телефонных сетей важнейшей характеристикой является вероятность потери заявки), стационарные распределения времени ожидания начала обслуживания и времени пребывания заявки в системе. Эти задачи впервые поставлены известным датским ученым А.К. Эрлангом [42], который и является родоначальником теории массового обслуживания (ТМО). Внимание многих математиков привлекли возможности применения этой теории к важнейшим практическим задачам в самых различных сферах: при эксплуатации различных транспортных систем, в медицинском обслуживании, в страховом деле, при профилактическом обслуживании технических устройств. Значительный вклад в разработку и анализ классических моделей ТМО внесли А.Я. Хинчин, Б.В. Гнеденко, А.А. Боровков, Г.П. Башарин, Д. Кендалл, Д. Литтл, Д. Кокс, В. Смит, Л. Такач, Ф. Поллачек. Бурное развитие информационно-телекоммуникационных технологий и сетей различного назначения направило методы ТМО, в первую очередь, на решение задач именно в этой области.
Модели, рассмотренные Эрлангом, имели пуассоновский входящий поток и экспоненциальное обслуживание. Но еще при анализе телефонных сетей было замечено, что во многих случаях требование экспо-ненциальности времени обслуживания не выполнено. Первой попыткой более адекватного описания обслуживания в реальных системах стало использование моделей с рекуррентным обслуживанием. Большое число работ посвящено модели однолинейной системы массового обслуживания (СМО) M/G/1/oo1 с накопителем бесконечной емкости. Для исследования указанной модели СМО разработаны различные методы исследования: построение вложенной цепи Маркова по момен- *В дальнейшем будем придерживаться классификации СМО, которую ввел Д. Кендалл [47]. Заметим, что существует другая классификация СМО, с которой подобно можно ознакомится в работе А.А. Боровкова [4]. там обслуживания заявок, исследование с помощью виртуального времени ожидания, введение дополнительной переменной, исследование с использованием процессов восстановления. Метод построения вложенной цепи, впервые предложенный А.Я. Хинчиным [25], позволил вычислить для СМО M/G/1/oo лишь некоторые характеристики, связанные с числом заявок в системе только в специальные моменты времени. Применение метода исследования с помощью виртуального времени ожидания приводит к интегро-дифференциальному уравнению Такача [54], которое разрешается с помощью преобразований Лапласа-Стилтьеса (ПЛС). Недостаток этого метода заключается в невозможности использования его для вычисления характеристик очереди. При использовании метода введении дополнительной переменной, как правило, в качестве дополнительной переменной рассматривается прошедшее или остаточное время обслуживания. С полным обоснованием этого метода можно ознакомится в работе Ю.К. Беляева [31]. Метод исследования с помощью процессов восстановления позволяет найти совместное нестационарное распределение практически любых характеристик обслуживания. Методы, разработанные для расчета модели однолинейной СМО M/G/1/r, позволили получить стационарные характеристики для однолинейных моделей СМО, обобщающих входящий поток и процесс обслуживания. В частности, в последнее время для описания СМО было предложено использовать марковский входящий поток. Тем не менее, несмотря на то, что созданы определенные методы расчета с марковским входящим потоком [6, 11, 15, 17, 18, 40, 41, 48, 50], в этом направлении остается немало нерешенных проблем, связанных с вычислительными сложностями.
К настоящему времени не создано методов исследования многолинейной СМО M/G/n/oo, которые позволяли бы находить для нее стационарные показатели в сколько-нибудь пригодном для анализа виде (Тем более это касается СМО G/G/n/oo. Даже для однолинейной СМО G/G/1/oo полученные на сегодняшний день результаты ориентированы на решение лишь качественных задач ТМО. При этом подавляющее число работ посвящено рассмотрению характеристик, связанных с временем пребывания заявок в системе, и так или иначе опирается на уравнение Линдли [49]. Еще более глубокие качествен- ные результаты относительно СМО GI/GI/1/oo с зависимыми временами между поступлениями заявок и временами обслуживания можно найти в монографиях А.А. Боровкова [4, 5]). Исключением такого положения вещей являются системы с немногими частными случаями рекуррентного потока (например, СМО M/D/n/oo, для которой получены соотношения для расчета стационарного распределения числа заявок в системе). Еще хуже обстоит дело с многолинейными СМО M/G/n/r с конечным накопителем. Они остаются практически неизученными (исключением является телефонная система M/G/n/О с потерями, для которой Б.А. Севастьяновым [32] получены стационарные вероятности состояний, которые фактически совпадают с формулами Эрланга).
Шагом вперед стало появление в начале 80-х годов прошлого века алгоритмических методов (см. работы [10, 38]), предложенных впервые М.Ф. Ньютсом [51] и позволивших на основе современных высокопроизводительных вычислительных устройств производить расчеты стационарного распределения очереди для модели СМО с марковским входящим потоком и фазовым распределением времени обслуживания, гораздо более адекватно описывающих функционирование ин-фотелекоммуникационных систем. Однако, предложенные там математические методы расчета, основанные на матричной модификации метода прогонки для решения систем уравнений равновесия, оказались неустойчивыми к погрешностям вычислений, что не позволило вычислить пользовательские показатели СМО с большим числом фаз входящего потока и обслуживания и большими емкостями накопителей. В настоящее время на основе этого подхода разработаны методы для расчета многолинейных СМО вида РН/РН/n/r и МАР/РН/п/г с накопителем конечной и бесконечной емкости (см., например, работу [37]).
Пуассоновский входящий поток заявок, в отличие от экспоненциального времени обслуживания, долгое время вполне удовлетворял исследователей. Однако, по мере развития инфотелекоммуникационных технологий появились системы, для которых использование моделей с пуассоновским, и даже с обобщающим его марковским входящим потоком является неприемлемым. Это привело к изучению модели СМО G/M/n/r с рекуррентным входящим потоком вида и экспоненциальным обслуживанием. Для модели СМО G/M/n/r удалось получить как стационарные вероятности состояний, которые представимы в геометрическом виде, так и стационарное распределение времени ожидания начала обслуживания и времени пребывания заявки в системе. Наконец, совсем недавно появились работы, позволяющие рассчитывать стационарные характеристики однолинейной СМО вида G/MSP/1/r с марковским процессом обслуживания и накопителем конечной и бесконечной очереди [7, 9]. В [7] для системы G/MSP/1/r в случае конечного числа мест ожидания, т. е. г < оо, было получено стационарное распределение длины очереди. Однако предложенная там вычислительная процедура хорошо работала только для относительно небольших значений г. В [9] предложен другой способ исследования системы G/MSP/1/r, основанный на методе последовательного исключения состояний вложенной цепи Маркова. Метод исследования СМО с помощью построения вложенной цепи Маркова дал возможность получить стационарные распределения времени ожидания начала обслуживания и времени пребывания произвольной, принятой к обслуживанию заявки. В работах Албореса с соавтором [31, 32] была рассмотрена многолинейная система с рекуррентным потоком, марковским обслуживанием и накопителем конечной емкости. Но полученные там алгоритмы расчета стационарных вероятностей применимы лишь к системам с малым числом приборов, фаз обслуживания и мест ожидания.
Среди новейших инфотелекоммуникационных систем встречаются системы, требующие применение моделей СМО с полумарковским потоком, обобщающим рекуррентный и марковский потоки (полумарковский поток в большинстве случаев, когда использование рекуррентного или марковского процесса является неадекватным, весьма точно позволяет отразить свойства описываемой реальной системы). Однолинейная система с полумарковским входящим потоком, двумя типами заявок, марковским обслуживанием была рассмотрена в работе А.В. Печинкина и СИ. Тришечкина [19]. До настоящего времени не было работ, посвященных моделям многолинейных СМО с полумарковским входящим потоком и марковским обслуживанием.
В диссертации также рассмотрена модель СМО с отрицательными заявками. Модели СМО с отрицательными заявками тесно связаны с G-сетями [8, 1] и являются предметом интенсивных исследований. Первая работа, в которой была исследована однолинейная СМО с неограниченным накопителем с отрицательными заявками, принадлежит Е. Геленбе с соавторами [43]. В дальнейшем системы с отрицательными заявками рассматривались в работах П.Харрисона [44], П.Харрисона с соавторами [45, 46, 39], Н.Байера и О.Боксмы [36], И.Атенсиа с соавторами [33, 34, 35], Д.Албореса, П.П.Бочарова и Д. Ю.Любина [29, 30]. Хотя понятие отрицательной заявки было введено Е. Геленбе сравнительно недавно, однако в ТМО уже давно известны СМО с ограниченным временем пребывания или, что то же самое, СМО с нетерпеливыми заявками (см., например, Б.В. Гнеденко [13]), которые по своей сущности практически ничем не отличаются от отрицательных заявок.
Таким образом, модели СМО с немарковским входящим потоками и марковским обслуживанием востребованы для описания современных технических систем. Поэтому разработка методов расчета стационарных характеристик таких моделей, в том числе распределений времени ожидания и времени пребывания заявки в системе, является актуальной задачей.
Кратко остановимся на содержании диссертации.
Система SM/MSP/n/r с конечным накопителем
В этом разделе будем предполагать, что г 2. В случае г — 0,1 часть из полученных здесь формул требуют определенных изменений, которые в виду их тривиальности не приводятся.
Рассмотрим последовательные моменты тп, п О, поступления заявок в систему. Пусть г] (t) и (t) — фазы генерации и обслуживания заявок в момент времени t, a v(t) — число заявок в системе в этот момент.
Определим случайные величины г\п = г)(тп + 0), n = (тп + 0) и vn — (rn + 0), которые задают соответственно фазы генерации и обслуживания и число заявок в системе непосредственно после момента поступления п-й заявки. Кроме того, положим п — (г]п,п, vn). Тогда последовательность {п, п 0} образует однородную цепь Маркова, которую будем называть вложенной. Очевидно, что множество состояний X вложенной цепи Маркова имеет вид X = {(i,j, к), г = TTm, j = 1, lk, к = 1,п + г}, где индексы г, j и к указывают соответственно фазы генерации и обслуживания и число заявок в системе непосредственно после момента поступления заявки.
Выпишем матрицу переходных вероятностей вложенной цепи Маркова {п, п 0}. Для этого сначала определим следующие матрицы: jFfc(z), к 0, — матрица, элемент (Fk(х)) -, i, j = 1,/, которой представляет собой условную вероятность того, что за время х обслужится к заявок и процесс обслуживания перейдет на фазу j при условии, что в начальный момент в системе (вместе с заявками на приборах) было не менее к + п заявок, процесс обслуживания находился на фазе г и за время х в систему не поступила новая заявка;
А , к 0, — матрица, элемент {Ak)ij, i,j = l,ml, которой представляет собой условную вероятность того, что за время между поступлениями заявок обслужится к заявок и процессы генерации и обслуживания после поступления новой заявки окажутся на фазах s и t при условии, что в начальный момент в системе было не менее к + п заявок и процессы генерации и обслуживания находились на фазах и и v. Здесь и далее для матриц размера ml\ х га , описывающих совместное изменение фаз генерации и и s и обслуживания v nt, мы используем обозначения і = 1\{и — l) + v, j = l2(s — l)+t,rfl &u,s = l,m, v = l,/i, = 1,/2, что позволяет применять кронекерово произведение матриц.
Матричные функции Fk(x) удовлетворяют рекуррентным соотношениям ад = ек\ (1.1) X Fk{x) = j Fk-_l{y)NF0{x-y)dy, к 1, (1.2)
Чтобы получить соотношения для матриц Ак, воспользуемся кронекеровым произведением двух матриц.
Определение. Пусть А и В — прямоугольные матрицы размеров тх п и р х q соответственно. Кронекеровым произведением А 8 В матриц А и В называется следующая матрица размера тр х nq блочного вида: АВ = (aijB)i=T f j /аиВ апВ . аыВ\ а2\В «22 В . &2пВ \o-m\B 0-гп2В . GmnU/ Подробнее со свойствами этой матричной операции можно ознакомится, например, в работах [2, 12, 10]. Матрицы Ak определяются формулой Ак = / dA{x) Ffc(x), 0. (1.3)
В дальнейшем понадобятся также следующие матрицы: Fkw{x), w = 0, п — 1, к w, — матрица, элемент (і ьДж))у, і — 1, Ik, j = 1, /ш, которой представляет собой условную вероятность того, что за время х обслужится к — w заявок и процесс обслуживания перейдет на фазу j при условии, что в начальный момент в системе (вместе с заявками на приборах) было к заявок, процесс обслуживания находился на фазе г и за время х в систему не поступила новая заявка;
Akw, w = 0, п — 1, к w, — матрица, элемент (Akw)ij, = h{u—l)-\-v, 3 = lw+i(s—l)+t, и, s = 1, m, v = 1, Ik, t = 1, lw+i, которой представляет собой условную вероятность того, что за время между поступлениями заявок обслужится к — w заявок и процессы генерации и обслуживания после поступления новой заявки перейдут на фазы s и t при условии, что в начальный момент в системе было к заявок и процессы генерации и обслуживания находились на фазах и и v. Матрицы Fkw(x) можно найти из соотношений F00(x) = / (1.4) (здесь и далее / — единичная матрица, порядок которой определяется из контекста или нижним индексом),
Система G/MSP/n/r с конечным накопителем
Построим вложенную цепь Маркова, как и для общего случая, по моментам тп, п О, поступления заявок в систему. Последовательность {Cn = {ini nji п 0}) образует однородную цепь Маркова, где, как и ранее, „ и ип — соответственно фаза обслуживания и число заявок в системе непосредственно после момента поступления п-й заявки. Множество состояний X вложенной цепи Маркова имеет вид X = {(i,k), i = l,lk, к = l,n + r}, где индексы г и к указывают соответственно фазу обслуживания и число заявок в системе непосредственно после момента поступления заявки. Введем по аналогии с общим случаем матрицы Fk(x), Ffcm(a;), Ак и
Акт Матрицы Fk(x), к 0 и матрицы Fkm(x), т = 0, п — 1, к т, имеют тот же смысл, что и в общем случае, и определяются формулами (1.1), (1.2), (1.4)-(1.6);
Ak, к О, — матрица, элемент (Ak)ij которой представляет собой условную вероятность того, что за время между поступлениями заявок обслужится к заявок и процесс обслуживания перейдет на фазу j, при условии, что в начальный момент в системе было не менее к + п заявок и процесс обслуживания находился на фазе і. Матричные функции Ak удовлетворяют соотношениям оо Ак= f Fk(x)dA{x), к 0. (1.42) о
Акт, m = 0,п— 1, к т, — матрица, элемент {Akm)ij которой представляет собой условную вероятность того, что за время между поступлениями заявок обслужится к — т заявок и процесс обслуживания после поступления новой заявки перейдет на фазу j, при условии, что в начальный момент в системе было к заявок и процесс обслуживания находился на фазе і.
Матрица переходных вероятностей вложенной цепи Маркова {п, п 0} в указанных обозначениях будет иметь вид (1.8).
Матрицы Акт — из соотношения Акт = / Fkm(x) dA(x) fim, т = 0,п-1, к т. (1.43) о Обозначим через р к, і = 1, , к = 1,п + г, стационарную по вложенной цепи Маркова вероятность того, что в системе имеется к заявок и фаза обслуживания равна і, и положим р к = {р\кт - - Рікк)- р = (Pi,..., Рп+г)- Тогда для р справедлива система уравнений равновесия (СУР) (1.9), координатная форма которой в новых обозначениях имеет вид (1.10) с условием нормировки (1.11).
Зная стационарное распределение вложенной цепи Маркова, нетрудно определить другие стационарные характеристики обслуживания в рассматриваемой системе.
Векторы р = (РГА; - Pjfc) 0,n + r, где рТк — стационарная вероятность того, что поступающая в систему заявка застанет в ней к
других заявок и марковский процесс обслуживания после ее поступления окажется на фазе І, определяются соотношениями (1.12), (1.13).
Стационарная вероятность 7Г потери заявки определяется формулой
7Г = Рп+А =РІ+іЛ)і Для нахождения стационарных вероятностей состояний по времени введем матрицы Тк, к = 0, г, и Ткт, к = 1, п + г, т = 0, min{&, п — 1}. Элемент (Tk)ij, h 3 = 1 I, матрицы Тк представляет собой среднее время, проведенное рассматриваемой системой на интервале между соседними моментами поступления заявок в состоянии {j,n-\-r — к), при условии, что после поступления первой заявки в системе оказалось п 4- г заявок и фаза обслуживания была і. Элемент (Tkm)ij, і = 1,1к, j = l,lm, матрицы Тктп представляет собой среднее время, проведенное рассматриваемой системой на интервале между соседними моментами поступления заявок в состоянии (j,m), при условии, что после поступления первой заявки в системе оказалось к заявок и фаза обслуживания была г.
Соотношения (1.14)-(1.15) для матриц Тк и Ткт принимают вид: Тк = J(l-A{x))Fk(x)dx, к = 0,г; (1.44) Tkm = ({I - A{x))Fkm{x) dx, (1.45) fc = l,n + r, т = 0,min{fc,n — 1}.
Векторы рк, к — 0,n-f г, стационарных вероятностей состояний по времени, найдем из формул где Т — среднее время между изменениями состояний вложенной цепи Маркова, которое для рассматриваемой системы совпадает со средним временем а между поступлениями заявок, т.е. Т = а.
Аналогично общему случаю нетрудно получить формулы для среднего времени w ожидания начала обслуживания для ФР W(x) времени ожидания начала обслуживания
Обратимся теперь к системе с бесконечным накопителем (г = со). Рассмотрим, как и в случае конечного накопителя, вложенную цепь Маркова, множество состояний которой X = {(i,k), i = l,lfc, 1} является будет счетным.
Вводя, как и прежде, векторы pj, к 1, и р = (рї,Рг» ) стационарных вероятностей состояний вложенной цепи Маркова, получаем для р СУР (1.9), в которой матрица Р переходных вероятностей имеет вид (1.20), причем матрицы Ak, к 0 и матрицы Akm, m = 0, п — 1, к т. определяются соответственно соотношениями (1.42) и (1.43).
Как и ранее при к п стационарные вероятности р к имеют вид (1.24), где G — решение уравнения (1.25). Напомним, что в случае бесконечного накопителя мы предполагаем, что р 1. Поэтому справедлива лемма 1.
Оставшиеся неизвестными векторы р, к = 1, та, найдем из уравнений (1.26), (1.27). Как говорилось ранее, система уравнений (1.26), (1.27) с условием нормировки (1.39) имеет единственное решение.
Бесконечный накопитель
Процесс поступления отрицательных заявок определяется следующим образом. Пусть в случайные моменты времени в систему поступают отрицательные заявки, которые убивают заявки в накопителе. Убитые заявки на обслуживание не принимаются и покидают систему. Предполагается, что процесс поступления отрицательных заявок является марковским процессом с непрерывным временем и конечным числом q состояний, который описывается следующим образом. За «малое» время А с вероятностью 7гА + о(А), г, j = 1, q, фаза процесса изменится на j, и ни одной заявки в накопителе убито не будет при условии, что в начальный момент процесс находился на фазе г, и с вероятностью 7ijA + о(А), i,j = l,q, фаза процесса изменится на j, и ровно т заявок в накопителе будут убиты и покинут систему при условии, что в начальный момент процесс находился на фазе г и в накопителе находилось более т заявок. Матрицы из элементов 7г, hj = l,q, т = 0,1,2,..., обозначены через Гто. Если в некоторый момент времени в накопителе находилось т, т 0, заявок, то за «малое» время А с вероятностью jfj A + о(А), i,j = l,q, фаза процесса изменится на j и все т заявок будут убиты и покинут систему при условии, что в начальный момент процесс находился на фазе г. Матрицы из элементов 7ij hj = l,g, m = 0,1,2,..., обозначены через Г , причем r; = rfc, m = o,i,2,..., г = г;. к=т
Предположим, что матрица Г является неразложимой, а матрица Г ненулевой. Будем считать также, что на периоде, когда в накопителе отсутствуют заявки, фаза процесса не меняется. Вектор стационарных вероятностей марковского процесса поступления отрицательных заявок (т.е. марковского процесса с инфинитиземальной матрицей Г ) будем обозначать через 7- Стационарную интенсивность убийства заявок мож 00 но записать в виде a = (j)T Yl kTkl. к=і Если в накопителе находятся к, к = 1,г, заявок, то будем говорить, что заявка находится на г-м месте, г = 1, к, в накопителе, если в накопителе присутствует ровно г — 1 заявка, которые попали в накопитель ранее рассматриваемой заявки. Если в некоторый момент в накопителе находится к, к = 1, г, заявок и в этот момент в систему поступает отрицательная заявка, которая может убить ровно т, т = 1, к заявок, то будут убиты первые т заявок из накопителя.
Будем считать, что во время отсутствия заявок в накопителе, фаза процесса поступления отрицательных заявок не меняется.
Марковский процесс обслуживания заявок определяется следующим образом. В том случае, когда в системе находится к, O fc n + r, заявок, процесс обслуживания может находиться в одном из Ik, h со, состояний (фаз обслуживания). Тогда, если в некоторый момент в системе находится к, к = 1,п + г, заявок и фаза обслуживания равна г, г = 1, Ik, то за «малое» время Д с вероятностью Л - А + о(Д) фаза изменится на j, j = 1, Ik, и все заявки будут продолжать обслуживаться, а с вероятностью n-jA + о(А) фаза изменится на j, j = 1, lk-і, но обслуживание одной из заявок закончится, и она покинет систему. Матрицы из элементов Лг- и щ, будем обозначать через А и N k\ к = 1, п + г.
Далее всюду будем предполагать, что h = I при к = п,п + г, матрицы Л( 0 — Л совпадают при к = п,п-\-г, матрицы N = N совпадают при к = п + 1,п + г. Будем считать, что на свободном периоде фаза обслуживания г, г = 1,/(Ь не изменяется.
Наконец, при к = 0, п — 1 будем предполагать, что если в момент поступления очередной заявки в системе имеется к других заявок и фаза обслуживания равна г, г = 1, , то после поступления новой заявки она с вероятностью ш\- изменится Haj, j = 1,/fc+i- Соответственно, матрицу из элементов UJIJ будем обозначать через П .
Заявки обслуживаются в порядке поступления (дисциплина FCFS). Заявка, поступающая в систему, в которой уже находится п + r заявок (п на приборах и г в накопителе), теряется.
Назовем общим процессом ухода заявок из системы процесс, образованный изменениями в системе как в моменты изменения состояний марковского процесса обслуживания заявок, так и в моменты поступле ния отрицательных заявок в систему.
В том случае, когда в системе находится к, О к п + г, заявок, процесс ухода заявок может находиться в одном из hk = q h состояний. Из описания процесса обслуживания заявок следует, что hk = h при к = п,п + г.
Определим следующие матрицы где i/A и Iq — единичные матрицы порядков Ik и g соответственно.
Пусть в некоторый момент в системе находится к заявок, фаза процесса поступления отрицательных заявок в систему равна г, г = 1, q, а фаза обслуживания равна j, j = 1, Ik- Тогда за «малое» время Д: 1) если к = 0,п, то с вероятностью (о ) Д+(А) u = i(lk — 1)+І, v = e(/fc — 1) + d, e = l,g, с? = 1,/fc, фаза процесса поступления отрицательных заявок сменится на е, фаза процесса обслуживания заявок сменится d и ни одна заявка не покинет систему2 и с вероятностью (і ) А + о(А), процесс ухода заявок из системы перешел на фазу v, v = 1, hk-ъ и одна заявка покинет систему, при условии, что в начальный момент в системе были заявки и процесс ухода заявок из системы находился на фазе u, и = 1, hk, к = 1, п;
Конечный накопитель
В настоящем разделе предложенны алгоритмы расчета характеристик по математическим соотношениям для СМО SM/MSP/n/r с конечным и бесконечным накопителем, которые получены в пунктах 1.2. и 1.3.. Для СМО SM/PH/n/r получены алгоритм построения матриц, описывающих марковский процесс обслуживания модели СМО SM/MSP/n/r, и расчетные формулы для ФР V(х) времени пребывания заявки в системе.
Обозначим через с модуль минимального диагонального элемента всех матриц Ак и Л. Положим QQ = /, Qk = I -\- Ак/с, к = 1,п — 1, и Q = I + Л/с.
Рассмотрим теперь систему SM/PH/n/r и покажем, каким образом можно выбрать параметры общей СМО SM/MSP/n/r, чтобы получить систему SM/PH/n/r.
Обслуживание каждым прибором имеет фазовый тип с параметрами: М — квадратной матрицей порядка s с элементами {іц\ Ь — вектором размерности s с координатами Ъ{. Положим также s fJ i = — / fJ jj-3=1
Состояние марковского процесса обслуживания при к заявках характеризуется мультииндексом і = (ii,..., is)} где ij — число заявок на приборах, обслуживаемых на фазе j. Очевидно, что г = i\ + ... 4- is = к.
Для любого вектора і с координатой ij 1 положим: ij — вектор, все координаты которого, кроме j-й, совпадают с координатами вектора і, а j-я координата равна ij — 1; ij — вектор, все координаты которого, кроме j-й и w-й, совпадают с координатами вектора г, а j-я и w-я координаты равны ij — 1 и iw + 1 соответственно.
Кроме того, для любого вектора і обозначим через iw — вектор, все координаты которого, кроме w-й, совпадают с координатами вектора г, а w-я координата равна iw + 1. Теперь матрицы Ак, Л, Nk, N и Qk общей СМО SM/MSP/n/r определим следующим образом:
Остальные элементы матриц Ak, A, Nk, N и Q,k равны нулю.
Для численных расчетов необходимо произвести линейную нумерацию состояний. Это можно сделать следующим образом.
Состоянием с номером 1 при к обслуживаемых на приборах заявках является состояние, при котором все заявки на приборе обслуживаются на первой фазе.
Следующие CgZf состояний представляют собой все состояния, при которых к — 1 заявок обслуживаются на первой фазе, а еще одна заявка — на какой-то из остальных s — 1 фаз.
Еще Cg 2 состояний представляют собой все состояния, при которых к — 2 заявок обслуживаются на первой фазе, а еще две заявки — на каких-то из остальных s — 1 фаз и т.д.
Нумерация заявок на остальных s — 1 фазах производится по аналогичному принципу.
Таким образом, при числе заявок на приборах к состоянию, характеризуемому мультииндексом і = («і,... ,is), соответствует состояние с линейным номером
Для модели СМО G/MSP/n/r предложены расчетные формулы для вспомогательной матричной функции R(x), математические соотношения которой получены в пункте 1.5.. Численные методы расчета матрицы Fk(x) и Fk(x) приводятся в [10].
Положим Q = Id— (Im Л)/а, где а — модуль минимального диагонального элемента матрицы Л.
