Исследование дискретных систем массового обслуживания с конечными источниками тема автореферата и диссертации по математике, 01.01.05 ВАК РФ

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени М.В. ЛОМОНОСОВА

Факультет вычислительной математики и кибернетики

На правах рукописи Рослова Наталия Михайловна

УДК 519.21

ИССЛЕДОВАНИЕ ДИСКРЕТНЫХ СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ С КОНЕЧНЫМИ ИСТОЧНИКАМИ

01.01.05 - теория вероятностей и математическая статистика

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Москва - 1992

Работа выполнена на кафедре математической статистики факультета вычислительной математики и кибернетики Московского государственного университета имени М.В.Ломоносова.

I

Научный руководитель - кандидат физико-математических

наук, доцент В.Г.Ушаков.

Официальные оппоненты - доктор физико-математических наук,

профессор В.В.Рыков; кандидат физико-математических наук А.И.Костогрызов.

Ведудая организация - Нижегородский государственный университет имени Н.И.Лобачевского.

Защита диссертации состоится "£Г" 1992 г:

—«м 1 I/

в -// час. СО мин. на заседании Специализированного Совета Д.053.05.38 по математике в Московском государственном университете имени М.В.Ломоносова по адресу:

П9899 ГСП, Москва, В-234, Ленинские горы, МГУ, факультет вычислительной математики и кибернетики, аудитория

С диссертацией можно ознакомиться в библиотеке факультета вычислительной математики и кибернетики МГУ. -

Автореферат разослан "_" _ 1992 г.

Ученый секретарь Совета, профессор

Н.П.Трифонов

>ОССИЙСКЛг: I Отдел I УДЛ?.. |Д8805?Т-г,88{

БИБЛИО^чА- ОЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность,

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

Дискретные системы массового обслуживания позволяют учитывать природу передаваемых данных и дискретный характер протоколов множественного доступа вычислительных сетей.

Исследованию приоритетных систем обслуживания в дискретном времени уделялось довольно много внимания, например, можно назвать работы Раджесвари, Сиди, Ивановского, Соколова.

Системы с конечными источниками изучены значительно меньше. Классическим примером задачи, для которой применяется модель с конечным источником, является задача о простое станков. Она была сформулирована Хинчиным и исследовалась также Пальмой, Такачем, Джейсуолом. Характеристикам, не использовавшимся непосредственно для этой задачи, было уделено мало внимания. Здесь можно назвать работы Тирувенгадама и Джейсуола. Работы Димитрова Б.Н. и Карапенева Х.К. посвящены исследованию систем обслуживания с конечными источниками и одним ненадежным прибором.

В настоящей диссертационной работе исследуются дискретные системы массового обслуживания с несколькими независимыми конечными источниками и различным приоритетом.

Целью работы является получение распределений основных характеристик дискретной системы массового обслуживания с ч- > л конечными источниками и приоритетом: относительным, абсолютным, чередующимся и циклическим.

Научная новизна.

Основные результаты диссертации заключаются в следующем:

1. Для дискретных систем массового обслуживания с t конечными источниками и относительным, абсолютным, чередующимся и циклическим приоритетом получены распределения числа требований в стационарном и нестационарном режимах.

2. Для этих же систем обслуживания изучена такая характеристика, как время ожидания начала обслуживания, и получена производящая функция времени до первого освобождения прибора.

Все полученные результаты являются новыми.

Применения.

Рассмотренные в диссертационной работе системы массового обслуживания служат математическими моделями вычислительных систем и сетей, различных производственных процессов, используются при анализе функционирования сложных систем и разработке АСУ.

Апробация.

Результаты диссертации докладывались на научно-исследовательском семинаре кафедры математической статистики и семинаре " Аналитические методы в теории массового обслуживания " факультета ШиК МГУ.

Публикации.

По теме диссертации опубликовано три работы, перечисленные в конце автореферата / 1-3 /.

Структура и объем диссертации.

Диссертация состоит из введения, девяти параграфов и списка литературы, включающего 62 наименования. Объем диссертации составляет 79 страниц машинописного текста.

СОДЕРЖАНИЕ РАБОТЫ

Во введении дается обоснование актуальности теш диссертации, приводится обзор работ по теме диссертации и основные результаты работы.

К моделям с конечными источниками из-за переменных коэффициентов трудно применить метод производящих функций, который обычно используется для моделей с бесконечными источниками, поэтому вводятся дискретные преобразования, с помощью которых множество вероятностных уравнений преобразуется в множество более простых уравнений.

В § I вводятся основные обозначения и дается описание исследуемой системы массового обслуживания.

Все изменения состояний системы могут происходить лишь в моменты времени , ... такие, что =0, , о.

Требования поступают из источников конечных объемов ^,

Л/д , ..., . Длительность обслуживания требования из д -го источника является дискретной случайной величиной с

функцией распределения общего ввда В^ (.*■)» • Если к

моменту ■Ьь в 1-ом источнике находится требований, то в момент из этого источника в систему поступит требование с вероятностью . После окончания обслуживания требо-

вание возвращается в тот источник, из которого оно поступило. Требования из -го источника имеют более высокий приоритет-

перед требованиями из -го источника при ч.«.^ .

Будем рассматривать многомерный случайный процесс ..., Ь^уС), , где

¿аОФ » • ••> ^чС^ - число требований каждого приоритета в 1

системе в момент времени ;

- номер приоритета обслуживающегося требования; ¿(>) - число тактов времени, прошедших с начала обслуживания этого требования до момента .

Введенные обозначения относятся ко всем параграфам, если не оговорено противное.

В § 2 исследуется дискретная система массового обслуживания с относительным приоритетом. Результат этого исследования ыохно сформулировать следующим образом:

Теорема. Стационарное распределение случайного процесса 0м(>) » •••» ^(п.) , ь(>) , ¿О^У) для дискретной системы с относительным приоритетом определяется соотношениям; •

Положим

Для векторных величин введем следующие обозначения:

*>(*»-! *»*«♦«.....СО;

СЯ.кО-ОЧ.-.ич-оЧУ

и * ^

и ¿.¡г П ;

I з о к* 4

- 2. Л^аи-.^.^оУ

К*1

где \ 4 ь & х , и коэффициенты находятся по формулам:

С* > - й ( £, Л1 ^

е. 4 __.

ЯР(Л\е)- I I -су\' ->

оо ч

2. Са-А^П ¿¡¡? С П СА-К^О]1"'.

»■•а м.«а Л» 4

»и.» О

В § 3 для системы с относительным приоритетом изучаются такие характеристики, как время ожидания и длина очереди. Исследование процесса обслуживания показало, что определение времени ожидания начала обслуживания можно свести к нахождению времени до первого освобождения прибора. Обозначим

^«.(Л*} - время ожидания требования приоритета , поступившего в систему в момент времени ;

" число требований -го приоритета в системе;

Ч*-} - номер приоритета обслуживающегося требования;

- число уже обслужившихся тактов времени;

- время обслуживания требования I -го приоритета; ^уи.4- время до 1-го освобождения прибора, если

в начальный момент времени в системе было , ...,«к., требований приоритета I, ...,1-4 , соответственно.

Теорема. Производящая фикция случайного процесса СЦО") , .... Цч.(и}, , определяется следующими

соотношениями:

0 г-о 1

к.

Y* л]' л^с*»,*)

d 1-jM 4 à

Оч

W-0 \.Ч 0 '

где Y44) - производящая функция времени до первого освобождения прибора » коэффициенты находятся по рекуррентным формулам:

-I -sс*

ке

П еД1 4 | П з

ги f ь

«я,*,. ^ ; .

Чм ^Чс^СЧ«^

^»о ^ 1=0

'Д .

уи--и - число требований V -го приоритета / в сис-

теме в начальный ыоыент времени.

§§ 4,5 посвящены исследованию систеш массового обслуживания с абсолютным приоритетом. Рассматривается две схемы абсолютного приоритета: I/ прерванное требование теряется; 2/ прерванное требование возвращается в источник и при новом поступлении на прибор обслуживается заново с новой реализацией времени обслуживания.

В § 4 получено стационарное распределение многомерного случайного процесса (Ц{.к) , ..., Ь (>") , 4*0 для

системы с абсолютным приоритетом. В § 5 изучается время ожидания начала обслуживания, выводятся рекуррентные формулы для определения производящей функции случайного процесса (. ЦОО, • ••» > ЧЛ} I и» в частности, производящей функци;

времени до первого освобождения прибора.

В §§ 6,7 исследуется дискретная система с ч^-х, конечными источниками и чередующимся приоритетом, то есть при завершении обслуживания требования I-го приоритета на обслуживание выбирается следующее требование этого же приоритета, если такого в очереди нет , то выбирается требование с наибольшим приоритетом. Также как и в предыдущих параграфах, исследуется случайный процесс

Сиди"),..., Ь^СЮ, "^оо, и1^-

В § б получено стационарное распределение этого случайного процесса. Основной результат, полученный в § 7, можно сформулировать следующим образом.

Теорема. Для дискретной системы массового обслуживания с чередующимся приоритетом

I/ производящая функция времени до первого освобождения прибора имеет вид:

КЧ к 1М

2/ производящая функция случайного процесса (.Ц 00« •••»^ч.С'О» 100 » ¡(>У) определяется следующими соотношениями:

1«0 исМ

*,о) - £ £ - $>ОД, «ч,\«г, |, ■

• 5 С», до -П* С У П(О* 4 ,>4 \ з

где функции и имеют вид:

- число требований I -го приоритета в начальный момент

В § 8 изучается система, в которой требования обслуживаются в циклическом порядке, то есть после обслуживания всех требований приоритета и , находящихся в системе на данный момент времени, будут обслуживаться требования приоритета / I +1 /.

стационарном режиме.

В § 9 также исследуется дискретная система циклического обслуживания. Рассматриваются такие характеристики, кал время ожвдания начала обслуживания и число требований каждого приоритета в системе.

■ Введем следующие обозначения: ^кЛ"6) - время ожидания начала обслуживания требования приоритета Уу,, поступившего в систему в момент времени ^ ; ^Ь^Р - время, оставшееся до окончания обслуживания требования приоритета ус ».находящегося в момент 1 на приборе, если оно уже обслужилось ^ тактов;

¡_ - время обслуживания х. -го требования I -го приоритета; и назовем периодом занятости 1-го типа время до первого освобождения прибора от требований приоритета ^ ,

Для этой системы получены распределения числа требований в

если в начальный момент времени в системе было таких требований.

Тогда время ожидания будет равно

где

Доказана теорема аналогичная теореме для системы с чередующимся приоритетом, и получены производящая функция случайного процесса . •••> | , ¿СМ) и производящая

функция периода занятости системы. Производящая функция периода занятости I -го типа является частным случаем / при * ■ А / производящей функции общего периода занятости системы.

Автор выражает глубокую признательность своему научному руководителю В.Г.Ушакову за постановку задачи и полезные советы.

Основные результаты диссертации опубликованы в следующих

работах:

1. Рослова Н.М. Дискретная система массового обслуживания с абсолютным приоритетом. // Ежегодник Талды-Курганского филиала Союза молодых ученых Казахстана, 1991. - Зс.

2. Рослова Н.М. Дискретная система массового обслуживания с относительным приоритетом. // Вестн. Моск. ун-та. Выч. математика и кибернетика. - 1992. - 1Р 2, - С.68-72.

3. Рослова Н.М. О дискретной системе массового обслуживания с конечными источниками. - Деп. ВИНИТИ № 181-В92 от 16.01.92. - Деп. 9с.