автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Открытие многокальные системы дифференцированного обслуживания поликомпонентных потоков

ТПТОВЦЕВ Антон Сергеевич

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

05.13.18 - Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

¡1 2 МАЙ 2011

Казань-2011

4845412

Работа выполнена на кафедре Интеллектуальных систем и управления информационными ресурсами Казанского государственного технологического университета.

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

Кирпичников Александр Петрович

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

Крылов Владимир Владимирович

доктор технических наук, профессор Ахмадиев Файл Габдулбарович

Ведущая организация: Санкт-Петербургский государственный

университет информационных технологий, механики и оптики

Защита состоится «27» мая 2011 г. в 14 час. 00 мин. на заседании диссертационного совета Д 212.080.13 при Казанском государственном технологическом университете по адресу: 420015, г. Казань, ул. К. Маркса, д. 68, зал заседаний Ученого совета (аудитория А-330).

Отзыв на автореферат в двух экземплярах, заверенный гербовой печатью, просим направлять по адресу: 420015, г. Казань, ул. К. Маркса, д. 68, Казанский государственный технологический университет, ученому секретарю диссертационного совета Д 212.080.13.

С диссертацией можно ознакомиться в фундаментальной библиотеке Казанского государственного технологического университета.

Электронный вариант автореферата размещен на официальном сайте Казанского государственного технологического университета (www.kstu.ru).

Автореферат разослан «25> апреля 2011 г.

Ученый секретарь диссертационного совета доктор технических наук,

профессор

А.В. Клинов

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. В настоящее время всё чаще возникают задачи, связанные с обслуживанием потоков требований случайного характера. Подобные задачи возникали всегда, однако в простейших случаях они решались без применения методов математического моделирования. Научный подход к задачам массового обслуживания стал применяться тогда, когда подобные проблемы стали возникать в технических системах, так как в этом случае требовалась высокая точность и экономическая эффективность решения. Возникнув в связи с проблемами телефонии, теория массового обслуживания нашла применение в других областях человеческой деятельности. За время существования теории массового обслуживания проделано немало трудов в различных её направлениях. Примечательно, что большинство исследований в этой области было связано с решением конкретных прикладных задач. По мере роста технического прогресса появляются новые области приложений этой теории, такие как телекоммуникации, транспорт, сфера обслуживания населения и др. Обзор научных статей в данной области за последние годы показывает, что работы ученых этого времени были ориентированы на решение задач в области телекоммуникации. Однако в последнее время в связи с развитием рынка в России появляется все большее количество различного рода товаров и услуг, и возникают проблемы, связанные с организацией пунктов торговли и обслуживания населения, таких как супермаркеты, торговые базы, оптовые рынки. Для решения подобных задач целесообразно использовать методы теории массового обслуживания, основанные на математическом аппарате теории случайных процессов и цепей Маркова.

Несмотря на появление программных средств имитационного моделирования случайных процессов на ЭВМ, аналитическое моделирование систем массового обслуживания остается актуальным, поскольку только аналитическое решение обладает общностью результата и позволяет предсказать характер поведения системы при любых изменениях параметров модели. Сложность аналитических методов не позволяет решать с их помощью любые задачи массового обслуживания, однако, круг задач, решаемых аналитически, весьма широк. Для решения практических задач достаточно рассмотреть системы весьма общей структуры в стационарном режиме функционирования. Особый практический интерес представляют модели массового обслуживания, являющиеся комбинациями ранее изученных моделей, поскольку подобные модели наиболее полно описывают реальные объекты. Однако в литературе комбинированные модели массового обслуживания почти не изучены, а близкие к ним модели обслуживания с различными ограничениями рассмотрены весьма поверхностно. В частности, в трудах Коэна (Cohen, J.W.: Certain Delay Problems for a Full Availability Trunk Group Loaded by Two Sources, Commun. News, vol. 16, pp. 105113, 1956.) приводятся лишь вероятностные характеристики для многоканальной модели обслуживания - комбинации классической модели и модели Эрлан-

/

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

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

Методом исследования является математическое моделирование с применением математического аппарата теории вероятностей, теории случайных процессов, включая аппарат непрерывных цепей Маркова..

Имитационное моделирование систем массового обслуживания данного типа осуществлялось с использованием инструментального средства GPSS World, основанного на методе Монте-Карло.

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

Научная новизна. Впервые изучены открытые многоканальные системы массового обслуживания (СМО) с.входным потоком, содержащим требования разных типов: для одних имеет место ожидание до наступления обслуживания, для других действуют ограничения на длину очереди, третьи получают отказ в обслуживании в случае отсутствия свободного обслуживающего устройства. Потоки такого рода предложено называть поликомпонентными потоками заявок. Введены новые вероятностные характеристики, использование которых значительно упрощает процедуру математического моделирования таких СМО. Разработана программа имитационного моделирования и численный алгоритм организации обслуживания в СМО данного типа.

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

Апробация. Основные результаты диссертационной работы докладывались и обсуждались на:

XVIII Всероссийской научно-технической конференции «Современные проблемы математики и естествознания» (г. Нижний Новгород, 2006);

XX Международной научной конференции «Математические методы в технике и технологиях ММТТ-20» (г. Ярославль, 2007);

VI!! Всероссийском симпозиуме по прикладной и промышленной математике (г. Адлер, 2007);

XIX Всероссийской научно-технической конференции «Современные проблемы математики и естествознания» (г. Нижний Новгород, 2007);

V Международной научно-практической конференции «Исследование, разработка и применение высоких технологий в промышленности» (г. Санкт-Петербург, 2008);

XII Международной научной конференции им. академика М. Кравчука (г. Киев, 2008);

IX Всероссийском симпозиуме по прикладной и промышленной математике (г. Кисловодск, 2008).

Публикации. По теме диссертации опубликовано 10 научных работ, 4 из них - в журналах, рекомендованных ВАК.

Структура и объем диссертационной работы. Диссертация состоит из введения, четырех глав, заключения, библиографического списка и приложения. Работа изложена на 143 страницах, иллюстративный материал представлен в виде 68 рисунков, библиография включает 70 наименований.

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

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

В главе I представлена новая математическая модель СМ О - модель открытых многоканальных систем дифференцированного обслуживания поликомпонентных потоков. Подобные СМО имеют т обслуживающих устройств и входной поток требований, содержащий заявки трёх типов:

• 1-й тип - заявки, которые обслуживаются при любых обстоятельствах, независимо от наличия свободных обслуживающих устройств и количества заявок, ожидающих обслуживания в очереди;

• 2-й тип - заявки, которые обслуживаются при наличии свободного обслуживающего устройства, либо становятся в очередь, если число требований в очереди меньше определённого числа Е. В случае, когда в очереди уже имеется Е или более требований, вновь поступившая заявка второго типа получает отказ и выбывает из системы необслуженной;

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

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

Потоки заявок каждого типа являются простейшими и имеют интенсивности Л1,Л2,Л3 соответственно, суммарный поток с интенсивностью А = Л, +Л2 +Л3 также является простейшим, Л- Лх + Л2 - входной поток требований после т-го состояния иЛ1 - входной поток требований после (т+£)-го состояния (также простейшие). Средняя интенсивность обслуживания заявок одним обслуживающим устройством равна /л, интенсивность выходного потока обслуженных заявок до от-го состояния кратна /л и зависит от числа занятых каналов, а после т-го состояния - равна т/л. Поток обслуженных заявок также простейший. Приведённые интенсивности соответствующих потоков заявок:

Л\ Л-, Я, А Л

Р\=—; ¿>2 = ^-; л = - = р = - = р\+р2- о

¡Л /I /1 /I /I

Состояния СМО соответствуют числу требований, находящихся в системе. Случайный процесс, происходящий в СМО, представляет собой непрерывную марковскую цепь, граф состояний которой приведён на рис. 1.

Рис. 1. Граф состояний и переходов открытой многоканальной системы дифференцированного обслуживания поликомпонентного потока По данному графу составлена система уравнений Колмогорова для вероятностей состояний СМО в стационарном режиме функционирования: 'Р0 А = />//

/}Л + /> = />0Л+/> -2// Р2\ + Рг-2/1 = Р{А + РгЗ/1

Рп-А + ~ О/' = Рт-гА + Рт ' »'/'

_ р„А + Р,п = Рт-А + Р„,А-г»и

Р<„^ + Р„„ 1 • т/1 = Ртк + Р„„2 ■ т/1

Р^Л + Р„,+/;ч ■ т/1 = Р^,:.2А + Р„^,: ■ т/1 Р„ыЛ + Р„»,;'= Р,„■<.■■/- + Р,■ "Ч' Р„„пЛ + „-/..,!''»/' = Р,„,гА + Р„,^2 ■

С учетом условия нормировки £ Р, - 1 система имеет единственное ре-

/=0

шение в виде вероятностей всех возможных состояний СМО в установившемся режиме.

Ро =

Я"

т\

т - р

И*

т

Р\ Р

+ — , р*т

т- рх\т

Е + -

Р,

т ~ Р\

р-т

(3)

где ет (Я) = - неполная экспонента;

Р. =

У?'

Р0, 0 < / < т

рТ'" 1Г_

т) т\

Рп. т <1<т + Е

(4)

(р \ т

,-„,-Е/р у /г

А, />т + Е

ч /7? у /7?!

В разделе 1.1 введены новые базисные вероятностные характеристики: - вероятность неполной загрузки накопителя

.т,

т^Ч-1

Г:

____________т<

т:

- вероятность полной загрузки накопителя

\-Р т

£, /з = т

Е

(5)

,=,„+/; т\ , Р\

1-

«г

■ вероятность немедленного обслуживания

т-1

Рно = ТР,=- = етЛР)Ро-

¡=о

Также сформулированы традиционные вероятностные характеристики: - вероятность ожидания обслуживания заявкой в очереди

Рамс 'ЦР, +~Г £ = ' " - ~ Рщн + Рпзн ' Л А ,=,„ Я К

(6)

(7)

(В)

- вероятность отказа в обслуживании вновь прибывшей заявке

Р,

Л Л /_--,„,/;

тн Р„х

' РнО Ри м- ■

(9)

В разделе 1.2 приводится формализация числовых характеристик СМО:

- относительная пропускная способность

9 = 1-^; (ю)

- абсолютная пропускная способность

А = Кц^--^КРН()+ХРш+Х]Ртн\ (11)

- среднее число требований, находящихся под обслуживанием

III с

= ЯРИ0 + рРшн + р, Рпзн = К{рнп +Р„Л (12)

1-0 /=«/+1

- осреднённый квадрат числа требований, находящихся под обслуживанием

- т т.

>Г = 1.ГР, + 2>2/} = + +тРаЛ (13)

1-0 ¡=тМ

- среднее число заявок, находящихся в очереди (средняя длина очереди! Р

т - р Е +1

{РнЗИ-ЕРтЛ Р*

т

' юн'

р = т

+ P^

Е

{т т-р,;

Р

тн'

(14)

- осреднённый квадрат числа треоований в очереди

Р

т + р \т-р т-р (£ + 0(2£ + 1)

( т, 2/77 ^

£ +- , рфт

1 т-р) ■ +

Е

р = т

2Е +

(15)

т т - рх

т + рх т~Рх

тн >

■ среднее число требований в системе в целом

к =п+1 =■•• = ЯРиа +

-[(1 +т-р)Рти-ЕРт+1:\ р*т

т-р т +-\Р,

> +

+ Р.

Р=т , \

^ т т - Р\ )

тн'

(16)

- осреднённый квадрат числа треоований в системе в целом

¥ = 7- + Г' + 2т 1 = • • • = Я2(Рно - С,) + Я(Рно + тР1Ш.) +

т- р

т + р

2т +-^

т- р

2Е +

( I VI

Е + 2т

т + -

+ А

Р = т

г

> +

„/ „х 111 + р.

2 (т + Е)+-^

т-рх)

^тн-

(17)

т т - р{\

В разделе 1.3 приводится формализация временных характеристик СМО:

- функция распределения времени обслуживания одной заявки

^,(0=1-е-"';

- среднее время обслуживания одной заявки в системе

^ ООС1

(18) (19)

- осредненныи квадрат времени оослуживания заявки

м

- функция распределения времени ожидания заявки в очереди

(20)

' О.жппу / 1 ^

<7

т - р

т ~ Р\

\Р>.

\т- р] т - р)\т - плотность распределения времени ожидания заявки в очереди

' I»-I /

Я

- среднее время ожидания обслуживания заявкой в очереди

_ * [

о л

- осреднённый квадрат времени ожидания заявки в очереди

С,™,) = ¡г2/ш„Лд^ = - =

(21)

(22)

(23)

р(т-р) Е2 -I

т -

-{РНЗН-ЕР„И,)-Е{Е + \)Р„„,

р Ф т

Зтр

Р,ПН> Р = т

+

Ац(т-р,)

{

2/0,

1

ПЗН

+ Е(Е + \)Рт^:

(24)

т т-рх)

- среднее время пребывания заявки в системе в целом (как в очереди, так и под обслуживанием)

к

^сист ^оба ^ожчо

А'

(25)

- осреднённый квадрат времени пребывания заявки в системе

Киан К/жио ^обс.1

АМ

Щю+Рр,т+Р>\- + Чрти

т

+ — А

м{т-р) Е+

т-р

-((1 + т-р)Ртн -ЕРтг,)- Е{2р + £ + \)Р„^:

рфт

Е+\(Е-\

Ар{т-рх)

2 р\

1 +

т т - р]

+ Е{Е + \)РпЫ:

(26)

В главе 2 приводится методика организации дифференцированного обслуживания поликомпонентных потоков.

В разделах 2.1 - 2.2 сформулированы постановка задачи организации обслуживания в подобных СМО и алгоритм её решения.

Суть данной методики заключается в том, чтобы по известным в качестве исходных данных интенсивностям входных потоков заявок всех типов и заданным требованиям к производительности СМО по каждому типу заявок рассчитать необходимое число обслуживающих устройств, а также ограничение по длине очереди для заявок 2-го типа. Для этого абсолютная пропускная способность СМО представлена в виде трёх слагаемых, каждое из которых представляет собой количество обслуженных заявок определенного типа.

А = АРИ0+АРтн

(27)

+ ^\РПЗН - {РН0 + рнзн + рпзн)+

+ Я2(РН0 + Рнзн )+ ^Рно = А + л2 + А}. Поскольку заявки 1-го типа обслуживаются при любых обстоятельствах, то задать требуемую производительность можно только для заявок 2-го и 3-го типов. Из последнего выражения следует

Задание параметров

ц2 и яЗ

_

Получение системы уравнений по мат. модели

-Л-

Решение системы уравнений методом простых итераций и получение значений т и Е

XX

Подстановка т и Е в систему и получение новых с\2 и цЗ

Принятие решения

Рис. 2. Блок-схема алгоритма организации обслуживания в системах дифференцированного обслуживания поликомпонентных потоков.

или в относительных единицах

(29)

Система уравнений (28) используется, если задана абсолютная пропускная способность по каждому типу заявок, система (29) - если требуемая производительность задана в относительных единицах. Так как правые части уравнений являются функциями от т и £, решение системы в той или иной форме относительно данных переменных дает значения числа обслуживающих устройств и ограничения длины очереди, удовлетворяющие заданным требованиям. Методику решения данной задачи можно представить в виде блок-схемы, приведенной на рис. 2.

В раздела* 2.3 - 2.6 сформулированы частные модели С МО данного класса: комбинация моделей М/М/т, М/М/т:Е, М/М/т:0; комбинация моделей М/М/т, М/М/т:Е; комбинация моделей М/М/т, М/М/т:0; комбинация моделей М/М/т:Е, М/М/т:0, а также решение задачи организации обслуживания в СМО, описываемых частными моделями.

В главе 3 исследован характер поведения числовых и временных характеристик полученной модели СМО. Поскольку в реальных СМО обычно всегда присутствуют требования, которые дожидаются обслуживания до конца, в качестве базовой модели принята классическая модель М/М/т. Добавляя последовательно к базовой модели потоки требований 2-го и 3-го типов, исследовано сначала влияние каждой составляющей входного потока требований на характеристики производительности СМО, а затем и поведение характеристик общей комбинированной модели.

В разделе 3.1 исследовано поведение характеристик модели СМО - комбинации моделей М/М/т и М/М/т:0.

Вероятность простоя системы (нулевого состояния) имеет монотонно убывающий характер и при достижении точки с абсциссой р, = т обращается в нуль. По мере роста приведенной интенсивности рг потока требований третьего типа начальное значение вероятности нулевого состояния СМО (при р, = 0) стремительно приближается к нулю. Такой характер поведения вероятности нулевого состояния свидетельствует о том, что неэффективные простои СМО возможны только при малых значениях интенсивностей входных потоков.

Вероятность полной загрузки накопителя (ПЗН) имеет монотонно возрастающий характер и при достижении точки рх = т становится равной I. По мере увеличения приведенной интенсивности р3 начальное значение вероятности увеличивается, уменьшая крутизну кривых. В предельном случае при рг = оо вероятность ПЗН равна 1 и не зависит от р,.

Вероятность немедленного обслуживания (НО) вновь прибывшей заявки имеет прямо противоположный вероятности ПЗН характер поведения, а графи-

км её являются зеркальным отображением кривых вероятности ПЗН. Данное обстоятельство вытекает из условия нормировки. Вновь прибывшая заявка обслуживается немедленно, если свободно хотя бы одно обслуживающее устройство. Положительная сторона возрастания этой характеристики в том, что чем она больше, тем меньше очередь. С другой стороны, высокая вероятность немедленного обслуживания означает, что на момент поступления заявки значительная доля обслуживающих устройств простаивает. Наиболее оптимальной является ненулевая, но и не высокая вероятность немедленного обслуживания.

В данной СМО только заявки 1-го типа ожидают обслуживания в очереди. Вероятность ожидания обслуживания вновь прибывшей заявкой в очереди монотонно возрастает по мере увеличения приведенной интенсивности р, и достигает единицы только при нулевом значении р3. Такое возрастание объясняется тем, что с увеличением интенсивное™ входного потока требований падает число свободных обслуживающих устройств. По мере увеличения приведенной интенсивности р, предельное значение вероятности ожидания при р, = т уменьшается, изменяя наклон кривых. Несмотря на то, что заявки 1-го типа дожидаются обслуживания до конца, при р3 = со вероятность ожидания практически не зависит от р, и равна 0, т. к. в этом случае приведенная интенсивность р, пренебрежительно мала по отношению к р3. Чем больше вероятность ожидания, тем меньше вероятность простоя обслуживающих устройств и больше число заявок, которые будут обслужены. Однако высокая вероятность ожидания благоприятна в том случае, если в системе не происходит переполнения очереди.

Вероятность отказа в обслуживании вновь прибывшей заявке в целом имеет слабо возрастающий характер и увеличивается по мере роста приведенной интенсивности р.. В предельных случаях при р, = 0 и р3 = =свероятность отказа не зависит от интенсивности р, и равна соответственно 0 и 1. Чем меньше вероятность отказа, тем большая доля заявок из общего входного потока будет обслужена.

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

Среднее число требований, находящихся под обслуживанием, носит монотонно возрастающий характер и в точке р, = т достигает максимального значения, равного числу обслуживающих устройств т. По мере увеличения приведенной интенсивности р, начальное значение данного параметра увеличивается с понижением скорости возрастания, и в предельном случае, при бесконечном р3, принимает постоянное значение т независимо от интенсивности потока р,. Среднее число требований под обслуживанием, деленное на число обслуживающих устройств т, дает коэффициент загрузки СМО. Чем больше коэффициент загрузки, тем эффективнее система. Однако повышение коэффициента загрузки СМО не должно быть следствием чрезмерного увеличения ин-

тенсивности входного потока требований, вызывающего переполнение очереди или сплошные отказы в обслуживании.

Средняя длина очереди имеет монотонно возрастающий характер, резкое возрастание наблюдается в окрестности точки р, =т. Такое бесконечное возрастание объясняется переполнением очереди при приближении приведенной интенсивности р, к значению т. Всякое изменение интенсивности потока р} на характер поведения средней длины очереди влияет незначительно, поскольку при наличии очереди в системе заявки 3-го типа получают отказ. Чем больше очередь, тем больше заявок будет обслужено, но при этом не должно происходить переполнения очереди.

В разделе 3.2 исследовано поведение характеристик модели СМО - комбинации моделей М/М/гп и М/М/ш:Е.

Вероятность простоя системы имеет монотонно убывающий характер и при достижении точки с абсциссой р, = т обращается в нуль. По мере роста приведенной интенсивности р2 потока требований второго типа начальное значение вероятности нулевого состояния СМО (при рх - 0) стремительно приближается к нулю. Такой характер поведения вероятности нулевого состояния свидетельствует о том, что неэффективные простои СМО возможны только при малых значениях интенсивностей входных потоков.

При наличии во входном потоке требований одного типа вероятность неполной загрузки накопителя (НЗН) ведет себя неоднозначно. Некоторое запаздывание в возрастании объясняется тем, что при малых значениях р, ещё не заняты все обслуживающие устройства. При дальнейшем возрастании интенсивности входного потока занимаются все устройства, но остаются свободные места в накопителе ёмкостью Е, поэтому вероятность НЗН имеет возрастающий характер. Однако, при больших значениях /?, в окрестности точки рх - т плавно возрастающий характер вероятности НЗН меняется на резко убывающий, поскольку в этом случае накопитель заполняется почти полностью. Добавление во входной поток требований других типов приводит к ненулевому начальному значению вероятности НЗН. По мере увеличения интенсивности общего входного потока экстремум смещается влево, а затем и вовсе исчезает, вероятность НЗН приобретает монотонно убывающий характер. Дальнейшее бесконечное увеличение нагрузки со стороны входного потока приводит к пол-нон загрузке накопителя и нулевому значению вероятности НЗН.

Вероятность полной загрузки накопителя имеет монотонно возрастающий характер и при достижении точки р^-т становится равной 1. По мере увеличения приведенной интенсивности р2 начальное значение вероятности увеличивается, уменьшая крутизну кривых. В предельном случае при рг - (»вероятность ПЗН равна 1 и не зависит от р1.

Вновь прибывшая заявка обслуживается немедленно, если свободно хотя бы одно обслуживающее устройство. Чем больше вероятность НО, тем меньше очередь. С другой стороны, высокая вероятность немедленного обслуживания

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

Вероятность ожидания обслуживания вновь прибывшей заявкой в очереди монотонно возрастает по мере увеличения приведенной интенсивности рх и достигает единицы только при нулевом значении р,. Такое возрастание объясняется тем, что с увеличением интенсивности входного потока требований падает число свободных обслуживающих устройств. Добавление во входной поток требований других типов приводит к ненулевому начальному значению вероятности ожидания. По мере увеличения интенсивности общего входного потока экстремум смещается влево, а затем и вовсе исчезает, вероятность ожидания приобретает слабо убывающий характер. Несмотря на то, что заявки 1-го типа дожидаются обслуживания до конца, при р, = со вероятность ожидания практически не зависит от р, и равна 0, т. к. в этом случае приведенная интенсивность р, пренебрежительно мала по отношению к р2. Чем больше вероятность ожидания, тем меньше вероятность простоя обслуживающих устройств и больше число заявок, которые будут обслужены. Однако высокая вероятность ожидания благоприятна в том случае, если в системе не происходит переполнения очереди.

Вероятность отказа в обслуживании вновь прибывшей заявке в целом имеет возрастающий характер и увеличивается по мере роста приведенной интенсивности р2. В предельных случаях при р2=0 и р2 = <х вероятность отказа не зависит от интенсивности р, и равна соответственно 0 и 1. Чем меньше вероятность отказа, тем большая доля заявок- из общего входного потока будет обслужена.

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

Среднее число требований, находящихся под обслуживанием, носит монотонно возрастающий характер и в точке р, = т достигает максимального значения, равного числу обслуживающих устройств т. По мере увеличения приведенной интенсивности р2 начальное значение данного параметра увеличивается с понижением скорости возрастания, и в предельном случае, при бесконечном р2, принимает постоянное значение т независимо от интенсивности потока р,. Среднее число требований под обслуживанием, деленное на число обслуживающих устройств т, дает коэффициент загрузки СМО. Чем больше коэффициент загрузки, тем эффективнее система. Однако повышение коэффициента загрузки СМО не должно быть следствием чрезмерного увеличения интенсивности входного потока требований, вызывающего переполнение очереди или сплошные отказы в обслуживании.

Средняя длина очереди имеет монотонно возрастающий характер, резкое возрастание наблюдается в окрестности точки р, = т. Такое бесконечное воз-

растание объясняется переполнением очереди при приближении приведенной интенсивности р, к значению т. По мере увеличения интенсивности начальное значение средней длины очереди увеличивается, и в предельном случае, при р2 = со, достигает значения, равного числу мест в накопителе Е. Чем больше очередь, тем больше заявок будет обслужено, но при этом не должно происходить переполнения очереди.

В разделе 3.3 исследовано поведение характеристик модели СМО - комбинации моделей М/М/т, М/М/т:Е, М/М/т:0. Характеристики общей комбинированной модели качественно схожи с характеристиками предыдущей модели СМО - комбинации моделей М/М/т, М/М/пг.Е.

Графики показывают, что введение во входной поток заявок 3-го типа, которые обслуживаются только при наличии свободных обслуживающих устройств, не оказывает существенного влияния на характер поведения характеристик системы. Подобное исследование позволяет лишь качественно оценить производительность системы при изменении интенсивности входного потока требований, но не позволяет оценить необходимое число обслуживающих устройств и мест в накопителе для эффективной работы СМО.

В главе 4 исследован нестационарный режим работы открытых систем дифференцированного обслуживания поликомпонентных потоков.

В разделе 4.1 приводится программа, по которой осуществляется имитационное моделирование СМО в системе GPSS World.

В разделе 4.2 приводятся результаты численных экспериментов, в рамках которых исследован нестационарный режим функционирования данных систем. Полученные зависимости числовых и временных характеристик СМО от времени моделирования описываются одной формулой:

т = е ' (30)

как для общей комбинированной модели, так и для всех частных моделей, приведенных в разделах 2.3 - 2.6, но с разными значениями коэффициентов а, Ь, с в каждом отдельном случае. Выявлено, что квазистационарный режим в СМО подобного типа устанавливается приблизительно за 100 единиц модельного времени, равных среднему времени обслуживания заявки одним обслуживающим устройством.

Результаты имитационного моделирования на ЭВМ приведены в таблице 1. Испытание проводилось при т = 5, р[ = 3, р2 = 3, р3 = 2, а также при нескольких значениях параметра Е.

Таблица 1

Е п п I 7 ! ^ож 7ож

1 4,6586 4,658 1,4742 1,474 j 0,31644 0,349

2 4,7478 4,748 2,0036 2,005 0,422 0,452

5 4,8822 4,883 .3,9318 3,932 1 0,80532 0,830

10 4,9592 4,959 7,8035 7,803 1 1.5735 1 1,590

В таблице I п, I, - значения параметров, вычисленные по математической модели, а п,1,Тож. - результаты выполнения программы имитационного моделирования.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

• Построены математические модели СМО нового типа - открытых многоканальных систем дифференцированного обслуживания поликомпонентных потоков в стационарном режиме функционирования.

• Усовершенствован метод аналитического моделирования СМО, основанный на применении математического аппарата цепей Маркова, путем введения новых вероятностных характеристик, таких как вероятность неполной загрузки накопителя, вероятность полной загрузки накопителя и вероятность немедленного обслуживания. Данные характеристики играют роль базисных параметров, через которые выражаются вероятностные характеристики, а также первые и вторые моменты числовых и временных характеристик стационарного режима функционирования СМО как в общем, так и в вырожденном случае, когда общие формулы при р = m имеют неопределенность.

• Исследован характер поведения вероятностных, а также числовых и временных характеристик стационарного режима в системах дифференцированного обслуживания поликомпонентных потоков с применением полученных аналитических моделей и вычислительного эксперимента.

• Разработана программа имитационного моделирования открытых систем дифференцированного обслуживания поликомпонентных потоков и проведён цикл численных экспериментов, в рамках которых исследован нестационарный режим функционирования данных систем и получена общая формула зависимости числовых и временных характеристик таких СМО от времени в нестационарном режиме. Выявлено, что квазистационарный режим в СМО подобного типа устанавливается приблизительно за 100 единиц модельного времени, равных среднему времени обслуживания заявки одним обслуживающим устройством.

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

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

Публикации в журналах, рекомендованных ВАК:

1. Кирпичников А.П., Титовцев A.C. Открытая одноканальная система массового обслуживания с отказами и неограниченной очередью.// Вестник Казанского технологического университета. - 2006. - №4. - С. 78 - 85.

2. Кирпичников А.П., Титовцев A.C. Системы массового обслуживания с отказами и неограниченной очередью. // Обозрение прикладной и промышленной математики. - 2007. - Т. 14 - Вып. 5. - С. 893 - 896.

3. Кирпичников А.П., Титовцев A.C. Методика оптимальной организации систем массового обслуживания с отказами и очередью. // Обозрение прикладной и промышленной математики. -2008. - Т. 15 - Вып. 6. - С. 1090- 1091.

4. Кирпичников А.П., Титовцев A.C. Системы обслуживания с неоднородным входным потоком требований, отказами и очередью.// Вестник Казанского технологического университета.-20 П.-№5.-С. 154- 161.

Публикации в сборниках трудов всероссийских и международных научных конференций:

5. Кирпичников А.П., Титовцев A.C. Математическая модель открытой одно-канальной системы массового обслуживания с ограниченной очередью. // Материалы Всероссийской научно-технической конференции «Современные проблемы математики и естествознания» - Нижний Новгород, ННИМЦ «Диалог», 2006, С. 10.

6. Кирпичников А.П., Титовцев A.C. Математическая модель открытой одно-канальной системы массового обслуживания с потерями и неограниченной очередью. // Материалы Всероссийской научно-технической конференции «Современные проблемы математики и естествознания» - Нижний Новгород, ННИМЦ «Диалог», 2006, С.10.

7. Кирпичников А.П., Титовцев A.C. Открытая многоканальная система массового обслуживания с потерями и неограниченной очередью. // Сборник трудов XX Международной научной конференции «Математические методы в технике и технологиях ММТТ-20». - Т.6. - Ярославль, ЯГТУ, 2007, С.217 -220.

8. Кирпичников А.П., Титовцев A.C. Математическая модель открытых систем массового обслуживания с отказами и очередью. // Материалы Всероссийской научно-технической конференции «Современные проблемы математики и естествознания» - Нижний Новгород, ННИМЦ «Диалог», 2007, С.12 -16.

9. Титовцев A.C., Кирпичников А.П. Многолинейные системы массового обслуживания с потерями и очередью. // Сборник трудов пятой международной научно-практической конференции «Исследование, разработка и применение высоких технологий в промышленности». - Т. 12. - Санкт-Петербург, изд-во Политехнического университета, 2008, С. 121 - 127.

10. Кирпичников А.П., Титовцев A.C. Многолинейные системы массового обслуживания с отказами и очередью. // XII Международная научная конференция им. академика М. Кравчука - Киев, 2008. - С. 69.

Соискатель

А.С. Титовцев

Тираж 100 экз.

Заказ №

Офсетная лаборатория Казанского государственного технологического университета 420015, Казань, К.Маркса,68

Введение.

Глава

Математическая формализация модели класса систем дифференцированного обслуживания поликомпонентных потоков.

1.1 Вероятностные характеристики СМО.

1.2 Числовые характеристики СМО.

1.3 Временные характеристики СМО.

Глава

Методика организации дифференцированного обслуживания поликомпонентных потоков.

2.1 Постановка задачи.

2.2 Методика организации обслуживания в СМО.

2.3 Модель СМО - комбинация моделей М/М/т, М/М/т:Е, М/М/т:0,.„

2.4 Модель СМО - комбинация моделей М/М/т, М/М/т:Е.

2.5 Модель СМО - комбинация моделей М/М/т и М/М/т:0.

2.6 Модель СМО - комбинация моделей М/М/т:Е и М/М/т:0,.

Глава

Исследование характеристик систем дифференцированного обслуживания поликомпонентных потоков.

3.1 Модель СМО - комбинация моделей М/М/т и М/М/т:0.

3.2 Модель СМО - комбинация моделей М/М/т, М/М/т:Е.

3.3 Модель СМО - комбинация моделей М/М/т, М/М/т:Е, М/М/т:0.„.

Глава

Численное моделирование нестационарного режима работы систем дифференцированного обслуживания поликомпонентных потоков.

4.1 Имитационное моделирование систем дифференцированного обслуживания поликомпонентных потоков.

4.2 Исследование нестационарного режима в системах дифференцированного обслуживания поликомпонентных потоков.

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

Основоположником этой теории стал датчанин, сотрудник Копенгагенской телефонной компании А.К. Эрланг. В своих работах (1908 — 1918) [1] он дал четкую математическую формулировку проблемы очередей, возникающих в сетях связи из-за того, что количество телефонных каналов по причинам экономического характера всегда существенно меньше числа установленных телефонов. Эрланг преследовал практическую цель — предложить методику расчета числа каналов, достаточного для обслуживания всех подключенных к сети телефонных аппаратов с малой вероятностью потери вызова. Допустив, что входной поток вызовов из бесконечного источника является пуассоновским, Эрланг получил .формулы для вероятностей различного числа ожидающих абонентов, распределения времени ожидания при равновесном состоянии системы и вероятности отказов для системы с потерями. Он получил решения для системы с ожиданием при постоянном времени обслуживания в случае одного, двух и трёх каналов, а также для произвольного числа каналов при экспоненциальном времени обслуживания. Направление, которое развивал Эрланг, называется сегодня теорией телетрафика и является разделом теории массового обслуживания.

Труды Эрланга послужили толчком для других работ в этом направлении. В данной области работали Фрай [2], Молина [3] и О'Делл [4]. Изучив первые работы по теории массового обслуживания, Сиски [5] приходит к выводу, что они были связаны в основном с одобрением или опровержением результатов Эрланга.

Позднее подобные задачи стали возникать и в других областях, не связанных с телефонией. После появления обобщающей статьи Кендалла [6] такого рода задачи выделяют в особую группу под названием теория очередей. Однако эта теория уже не охватывает системы массового обслуживания с потерями. К тому же очередь представляет собой группу клиентов, стоящих один за другим, что подразумевает обслуживание требований в порядке поступления. Кендалл вводит понятие дисциплина очереди, имея в виду другие возможные порядки обслуживания. На практике в наиболее напряжённые периоды перегрузок систем обслуживания оператор или устройство, управляющее процессом обслуживания, часто не в состоянии обеспечить обслуживание в порядке поступления. Как показал Уилкинсон [7], в этом случае фактический порядок обслуживания приближается к случайному выбору на обслуживание. В этой связи наиболее подходящим является термин теория массового обслуживания, введённый советским математиком А .Я. Хинчи-ным [8]. Предметом данной теории является как вероятностное описание процессов массового обслуживания, так и рассмотрение их в динамике.

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

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

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

Системы с обслуживанием требований в порядке поступления

В книге Феллера [10] исследовались задачи, связанные с очередями. С теоретической точки зрения значительный интерес представляет статья Кен-далла [11], в которой было введено понятие вложенных цепей Маркова. Класс систем, к которым применим метод вложенных цепей Маркова, весьма широк. Это системы, в которых либо поток не пуассоновский, либо обслуживание распределено по закону, не сводящемуся к смеси эрланговских законов, либо имеет место и то и другое. В него, в частности, входят многолинейные системы с ожиданием, с входящим потоком пальмовского типа и произвольно распределённой длительностью обслуживания. Примечательно, что при решении конкретных задач данный метод использовался значительно раньше в работах Фрая [12], чем появились работы Кендалла. В следующей статье Кендалл предложил классификацию систем массового обслуживания [13]. Кларк получил решение уравнений процесса рождения и гибели с постоянными коэффициентами для переходного состояния. В последующие годы различными способами решение этих уравнений получили Ледерманн и Ройтер [14], Бейли [15], Морз [16], Чемпернаун [17]. Карлин и Мак-Грегор [18] предложили решение этой задачи с помощью коэффициентов, являющихся функциями числа требований в очереди. Саати [19] с помощью преобразований Лапласа получил решение для переходного состояния марковской модели многоканальной системы. Кларк [20], а затем Лучак исследовали задачу, в которой коэффициенты являются функциями времени. Линдли [21] получил выражение для среднего времени ожидания при стационарном состоянии в одноканальной системе с произвольным входящим потоком и произвольным временем обслуживания при обслуживании требований в порядке поступления.

Системы со случайным выбором на обслуживание

Меллор [22] сделал попытку получить распределение времени ожидания для* системы со случайным выбором из очереди. Воло [23] дал точную формулировку этой задачи для системы с большим числом каналов при пуассо-новском выходящем потоке и экспоненциальном времени обслуживания. Позже эта задача была решена Поллачеком [24] и Пальмом [25]. Риордан разработал метод нахождения распределения времени ожидания, а Уилкин-сон [7] получил кривые распределения. Бёрк [26] исследовал задачу случайного выбора на обслуживание для одноканальной системы с пуассоновским входящим потоком и постоянным временем обслуживания.

Системы с приоритетом

Кобхем опубликовал первую статью, посвящённую системе с приоритетом, не прерывающим обслуживание, при пуассоновском входящем потоке и экспоненциальном времени обслуживания для одного и нескольких каналов. Он получил выражения для среднего времени ожидания требования, обладающего данным приоритетом. Холли упростил результаты Кобхема. Фиппс обобщил решение Кобхема на случай непрерывного числа приоритетов с приложением к ремонту станков. Морз [27] получил производящую функцию вероятностей стационарного состояния системы с двумя приоритетами, имеющими экспоненциальное время обслуживания с различными параметрами. Кестен и Ранненбург исследовали задачу Кобхема более детально и получили преобразования Лапласа-Стилтьеса, а также первые два момента для времени ожидания при стационарном состоянии в системе с произвольным временем обслуживания.

Дж. Джексон рассматривал системы с динамическими приоритетами [28]. Барри и Стефан исследовали систему с двумя приоритетами, прерывающими обслуживание, для случая пуассоновского входящего потока и экспоненциального времени обслуживания. Уайт и Кристай- рассмотрели ту же задачу для двух каналов и получили выражения для среднего времени обслуживания и среднего времени ожидания в системе с любым приоритетом, а также производящие функции распределения времени ожидания. Они рассмотрели также сходство между этой системой и системой, с разрушением очереди.

Р. Миллер [29] привёл несколько полученных результатов для системы с двумя приоритетами, имеющими экспоненциальное время обслуживания с различными параметрами, а также нашёл преобразования Лапласа-Стилтьеса и производящие функции для новых случаев. Хиткоут сделал значительный вклад в изучение систем с приоритетом, прерывающим обслуживание, исследовав многоканальную систему с несколькими приоритетами в переходном состоянии.

Системы с отказами

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

Подобную задачу, в которой длина очереди не может превосходить фиксированное конечное значение, исследовал Финч [30] для случая произвольного входящего потока. Он получил распределение длины очереди для стационарного состояния, доказав его существование.

В более ранних статьях Баррер [31] рассмотрел задачу о нетерпеливых клиентах, которые после определённого времени ожидания покидают находящуюся в стационарном состоянии одноканальную систему с пуассонов-ским входящим потоком и экспоненциальным временем обслуживания при случайном выборе заявки на обслуживание. Он также исследовал эту задачу [32] для системы с обслуживанием требований в порядке их поступления в случае, когда заявки покидают систему через определённый промежуток времени ожидания, и получил распределение длины очереди. Финч исследовал эту задачу для многоканальной системы с произвольным, входящим потоком. Он рассматривал также случай недетерминированного нетерпения в многоканальной системе с пуассоновским входящим потоком и экспоненциальным временем обслуживания и получил распределение длины очереди. Хейт изучал комбинацию оставления очереди с неприсоединением к очереди. Пальм исследовал случай раннего оставления очереди, а Коэн обобщил эту задачу для случая повторного поступления требований.

Интересные формулы найдены М.А. Шнепсом [33,34]. Он рассматривал сложную систему массового обслуживания с отказами, которая является отражением типичных телефонных систем.

Одним из важных вопросов, возникших в задачах телефонии, был вопрос о возможности использования формул, выведенных в предположении, что длительность обслуживания распределена по показательному закону при другом законе, но с тем же математическим ожиданием. Первым результатом, повлекшим за собой целую серию исследований, была известная теорема Б.А. Севастьянова [35] о независимости распределения состояний многолинейной системы с отказами от распределения длительности обслуживания при фиксированной средней длительности. Данная теорема была доказана методом интегро-дифференциальных уравнений. Позднее И.Н. Коваленко нашёл элементарное доказательство теоремы Севастьянова, опирающееся на метод Кендалла. Целый ряд постановок задач подобного рода, актуальных для приложений, был сформулирован Б.В. Гнеденко и решён его учениками: Т.П. Марьяновичем, В.Н. Ярошенко, И.Н. Коваленко. Эти результаты применимы для многих коммутационных систём, а также позволяют развить теорию телефонных систем с отказами обслуживающих приборов. Вместе с'тем, выяснилось, что в широком классе случаев перенесение результатов с показательного закона на произвольный принципиально невозможно. Соответствующий результат был также получен И.Н. Коваленко [36].

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

Системы с многофазным обслуживанием

О'Брайен исследовал две системы многофазного обслуживания: обе фазы в состоянии равновесия, с пуассоновскими входящими потоками и экспоненциальным временем обслуживания. Им получены выражения для распределения длины очереди и среднего времени ожидания. Р. Джексон [37] исследовал эту задачу для ограниченного и неограниченного входящих потоков при двух и трёх фазах и также получил распределение длины очереди. Хант изучал двухфазные системы с потерями, с ограниченной конечной очередью, и с неограниченной очередью и вычислил среднее число требований в системе. Маршалл и Рейч исследовали время ожидания для многофазных систем. Бёрк [38], Рейч [39], Коэн и Финч исследовали выходящий поток и установили независимо друг от друга, что выходящий поток для системы с пуассонов-ским входящим потоком и экспоненциальным временем обслуживания также будет пуассоновским. Д. Кениг и К. Маттес рассмотрели «маркированное обслуживание», включающее в качестве частных случаев многофазное обслуживание и обслуживание при выходе из строя обслуживающих приборов. Важные примеры такого рода были изучены ранее Т.П. Марьяновичем [40 — 42].

Системы смешанного типа

Важной задачей является исследование систем массового обслуживания смешанного типа, занимающих промежуточное положение между системами с ожиданием и системами с отказами. В действительности почти любой системе свойственны временные ограничения на длительность ожидания или длительность пребывания требований в системе. Обобщением классических результатов для систем смешанного типа занимались Д. Баррер, С.М. Броди, В.И. Мудров, И.Н. Коваленко, Л.Г. Афанасьева и другие. И.Н. Коваленко были исследованы системы с ограничением и обслуживанием в порядке поступления [43], а также многолинейные системы с простейшим входящим потоком и показательно распределённой длительностью обслуживания при постоянном ограничении на время ожидания или время пребывания требований в системе [44].

Системы с восстановлением

Пользуясь методами теории восстановления, Б.В. Гнеденко осуществил точный и асимптотический анализ схем массового обслуживания, описывающих функционирование дублированных систем [45,46]. Подобные системы часто встречаются в технике, в системах связи. Ряд результатов, опирающихся на теорию процессов восстановления, получен в работах А.Д. Соловьёва, Ю.К. Беляева, В.А. Каштанова, Е.Ю. Барзиловича и других.

Неполнодоступные системы

В неполнодоступных системах линии располагаются упорядоченными группами - пучками. Только некоторые обслуживающие устройства доступны клиентам. Вновь прибывшая заявка может быть обслужена свободной линией пучка с меньшим порядковым номером. Подобные системы изучались Эрлангом, Брокмейером, Пальмом [47], Уилкинсоном [48].

По мере развития теории массового обслуживания назрела необходимость построения математической теории, которая позволяла бы анализировать системы массового обслуживания универсальными методами. Такая теория должна ориентироваться на потребности современных сложных систем: систем связи, вычислительных машин, вычислительных комплексов, транспортных систем и др. Один из возможных вариантов схематизации сложных систем предложен Н.П. Бусленко [49]. Автор предлагает рассматривать агрегатированные системы весьма общей структуры; системы массового обслуживания, рассматриваемые в книге Риордана [50], представляют собой весьма частный случай агрегатированных систем. Было показано, что агрегатированные системы могут быть изучены при помощи метода Монте-Карло. Более узкий класс систем, допускающих изучение средствами теории марковских процессов, выделен И.Н. Коваленко [51]. В рамках обобщённых схем можно производить структурный анализ систем, устанавливая связь эффективности системы с эффективностью отдельных агрегатов, решать статистические задачи, связанные с оценкой надёжности и эффективности.

Как показывает исторический обзор, за время существования теории массового обслуживания проделано немало трудов в различных её направлениях. Примечательно, что большинство исследований в этой области было связано с решением конкретных прикладных задач. Задачи, связанные с массовым обслуживанием, всегда являются актуальными, а порой и злободневными. Интерес к теории массового обслуживания высок и сегодня. По мере роста технического прогресса появляются новые области приложений этой теории. Обзор научных статей [52 — 67] в данной области за последние годы показывает, что работы ученых этого времени были ориентированы на решение задач в области телекоммуникации. Однако в последнее время в связи с развитием рынка в России появляется все большее количество различного рода товаров и услуг, и возникают проблемы, связанные с организацией пунктов торговли и обслуживания населения. Для решения подобных задач целесообразно использовать методы теории массового обслуживания, основанные на математическом аппарате теории случайных процессов и цепей Маркова.

С появлением различных систем имитационного моделирования наблюдается снижение количества исследований систем массового обслуживания аналитическими методами. Это объясняется тем, что при помощи программных средств имитационного моделирования на основе метода Монте-Карло, сетей Петри и других методов возможно исследование широкого круга систем разной сложности. Подобные средства позволяют опытным путём испытать характер поведения системы ещё на этапе её проектирования. Для конкретного приложения возможно достаточно только численного решения задачи. Но для науки всегда большее значение имеют результаты, полученные аналитически, поскольку численное решение не обладает общностью, а является лишь частным случаем общего решения. Кроме того, решая конкретную задачу в общем виде, можно обнаружить возможные приложения найденного решения к другим областям. Так и зарождалась в своё время теория массового обслуживания. Наука не должна останавливать своё развитие при появлении альтернативных подходов решения рассматриваемых ею задач. Сложность аналитических методов не позволяет решать с их помощью любые задачи массового обслуживания, однако, круг задач, решаемых аналитически, весьма широк.

Практический интерес представляют модели массового обслуживания, являющиеся комбинациями ранее изученных моделей. Подобные модели наиболее полно описывают реальные объекты. В таких системах входные потоки включают требования разного типа, которые ведут себя в системе по-разному: одни обслуживаются только при наличии свободных аппаратов, другие - становятся в очередь, если она содержит не более определённого числа требований, третьи — дожидаются обслуживания до конца. Потоки, включающие заявки разных типов, будем называть поликомпонентными, а системы массового обслуживания (СМО), в которых заявки разных типов обслуживаются по-разному в, зависимости от выполнения тех или иных условий, - системами дифференцированного обслуживания. Примерами подобных систем могут служить различные пункты обслуживания населения. В этой связи цель настоящей работы заключается в разработке методов и алгоритмов организации обслуживания в системах массового обслуживания нового типа - открытых системах дифференцированного обслуживания поликомпонентных потоков, применимых для различных областей: телекоммуникаций, сферы обслуживания и др.

Математическая формализация обобщенных моделей массового обслуживания аналитическими методами невозможна без ряда допущений. Однако допущения о марковском характере процесса, протекающего в подобных системах в большинстве случаев, вполне оправданно. В большинстве задач прикладного характера замена непуассоновских потоков событий пуассонов-скими с теми же интенсивностями приводит к получению решения, которое мало отличается от истинного, а иногда и вовсе не отличается. При этом погрешность решения, как правило, находится в пределах точности исходных данных, которые зачастую известны весьма приближённо. Специальное моделирование различных задач, проведенное методом Монте-Карло [68], показало, что в большинстве случаев эта погрешность ограничена 3 — 5% и лишь в редких случаях доходит до 10 - 12%, что вполне приемлемо при решении прикладных задач. Данное положение объясняется тем, что потоки событий, протекающие в реальных системах, в силу предельных теорем теории потоков по своей структуре весьма близки к пуассоновским. Достаточные условия близости суммарного потока, слагаемые которого независимы и равномерно малы, к простейшему потоку были изложены А.Я. Хинчиным [9]. Его ученик Г.А. Ососков выяснил, что эти условия являются и необходимыми. Однако, как показал А.Д. Соловьёв, имеются особые условия, когда погрешность может достигать значительных величин. Поэтому при решении сложных задач, когда нет уверенности в том, что замена реальных потоков пуас-соновскими приведёт к малым ошибкам, нужно рекомендовать проверять аналитическое решение методом статистических испытаний. Проведение подобного эксперимента возможно на ЭВМ с применением специальных программных продуктов. При этом решение, полученное с помощью пуассонов-ских систем, можно рассматривать как первое приближение. В качестве простого инженерного критерия близости реального стационарного потока к пу-ассоновскому можно рассматривать близость математического ожидания и дисперсии числа событий, наступающих на определённом промежутке времени в реальном потоке. В большинстве случаев также достаточно получить характеристики системы для установившегося режима её работы. При малой продолжительности переходных процессов допустимо считать переходы между стационарными состояниями скачкообразными, исследуя только установившиеся режимы при различных значениях параметров. При большей длительности переходных режимовхледует разбивать их на несколько ступеней, представляющих собой кратковременные равновесные состояния.

Из выше изложенного очевидно, что для изучения реальных систем массового обслуживания не следует прибегать к применению сложного математического аппарата. Для решения практических задач достаточно рассмотреть системы весьма общей структуры в стационарном режиме функционирования. Входной поток заявок может состоять из нескольких потоков требований разного типа. В предположении, что отдельные потоки требований являются простейшими, входной поток, представляющий собой суперпозицию пуассоновских потоков, также будет простейшим с интенсивностью, равной сумме интенсивностей отдельных его составляющих [69]. Считая время обслуживания экспоненциально распределённым, получим пуассоновский выходной поток обслуженных заявок. В результате имеем марковский случайный процесс со счётным числом состояний и непрерывным временем, протекающий в системе. Исследовав стационарный режим функционирования при различных нагрузках, можно сделать выводы об эффективности работы системы массового обслуживания.

В книге А.П. Кирпичникова [70] приводится общий алгоритм построения классических моделей массового обслуживания прямыми аналитическими методами для стационарного режима функционирования с учётом принятых допущений. Наша задача заключается в том, чтобы, используя данную методику, получить общие математические зависимости для вероятностных, числовых и временных характеристик открытой многоканальной системы дифференцированного обслуживания поликомпонентных потоков в стационарном режиме работы.

16

ЗАКЛЮЧЕНИЕ

В настоящей работе были получены следующие результаты:

• Построены математические модели СМО нового типа — открытых многоканальных систем дифференцированного обслуживания поликомпонентных потоков в стационарном режиме функционирования.

• Усовершенствован метод аналитического моделирования СМО, основанный на применении математического аппарата цепей Маркова, путем введения новых вероятностных характеристик, таких как вероятность неполной загрузки накопителя, вероятность полной загрузки накопителя и вероятность немедленного обслуживания. Данные характеристики играют роль базисных параметров, через которые выражаются вероятностные характеристики, а также первые и вторые моменты числовых и временных характеристик стационарного режима функционирования СМО как в общем, так и в вырожденном случае, когда общие формулы при р = т имеют неопределенность.

• Исследован характер поведения вероятностных, а также числовых и временных характеристик стационарного режима в системах дифференцированного обслуживания поликомпонентных потоков с применением полученных аналитических моделей и вычислительного эксперимента.

• Разработана программа имитационного моделирования открытых систем дифференцированного обслуживания поликомпонентных потоков и проведён цикл численных экспериментов, в рамках которых исследован нестационарный режим функционирования данных систем. Выявлено, что квазистационарный режим в подобных СМО устанавливается приблизительно за 100 единиц модельного времени, равных среднему времени обслуживания заявки одним обслуживающим устройством. Получена общая формула зависимости числовых и временных характеристик СМО от времени в нестационарном режиме.

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

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

1. Brockmeyer Е., Halstrom H.L., Jensen A., «The Life and Works of A.K. Erlang», Copenhagen Telephone Company, Copenhagen, 1948.

2. Fry T.C., The Theory of Probability as Applied to Problems of Congestion, 1928.

3. Molina E.C., Application of the Theory of Probability to Telephone Trunking Problems, Bell System Tech. J., vol. 6, pp. 461-494, 1927.

4. O'Dell C.F., Theoretical Principles of the Traffic Capacity of Automatic Switches, P.O. Elec. Engrs. J., vol. 13, pp. 209-223, 1920.

5. Syski R., The Theory of Congestion in Lost-call Systems, A.Т.Е. Journal, vol. 9, pp. 182-215, 1953.

6. Kendall D.G. Some problems in the theory of queues, J. Roy. Statist. Soc., Ser. В., 1951, v. 13, pp. 151-173.

7. Wilkinson R.I., Working Curves for Delayed Exponential Calls Served in Random Order, Bell System Tech. J., vol. 32, pp. 360-383, 1933.

8. Хинчин А.Я. Математические методы в теории массового обслуживания. «Труды Математического института им. В.А. Стеклова», т. 49, 1955.

9. Хинчин А.Я. Работы по математической теории массового обслуживания. М.: Едиториал УРСС, 2004. 240 с.

10. Feller W., An Introduction to Probability Theory and Its Applications. John Wiley, New York, 1957.

11. Kendall D.G., Some Problems in the Theory of Queues, J.Roy. Statist. Soc., Ser. B, vol 13, №2, pp. 151-185, 1951.

12. Fry Т. C. Probability and its engineering uses. Van Nostrand, New York, 1928, p. 218.

13. Kendall D.G., Stochastic Processes Occuring in the Theory of Queues and Their Analysis by the Method of the Imbedded Markov Chain, Ann. Math. Statist., vol. 24, pp. 338-354, 1953.

14. Ledermann W., Reuter G.E., Spectral Theory for the Differential Equations of Simple Birth and Death Processes, Phil. Trans. Roy. Soc. London, Ser. A, vol. 246, pp. 321-369, 1954.

15. Bailey N.T. J., A Continuous Time Treatment of a Simple Queue, Using Generating Functions, J. Roy. Statist. Soc., Ser. B, vol. 16, pp. 288-291, 1954.

16. Morse P.M., Stochastic Properties of Waiting Lines, J. Operations Research Soc. Am., vol. 3, pp. 255-261, 1955.

17. Champernowne D.G., An Elementary Method of the Solution of the Queueing Problem with a Single Server and Constant Parameter, J. Roy. Statist. Soc., Ser. B, vol. 18, № l,pp. 125-128, 1956.

18. Karlin S., Mcgregor J., Many Server Queueing Processes, with Poisson Input and Exponential Service Times, Pasific J. Math., vol. 8, №1, pp. 87-118, 1958.

19. Saaty T.L., Time Dependent Solution of the Many Server Poisson Queue, Operations Reaserch, 1960.

20. Clarke A.B., A Waiting Time Process of Markov Type, Ann. Math. Statist., vol. 27, pp. 452-459, 1956.

21. Lindley D.V., Mathematical Theory — Marshalling & Queueing, Operational Research Quart., vol. 3, № 1, 1952.

22. Mellor S.D., Delayed Call Formulae When Calls Are Served in Random Order, P.O. Elec. Engrs. J., vol. 35, pt. 2, pp. 53-56, 1942.

23. Vaulot A.E., Délais d'attente des appels telephoniques, traits au hasard, Compt. rend., vol. 222, pp. 268-269, 1946.

24. Pollaszek F., La loi d'attente des appels telephoniques. Compt. rend., vol. 222, pp. 353-355, 1946.

25. Palm C., Research on Telephone Traffic Carried by Full Availability Groups, Tele., № 1, 1957.

26. Burke P.J., Equilibrium Delay Distribution for One Channel with Constant Holding Time, Poisson Input and Random Service, Bell System Tech. J., pp. 10211031, 1959.

27. Morse P.M., «Queues, Inventories and Maintenance», John Wiley, New York, 1958.

28. Jackson J.R., Some Problems in Queueing with Dynamic Priorities, Univ. Calif., Management Sci. Research Project Paper 62, 1959.

29. Miller R.G., Jr., Priority Queues, Ann. Math. Statist., vol. 31, № 1, 1960.

30. Finsh P.D., Balking in the Queueing System Gl/M/1, Acta math. Acad. Sci. Hung., vol. 10, № 1/2, pp. 241-247, 1959.

31. Barrer D.Y., Queueing with Impatient Customers and Indifferent Clerks, Operations Research, vol. 5, № 5, 1957.

32. Barrer D.Y., Queueing with Impatient Customers and Ordered Service, Operations Research, vol. 5, pp. 650-656, 1957.

33. Шнепс M.A. О применении цепей Маркова для изучения телефонных систем с потерями. Сб. «Проблемы передачи информации», вып. 12, 1963. Изд. АН СССР. М., с. 124- 134.

34. Шнепс М.А. О применении метода вложенных цепей Маркова к моделированию систем массового обслуживания с потерями. «Ученые записки Латвийского университета», т.47, 1963, с. 261 —266.

35. Севастьянов Б.А. Эргодическая теорема для марковских процессов и ее приложения к телефонным системам с отказами. «Теория вероятностей и ее применения», т. 2, вып. 1, 1957, с. 106 116.

36. Коваленко И.Н. Некоторые задачи массового обслуживания с ограничением. «Теория вероятностей и ее применения», т. 6, вып. 2, 1961, с. 222 228.

37. Jackson R. R. P., Queueing Systems with Phase Type Service, Operations Research Quart., vol. 5, pp. 109 120, 1954.

38. Burke P. J., The Output of a Queueing System, Operations Research, vol. 4, pp. 699-704, 1956.

39. Reich E., Waiting Times When Queues are in Tandem, Ann. Math. Statist., vol. 28, №3, p. 768, September, 1957.

40. Марьянович Т.П. Обобщение формул Эрланга на случай, когда приборы могут выходить из строя и восстанавливаться. «Украинский математический журнал», т. 12, №3, 1960, с. 279 286.

41. Марьянович Т.П. Надежность системы со смешанным резервом. «Доклады АН УССР», №8, 1961, с: 964 997.

42. Марьянович Т.П. Однолинейная система массового обслуживания с ненадежным прибором. «Украинский математический журнал», т. 14, №4, 1962, с. 417-422.

43. Коваленко И.Н. Исследование многолинейной системы массового обслуживания с очередью и ограниченным временем пребывания в системе. «Украинский математический журнал», т. 12, №4, 1960, с. 471 — 476.

44. Коваленко И.Н. Об одном методе в теории массового обслуживания. «Труды VI Всесоюзного совещания по теории вероятностей и математической статистике. 1960», Вильнюс, 1962, с. 357 358.

45. Гнеденко Б.В. О ненагруженном дублировании. «Изд. АН СССР. Техническая кибернетика», №4, 1964, с. 3 12.

46. Гнеденко Б.В. О дублировании с восстановлением. «Изв. АН СССР. Техническая кибернетика», №5, 1964, с. 111 — 118.

47. Palm С. Caicul exact de la perte dans les gropes de circuits échelonnes, Ericsson Technics, 1936, v. 3, pp. 41—71.

48. Wilkinson R. I. The interconnection of telephone systems — graded multiples, Bell System Tech. J., 1931, v. 10, pp. 531 564.

49. Бусленко Н.П. К теории сложных систем. «Изв. АН СССР. Техническая кибернетика», №5, 1963, с. 7 — 18.

50. Риордан Дж. Вероятностные системы обслуживания. М.: Связь, 1966.

51. Коваленко И.Н. О некоторых классах сложных систем. I. «Изв. АН СССР. Техническая кибернетика», №6, 1964, с. 3.

52. Герасимов А.И. О нормализующих константах в открытых и смешанных сетях массового обслуживания с несколькими классами сообщений / А.И. Герасимов // Доклады Академии Наук. — 2008. №3. — с. 314-318.

53. Gerasimov A.I. Analytical Methods for the Investigation and Optimization of Computer Systems and Networks Based on Queueing Network Models. Moscow: Radio & Svjaz, 2003. 288»p.

54. Герасимов А.И. Аналитические методы исследования и оптимизации вы1числительных систем и сетей на основе сетевых моделей массового' обслуживания. М.: Радио и связь, 2001. 240 с.

55. Митрофанов Ю.И., Рогачко Е.С. Управление распределением нагрузки в сетях массового обслуживания. Автоматика и телемеханика. 2008. №9.

56. Касконе Н., Разумчик Р.В. Экспоненциальная система массового обслуживания с отрицательными заявками и бункером для вытеснения заявок. Автоматика и телемеханика. 2008. №9.

57. Бочаров П.П., Печинкин A.B. Теория массового обслуживания. М.: Изд. РУДН, 1995.

58. Ким Ч.С., Клименок В.И., Орловский Д.С. Многолинейная система обслуживания с групповым марковским потоком и отрицательными заявками. Автоматика и телемеханика. 2006. №12.

59. Бочаров П.П., Вискова Е., Надаев Э. Марковская система массового обслуживания конечной емкости с отрицательными заявками в дискретном времени. Queues: Flows, Systems, Networks. 2005. № 18. P. 14-19.

60. Бочаров П.П. Система МАР/Г/l/r в условиях большого коэффициента вариации времени обслуживания. Автоматика и телемеханика. 2005. №11.

61. Башарин Г.П., Бочаров П.П., Коган Я.А. Анализ очередей в вычислительных сетях. Теория и методы расчета. М.: Наука, 1989.

62. Bocharov P.P., D'Apice С., Pechinkin A.V., Salerno S. Queueing theory. Utrecht-Boston: VSP, 2004.

63. Димитров Б.Н., Рыков B.B., Круглый 3.JI. Периодические пуассоновские процессы и распределения с почти отсутствующей памятью. Автоматика и телемеханика. 2004. № 10.

64. Д'Апиче Ч., Манзо Р., Печинкин A.B. Система обслуживания МАРК/ Gk/1 конечной емкости с обобщенной дисциплиной преимущественного разделения прибора. Автоматика и телемеханика. 2004. №. 11.

65. Д'Апиче Ч., Кристофано M.JL, Печинкин A.B. Система обслуживания МАРК/ Gk/1/oc с обобщенной дисциплиной преимущественного разделения прибора. Автоматика и телемеханика. 2004. №. 12.

66. Микадзе И.С., Хочолава В.В., Хуродзе P.A. Виртуальное время ожидания в однолинейной СМО с ненадежным прибором. Автоматика и телемеханика. 2004. №. 12.

67. Хочолава В.В., Микадзе И.С. Об одной модели системы массового обслуживания. Georg, engin, news. 2002. № 4. с. 47-52.

68. Овчаров JI.A. Прикладные задачи теории массового обслуживания. М.: Машиностроение, 1969.

69. Тихоненко О.М. Модели массового обслуживания в информационных системах. Мн.: УП «Технопринт», 2003. 327 с.

70. Кирпичников А.П. Прикладная теория массового обслуживания. Казань: Изд-во Казанск. гос. ун-та, 2008. 118 с.