Автоматика и телемеханика, № 5, 2009
PACS 02.50.-r
© 2009 г. Т.А. МИЛОВАНОВА (Российский университет дружбы народов, Москва)
СИСТЕМА ВМАР/С/1/го С ИНВЕРСИОННЫМ ПОРЯДКОМ ОБСЛУЖИВАНИЯ И ВЕРОЯТНОСТНЫМ ПРИОРИТЕТОМ1
Рассматривается однолинейная система массового обслуживания ВМАР/О/1/то с групповым марковским входящим потоком, произвольным обслуживанием, накопителем конечной емкости и инверсионной дисциплиной обслуживания с вероятностным приоритетом. Получены уравнения для нахождения стационарных вероятностей состояний и стационарных характеристик, связанных с временем пребыванием заявки в системе.
1. Введение
Одной из интереснейших задач современной теории массового обслуживания является исследование систем массового обслуживания (СМО) с дисциплинами, отличными от стандартной дисциплины обслуживания заявок в порядке поступления в систему. Особенностью таких дисциплин является возможность улучшения качества функционирования СМО практически без всяких технических усовершенствований.
В [1] была рассмотрена СМО M/G/1/ж с дисциплиной обслуживания (названной автором инвариантной), при которой известны остаточные времена обслуживания (длины) всех находящихся в системе заявок, при поступлении новой заявки ее длина сравнивается с длиной заявки на приборе и та из них, длина которой минимальна, становится на прибор, оставляя за второй первое место в очереди. Оказалось, что стационарное распределение числа заявок в этой системе зависит только от загрузки системы (является инвариантным относительно распределения времени обслуживания при данной загрузке) и имеет точно такой же вид, как и в системе M/D/1/те с детерминированным временем обслуживания и той же загрузкой. Отметим, что инвариантность стационарного распределения числа заявок при такой дисциплине в корне отличается от аналогичной инвариантности при других дисциплинах, наиболее известными из которых являются равномерное разделение процессора, инверсионный порядок обслуживания с прерыванием обслуживания, обслуживание на бесконечнолинейной системе. При этом инвариантная дисциплина при времени обслуживания заявки, отличном от постоянного, дает меньшие среднюю очередь и среднее время пребывания заявки в системе, чем другие упомянутые выше дисциплины. Кроме того, с ее помощью была доказана гипотеза А.Д. Соловьева о том, что постоянная длина обслуживания является наихудшей для СМО M/G/1/те с дисциплиной обслуживания заявки минимальной обслуженной длины (shortest remaining processing time-SRPT), введенной в [2] и дающей наилучшие показатели функционирования среди всех консервативных дисциплин (см. [3-7]).
1 Работа выполнена при поддержке Российского фонда фундаментальных исследований (проект № 06-07-89056).
В [8, 9] было введено обобщение инвариантной дисциплины [1], названное инверсионным порядком обслуживания с вероятностным приоритетом (last come first served probabilistic priority - LCFS PP). При дисциплине LCFS PP, как и при инвариантной дисциплине, после сравнения длин заявок на приборе и вновь поступившей эти две заявки занимают место на приборе и первое место в очереди. Однако в отличие от инвариантной дисциплины на прибор может попасть любая из этих заявок (не обязательно кратчайшая) с определенной вероятностью, зависящей только от длин сравниваемых заявок. В [8, 9] были найдены также стационарные распределения основных характеристик обслуживания в системах M/G/1/r и M/G/1/те с дисциплиной LCFS PP.
В дальнейшем появилось много работ, посвященных СМО с дисциплиной LCFS PP и различными ее обобщениями. В частности, системы с различными типами пуассоновского потока и дисциплиной LCFS PP рассмотрены в [10-16] и др. (см. также [17, гл. 7, § 2]). С другой стороны, в современной теории массового обслуживания важную роль играют СМО с марковским входящим потоком. Системы MAP/G/1/г и MAP/G/1/те с дисциплиной LCFS PP и марковским входящим потоком были исследованы в [18, 19] (поскольку марковский поток является обобщением потока фазового типа и не является рекуррентным, то это обстоятельство делают модель СМО с марковским потоком привлекательной для исследования своей общностью). Наконец, упомянем еще работы [20, 21], в которых была изучена система BMAP/G/1/r/LCFS PP (обозначение BMAP (batch Markov arrival process) на первой позиции соответствует групповому марковскому входящему потоку заявок) с накопителем конечной емкости.
В настоящей статье рассматривается СМО BMAP/G/1/œ/LCFS PP с накопителем бесконечной емкости. Получены соотношения, позволяющие вычислять стационарные вероятности состояний и стационарные характеристики, связанные с временем пребыванием заявки в системе.
2. Описание системы
Рассмотрим однолинейную СМО, в которую поступает групповой марковский поток заявок (ВМАР). Групповой марковский поток задается матрицами Л и N порядка I. Каждый элемент матрицы Л = (Л)^ при г = ] является интенсивностью перехода процесса генерации с фазы г на фазу ], не сопровождаемого появлением новой группы заявок. Элемент матрицы Ак = (А, к > 1, является интенсивностью перехода с фазы генерации г на фазу ], при котором появляется новая группа
_ ^ _
заявок размера к. Положим N = ^ Ак+г. Каждый элемент матрицы N являет-
¿=0
ся интенсивностью перехода процесса генерации заявок с фазы г на фазу ], при котором в систему поступает группа, содержащая по крайней мере к заявок.
Введем матрицу Л* = Л + А1, которая является инфинитезимальной матрицей процесса генерации заявок. Будем предполагать, что матрица Л* неразложима. Через 7? обозначим вектор стационарных вероятностей фаз генерации заявок, т.е. стационарных вероятностей состояний марковского процесса с инфинитезимальной матрицей Л*. Тогда П можно найти из системы уравнений равновесия
0 = ПЛ*
с условием нормировки
7Г1 = 1.
Времена обслуживания заявок (длины заявок) независимы в совокупности и име-
оо
ют функцию распределения В (ж) с конечным средним Ь = § ж^В(ж) < ж, причем
о
для простоты изложения будем считать, что В (ж) имеет плотность Ь(ж) = В '(ж).
Будем предполагать, что в момент прихода заявки в систему становится известной ее длина ж, которая сравнивается с остаточной длиной у заявки, находящейся на приборе. Для определенности будем считать, что заявки в группе занимают места случайным образом и любая заявка может оказаться на любом месте в группе размера к с вероятностью 1/к.
Инверсионный порядок обслуживания с вероятностным приоритетом (ЪСРЯ РР) определяется следующим образом.
1. Если в момент поступления группы из к заявок система свободна, то первая заявка из этой группы сразу же начинает обслуживаться, остальные заявки занимают первые к — 1 мест в очереди.
2. Если в системе имеется п заявок и поступает группа, содержащая к заявок, то первая заявка длины ж из группы, заставшая на приборе заявку длины у, с вероятностью ^(ж,у), зависящей только от длин ж и у и не зависящей от предыстории функционирования системы, прерывает обслуживание и сама становится на прибор, остальные к — 1 заявки из этой группы занимают первые к — 1 мест в очереди, а ранее обслуживаемая заявка занимает к-е место в очереди. Заявки, находящиеся в очереди до поступления группы, становятся после этой заявки с сохранением порядка. Кроме того, с дополнительной вероятностью 1 — ^(ж,у) заявка на приборе продолжает обслуживаться, поступившая группа из к заявок занимает первые к мест в очереди, остальные заявки, находящиеся в очереди, становятся после группы вновь пришедших заявок с сохранением порядка.
Недообслуженные заявки дообслуживаются.
3. Марковский процесс, описывающий функционирование системы
Для исследования системы применим метод введения дополнительных переменных. Рассмотрим случайный процесс п(2) = (С(¿)>Р(^)), 2 > 0, где С(2) - фаза генерации в момент V(2) - число заявок в системе в момент а р(2) = (£1(2),... • • •, £^(4) (2)), где £1 (£),..., £^(4) (¿) - (остаточные) длины заявок, находящихся в системе и расположенных в порядке очереди в момент т.е. £1 (2) - длина обслуживаемой заявки, £2 (2) - длина заявки, находящейся в очереди на первом месте, и т.д. В случае V(2) = 0 вектор р(2) не определяется. Процесс п(2) является марковским. Обозначим через ро и рп(ж1,... , жп), 1 < п < Д, предельные (стационарные) вероятности того, что в системе отсутствуют заявки и находится п заявок длин меньше ж1,...,жп, а через рп(ж1,..., жп) = дпрп (ж1,..., жп)/дж1... джп соответствующие плотности вероятностей. Здесь координаты векторов, как обычно, соответствуют состояниям процесса С(2) генерации заявок.
4. Период занятости
Обозначим через Н(в) матрицу, элементом (Н(в))^ которой является преобразование Лапласа-Стилтьеса (ПЛС) периода занятости (ПЗ) и события, заключающегося в том, что в конце ПЗ фаза генерации будет ] при условии, что в начале ПЗ она была г. Через Н(в | ж) обозначим аналогичную матрицу, но при условии, что ПЗ открывался заявкой длины ж.
Поскольку ПЗ системы с накопителем бесконечной емкости один и тот же при любой консервативной дисциплине обслуживания (см. [17, гл. 7, § 8]), то для вычисления Н(в | ж) и Н(в) можно применить любую дисциплину обслуживания. В частности, воспользовавшись дисциплиной ЪСГЯ с прерыванием обслуживания и дообслуживанием, получаем (см., например, [22, раздел 8.4.1])
,Л+£ N [И(в)]к—з1
Н (в | ж) = е
Введем матрицу Е, элемент Еу которой представляет собой условную вероятность того, что в конце ПЗ фаза генерации будет ] при условии, что в начале этого ПЗ фаза генерации была г. Матрица Е(ж) определяется аналогично матрице Е, но при дополнительном условии, что ПЗ открывался заявкой длины ж. Тогда
Е(ж) = Н(0 | ж) = Л к=1
Г Л+ V N ^к X
Е = Н(0) = Л к=1 } ь(ж) ^ж.
Введем также матрицы Ек (ж) и Ек. Каждый элемент (Ек матрицы Ек представляет собой условную вероятность того, что в конце периода занятости, открываемого заявкой произвольной длины на приборе и еще к заявками произвольных длин в очереди, фаза генерации будет ] при условии, что в начале этого ПЗ фаза генерации была г. Матрица Ек (ж) определяется аналогично матрице Ек , но при дополнительном условии, что ПЗ открывался заявкой длины ж на пр
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.