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

• Лезарев, Александр Викторович
• кандидат технических наук
• 2005

Оглавление диссертации кандидат технических наук Лезарев, Александр Викторович

ВВЕДЕНИЕ.

ГЛАВА 1 .СРЕДНЯЯ ДЛИТЕЛЬНОСТЬ ПЕРОДА ЗАНЯТОСТИ В ОДНОЛИНЕЙНОЙ СИСТЕМЕ МАССОВОГО ОБСЛУЖИВАНИЯ С ДВАЖДЫ СТОХАСТИЧЕСКИМ СИНХРОННЫМ ВХОДЯЩИМ ПОТОКОМ.

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

1.2 Вывод дифференциальных уравнений.

1.3 Вид решений и их нахождение.

1.4 характеристическое уравнение.

1.5 Нахождение Вх и В2.

1.6 Нахождение средней длины периода занятости.

0 1.7 Расчет безусловной средней длительности периода занятости

1.8 Расчет вспомогательных вероятностей.

1.9 Расчет основных вероятностей.

1.10 Характеристическое уравнение и его корни. щ 1.11 Нахождение Pu(l) и P21(l).

1.12 Нахождение щ и 7г2.

1.13 Стационарная плотность вероятностей незавершенной работы.

ГЛАВА 2. СРЕДНЯЯ ДЛИТЕЛЬНОСТЬ ПЕРИОДА ЗАНЯТОСТИ СИСТЕМЫ МАССОВОГО ОБСЛУЖИВАНИЯ С ВЫТЕСНЕНИЕМ ЗАЯВКИ ПРИ ДВАЖДЫ СТОХАСТИЧЕСКОМ СИНХРОННОМ ВХОДЯЩЕМ ПОТОКЕ.

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

2.2 Вывод уравнений для условной средней длительности периода занятости.

2.3 Нахождение условных средних длительностей периода занятости.

2.4 Вычисление вероятностей.

2.5 Плотность вероятностей незавершенной работы.

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

3.1 Описание системы.

3.2 Финальные вероятности.

3.3 Расчет характеристик системы через производящие функции.

3.3.1 Расчет финальных вероятностей состояния потока.

3.3.2 Математическое ожидание числа заявок в системе.

3.3.3 Дисперсия числа заявок в системе.

3.4 Непосредственный расчет характеристик системы.

3.4.1 Расчет среднего числа заявок в системе.

3.4.2 Вычисление вторых начальных моментов.

3.4.3 Функция корреляции.

3.5 Асимптотическое исследование системы.

3.6 Период занятости.

3.7 Средняя длительность периода занятости.

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

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

4.2 Программное обеспечение проведенных исследований.

4.2.1 Общая характеристика программы.

4.2.2 Основы работы с программой.

4.2.3 Расчет характеристик однолинейной СМО.

4.2.4 Расчет характеристик СМО с вытеснением заявки.

4.2.5 Расчет характеристик бесконечнолинейной СМО.

4.2.6. Экспорт данных.

4.2.7. Окно результатов.

4.2.8. Примеры имитационного моделирования СМО.

Введение диссертации (часть автореферата) на тему «Характеристики периода занятости систем массового обслуживания при дважды стохастическом синхронном входящем потоке»

Актуальность работы

Системы массового обслуживания (СМО) являются стандартной математической моделью для описания многих технических, биологических и других систем. В частности, они находят всё более широкое применение для описания сетей связи и сетей ЭВМ, как локальных, так и глобальных [5, 44].

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

В реальных системах эти потоки событий, как правило, являются нестационарными. Кроме того, интенсивность потока может также меняться случайным образом. Поэтому достаточно адекватной реальности являются так называемые дважды стохастические потоки заявок, еще слабо изученные [6, 61, 67,71, 74]. Изучению систем массового обслуживания с такими входящими потоками посвящены работы А.Н. Дудина и его сотрудников [40—42], а также отдельные работы других авторов.

Одним из наиболее изученных дважды стохастических потоков является поток событий с двумя возможными значениями интенсивности. Свойства потоков, где переходы между значениями интенсивности образуют дискретный марковский процесс с непрерывным временем, оценка его параметров и фильтрация интенсивности изучена в работах A.M. Горцева и его сотрудников [27-36]. Ими же изучены характеристики ряда систем массового обслуживания при таком входящем потоке [28, 33].

Однако имеется одна характеристика, которая осталась не исследованной в работах A.M. Горцева и его соавторов. Эта характеристика — период занятости системы массового обслуживания при таком входящем потоке. Между тем знание хотя бы средней длительности периода занятости представляет определенный интерес при проектировании сетей связи и сетей ЭВМ.

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

1. Администрирование в сетях ЭВМ. Например, провайдер, который пре-« доставляет нам доступ в Интернет, фиксирует только наш вход в систему и выход из нее, а к каким сайтам мы обращаемся во время нашего сеанса работы - его не касается. Поэтому свое представление о нас он формирует только по моментам начала и конца периодов занятости и должен строить свои оценки именно по этим данным. * 2. В последнее время при проектировании и эксплуатации вычислительных сетей часто используются технологии распределенных сетевых ресурсов и распределенных вычислений. Основная идея этих технологий заключается в следующем: дорогостоящие ресурсы вычислительной сети не должны дублироваться на рабочих местах пользователей, но при этом мощности сетевых ф вычислительных ресурсов должны обеспечить комфортную работу всех пользователей сети. Приведем классические примеры организации таких сетевых ресурсов: не стоит покупать на каждое рабочее место сети принтер, достаточно ку-^ пить несколько сетевых принтеров, количество которых должно быть определено исходя из соображений оптимальной загрузки таких ресурсов; не стоит устанавливать для каждого пользователя сети сервер для доступа в Internet, достаточно установить ряд серверов, количество и вычислительные мощности которых должны обеспечить пользователям допустимый уровень работы в Internet; наконец, современные технологии позволяют развивать вычислительные ресурсы предприятий двумя способами: увеличение технических возможностей каждого рабочего места пользователей, т.е. всего парка вычислительных машин, или, создание так называемых терминальных центров, каждый из которых реализует поддержку определенного количества пользователей. С экономической точки зрения выгоднее поддерживать терминальный центр, кроме того, организация вычислительных сетей таким образом более выгодна и в связи с участившимися случаями «компьютерного пиратства».

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

3. Наконец, типичным примером таких ситуаций являются физические, технические или биологические системы с так называемым «мёртвым временем», когда часть событий исходного потока теряется из-за эффекта мёртвого времени, возникающего в регистрирующих приборах, и наблюдению доступны лишь моменты начала периодов занятости.

Поэтому изучение этой характеристики дополняет работы A.M. Горцева и представляет определенный практический интерес. В работах А.Б. Орлова [12-14,16,17,57,58] изучены свойства этой характеристики, когда входящий поток заявок является дважды стохастическим потоком с двумя значениями интенсивности, переходы между которыми образуют дискретный марковский процесс с непрерывным временем. Представляет интерес дальнейшее изучение систем массового обслуживания для других видов дважды стохастических входящих потоков.

Цель работы

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

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

I. Найти для однолинейной СМО с бесконечным бункером и однолинейной СМО с вытеснением заявки, находящейся на обслуживании:

1. Условную среднюю длительность периода занятости при условии, что известно значение интенсивности в начале периода;

2. Переходные вероятности между значениями интенсивности в начале и в конце периода занятости;

3. Переходные вероятности между значениями интенсивности в нача-t ле и в конце периода простоя системы;

4. Финальные вероятности значения интенсивности в начале периода занятости и безусловную среднюю длительность периода занятости.

И. Найти для бесконечнолинейной СМО: ^ 1. Математическое ожидание, дисперсию и функцию корреляции числа заявок в системе;

2. Коэффициенты сноса и диффузии, среднюю длительность периода занятости, показав, что при больших загрузках число заявок в системе может быть аппроксимировано диффузионным случайным процессом. * III. Разработать программное обеспечение для расчета всех этих характеристик.

Работа проводилась по плану научно исследовательских работ факультета информатики, экономики и математики филиала Кемеровского государственного университета в г. Анжеро-Судженске.

Состояние проблемы

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

Вообще говоря, характеристики периода занятости не привлекали особого внимания исследователей. В классических монографиях [7, 26, 48] и даже в очень подробных справочниках [43, 71] можно найти лишь распределение длительности периода занятости однолинейной СМО в следующих ситуациях: рекуррентный входящий поток заявок и экспоненциальное распределение времени обслуживания; пуассоновский входящий поток заявок и рекуррентное обслуживание.

Однако даже характеристики периода занятости в бесконечнолинейной

СМО при пуассоновском входящем потоке заявок и рекуррентном обслуживании были получены сравнительно недавно [22, 23].

С другой стороны, период занятости СМО имеет самое прямое отношение к проблемам регистрации частиц в системах с так называемым «продлевающимся мертвым временем» [11,15,18-25]. Случайные потоки событий являются непременной частью экспериментальных исследований по определению характеристик излучения и его взаимодействия с веществом в оптике, квантовой электронике, астрофизике, ядерной физике и т.д. Современная регистрирующая аппаратура позволяет разрешать импульсы во времени с точностью порядка 10"|2с, что позволяет вести анализ, считая отдельные фотоны или фотоэлектроны [1]. Именно в таких быстродействующих устройствах и может проявляться эффект мертвого времени, который заключается в том, что после регистрации одного фотона или частицы система некоторое время не реагирует на другие частицы. С этим же эффектом приходится сталкиваться и при изучении биологических систем, например, нейронных сетей, так как в этом случае период занятости соответствует тому времени, в течение которого регистрирующий прибор не реагирует на поступающие внешние воздействия. Поэтому знание характеристик периода занятости не только позволяет оценить возможности регистрирующей аппаратуры, но и построить оценки интенсивности потока поступающих на прибор частиц по наблюдениям над началами периодов занятости. Исследованиям в этом направлении посвящены работы Е.В. Глуховой и А.С. Шкуркина, непосредственным продолжением которых является и настоящая работа.

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

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

Методика исследования

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

Научные результаты, выносимые на защиту.

Во всех рассмотренных системах входящий поток заявок является дважды стохастическим синхронным потоком с двумя состояниями интенсивности A,j и Х2. Переходы между этими состояниями возможны только в момент наступления нового события. Если поток находится в состоянии А,,, то вероятность перехода Х{ —> Х2 равна al5 а вероятность остаться в том же состоянии 1-aj. Если поток находится в состоянии Х2, то вероятность перехода

Х2 —> Х{ равна а2, а вероятность остаться в том же состоянии 1 - а2.

Автор выносит на защиту следующие научные результаты:

1. Для однолинейной СМО с бесконечным бункером и экспоненциальным распределением времени обслуживания найдены: а) условные средние длительности периода занятости Щ и т2, при ус* ловии, что в момент начала периода занятости интенсивность потока Х = Х-п / = 1,2; б) финальные вероятности тс,- того, что период занятости начнется при значении интенсивности Х = Х{; js в) условные (при условии, что интенсивность потока равна Х{) стационарные плотности вероятностей 7r,(w) и л2 (vv) незавершенной работы, а также безусловная плотность вероятностей незавершенной работы.

2. Для однолинейной СМО с вытеснением заявки, находящейся на об* служивании при произвольном распределении времени обслуживания найдены а) условные средние длительности тх и Тп2 периода занятости системы при условии, что в момент начала периода занятости интенсивность потока была равна Xt, / = 1,2; б) финальные вероятности п{ и п2 того, что период занятости начнется с состояния интенсивности потока Х = Х{, / = 1,2, и безусловную среднюю длительность периода занятости; в) условные плотности вероятностей 7i,(w) и n2(w) незавершенной работы w при условии, что интенсивность потока X = Xh / = 1,2, и безусловную плотность вероятностей 7t(w) незавершенной работы. И

3. Для бесконечнолинейной СМО с экспоненциальным распределением времени обслуживания найдены математическое ожидание и дисперсия числа заявок в системе; функция корреляции числа заявок.

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

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

Практическая ценность

Разработанные алгоритмы реализованы в виде программы в системе Delphi 6.0. Они могут быть использованы при расчете характеристик проектируемых СМО. Результаты работы включены в спецкурс «Системы массового обслуживания», читаемого студентам факультета математики и информатики филиала Кемеровского государственного университета в г. Анжеро-Судженске.

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

Во всех главах входящий поток заявок представляет собой дважды стохастический пуассоновский поток событий с двумя состояниями интенсивности — и Х2. Термин «пуассоновский» означает, что при фиксированном значении интенсивности поток заявок является пуассоновским с соответствующей интенсивностью. В дальнейшем для определенности будем считать, что A,t > Х2 • Переходы между этими состояниями возможны только в момент наступления нового события. Если поток находится в состоянии то вероятность перехода —> Х2 равна а15 а вероятность остаться в том же состоянии 1 —а!. Если поток находится в состоянии Х2, то вероятность перехода Х2 равна а2, а вероятность остаться в том же состоянии 1-а2.Время обслуживания в главах 1, 3 предполагается распределенным по экспоненциальному закону с интенсивностью jli .

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

Обозначим через m^w), / = 1,2 среднее время до опустошения системы, если в момент времени t она находится в состоянии i. В работе показывается, что эти величины удовлетворяют системе уравнений

00 m[(w) = l-A,1/w1(w) + X,1a1 Jm2(w+x)p(x)dx + о

00 X, (1 - a!) Jwj (w+x)p{x)dx, о

00 m2 (w) = 1 - X2m2 (w) + X2a2 Jml (w+x)p(x)dx + о oo X2 (1 - a2 ) Jm2 (w+jc) p(x)dx, о с граничными условиями m^O) = m2(0) = 0, где p(x) - плотность вероятностей работы которую несет заявка.

В работе найдено явное решение этой системы, которое не выписано здесь из-за его громоздкости. Для величин условной средней длительности периода занятости при условии, что в момент времени t система находится в состоянии i

00 т;= Jm, (w) • ц ехр(-ц-уу) Jw получены более простые выражения тх = т2 =

14

14 zO 4- 2 - А,16)(^1а1 4- X2a2)zQ z9 + 2-A,28)(^1a1 4-X2a2)z0 ^а, (1 - Я-20) 4- Я,2а2 (1 - ^0) 0 z04-1)(z04-1-?i20)' 0 z0 4- l)(z0 4-1 - A,t0)' где z — положительный корень характеристического уравнения z392 - z20(A,,9 + X2Q - 2)+ z( 1 - A-^Ca! 4-1) -Л.20(а2 4-1) 4- A.,^©2) --^a^l-A^-^a^l-X^) = 0.

К сожалению, единственность этого корня доказать не удалось, однако, в работе указано достаточное условие, при котором этот корень будет единственным. При выполнении условия а2(1-/1) + а1(1-/2)>0, которое является условием работоспособности системы (в противном случае система будет перегружена, и в ней не будет существовать стационарного режима), и а{ 4- а2 < 1, положительный корень этого уравнения единственный.

Для нахождения безусловной средней длительности периода занятости надо найти финальные вероятности л,-, i = 1,2 того, что период занятости начнется при значении интенсивности X = Xt. Громоздкими вычислениями показано, что эти величины имеют вид

71,= (1 -ах)(к- 1)/С + а2{\-кК) (1 - Z£)(l - к + а,к 4- а2к) а1(к-К) + (1-а2)(1-к) (1 - /Q(l - к + а{к + а2к) ' где к: - корень уравнения к3/^(1 - а, - а2 )+ к2 + /2а2 - (/t + /2 + /t/2)) + к(1{ + /2 +1) -1 = О, лежащий на отрезке (0, 1). Показано, что этот корень единственный. Теперь можно найти и безусловную среднюю длительность периода занятости Ш = щЩ + 7r2w2.

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

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

Обозначим через mi (w) среднее время до окончания периода занятости, если в момент времени t интенсивность потока Х = Х( и остаточное время обслуживания заявки, находящейся на приборе, если она не будет вытеснена другой заявкой, равно w. Другими словами, w есть незавершенная работа заявки, находящейся на обслуживании. Рассматривая переходы между состояниями системы за интервал времени At, получены следующие уравнения т[ (w) + Xj/WJ (w) = 1 + (1 - at )Xlmx + a{Xlm2, m'2(w) + A.2mi(w) = 1 + (1 — a2)A,2m2 + a 2Х2Щ, ao ml (o) = m2(0) = 0.

Решение этой системы дает следующий результат

Тогда условные средние значения длительности периода занятости имеют вид

МФ1Ф2 ~Ф| -азф^-Ячадфг

ГП\ —

1 ^А,2(ф2 - а2ф2 + ф! - ф!ф2 + а2ф!ф2 - а^! + а^срг -1)' (Ф1Ф2 - Ф2 -а^Фг)~^2а2Ф|Ф2 т2 = гСФг - а2Фг + Ф1 ~ Ф1Ф2 + а2Ф1Ф2 - + ЗДФ2 -1) се где (т)А. о

Для нахождения безусловной средней длительности периода занятости надо найти вероятности, i -1,2 того, что период занятости начинается со значения Х = Х-,.

Обозначим через Py{w) вероятность того, что период занятости закончится при значении интенсивности X = Xj при условии, что в момент t интенсивность X — Xi и незавершенная работа заявки, находящейся на обслуживании, была w. Уравнения для них имеют вид (приводится лишь два из четырех уравнений)

P{x{w) + X{Pn(w) = (1 - + a^i,

Р210) + X2P2l(w) = (1 - а2)Х2Р21 + а2Х2Рп,

00 где Pjj = J/^(x)/?(x)

Р21(0) = 0.

Решение этой системы имеет вид

Pu(w) = ((I - a,)PU + а,Р21 )(l - e~x*w)+ ,

P2l (w) = (1 - a2 )P2l + a2Pn (l -

Окончательно

Wi (Ф2 ~ Ф2а2 ~ О

Рц = ф2 - ф2а2 + ф, - ф!ф2 + ф!ф2а2 - ф^, + ф^а, -1)

Г21 ф2 - ф2а2 + ф1 - ф,ф2 + ф!ф2а2 - ф^! + ф,ф2а! -1)'

16 где cpf = |ф/(х)р(т)Л, i|/1(w) = e vjJ2(w) = e XiW, \|/f = jy i(T)p(i)ch. о о

Обозначим через q(j вероятность того, что период простоя системы закончится при значении интенсивности X = Xj, если он начался при значении интенсивности Х = Х(. Тогда

012=Ctl> 011 =1а1' 022 021 =а2

Теперь можно вычислить величины Гу = Pnqij + //202у и найти финальные вероятности я,-того, что период занятости начнется при значении интенсивности Х{:

7Гj =-—-, 7Г2 =-—-, т = ЩГПХ + 7t2m2 . rI2+r21 Г12+Г21

Разумеется, все эти вычисления можно проделать лишь численно на ЭВМ при конкретизации вида р{т).

В последнем параграфе этой главы находится стационарная плотность вероятностей 7t(w) незавершенной работы w. Обозначим ti; (w), / = 1,2 стационарную плотность вероятностей незавершенной работы w при условии, что интенсивность входящего потока равна Xt. Тогда вычисления дают

00

7i,(w) = ((l-a1)^i +a2X2)ex*w Jр{Хух*х dx, w

00 тг2(w) = ((1 - a2)X2 + a,^ )eXiW Jp(jc)e"^ dx. w

Безусловную плотность вероятностей 7t(w) незавершенной работы w можно записать в виде = a2^27ti(w)+a1^17r2(w) 0С|А.| + ct2X2 ft

17

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

Пусть 71/** есть финальная вероятность того, что в системе находится на обслуживании i заявок и интенсивность потока Система уравнений для имеет вид

-А^+ЦЯ^О, -А^тг^ + цтг^ =0,

- + /»7Г,(1) + (/ + 1)я£\ = 0, / =

А.2*2*м + - (Х2 + /ц)71р> + (i + 1)я£{ = 0, / = 1, со.

Для решения этой системы переходим к производящим функциям

Pk = А" = 1,2. о

Тогда система уравнений для них принимает вид r-l)(P,'(z)-/1P1(z)) + z(^/1PI(z)-ip2/2P2(z)) = 0, (z -1 )(Р2' (z) - /2 Р2 (г))+z(p2l2 Р2 (z) - рх1, Рх (z)) = 0, где /,•

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

Финальные вероятности состояния потока в стационарном режиме р М п РА

К, —-----— , К-у —--

М + Рг1г ' РА + Рг12 ' где введены безразмерные величины /, = А^/ц, / = 1,2.

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

P\h + Pih

Дисперсия числа заявок в системе

RXR2((/|-/2)(/I-/) , (/2-/,)(/2-/)Л

2 V hP\ hPi где l = lxRx+l2R2

В работе проведен непосредственный расчет характеристик системы. Пусть /(/) есть число заявок, находящихся в системе в момент времени t. Рассмотрим процессы ik (/) = i{t)Pk (t), к = \,2, где предполагается, что в момент времени t интенсивность потока равна Хк. Обозначим mk(t) = M{ik(t)}. Для mK(t) получена система дифференциальных уравнений m[{t) = XxPx(t)~ цтх (/) - Xxpxmx (/) + X2p2m2 (t), m2 (0 = X2P2 (t) - \un2 (/) - X2p2m2 (/) + Xxpxmx {t). Обозначая lim mk (t) = mk получается oo w l\l2Pi(l + l2(P\+ Рг)) tfl\ —

1 (AA + hPi)^ + hP\ + liPi) ' m hhPx^ + hiPx + Pi))

2 (hPx+hPiW + hPx+liPi)

Среднее число заявок, находящихся в системе в стационарном режиме

M{i(t)} = тх + т2 = hPi+kPi

Для расчета дисперсии числа заявок в системе в стационарном режиме Л рассмотрим процесс i2k(t) = i (t)Pk(t), £ = 1,2; его математическое ожидание будем обозначать как m2k (t). Для т2к (/) получена система уравнений

2 + lxpx)m2x-l2p2m22 = (1 + 21 х)тх + /,Rx, ~hP\m2\ + (2 + llPl )т22 = 0 + 2h)m2 + hR 2» где limmlk{t) = m2k. t-> oo

Явное выражение для m2k(t)не выписано из-за громоздкости. Заметим Л лишь, что т2Х + т22 = M{i }. Откуда можно получить выражение для D{i}. Для процесса /(/) найдена функция корреляции.

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

2, если X(t) = X2

Обозначим P{i{t) = i,k{t)-k) = Pk(i,t). Опишем систему в случае больших нагрузок. Рассмотрим случай, когда интенсивность обслуживания р мала, точнее, асимптотика получится в предположении, что р. —» 0.

Л Л

Обозначим р = е , \x.t = 8 t = т. Перейдем от процесса i(t) к процессу е2/ = pi = jc(t) + sу, где jc(x) — некоторый детерминированный процесс, а у — случайная добавка. Кроме этого, введем функцию т1к(у,туг) = Pk(i,t)/s и будем считать ее непрерывной дифференцируемой функцией. Для пк(у,т,е) получена система уравнений: от ду Xxq{(у - е, т, s) + О(т) + е(у + е))7Г! (у + 8, т, s) + Х2р2п2 (у - s, т, е), от ду X2q2TZ2 (у - 8, Т, 8) + (х(х) + 8(у + 8))7Г2 (у + 8, X, s) + Xlp{Kl {у ~ 8, X, S).

Асимптотическое исследование проведено в три этапа.

Первый этап. Обозначим кк{у,т) = limnk(y,х,е) и перейдем к пределу

->0 s —» 0. Тогда получим соотношение между щ(у,т) и п2(у,х):

СУ» т) = "Ь-гРгЪг СУ»т) •

Откуда можно записать лк(у,т) = Ркп(у,т), к = 1,2, 20 где Rk финальные вероятности состояний потока.

Этап 2. На этом этапе в системе для 7Га0>,х,е) оставим лишь слагаемые со степенью г не выше первой. Тогда, показано, что этой системе удовлетворяет решение вида: л / ч пк (,у, х, е) = Rkn(y, х) + ehk —+ о(б) , ду где hk, к = 1,2 - некоторые константы.

Этап 3. На этом этапе рассмотрим слагаемые, содержащие е2. Введем функцию п(у, х, е) = тс j (у, х, s) + тг2 (у, х, е). А, — X

И обозначив ст = Л, + 2(Л.г -А,2)—11-, громоздкими преобразованиями

Ххрх получим, что уравнение для 7t(jy,x) можно записать

Мул) = д(ук{у,х)) 1 f jd2Tt(.y,x) ах ^ 211; ' ду2 '

Из него следует, что процесс у(х) является диффузионным случайным процессом, описываемым следующим стохастическим дифференциальным уравнением dy(x) = -y{x)dx + ~Jx(t) + adw{i). Таким образом, процесс z(x) = jc(x) + sy(x) = (i/ при больших загрузках удовлетворяет следующему стохастическому дифференциальному уравнению dz(%) = (Х- z(x)) dx + л]\1{г{т) + a)dw(x) и является диффузионным случайным процессом.

Пусть H(z) и есть стационарная плотность вероятностей значений процесса z(x). Тогда после некоторых преобразований найден явный вид H(z)

H(z)= 2

ЦГ(У)

2z + a Ц ) у-1 ехр

И )

Далее в работе рассмотрен вопрос о периоде занятости рассматриваемой СМО. Точное решение задачи найти не удалось, поэтому эта проблема исследована в случае больших загрузок.

Пусть T(z) есть время до полного опустошения системы. Рассмотрим условную характеристическую функцию g{z,s) = M{exp(-sr(z)) | z( т) = z). Тогда после громоздких преобразований найдено преобразование Лапласа от плотности вероятностей длительности периода занятости

I И V- )

А, + ст — z

V И dz у V- P-J

Найти обратное преобразование Лапласа от этой функции не удалось; поэтому найдена средняя длительность периода занятости

I 1 /

Т = - f(l-z)cM ехр

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

Публикации

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

1. Lezarev A., Terpugov A. Mean length of mass service system's employment period with arequest supplanting by double stochastic incoming flow //8-th Korea — Russia Internation Symposium on Science and Technology. V. 2. 2004. P. 153-155.

2. Глухова E.B., Лезарев A.B. Средняя длительность периода занятости системы массового обслуживания с вытеснением заявки при дважды стохастическом входящем потоке // Обработка данных и управление в сложных системах. Вып. 6 - Томск: Из-во Том. ун-та, 2004. С. 49-59.

3. Лезарев А.В., Глухова Е.В. Безусловная средняя длительность периода занятости в однолинейной СМО с дважды стохастическим синхронным входящим потоком // Материалы III Всероссийской научнопрактической конференции «Информационные технологии и математическое моделирование» - Томск: Изд-во Том. ун-та, 2004. Ч. 2. С. 25— 27.

4. Лезарев А.В., Глухова Е.В. Средняя длительность периода занятости системы массового обслуживания с вытеснением заявки при дважды

• стохастическом входящем потоке // Материалы III Всероссийской научно-практической конференции «Информационные технологии и математическое моделирование» - Томск: Изд-во Том. ун-та, 2004. Ч. 2. С. 28-30.

5. Змеев О.А., Лезарев А.В. Функциональные требования для систем имитационного моделирования систем массового обслуживания // Материалы Всероссийской научно-практической конференции «Информационные технологии и математическое моделирование» — Томск «Твердыня» 2002. С. 128-130.

6. Змеев О.А., Лезарев А.В. Шаблон объектного проектирования для реализации функциональности процесса моделирования в имитационных моделях систем массового обслуживания // Вестник Томского государственного университета, серия «Математика. Кибернетика. Информатика», апрель 2002, №275. С. 108-111.

7. Капустин Е.В., Лезарев А.В. Имитационное моделирование работы страховых компаний // "Новые технологии и комплексные решения: наука, образование производство". Материалы всероссийской научно-практической конференции. Часть VI. (Информатика). Тезисы докладов. г. Анжеро-Судженск. 2001. №2. С. 35-37.

8. Капустин Е.В., Лезарев А.В. Расчет характеристик бесконечно линейной системы массового обслуживания при дважды стохастическом входящем потоке // Известия высших учебных заведений. Физика. Том 47, 2004. № 2. С. 35-38.

9. Лезарев Ф.В., Терпугов А.Ф. Средняя длительность периода занятости в однолинейной системе массового обслуживания с дважды стохастическим синхронным входящим потоком // Вестник Томского государственного университета, серия «Математика. Кибернетика. Информатика», декабрь 2004, № 280. С. 151-154.

Ю.Глухова Е.В., Лезарев А.В. Расчет характеристик бесконечнолинейной системы массового обслуживания при дважды стохастическом синхронном входящем потоке // Обработка данных и управление в сложных системах. Вып. 7 — Томск: Из-во Том. ун-та, 2005. С. 62-80.

Апробация работы

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

1. Всероссийской научно-практической конференции «Новые технологии и комплексные решения: наука, образование производство» Анжеро-Судженск, 2001 г.

2. Всероссийской научно-практической конференции «Информационные технологии и математическое моделирование» Анжеро-Судженск, 2002 г.

3. 8-th Korea - Russia Internation Symposium on Science and Technology. 2004.

4. Ill Всероссийской научно-практической конференции «Информационные технологии и математическое моделирование». 2004 г.

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Лезарев, Александр Викторович

ЗАКЛЮЧЕНИЕ

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

1. Рассматривается входящий поток событий, который условно называется дважды стохастическим синхронным пуассоновским потоком событий с двумя состояниями интенсивности — и Х2. Термин «пуассоновский» означает, что при фиксированном значении интенсивности поток заявок является пуассоновским с соответствующей интенсивностью. Для определенности считается, что А,] >Х2. Переходы между этими состояниями возможны в моменты прихода новых заявок.

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

Для первой и третьей систем обслуживание считается экспоненциальным, для второй системы - рекуррентным.

3. Для однолинейная СМО с бесконечным буфером и СМО с вытеснением заявки, находящейся на обслуживании найдены основные характеристики периода занятости, а именно: а) условные математические ожидания длительности периода занятости; б) финальные вероятности того, что период занятости начнется при том или ином значении интенсивности; в) безусловное математическое ожидание длительности периода занятости; г) плотности вероятностей незавершенной работы (для систем а) и в) ) и плотность вероятностей максимального остаточного времени обслуживания (для системы б) ).

4.Дпя бесконечнолинейной СМО найдены а) математическое ожидание и дисперсия числа заявок в системе; б) функция корреляции числа заявок.

Проведен асимптотический анализ изучаемой системы при больших загрузках и показано, что число заявок в системе может быть аппроксимировано диффузионным случайным процессом. Найдены в) коэффициенты сноса и диффузии этого процесса; г) асимптотическая плотность вероятностей для числа заявок в системе; д) преобразование Лапласа от плотности вероятностей периода занятости изучаемой системы; е) средняя длительность периода занятости.

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

Список литературы диссертационного исследования кандидат технических наук Лезарев, Александр Викторович, 2005 год

1. Апанасович В.В., Коляда А.А., Чернявский А.Ф. Статистический анализ случайных потоков в физическом эксперименте. — Минск: «Университетское», 1988. — 254 с.t

2. Архангельский А.Я. Разработка прикладных программ для Windows в Delphi 5. М.: ЗАО "Издательство БИНОМ", 1999. - 256 с.

3. Бейтмен Г., Эрдейи А. Таблицы интегральных преобразований. Т.1. — М.: Наука, 1969.-343 с.

4. Бейтмен Г., Эрдейи А. Высшие трансцендентные функции. Гипергеометрическая функция. Функция Лежандра. М.: Наука, 1965. — 294 с.

5. Бертсекас Д., Галлагер Р. Сети передачи данных. — М.: Мир, 1989. -542 с.

6. Большаков И.А., Раношиц B.C. Прикладная теория случайных потоков. М.: Сов. радио, 1978. - 248 с.

7. Бочаров П.П., Печинкин А.В. Теория массового обслуживания. — М.: УДН, 1995.-529 с.

8. Буч Г., Рамбо Д., Джекобсон А. «Язык UML. Руководство пользователя». М.: ДМК, 2000. - 432 с.

9. Васильева Л.А., Горцев A.M. Оценивание длительности мертвого времени асинхронного дважды стохастического потока событий в условиях его неполной наблюдаемости // Автоматика и телемеханика. — 2003. №12. С. 69-79.

10. Гихман И.И., Скороход А.В. Стохастические дифференциальные уравнения. Киев: Наукова думка, 1968. - 354 с.

11. Глухова Е.В. Оценка параметров мёртвого времени в биологических объектах // Информатика и процессы управления. Красноярск: КГТУ, 1996. С. 116-123.

12. Глухова Е.В., Орлов А.Б. Средняя длительность периода занятости в однолинейной СМО с дважды стохастическим входящим потоком // Статистическая обработка данных и управление в сложных системах. Вып. 3. Томск: Изд-во Том. ун-та, 2001. С. 26-34.

13. Глухова Е.В., Орлов А.Б. Безусловная средняя длительность периода занятости и простоя в однолинейной СМО с дважды стохастическим входящим потоком // Обработка данных и управление в сложных системах. Вып. 4. — Томск: Изд-во Том. ун-та, 2002. С. 25-32.

14. Глухова Е.В., Орлов А.Б. Средняя длительность периода занятости бесконечно линейной системы массового обслуживания с дважды стохастическим входящим потоком // Изв. вузов. Физика. 2003. №3. С. 62-68.

15. Глухова Е.В., Терпугов А.Ф. Модель мёртвого времени при наличии нескольких регистрирующих приборов // Изв. вузов. Физика. 1997. № 4. С. 50-56.

16. Глухова Е.В., Терпугов А.Ф. Оценка интенсивности пуассоновского потока событий при наличии продлевающегося мёртвого времени // Изв. вузов. Физика. 1995. № 3. С.22-31.

17. Глухова Е.В., Терпугов А.Ф. Оценки параметров пуассоновского потока событий при продлевающемся мёртвом времени // Радиотехника. 1995. №9. С.10—12.

18. Глухова Е.В., Шкуркин А.С. Оценка характеристик пуассоновского потока заявок по наблюдениям над периодом занятости в системе MIGIоо при экспоненциальном законе убывания незавершенной работы // Известия вузов. Физика, 2002. №5. С. 34-38.

19. Глухова Е.В., Шкуркин А.С. Расчет характеристик периода занятости в однолинейной СМО с вытеснением заявок //Вестник Томского государственного университета. Томск: Изд-во ТГУ, 2000. С.45-47.

20. Глухова Е.В., Шкуркин А.С. Расчет характеристик периода занятости в СМО с вытеснением заявок //Статистическая обработка данных и управление в сложных системах. Выпуск 2: Сборник статей. -Томск:

21. Изд-во ТГУ, 2000. С.56-69.

22. Гнеденко Б.В., Коваленко И.Н. Введение в теорию массового обслуживания. М.: «Наука», 1987. 336 с.

23. Горцев A.M., Бушланов И.В. Алгоритм оптимальной оценки состояний синхронного дважды стохастического потока событий // Вестник Томского гос. Ун-та. Приложение. 2003. №6. С. 220-224.

24. Горцев A.M., Катаева С.С. Оптимизация подключения резервного прибора в вычислительной системе с двумя ЭВМ // Техника средств связи. Серия «Системы связи». 1989. Вып. 7. С. 12-18.

25. Горцев A.M., Климов И.С. Оценка интенсивности пуассоновского потока событий в условиях частичной его ненаблюдаемости // Радиотехника- 1991. № 12. С. 3-7.

26. Горцев A.M., Нежельская JI.A. Оптимальная нелинейная фильтрация марковского потока событий с переключениями // Техника средств связи. Серия: Системы связи. 1989. Вып. 7. С. 46-54.

27. Горцев A.M., Нежельская JI.A. Оценка параметров синхронно-альтернирующего пуассоновского потока событий методом моментов // Радиотехника. 1995. №7-8. С. 6-10.

28. Горцев A.M., Нежельская JI.A., Шевченко Т.Н. Оценивание состояний МС-потока событий при наличии ошибок измерений //Известия вузов. Физика. 1993. №12. С. 67-85.

29. Горцев A.M., Катаева С.С. Оптимизация гистерезисной дисциплины обслуживания несимметричным резервным каналом //Известия вузов. Физика. 1996. № 4. С. 3-10.

30. Горцев A.M., Куснатдинов Р.Т. Оценивание состояний МС-потока событий при его частичной наблюдаемости //Известия вузов. Физика.1998. № 4. С. 22-29.

31. Горцев A.M., Паршина М.Е. Оценка параметров альтернирующего потока событий в условиях мертвого времени // Изв.вузов. Физика.1999. №4. С. 8-13.

32. Горцев A.M., Шмырин И.С. Оптимальная оценка состояний дважды стохастического потока событий при наличии ошибок в измерениях моментов времени // Автоматика и телемеханика. 1999. №1. С. 52-66.

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

34. Диткин В.А., Прудников А.П. Интегральное преобразование и операционное исчисление. М.: Наука, 1974. - 542 с.

35. Диткин В.А., Прудников А.П. Справочник по операционному исчислению. — М.: Высшая школа, 1965. 466 с.

36. Дудин А.Н., Клименок В.И. Расчет характеристик однолинейной системы обслуживания, функционирующей в Марковской синхронной случайной среде // Автоматика и телемеханика. 1997. № 1. С. 74-84.

37. Дудин А.Н., Клименок В.И. О системе обслуживания BMAPIGI1 с альтернирующим режимом функционирования // Автоматика и телемеханика. 1999. № 10. С. 97-107.

38. Дудин А.Н., Клименок В.И. Системы массового обслуживания с коррелированными потоками. Минск: Изд-во БГУ, 2000. 175 с.

39. Жожикашвили В.А., Вишневский В.М. Сети массового обслуживания. Теория и применения к сетям ЭВМ. М.: Радио и связь, 1988, 192 с.

40. Ивницкий В.А. Теория сетей массового обслуживания. -М.: Изд-во: "Физико-математическая литература" 2004 770 с.

41. Калашников В.В., Рачев С.Т. Математические методы построения стохастических моделей обслуживания. М.: Наука, 1988. - 310 с.

42. Карлин С. Основы теории случайных процессов. — М.: Мир, 1971. — 536 с.

43. Кац В.М., Лившиц К.И., Назаров А.А. Исследование нестационарных бесконечнолинейных систем массового обслуживания и их применение к анализу экономико-математических моделей // Вестник ТТУ. 2002. №275. С. 189-192.

44. Клейнрок JT. Коммуникационные сети: стохастические потоки и задержки сообщений. М.: Наука, 1970. - 256 с.

45. Клейнрок Л. Теория массового обслуживания. М.: Машинострое1. V ние, 1979. — 432 с.

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

47. Кокс Д. Р., Смит У. Л. Теория очередей: Пер. с англ. М.:Мир, 1966 -218 с.

48. V> 52. Лаврентьев М.А., Шабат Б.В. Методы теории функций комплексногопеременного. -М.: Наука, 1965. — 716 с.

49. Ларман К. «Применение UML и шаблонов проектирования. Введение в объектно-ориентированный анализ и проектирование». — М.: Вильяме, 2001.-496 с.

50. Матвеев, В.Ф.; Ушаков, В.Г. Системы массового обслуживания. М.:1. Изд-во МГУ 1984 г. 240 с.

51. Матвеев Н.М. Методы интегрирования обыкновенных дифференциальных уравнений. — М.: Высшая школа, 1963. — 348 с.4 56. Назаров А.А. Асимптотический анализ марковизируемых систем. —

52. Томск: Изд-во Том. ун-та, 1991. — 158 с.

53. Орлов А.Б. Расчет характеристик бесконечно линейной системы массового обслуживания с дважды стохастическим входящим потоком // Обработка данных и управление в сложных системах. Вып. 5. — Томск: Изд-во Том. ун-та, 2003. С. 150-157.

54. Орлов А.Б. Средняя длительность периода занятости системы массового обслуживания с вытеснением заявки при дважды стохастическом входящем потоке // Обработка данных и управление в сложных системах. Вып. 5. Томск: Изд-во Том. ун-та, 2003. С. 158-170.

55. Рыбко А.Н., Столяр А.Л. Об эргодичности случайных процессов, описывающих функционирование открытых сетей массового обслуживания // Проблемы передачи информации, 1992, Т. 28, вып. 2, с. 3-26.

56. Саати Т. Элементы теории массового обслуживания и ее приложения. М.: Сов. радио. 1971.-520 с.

57. Справочник по специальным функциям с формулами, графиками и математическими таблицами / Под редакцией М. Абрамовича, И. Стиган и др. М.: Наука, 1979. - 830 с.

58. Такач JI. Комбинаторные методы в теории случайных процессов. — М.: Мир, 1971.-263 с.

59. Тейксейра С., Пачеко К. Delphi 5. Руководство разработчика, том 1. -М.: Издательский дом «Вильяме», 2000. — 832 с.

60. Тейксейра С., Пачеко К. Delphi 5. Руководство разработчика, том 2. — М.: Издательский дом «Вильяме», 2000. — 992 с.

61. Тихоненко О.М. Модели массового обслуживания в информационных системах. — М.: Изд-во: "Технопринт" 2003. — 327 с.

62. Уолрэнд, Дж. Введение в теорию сетей массового обслуживания. — М.: Мир. 1993. 336 с.

63. Фомин Г.П. Системы и модели массового обслуживания в коммерческой деятельности. М.: Изд-во "Финансы и статистика" 2000. -144 с.

64. Хинчин А.Я. Работы по математической теории массового обслуживания. М.: Физматгиз, 1963. - 236 с.

65. Bremaud P. Point processes and queues. Springer Verlag, New York, 1981.-354 p.

66. Disney R.L., Farrell R.L. etc. A characterization of M/G/l queues with renewal departure process // Management Science. 1973. V.19.№ 11. P. 1222-1228.

67. Gnedenko B.V., Konig D. Handbuch der Bedienungstheorie. II. Formeln und andere Ergebnisse. 1984. 608 p.

68. Lucantoni D.M. New results on the single server queue with a batch mark-ovian arrival process // Communications in Statistics Stochastic Models. 1991. Vol. 7. P. 1-46.

69. Raftery A.E., Akman V.E. Bayesian analysis of a Poisson process with a change point//Biometrika.1986. V. 73. № 1. P. 85-89.

70. Snyder D.L. Filtering and Detection for Doubly Stochastic Poisson Processes // IEEE Trans. Inform Theory, 1972. V. 11-18. № 1. P. 91-102.

71. Snyder D.L. Random point processes. N.Y.: Join Wiley and Sons, 1975.-486p.

72. Srivasan S.K. Stochastic point processes and their application. London: Griffin, 1974.-174 p.

73. Takagi H. Queuing Analysis. Amsterdam: North Holland. V. 1. 1991. V.2. 1993. V.3. 1993.-1503 p.