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

РГ6 оя 2 5 ДЕН 2003

Санкт-Петербургский государственных! университет

На правах рукописи Милов Денис Сергеевич

Методы идемпотентной алгебры и анализа при исследовании сетей с очередями

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

АВТОРЕФЕРАТ

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

Санкт-Петербург 2000

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

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

Официальные оппоненты: доктор физико-математических наук, профессор И. В. Романовский; кандидат физико-математических наук, А. Н. Сивков

Ведущая организация — Северо-Западный государственный заочный политехнический университет (СЗПИ).

Защита состоится "22" ^¿хуе ¿^-¿2000 г. в &ч'лс. на заседании диссертационного совета Д063.57.52 по защите диссертаций на соискание ученой степени доктора физико-математических наук в Санкт-Петербургском государственном университете по адресу: 198904, Санкт-Петербург, Ст. Петергоф, Библиотечная пл., д. 2.

С диссертацией можно познакомиться в Научной библиотеке им. М. Горького Санкт-Петербургского государственного университета по адресу: 199034, Санкт-Петербург, Университетская наб., д. 7/9.

Автореферат разослан " 'И> " ¡-О'^ч 2000 г.

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

наук, профессор И. К. Даугавет

2,ХН* /-/. Г)

Общая характеристика работы

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

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

Цель работы. Целями работы являются:

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

2. Определение и оценка среднего времени работы сети из нового класса до момента сбоя.

3. Оптимизация количества вычислений при моделировании работы сетей со строго определенной топологией сетевого графа.

Научная новизна. Представлены следующие новые результаты:

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

2. Описан набор обычных и вероятностных свойств для матричных операторов, которые использовались в диссертации.

3. Для нового класса сетей введено понятие среднего времени работы до момента сбоя и построен ряд оценок для этой величины.

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

6. Представлены примеры использования аппарата (тах,+)-алге-бры для описания динамики сетей, отличных от рассмотренных в основной части диссертации.

7. Дан пример программной реализации (объектно-ориентированная модель) работы сетей с очередями из рассматриваемого класса.

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

Практическая ценность. Теоретические результаты и программное ядро могут быть использованы для дальнейшего развития методов идепотентного анализа и моделирования сетей с очередями из рассмотренного в диссертации класса.

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

1. Международной конференции "Industrial Week '2000", Eindhoveen (Holland), 2000,

2. XII международной конференции "Проблемы теоретической кибернетики", Нижний Новгород, , 1999,

3. III международной конференции по моделированию "Mathematical methods in stochastic simulation and experimental design", St.Petersburg, 1998,

4. Международной конференции "Математические методы и компьютеры в экономике", Пенза, 1998,

5. II международной конференции по моделированию "Mathematical methods in stochastic simulation and experimental design", St.Petersburg, 1996

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

Публикации. Основные результаты опубликованы в работах [1-5].

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

Содержание работы

Во введении дается обзор области исследований, а также кратко излагается материал диссертации.

Глава 1. Глава посвящена идемпотентным алгебрам и (тах,+)-алгебре, в частности. Последняя (скалярная) определяется как множество вещественных чисел Н, расширенное путем добавления элемента £ = — оо, с заданными на нем операциями (-.) и 0, которые для любых х, у € Л определяются следующим образом:

х ф у — шах(з;, у), х ф у — х + у,

причем х ® е — е. Идемпотентная алгебра (полукольцо) вещественных матриц вводится обычным путем (см., например, Маслов В.П., Колокольное В.Н. Идемпотентный анализ и его применение в оптимальном управлении. М.: Физматлит, 1994. 144с.). Рассматриваются свойства скалярной и матричной (гпах,+)-алгебр, а также матрицы смежностей графа в последней из них. Описываются условия разрешимости уравнения

х — А с?) х ф Ь.

Глава 2. Описывается класс сетей с очередями, динамическое уравнение которого представимо при ряде условий в виде:

х(к) = А{к)®х(к- 1),

(1)

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

A(k) = (E®%®GT)®r ®Тк,

где G - матрица смежности сетевого графа, г - длина наибольшего пути в этом графе, Е - единичная матрица, а Тк ~ диагональная матрица времен обслуживания требований на к-ом цикле. Здесь же показаны оценки среднего времени рабочего цикла сетей из данного класса (см. Krivulin N.K., Nevzorov V.B. Оп Evaluation of the Mean Service Cycle Time in Tandem Queuing Systems. 2000, (in edition)).

Глава 3. Рассматриваются матричные операторы и их обычные а вероятностные свойства, которые используются в дальнейшем (см., например, Воробьев H.H. Экстремальная алгебра положительных матриц// Elektronische Informationscverarbeitung und Kybernetik. 1967. Bd. 3, N 1. S. 39-72.): для любой (m x п)-матрицы А — («у):

{£, если min 0 = е,

• , , ' j Л /i(A) = min {/ti (A),H2{A)} ,

min{a,'j I aij ф e), иначе; >i

(

e, если min0a,j = e,

= < min{a,j | a{j ф e}, иначе; >i

и

Глава 4. Описывается новый класс сетей со стохастической структурой сетевого графа. Его динамическое уравнение представимо в виде (1), но с переходной матрицей:

А(к) = А(Тк, А) = {Е®Тк® Г?)тк ф Тк,

где 1]к ~ максимальная длина пути в сетевом графе, соответствующем матрице Д на Аг-ом рабочем цикле. Здесь же определяется среднее время работы сети до момента сбоя:

оо

ЕШ\ = (1-р)^Е\\Ак\\рк, (2)

к = 1

где р - вероятность успешного завершения очередного рабочего цикла. Для (2) построен ряд верхних и нижних оценок (рассмотрена также точность верхних оценок для разных случаев). Например:

Лемма 1

ЕЫ > ар( 1 - рт) - 0р ~ ™Рт) + 7-ргр

т=[а/0\, а = Е\\Л(1)\\-а(Е[Т1}), 0=\\Е[Ъ]\\-11{Е[Ъ]), 7=||ВД||: Лемма 2

Е\\М\ < ^^1^(1)11.

Лемма 3 Для сетевого графа, принимающего равновероятно М состояний, справедливо (Я, - максимальный по всем графам путь):

р (М + 1) Зр (М — 1) + ШЧ + 16М д2 + Н(М^>

г^е 9 = — 1п(р)/2, ег^г) = (2/^ ехр(-*2)Л,

Я(М,,) = тах( м ^^Г*} •

Глава 5. Показано применение аппарата (тах,+)-алгебры для исследования ряда частных систем с очередями.

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

Глава 7. Дается краткое описание представленного в приложении

примера программы для моделирования работы сети с очередями из

нового, определенного в диссертации класса.

В заключении излагаются основные результаты диссертации.

Публикации автора по теме диссертации

[1] Кривулин Н.К., Милое Д.С. Оценки среднего времени безотказной работы для одного класса систем с очередями// Сб. тезисов (под редакцией Лупанова О.Б.) XII международной конференции "Проблемы теоретической кибернетики", Н.-Новгород, Издательство математико-механического факультета Московского государственного университета, Москва, 1999, Часть I, 120.

[2] Кривулин Н.К., Милоо Д. С. Оценки среднего времени работы для одного класса систем с очередями // Дискретные модели, синтез и оптимизация (Вычислительная техника и проблемы кибернетики, издание 29, под редакцией Чиркова М.К. и Маслова С.П.), Издательство С.-Петербургского государственного университета, С.-Петербург, 1998, 228-242.

[3] Милов Д.С. Анализ среднего времени работы систем с очередями на основе алгебраических моделей, Международная конференция " Математические методы и компьютеры в экономике", Пенза, сборник тезисов, май, 1998. Пензенский технологический институт, Пенза, 1998, Часть I, 48-49.

[4] Krivulin N.K., Milov D.S. Bounds on the Mean Working Time for Queuing Networks with Random Topology // in Proceedings 3rd St.Petersburg Workshop on Simulation, St.Petersburg, June 28-July 3, 1998. St.Petersburg University Press, St.Petersburg, 1998, 338-339.

[5] Krivulin N.K., Milov D.S. An Algebraic Model of Queuing Networks // in Proceedings 2nd St.Petersburg Workshop on Mathematical Methods in Stochastic Simulation and Experimental Design, St.Petersburg, June 18-21, 1996. (Ermakov S.M., Melas V.B., eds.), St.Petersburg University Press, St.Petersburg, 1996, 156-161.

Введение

1 Идемпотентная алгебра

1.1 Идемпотёнтные полугруппы и полукольца.

1.2 Определение и обозначения скалярной (тах,+)-алгебры

1.3 Основные свойства скалярной (тах,+)-алгебры.

1.4 Матричная (тах,+)-алгебра и ее основные свойства

1.5 Матрица смежностей ориентированного графа в (тах,+)-алгебре и ее свойства.

1.6 Уравнение х = А <%> х Ь и его разрешимость

2 Алгебраическая модель сети с очередями

2.1 Общие понятия

2.2 Модели сетей с операциями синхронизации

2.3 Частный класс сетей с операциями синхронизации

2.4 Среднее время рабочего цикла сети из частного класса

3 Матричные операторы в (тах,+)-алгебре и их свойства 2{

3.1 Определение четырех операторов

3.2 Обычные свойства операторов в (тах,+)-алгебре

3.3 Вероятностные свойства операторов в (тах,+)-алгебре

4 Стохастические сети

4.1 Определение стохастических сетей и основные свойства, связанные с ними

4.2 Среднее время работы стохастических сетей с отказами

4.3 Оценивание среднего времени работы сети.

4.4 Нижние оценки

4.5 Верхние оценки.

4.6 Примеры.

5 Примеры использования (тах,+)-алгебры для описания динамики ряда частных сетей

6 Оптимизация вычислений детерминированных сетей

6.1 Иерархия сетей и ее уровни.

6.1.1 Уровни иерархии.

6.1.2 Перенумерация узлов

6.1.3 Переходная матрица для сети с перенумерованными узлами.

6.2 Алгоритмы оптимизации вычислений при моделировании сетей с синхронизацией

7 Описание программы 73 Заключение 75 Библиография 77 Приложения

Методы анализа динамических систем условно можно разделить на две основные, несомненно, пересекающиеся части: аналитические методы и имитационные. Те и другие получили широкое признание во всем мире, своих приверженцев и противников, свои научные школы и направления в развитии. На данный момент затруднительно перечислить даже малую долю всех научных докладов, статей и монографий, которые посвящены этой теме. К примеру, в книге Ермакова С.М. [10], вышедшей в свет в 1971 году, указывается тот факт, что в период с 1955 по 1970 годы только в нашей стране вышло более 2000 научных публикаций посвященных лишь методу Монте-Карло, а ведь это . не охватывает всей области, в которой ведутся исследования посвященные анализу динамических систем и смежным вопросам.

Большой вклад в данную область внесли исследования аналитических методов анализа в работах Гнеденко Б.В.[7, 8], Колмогорова А.Ц. [8, 15], Феллера В. [28] и др.

В области имитационных методов анализа динамических систем хотелось бы отметить работы Бусленко Н.П. [3, 4], Ермакова С.М. [10, 11, 12, 35, 36, 37], Романовского И.В. [26], Соболя И.М. [27] и др.

Однако стоит отметить, что указанные ученые и их коллеги нередко ведут свои исследования в областях, занимающих промежуточное положение между аналитическими и имитационными методами анализа. Это связано, прежде всего, с рядом проблем по использованию этих методов в чистом виде. Аналитические методы зачастую накладывают весьма жесткие условия на рассматриваемые модели, существенно сужал класс рассматриваемых задач (как пример, узкий диапазон распределений в Теории Массового Обслуживания). Имитационные модели страдают зачастую другим недостатком - сложностью описания модели и учета всех ее характеристик. Одно из решений данной проблемы видится в нахождении математических аппаратов, позволяющих описывать динамические уравнения и характеристики больших систем в удобном для анализа и моделирования виде.

В последние годы в мире получил довольно широкое признание и интерес метод анализа, который основан на использовании аппарата идемпотентных алгебр. Здесь можно привести в пример работы Кинг-мена Ж.Ф.С.[45], Колокольцова В.Н.[24], Кунингхэм-Грина Р.А.[33], Маслова В.П. [24] и др.

Однако стоит отметить, что вопросы, связанные с данной областью, поднимались еще в 60-е годы Романовским И.В. в [26], где были получены результаты, связанные с решением дискретного уравнения Бел-лмана, а также Воробьевым H.H. [5], которым был описан ряд задач и методика их решения с помощью аппарата минимаксной алгебры.

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

В последние годы заметный интерес возник к описанию динамики сетевых систем с очередями с помощью идемпотентных алгебр, в частности, (тах,+)-алгебры. Здесь стоит отметить работы Кривулина Н.К. [20, 21, 22, 47, 48, 49, 50, 51, 52, 53, 55, 56, 57, 58, 63, 64, 65].

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

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

Также в диссертации рассматриваются свойства (обычные и вероятностные) ряда матричных операторов в данной (тах,+)-алгебре. С их помощью находится или оценивается ряд динамических характеристик для систем.

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

Первая глава носит вводный характер и дает краткий обзор понятий, связанных с идемпотентными алгебрами и с (тах,+)-алгеброй, в частности.

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

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

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

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

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

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

Отметим, что область применения аппарата (тах,+)-алгебры, несомненно, шире и заслуживает пристального внимания.

Основные результаты диссертационной работы можно сформулировать следующим образом:

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

Определено динамическое уравнение в идемпотентной (тах,+)-алгебре для нового класса сетей с очередями.

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

Введено понятие среднего времени работы до момента сбоя для нового класса сетей с очередями. Построен ряд оценок для данной величины.

Проведен анализ сетей со строго определенной топологией сетевого графа, для которых построен алгоритм перенумерации, узлов. Данная процедура позволяет сократить количество вычислительных операций при моделировании этого класса сетей с очередями.

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

Дан пример программной реализации (на основе объектно-ориентированной модели) работы сетей с очередями из рассматриваемого в диссертации класса. Результаты программного моделирования использовались в ряде примеров в диссертации.

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

Заключение

1. Бачелли Ф., Маковски A.M. Использование методов теории массового обслуживания для анализа систем с ограничениями по синхронизации// Труды Института Инженеров по Электротехнике и Радиоэлектронике. 1989. Т. 1. N 1. С. 99-128.

2. Боровков A.A. Теория вероятностей. М.: Наука, 1986

3. Бусленко H.H. Моделирование сложных систем. М.: Наука, 1968.

4. Бусленко Н.П., Голенко Д.И., Соболь И.М., Сро/гович В.Г., Шрей-дер Ю.А. Метод статистических испытаний (метод Монте-Карло), СМБ, Физматгиз, М., 1962.

5. Воробьев H.H. Экстремальная алгебра положительных матриц// Elektronische Informationscverarbeitung und Kybernetik. 1967. Bd. 3, N 1. S. 39-72.

6. Гладышев Е.Г. О статистической аппроксимации// Теория вероятностей и ее применения (1965), 10, N2, 297-300.

7. Гнеденко Б.В. Курс теории вероятностей. Гостехиздат, 1954.

8. Гнеденко Б.В., Колмогоров А.Н. Предельные распределения для сумм независимых случайных величин. Гостехиздат, 1949.

9. Градштейн И. С., Рыжик И.М. Таблицы интегралов сумм, рядов и произведений. М.: Физматгиз, 1962. 1100с.

10. Ермаков С.М. Метод Монте-Карло и смежные вопросы. М.: Наука, 1971., 328 стр.

11. Ермаков С.М., Мелас В. Б. Математический эксперимент с моделями сложных стохастических систем. Издательство Санкт-Петербургского Университета, 1993.

12. Ермаков С.М., Михайлов Г.А. Статистическое моделирование. -М.: Наука, 1982.

13. Клейн Дж. Статистические методы в имитационном моделировании. М.: Статистика, 1978.

14. Климов Г.П. Сохастические системы обслуживания. М.: Наука, 1966.

15. Колмогоров А.Н. Основные положения теории вероятности. ГОНТИ, 1936.

16. Коэн Г., Моллер П., Кадра Ж.-П., Въо М. Алгебраические средства оценивания характеристик дискретно-событийных систем // ТИИЭР. 1989. - Т. 77, N 1. - С. 30-53.

17. Кривулин Н.К. Оптимизация сложных систем для имитационного моделирования// Вестник Ленинградского Университета. Математика, 23 (1990), N 8, 100-102.

18. Кривулин Н.К. Использование моделирования для оптимизации дискретных динамических систем, диссертация на соискание степени кандидата физико-математических наук, Санкт

19. Петербургский Государственный Университет, Санкт-Петербург, 1990.

20. Кривулин Н.К., Милое Д. С. Оценки среднего времени безотказной работы для одного класса систем с очередями // Вестник Санкт-Петербургского государственного университета, 10 стр., (в печати).

21. Маслов В.П., Колоколъцов В.Н. Идемпотентный анализ и его применение в оптимальном управлении. М.: Физматлит, 1994. 144с.

22. Михайлов Г.А. Некоторые вопросы теории метода Монте-Карло. -Новосибирск, Наука, 1981.

23. Романовский И.В. Оптимизация стационарного управления дискретным детерминированным процессом// "Кибернетика", N 4, К., 1967, cnh 66-78.

24. Соболь И.М. Численные методы Монте-Карло. М., 1981.

25. Феллер В, Введение в теорию вероятностей и ее приложение: в 2-х томах. М., 1984.

26. Cassandras C.G., Strickland S.G. Perturbation Analytic Methodologies for Design and Optimization of Communication Networks// IEEE J. Select. Areas Commun., vol 6, issue 1, 1988, p. 158-171.

27. Chen L., Chen C.-L. A Fast Simulation Approach for Tandem Queueing Systems// Proc. 1990 Winter Simulation Conf. (Balci O., Sadowski R.P., Nance R.E., eds), 1990, p. 539-546.

28. Cuninghame-Green R.A. Minimax Algebra // Lecture notes in economics and mathematical systems, 166 / Berlin: Springier-Verlag, 1979.

29. Disney R.L., König D. Queueing Networks: a Survey of Their Random Processes// SIAM Review 27 (1985), no. 3, 335-403.

30. Ermakov S.M., Krhmlin N.K. Efficient Parallel Algorithms for Tandem Queueing System Simulation, in Proc. 3rd Beijing International Conference on System Simulation and Scientific

31. Computing, Beijing, China, October 17-19, 1995, Delayed Papers, 812.

32. Ermakov S.M., Krivulin N.K. Efficient Algorithms for Tandem Queueing System Simulation, Applied Mathematics Letters, 7 (1994), no. 6, 45-49.

33. Ermakov S.M., Krivulin N.K., Melas • V.B. Efficient Methods of Queueing Systems Simulation, in Proc. European Simulation Multiconference, Copenhagen, Denmark, June 17-19, 1991, (Mosekilde E., ed.), 8-20.

34. Glasserman P., Yao D.D. Stochastic Vestor Differenca equations with stationary coefficients, J. Appl. Probab. 32 (1995), 851-866.

35. Greenberg A.G., her B.D. Proc. Camb. Phil. Soc. vol 48, 1952, p. 277289.

36. Gumbel E.J. The Maxima of the Mean Largest Value and of the Range// Ann. Math. Statist. 25 (1954), 76-84.

37. Haber S. A Combination of Monte Carlo and Classical method for evaluating multiple integral// Bull. Amer. Math. Soc. 1968, 74, 683686.

38. Hammersley J.M., Handscomb D.C. Monte Carlo Method, London, N.Y., 1964.

39. Hartly H.O., David H.A. Universal Bounds for Mean Range and Extrem Observation// Ann. Math. Statist. 25 (1954), 89-99.

40. Kiefer J., Wolfowitz J. On the Theory of Queues with Many Servers// Trans. Amer. Math. Soc:., vol 78, 1955, p. 1-18.

41. Kingman J.F.C. Subadditive Ergodic Theory// Ann. Probab. 1 (1973), 883-909.

42. Kleinrock L. Queueing Systems, Volume II: Computer Applications, John Wiley, N.Y., 1976.

43. Krivulin N.K. Simple Bounds on the Mean Cycle Time in Acyclic Queueing Networks// in Proc. 3rd St.Petersburg Workshop on Simulation, St.Petersburg, June 28-July 3, 1998. St.Petersburg Univ. Press, St.Petersburg, 1998, 331-337.

44. Krivulin N.K. Monotonicity properties and simple bounds on the mean cycle time in acyclic fork-join queueing networks// Recent Advances in Information Science and Technology/ Ed. by Mastorakis N. World Scientific, 1998. P. 147-152.

45. Krivulin N.K. Bounds on Mean Cucle Time in Acyclic Fork-Join Queueing Networks// Proc. Intern. Workshop on Discrete Event Systems, Cagliari, Italy, August 26-28, 1998, IEE, London, 1988, pp. 469-474.

46. Krivulin N.K. Max-plus algebra models of queueing networks// Proc. Intern. Workshop on Discrete Event Systems WODES'96. London: University of Edinburgh, UK, August 19-21, 1996. The Institution of Electrical Engineers, 1996. P. 76-81.

47. Krivulin N.K. A Max-Algebra Approach to Modeling and Simulation of Tandem Queueing Systems, Mathematical and Computer Modelling, 22 (1995), no.3, 25-31.

48. Krivulin N.K. Algebraic Models in Simulation of Tandem Queueing Systems, in Proc. 1995 Summer Computer Simulation Conference,

49. Tuncer I. Oren, Louis G. Birta, eds.), Simulation Councils, Inc., 1995, 9-14.

50. Krivulin N.K. Unbiased Gradient Estimation in Queueing Networks with Parameter-Dependent Routing, in Proc. International Conference on Control and Information 1995, (Wong Wing-Shing, ed.), The Chinese University Press, Hong Kong, 1995, 351-356.

51. Krivulin N.K. An Algebraic Approach to Modeling and Simulation of Tandem Queueing Systems, in Proc. European Simulation Multiconference, Prague, Czech Republic, June 5-7, 1995, (Miroslav Snorek, Milan Sujansky, Alexander Verbraeck, eds.), 271-275.

52. Krivulin N.K. Recursive Equations Based Models of Queueing Systems, in Proc. European Simulation Symposium, Istanbul, Turkey, October 9-12, 1994, (Ali R„ Kaylan. Axel Lehmann, Tuncer I. Oren, eds.), 252-256.

53. Krivulin N.K. Using Max-Algebra Linear Models in the Representation of Queueing Systems, in Proc. 5th SIAM Conference on Applied Linear Algebra, Snowbird, UT, June 15-18, 1994, (John G. Lewis, ed.), 155-160.

54. Krivulin N.K. A Recursive Equations Based Representation for the G/G/m Queue, Applied Mathematics Letters, 7 (1994), no. 3, 73-78.

55. Krivulin N.K. Unbiased Estimates for Gradients of Stochastic Network Performance Measures, Acta Applicandae Mathematicae, 33 (1993), 21-43.

56. Krivulin N.K. An Analysis of the Least Median of Squares Regression Problem, in Proc. 10th Symposium 011 Computational Statistics, Neuchatel, Switzerland, August, 1992, (Dodge Y., Whittaker J., eds.),1, Physica-Verlag, 1992, 471-476.

57. Krivulin N.K. Optimization of Complex Systems for Simulation Modeling Vestnik Leningrad University: Mathematics, 23 (1990), no.2, 64-67.

58. Krivulin N.K., Nevzorov V.B. On Evaluation of the Mean Service Cycle Time in Tandem Queuing Systems. 2000, (in edition).

59. Loynes R.M. The Stability of a Queue with Non-independent Inter-Arrival and Service Times// Proc. Camb. Phil. Soc. 58 (1962), no. 3, 497-520.

60. Lindley D. V. The Theory of Queues with Single Server// Proc. Camb. Phil. Soc. vol 48, 1952, p. 277-289

61. Marci8kiewicz J., Zigmund A. Sur les Fonctions Indepedantes// Fund. Math. 29 (1937), 60-90.

62. Rubinstein R.Y. Simulation and the Monte Carlo Method, N.Y., 1981.

63. Sacks J. Ergodicity of Queues in Series// Ann. Math. Statist. 31 (1960), 579-588.

64. Shaked M., Shanthikamar J.G. Stochastic Convexity and its Applications// Adv. Appl. Prob., vol 20, 1988, p. 427-446.

65. Shanthikumar J.G., Yao D.D. Second-Order Stochastic Properties in Queueing Systems// Proc. IEEE, vol 77, issue 1, 1989, p. 162-170.