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

На правах рукописи

Орлов Алексей Борисович

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

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

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

Анжеро-Судженск - 2003 г.

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

Научный руководитель:

Доктор технических наук, доцент Глухова Е.В.

Официальные оппоненты:

Доктор технических наук, профессор Горцев A.M. Кандидат технических наук Кузнецов Д. Ю.

Ведущая организация - НИИ Систем Управления, Волновых Процессов и Технологий Минобразования РФ.

Защита состоится 16 октября 2003 г. в 10 часов 30 минут на заседании Диссертационного Совета Д 212.267.08 при Томском государственном университете ( 634050, г. Томск, пр. Ленина, 36 ).

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

Отзывы на автореферат (в двух экземплярах, заверенных печатью) просьба высылать по адресу: 634050, г. Томск, пр. Ленина, 36, Томский государственный университет, ученому секретарю университета Буровой

Автореферат разослан " (0 " сентября 2003 г. Ученый секретарь

Диссертационного Совета Д 212.267.08 кандидат технических наук, доцент

Н.Ю.

А.В.Скворцов

| О АКТУАЛЬНОСТЬ

РАБОТЫ

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

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

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

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

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

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

альность.

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

ЦЕЛЬ РАБОТЫ

Целью данной работы являлось:

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

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

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

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

4. Финальные вероятности значения интенсивности в начале периода занятости и безусловную среднюю длительность периода занятости для следующих систем массового обслуживания (СМО):

а) однолинейной СМО с бесконечным бункером;

б) бесконечнолинейной СМО;

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

5. Разработать программное обеспечение для расчета всех этих характеристик, работающее под управлением операционных систем Windows 95/98/2000, Windows NT.

СОСТОЯНИЕ ПРОБЛЕМЫ

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

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

- рекуррентный входящий поток заявок и экспоненциальное распределение времени обслуживания;

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

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

С другой стороны, период занятости СМО имеет само прямое отношение к проблемам регистрации частиц в системах с так называемым «продлевающимся мертвым временем». Случайные потоки событий являются непременной частью экспериментальных исследований по определению характеристик излучения и его взаимодействия с веществом в оптике, квантовой электронике, астрофизике, ядерной физике и т.д. Современная регистрирующая аппаратура позволяет разрешать импульсы во времени с точностью порядка 10"12с, что позволяет вести анализ, считая отдельные фотоны или фотоэлектроны. Именно в таких быстродействующих устройствах и может проявляться эффект мертвого времени, который заключается в том, что после регистрации одного фотона или частицы система некоторое время не реагирует на другие частицы. С этим же эффектом приходится сталкиваться и при изучении биологических систем, например, нейронных сетей, так как в этом случае период занятости соответствует тому времени' в течение которого регистрирующий прибор не реагирует на поступающие внешние воздействия. Поэтому знание характеристик периода занятости не только позволяет оценить возможности регистрирующей аппаратуры, но и построить оценки интенсивности потока поступающих на прибор частиц по наблюдениям над началами периодов занятости. Исследованиям в этом направлении посвящены работы Е.В. Глуховой и A.C. Шкуркина, непосредственным продолжением которых является и настоящая работа.

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

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

ОСНОВНЫЕ НАУЧНЫЕ ПОЛОЖЕНИЯ, полученные автором и выносимые им на защиту, следующие:

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

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

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

а) условные средние длительности периода занятости щ и т2, при условии, что в момент начала периода занятости интенсивность потока X = Xt, i = l,2;

б) финальные вероятности я,- того, что период занятости начнется при значении интенсивности X = Xf;

в) условные (при условии, что интенсивность потока равна Xt) стационарные плотности вероятностей tc,(w) и tc2(w) незавершенной работы, а также безусловная плотность вероятностей незавершенной работы.

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

а) безусловная производящая функция для числа заявок в системе; финальные вероятности для числа заявок в системе, в частности, вероятность того, что система пуста; среднее число заявок и дисперсия числа заявок, находящихся в системе;

б) условные средние длительности ^(w) и m2(w) до опустошения

системы при условии, что в начальный момент времени X = Xt, i = 1,2, и максимальное остаточное время обслуживания равно w;

в) условные средние длительности щ, / = 1,2 периода занятости

системы при условии, что период занятости начинается со значения интенсивности k = Xj",

г) финальные вероятности я,, i =1,2 того, что период занятости начнется с интенсивности X,-, и безусловная средняя длительность периода занятости;

д) плотность вероятностей максимального остаточного времени в стационарном режиме.

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

а) условные средние длительностл щ и т2 периода занятости системы при условии, что в момент тачала периода занятости интенсивность потока была равна А,,-, i = 1,2;

б) финальные вероятности jcj и п2 того, что период занятости начнется с состояния интенсивности потока X = , i = 1,2, и безусловную среднюю длительность периода занятости;

в) условные плотности вероятностей %(w) и n2(w) незавершенной

работы w при условии, что интенсивность потока X = i = 1,2, и безусловную плотность вероятностей 7t(w) незавершенной работы.

МЕТОДИКА ИССЛЕДОВАНИЙ

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

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

так называемый синхронный дважды стохастический поток заявок.

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

РЕАЛИЗАЦИЯ И ВНЕДРЕНИЕ ПОЛУЧЕННЫХ РЕЗУЛЬТАТОВ

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

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

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

Во всех главах входящий поток заявок представляет собой дважды стохастический пуассоновский поток событий с двумя состояниями интенсивности — Х,| и Х2. Термин «пуассоновский» означает, что при фиксированном значении интенсивности поток заявок является пуассонов-ским с соответствующей интенсивностью. В дальнейшем для определенности будем считать, что X, > Х2 • Между этими состояниями возможны переходы, которые образуют дискретный марковский процесс с непрерывным временем. Интенсивность перехода ^ Х2 мы будем обозначать как dj, интенсивность перехода Х2 —> как а2. Время обслуживания в главах 1-3 предполагается распределенным по экспоненциальному закону с интенсивностью ц.

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

Обозначим через ^¡¡(w), i-1,2 среднее время до опустошения системы, если в момент времени t она находится в состоянии i. Тогда в работе показывается, что эти величины удовлетворяют системе уравнений

т[ (и1) = 1- (Я.г+а, )от, (и>) + а1т2(и') +X] (м>+х) р(х)еЬс,

о

ао

т'2(-п>) = 1-(Х2 +а2)т2(■*>) + а2т1 (и/) + к2 ^тг{\»+х)р{х)йх,

о

с граничивши условиями от, (0) = т2 (0) = 0.

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

а>

о

получены более простые выражения

е

1Й2 :

1 , (Д1

а1(1-/2)+а2(1-/,)] 1 , (Д1+а2)^

1 + 2-11 е

1 + г-/2

где 1к=Хк/\1, а^ , 0 = 1/ц. Что касается г, то это - положитель-

ный корень характеристического уравнения

I3 -22(/, +/2 +а, +а2 -2)+г[(/, +а, -1)(/2 +а2 -1)-йг, -а2-а,а2]~ -[а1(1-/2) + а2(1-/1)]=0. В работе показано, что при выполнении условия а2(1-/1)+а1(1-/2)>0, которое является условием работоспособности системы (в противном случае система будет перегружена, и в ней не будет существовать стационарного режима), положительный корень этого уравнения единственный.

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

я .:/2Д|(К-*)+/2(4+Д|Х1-10 1 (1-ад20-к)+«,/2+а2/,)'

2 (1-ВД2(1-К) + а,/2+а2/,) ' где к - корень уравнения

/,/2к3 - к2 (/t/2 + /2л, + /,а2 + аха2) + к(/, + /2 + аг + а2 +1) -1 = 0, лежащий на отрезке (0, 1). Показано, что этот корень единственный. Теперь можно найти и безусловную среднюю длительность периода занятости т = щт1 + п2т2.

В работе найдены также характеристики простоя системы. Они следующие:

1. Пусть qy есть вероятности того, что период простоя закончится при значении интенсивности Xj пир условии, что он начался при значении интенсивности Xt. Тогда

/l(/2+az) , q2l(0)=-^-,

hl2 +ha 2 +l2al hl2 + lla2 +hai

2. Пусть mi, i = 1,2, есть среднее время простоя системы, если в начальный момент поток находился в состоянии X,. Тогда

ах12 + а21{ + /,/2 aj2 + а211 + /,/2

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

Во второй главе находятся финальные вероятности состояний бесконечнолинейной СМО. Пусть есть финальная вероятность того,

что в системе находится на обслуживании / заявок и интенсивность потока Х = Хк. В безразмерных величинах lk-=Xk/\i, ак =akj\i система

уравнений для имеет вид

-(/]+а1)я(о1)+т1« + аУ02)=0, /,*?> - (/, + а, + + (I + Vfnf + а2 яР> = О,

*2яы ~ (12 +аг+ г>/2) + (г + 1)тср> + ахп{Р = О, 10

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

ВД = 1У*<*\ ¿ = 1,2.

1=0

Тогда система уравнений для них принимает вид

РШ\ - г) + Р, (*)(/, (г-1)-а,) + а2Р2(2)= 0, РЦт - 2)+Р2(Х)(12(2 -1)- а2) + 01р,(2) - 0.

В работе находится явное выражение для производящих функций:

/»,(г) = ———Ф(а1 Д + в, + а2;(12 -/,Х* - П)^, а, +а2

а1 +а2

где Ф(а,с\2) есть вырожденная гипергеометрическая функция. Отсюда находится явный вид финальных вероятностей

--ф(Я] +а2 +1 + ^;/, -12),

(01 + <*2 +1). (Д2).

а\+а2 ,-0

-Ф(а2+я)а1+а2+1 + 5;/2-/1).

(йГ[ + а2 +1)5

В частности, вероятность того, что система пуста

я0 =———Ф(а, Д+а, +а2;/1-/2)е~'1+———Ф(а2,1+а, +й2;/2-/^е"'2, ^ +а2 а!+а2

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

А/{г| = /У(1) + Р2'(1) = + , а,+а2

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

В третьей главе находятся характеристики периода занятости бес-конечнолинейной СМО. Основой для исследования является использова-

/

1 1

Л

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

Обозначим через тк(уу) среднее время до опустошения системы, если в начальный момент времени I интенсивность потока была Хк и максимальное остаточное время обслуживания на занятых приборах было равно м>. Тогда, рассматривая переходы за интервал времени Л?, можно получить интегро-дифференциальное уравнение

(X,! + а, ^(м^!+а,т2(м')+>4(1 - е~ми,)т,(м/)+

аз

И'

и аналогичное уравнение для т1(м>). Их можно свести к системе дифференциальных уравнений

т1"(и')+(а1 +>., е"ци')т,'(н')= а,«^), т^)+(а2 +Х2 е~|1н')»г2(и')=а2т{(>е).

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

00

т,(0)=0, 1шгт[(и>)=1, /и,'(о)=1+Я, |т,(т)^е"мт</т, »->00 *

О

и аналогичные условия для т2{у/) .

Достаточно громоздкое исследование дает следующий результат

«,(*)=]ф(-в, 4-в, ~а2;(12 - 1Х)е~'")ехр(/1 е-*" + о

+ С2)ф(а2,1 + а1 +а2;(12 -^У^^-схр^ ,

0

где

1

1 + А |ф(-а,,1-а,-а2;(12-1у)г)^г<12-ф{-ау,\-а1 -а2,12 -/,)

с, --^-

2 1 '

ф{а2,\ + а1+а2,12 - |ф(я2,1 + а, +а2;(12 е'1* (Ь

о

и аналогичную формулу для т2(>у).

Так как период занятости начинается с прихода заявки в пустую систему, то в начале периода занятости IV имеет то же самое распределение, что и т, то есть р(н>) = цехр(-ц™). Тогда, усредняя по »V, получим следующее выражение для условной (при условии, что период занятости начинается при значении интенсивности X = Х1) средней длительности периода занятости

1 1 ' 1

Щ = ---|Ф(~ а1?1 - - а2;/2 -/,)+ С2Ф(а2,1 + ах+а2,12-1х )е'' -1], ц

и аналогичное выражение для т2.

Для усреднения по значению интенсивности X в начале периода занятости надо знать величины л,, I = 1,2, которые есть вероятности того, что период занятости начнется при значении интенсивности X,. Они рассчитываются достаточно сложно и в два этапа.

Обозначим через вероятность того, что опустошение систе-

мы произойдет при значении интенсивности Х = Х^ при условии, что в данный момент времени интенсивности потока Л. была равна Х1, и максимальное остаточное время обслуживания было равно ю. Тогда можно показать, что уравнение, скажем, для Рп(н-), имеет вид

Достаточно громоздкое исследование дает такой результат

ф(а2,1 + ах+а2;(/2 -Ое^хр^е"^,

о

г __ а1_

С2----.

ф(а2,1+а! +с2;/2 — /, )еЛ—/1 ^^'Ф^Дн-а, +в2;(/2 <Ь

о

Обозначим через Ру вероятность того, что в конце периода занятости будет X = X • при условии, что в начале периода занятости Х = Х(. Так как период занятости начинается с прихода первой заявки, для которой

13

Р(м)=це , то, усредняя по и», получим

)

р__о_

- 1

ф(а2,1 + а, +а2;12 -/,)е/1-/, ^"'"^Ф^Д + а, + а2;(/2 -¡¡)г)е1'2 йг

о

Аналогичные выражения имеют место и для остальных .

Обозначим через д^ вероятность того, что период простоя закончится при значении интенсивности X-Xj, если он начался при значении интенсивности А, = X,. Они имеют тот же вид, что и в главе !. Как и в главе 1, теперь можно вычислить величины Гу = Р^^ + Рац1} и найти финальные вероятности л,- того, что период занятости начнется при значении интенсивности Х1:

г2\ г\2 Щ=-, Л2=-,

г12+г21 г12+г21 что и дает возможность вычислить безусловную среднюю длительность периода занятости т = я, ■ щ + п2 ■ т2.

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

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

Обозначим через среднее время до окончания периода заня-

тости, если в момент времени / интенсивность потока X = Х1 и остаточное время обслуживания заявки, находящейся на приборе, если она не

14

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

т'2 (и>)+(я2 + а 2 )от2 М -о-2т\ С147)=1 + Х2т2,

®

где Ш; = |т,(т)р(тУт. Эт;, систему надо решить при граничных условиях о

/и,(0)=т2(0)=0.

Для решения системы переходим к преобразованию Лапласа

со

/я, (у)= |/я1-(и')е " '¿м>. Тогда эта система приобретает вид

о

5 т2 (д)+(Х2 + а2 )т2 (») - а2т! (»)=—.

Достаточно громоздкое решение этой системы дает следующий результат Щ (м>) = (1+Х1щ )ф, ,(м»)+(1 + Х2т2 )ф12(м>),

т2 М = 0 + )ф22 (И')+ (1 + КЩ )ф21 6")

Из входящих сюда функций <ру(ы) приведем для примера только одну; все остальные выписаны явно в основном тексте.

где 2Х и г2 - корни уравнения

г2 -¿(Х, +Х2 +<*! + а2)+(Х|Х2 +а{Х2 + а2Х!)=0. Оба эти корня положительные.

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

_ Фп -ф]2 -Х2(ф12ф22 + ф12ф21 -Ф11Ф22 +Ф22Ф|г)

_ 1-Х1Ф11 -Х2Ф22 +Х^Х2^иФ22 -ф,2ф2,)_

„ - Ф22 -Ф21 -^(Ф^ФИ +Ф21Ф12 -Ф22Ф11 +Ф11Ф21)

пг2--—-—-._ __————г-,

1-Х^, -Х2ф22 +Х,Х2\ФлФ22 "Ф12Ф21/ 15

т, =-

оо

где фу = |ф,у(т)/>(т)£/т.

о

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

Обозначим через Ру{м) вероятность того, что период занятости закончится при значении интенсивности X = Xj при условии, что в момент / интенсивность Х = Х1 и незавершенная работа заявки, находящейся на обслуживании, была м?. Уравнения для них имеют вид (приводится лишь два из четырех уравнений)

Р1М+(Х2 +а2)Р21(к)-а2РМ=Х2Р21,

да

где Рц = ^Ру{т)р{х)с1х. Их надо решить при граничных условиях ] (о)=1, о

Р21(0)=0.

Достаточно громоздкое решение с использованием преобразования Лапласа дает

Р21{п) = Х2Р2&22{ъ)+ >ь,/>1ф21(>у)+(р2(н'), где фу(и') те же, что и ранее, а функции фДи») имеют вид

ф1 з- ^2+а2~ Ч с-2,*> ^2 + "2 ~ г2 е-га№ 22 22~ 21

Фг М - —~— --— е-12"1.

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

р Ф10-^2Ф22)+Ф2'^2Ф12

-л2ф22 +А,,А,2(фпф22-Ф12Ф21)' р <Р2(1-^1Фп)+Ф|-^1Я»21

1-^Фп -^2Ф22 +^1^2(фцф22 -Ф12Ф21)'

со

где Ф, = /ф,-(ф(фх.

о

Нахождение величин я,- ведется так же, как и в главе 3. Находятся величины гц -РпЯ\] + РцЧу, и

пх =———, я2=———, т - + к2т2. r12+r21 г\2+г2\

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

В последнем параграфе этой главы находится с г." ионарная плотность вероятностей rt(vv) незавершенной работы w. Обозначим яДн»),

i = 1,2 стационарную плотность вероятностей незавершенной работы W при условии, что интенсивность входящего потока равна A,f. Тогда громоздкие вычисления дают

ф)= -^]p{xyiz dx-

Z2~Z\

Jz,-X2-a2)kl-X2a2 dx,

z2~zi ; и аналогичное выражение для n2(w). Безусловную плотность вероятностей re(w) незавершенной работы w можно записать в виде

а,+а2

В пятой главе диссертации описывается программное обеспечение д ля расчета полученных в работе характеристик. Программа разработана в системе Delphi 6.0 и работает под управлением операционных систем Windows 95/98/2000 или Windows NT. Программный продукт производит расчет характеристик полученных в главах 1-4 по вводимым параметрам рассмотренных СМО.

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

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

1. Глухова Е.В., Орлов А.Б. Средняя длительность периода занятости в однолинейной СМО с дважды стохастическим входящим потоком. //Статистическая обработка данных и управление в сложных системах.

Вып. 3. Томск: Изд-во Том. ун-та, 2001. С. 26-34.

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

3. Глухова Е.В., Орлов А.Б. Средняя длительность периода занятости бес-

конечно линейной системы массового обслуживания с дважды стохастическим входящим потоком. //Изв. вузов. Физика. 2003. №3. С. 62-68.

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

5. Орлов А.Б. Средняя длительность периода занятости системы массово-

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

1. Глухова Е.В., Орлов А.Б. Средняя длительность периода занятости в

однолинейной СМО с дважды стохастическим входящим потоком. //Вторая научно-практическая конференция «Наука и образование». Тезисы докладов. Белово: Филиал КемГУ в г. Белово, 2001. С. 294-296.

2. Глухова Е.Ь., Орлов А.Б. Расчет безусловной .редней длительности

периода занятости в однолинейной СМО с дважды стохастическим входящим потоком. //Новые технологии и комплексные решения: наука, образование, производство. Материал Всероссийской научно-практической конференции. Ч. II. КемГУ, 2001. С. 10-12.

3. Лыгач Е.В., Орлов А.Б., Холкин Д.В. Вычисление на ЭВМ характери-

стик однолинейной СМО, бесконечно линейной СМО, СМО с вытеснением заявки. //VII Межрегиональная научно-практическая конференция «Научное творчество молодежи». Томск, Издательство «Твер-

дыня», 2003. С. 100-102. Апробация работы

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

1. Межрегиональной научно-методической конференции «Повышение

эффективности научных исследований и совершенствование учебного процесса». Анжеро-Судженск 2000.

2. Второй научно-практической конференции «Наука и образование».

Белово, 2001.

3. Всероссийской научно-практической конференции «Новые технологии

и комплексные решения: наука, образование, производство». Кемерово, 2001.

4. Межрегиональной научно-практической конференции «Информацион-

ные технологии и математическое моделирование» Анжеро-Судженск, 2001.

5. Всероссийской научно-практической конференции «Информационные

технологии и математическое моделирование». Анжеро-Судженск, 2002.

6. VII Межрегиональной научно-практической конференции «Научное

творчество молодежи». Анжеро-Судженск, 2003.

»14170

2.о<РЗ -4 \4\JO

Заказ № 3 2-2, Тираж 100 экз. Формат 60x84

Подписано к печати £(. Р/ .03 Отпечатано на ризографе АСФ КемГУ 652470, г. Анжеро-Судженск, ул. Ленина, 8.

Введение

Глава 1. Средняя длительность периода занятости в однолинейной СМО с дважды стохастическим входящим потоком

1.1 Описание потока

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

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

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

1.5 Свойства корней характеристического уравнения

1.6 Нахождение и В

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

1.8 Среднее время простоя системы

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

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

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

1.12 Характеристическое уравнение и его корни

1.13 Нахождение Рх j (l) и Р2, (l) '

1.14 Нахождение щ и %

1.15 Стационарная плотность вероятностей незавершенной работы 37 Заключение

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

2.1 Описание системы

2.2 Уравнения для финальных вероятностей

2.3 Уравнения для производящих функций

2.4 Нахождение производящих функций

2.5 Характеристики системы 50 Заключение

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

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

3.2 Вывод уравнений для среднего времени опустошения системы

3.3 Нахождение т{(w) и m2{w)

3.4 Нахождение средней длительности периода занятости

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

3.6 Плотность вероятностей максимального остаточного времени в стационарном режиме

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

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

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

В реальных системах эти потоки событий, как правило, являются нестационарными - их интенсивность меняется со временем. Кроме того, интенсивность потока меняется случайным образом. Поэтому достаточно адекватной реальности являются так называемые дважды стохастические потоки заявок, еще слабо изученные [6, 38, 41,43, 44]. Изучению систем массового обслуживания с такими входящими потоками посвящены работы А.Н. Дудина и его сотрудников [27-29], а также отдельные работы других авторов [39].

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

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

Этими соображениями и вызвана данная работа.

Цель работы

При выполнении данной работы ставились следующие задачи.

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

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

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

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

4. Финальные вероятности значения интенсивности в начале периода занятости и безусловную среднюю длительность периода занятости для следующих систем массового обслуживания (СМО):

1. Однолинейной СМО с бесконечным бункером;

2. Бесконечнолинейной СМО;

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

Кроме этого, ставилась задача разработать программное обеспечение для расчета всех этих характеристик.

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

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

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

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

- рекуррентный входящий поток заявок и экспоненциальное распределение времени обслуживания;

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

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

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

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

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

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

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

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

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

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

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

1. Для однолинейной СМО с бесконечным бункером и экспоненциальным распределение времени обслуживания найдены: а) условные средние длительности периода занятости т1 и т2, при условии, что в момент начала периода занятости интенсивность потока = / = 1,2; б) финальные вероятности тс,- того, что период занятости начнется при значении интенсивности X = Xt\ в) условные (при условии, что интенсивность потока равна А,,) стационарные плотности вероятностей 7Cj(>v) и n2(w) незавершенной работы, а также безусловная плотность вероятностей незавершенной работы.

2. Для бесконечнолинейной СМО с экспоненциальным распределение времени обслуживания найдены а) безусловная производящая функция для числа заявок в системе; финальные вероятности для числа заявок в системе, в частности, вероятность того, что система пуста; среднее число заявок и дисперсия числа заявок, находящихся в системе; б) условные средние длительности m{{w) и m2(w) до опустошения системы при условии, что в начальный момент времени \ = 'ki, i = 1,2, и максимальное остаточное время обслуживания равно w; в) условные средние длительности mf, г = 1,2 периода занятости системы при условии, что период занятости начинается со значения интенсивности г) финальные вероятности л,-, / = 1,2 того, что период занятости начнется с интенсивности и безусловная средняя длительность периода занятости; д) плотность вероятностей максимального остаточного времени в стационарном режиме.

3. Для однолинейной СМО с вытеснением заявки, находящейся на обслуживании при произвольном распределении времени обслуживания найдены а) условные средние длительности Ш1 и т2 периода занятости системы при условии, что в момент начала периода занятости интенсивность потока была равна А, i = 1,2; б) финальные вероятности щ и тг2 того, что период занятости начнется с состояния интенсивности потока X = Xh / = 1,2, и безусловную среднюю длительность периода занятости; в) условные плотности вероятностей ^(w) и n2(w) незавершенной работы w при условии, что интенсивность потока X = X;, / = 1,2, и безусловную плотность вероятностей тс(и>) незавершенной работы.

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

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

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

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

Во всех главах входящий поток заявок представляет собой дважды стохастический пуассоновский поток событий с двумя состояниями интенсивности — А,, и Термин «пуассоновский» означает, что при фиксированном значении интенсивности поток заявок является пуассоновским с соответствующей интенсивностью. В дальнейшем для определенности будем считать, что А,! >Х2-Между этими состояниями возможны переходы, которые образуют дискретный марковский процесс с непрерывным временем. Интенсивность перехода X, —» Х2 мы будем обозначать как aj, интенсивность перехода Х2 -» А,, как а2. Время обслуживания в главах 1-3 предполагается распределенным по экспоненциальному закону с интенсивностью jx.

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

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

00 m[{w) = l-(Xl + a1)m1(w) + a1m2(w) + + x)p(x)dx, о

00 m'2 (w) = 1 - (A,2 + a2 )m2 (w) + a2Щ (w) + X2 jm2 (w + x)p(x)dx, о с граничными условиями m,(0) = m2(0) = 0.

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

00 о получены более простые выражения ax+a2)z 0

Wj= 1 + a1(l-/2)+^2(l-/i)J 1 + z-/,' = -(а,+а2)?---в or, (1 —/2) (l-/i)J 1 + Z-l2 где 1к=Хк/ц, ak=ak/\i, 0 = l/|j. Что касается z, то это - положительный корень характеристического уравнения z3 — z 2 (/j +/2 + ах + а2 - 2) + z[(lx + ах-1 )(/2 + а2 -1) - ах - а2 - аха^\

-h(i-/2)+«2(i-/,)]=о.

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

Для нахождения безусловной средней длительности периода занятости надо найти финальные вероятности л;,-, i = 1,2 того, что период занятости начнется при значении интенсивности Х = Х{. Громоздкими вычислениями показано, что эти величины имеют вид я = /2flj(*-*) + /2(fi+fliXl-K) 1 (1 - K)(lxl2 (1 - к) + ах12 + а21х)'

2 (\-К)(1х12(\-к) + ах12+а21х) ' где к - корень уравнения lxl2к3 - к2(/^2 + 12а 1 + 1\С12 + a\ai)+ + h + а\+ а2 +1) ~ 1= О> лежащий на отрезке (0, 1). Показано, что этот корень единственный. Теперь можно найти и безусловную среднюю длительность периода занятости т = щтх + п2т2.

В работе найдены также характеристики простоя системы, Они следующие:

1. Пусть qtj есть вероятности того, что период простоя закончится при значении интенсивности Xj пир условии, что он начался при значении интенсивности Xf. Тогда

1\12 +1\<*2 + *2а1 4*2 + Ча2 + ha\ и qn =\-qu, q22 =\~q2\.

2. Пусть mi, i = 1,2, есть среднее время простоя системы, если в начальный момент поток находился в состоянии X,. Тогда m]=ea+a1±L т2=6а±£2+А ci\l2 + a2lx + /j/2 <3j/2 + a2l\ +l\l2

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

11

Во второй главе находятся финальные вероятности состояний бесконеч-нолинейной СМО. Пусть я-** есть финальная вероятность того, что в системе находится на обслуживании / заявок и интенсивность потока Х = Хк. В безразмерных величинах lk = \k/\i, ак = ак/\х система уравнений для т^р имеет вид

- (/, + ^ )7CS0 + + ^Г27С(02> = О, -(/j + ах +/)+(? + l)7tS1) + а27uS2) =0, (h + «2 + + 0' + 1)Я/2) + а^Р = 0, Для решения этой системы переходим к производящим функциям о

Тогда система уравнений для них принимает вид

P/(z)(l - z) + Рх (z)(/, (z -1) - я,) + я2Р2 (z) = 0, Pi (z)( 1 - z) + P2 (z)(/2 (z -1) - a2 ) + a, P, (z) = 0.

В работе находится явное выражение для производящих функций:

Pl (*) = Ф(в, Л + + «2; (/2 -/,)(*-1)) е'« ^ >. ах + а2

Р2 (z) = Ф(я2,1 + а, + я2; (/, - /2 )(z -1)) е'^"1*, 2 где <E>(a,c;z) есть вырожденная гипергеометрическая функция. Отсюда находится явный вид финальных вероятностей

I к / \

I к г \

В частности, вероятность того, что система пуста

7и0 = —^—Ф{ах,\ + ах + a2;lx -/2)е/> +—^—0(a2,l + aj + я2;/2 —/Ле-'2, ах +а2 ах + а2 среднее число заявок в системе

M{/} = P1'(1) + P2'(1) = -L 12 i/2 + a2l\ ах +а2 дисперсия числа заявок в системе ы а21х+ах12 ( 1 1 1 аха2{12 -/j)2.

Uai+a2)2 al+a2+1

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

Обозначим через mk(w) среднее время до опустошения системы, если в начальный момент времени t интенсивность потока была Хк и максимальное остаточное время обслуживания на занятых приборах было равно w. Тогда, рассматривая переходы за интервал времени At, можно получить интегро-дифференциальное уравнение и аналогичное уравнение для т2 (w). Их можно свести к системе дифференциальных уравнений

00 W

В работе показывается, что граничные условия имеют вид т1 (о) = 0, т1 (т)ц е"цт dx, и аналогичные условия для т2 (w).

Достаточно громоздкое исследование дает следующий результат w тх(w) = |ф(- ах,1 -ах-а2;(l2 - lx )ецх)exp(lx )dx + W О w C2 \ф(а2,1 + ax + а2;{12 - /,ехр(/, о где i

1 + /, ]ф(- ах ,\-ах- а2;(/2 - lx )z)e/,z dz - Ф(- ах ,1 - ах - а2 ;/2 - 1Х) с о и2 - 1 ' ф(в2л+*1 +*2;/2 -А У1 - /ф(л2л+в1 -h)z)zai+a>^zdz о и аналогичную формулу для т2 (w).

Так как период занятости начинается с прихода заявки в пустую систему, то в начале периода занятости w имеет то же самое распределение, что и т, то есть p(w) = \i ехр(- ци>). Тогда, усредняя по w, получим следующее выражение для условной (при условии, что период занятости начинается при значении интенсивности X = Ai) средней длительности периода занятости

Щ ~ах —а2;12-1х)+С2Ф{а2,\ +ах +a2\l2 -/Je^-l], и аналогичное выражение для т2.

Для усреднения по значению интенсивности X в начале периода занятости надо знать величины i = 1,2, которые есть вероятности того, что период занятости начнется при значении интенсивности Хг Они рассчитываются достаточно сложно и в два этапа.

Обозначим через Py(w) вероятность того, что опустошение системы произойдет при значении интенсивности X = Xj при условии, что в данный момент времени интенсивности потока X была равна Xh и максимальное остаточное время обслуживания было равно w. Тогда можно показать, что уравнение, скажем, для Рхх (w), имеет вид

00

Ри М + («1+^1 е-^ У 1М = axp2l М+xx[i J>,! (х)е"цт dz.

Достаточно громоздкое исследование дает такой результат w

Pn(w)= 1 - C2 ф(а2,1 + о, + a2;(/2 - /, )e^)exp(/, e^jkfa,

C,=-;-—

Ф(a2,\ + al+a2;I2-1\)e/'-lx jza' ф(<я2,1 + ax + a2;(/2 -/,)z)e/lZak о

Обозначим через Ру вероятность того, что в конце периода занятости будет X = Xj при условии, что в начале периода занятости Х = ХГ Так как период занятости начинается с прихода первой заявки, для которой />(w) = fj.e"MVV, то, усредняя по w, получим ф{а2,\ + ах +a2;l2-ll)ell-(al + lx)jzai+a2<&(a2,l +ах + a2;(l2-lx)z)ellZdz о l ф{а2,\ + ах +a2;l2 -lx)eZl-/, jza[+a^(a2,l + ax+ a2\(l2 -lx)z)e!lZ dz

Аналогичные выражения имеют место и для остальных Ру.

Обозначим через qtj вероятность того, что период простоя закончится при значении интенсивности X = Xj, если он начался при значении интенсивности Х = Х;. Они имеют тот же вид, что и в главе 1. Как и в главе 1, теперь можно вычислить величины r^ = PiXqXj- + //2#2у и найти финальные вероятности л,-того, что период занятости начнется при значении интенсивности Х{: тс - 7Г -—ill—

711 --> Я 2 --» rl2+r2l r\2+r2l что и дает возможность вычислить безусловную среднюю длительность периода занятости т = кх • тх + п2 ■ т2.

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

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

Обозначим через mt{w) среднее время до окончания периода занятости, если в момент времени t интенсивность потока Х = Х{ и остаточное время обслуживания заявки, находящейся на приборе, если она не будет вытеснена другой заявкой, равно w. Другими словами, w есть незавершенная работа заявки, находящейся на обслуживании. Рассматривая переходы между состояниями системы за интервал времени At, получены следующие уравнения т[(w)+(A,j + cxj )тх (w) - axm2 (w) = 1 + Xxmx, m'2 (w) + (X2 + «2 )m2 (W) - a2wl (W) = 1 + A,2W2 ,

00 где Щ = jmi(,z)p(x)dx. Эту систему надо решить при граничных условиях о тх (о) = /я2 (О) = 0.

Для решения системы переходим к преобразованию Лапласа

00 т{ (5) = jm^w^e'^dw. Тогда эта система приобретает вид о jotj^ + ^I + ах)тх(5)-ахт2(5) = ^ + } s

5w2(y) + (A,2 + a2)fh2{s)-a2mx{s) =-2^2^ s

Достаточно громоздкое решение этой системы дает следующий результат тх (w) = (l + ХхЩ )ф, j (w) + (l + Х2Щ )ф12 (w), т2 (w) = (l + Х2т2 )ф22 (w) 4- (l + Ххтх )ф21 (w).

Из входящих сюда функций ф;у (и>) приведем для примера только одну; все остальные выписаны явно в основном тексте.

Zj + z2 z2 \z2 —Zx) z2\z2 — Zj) где zx и z2 - корни уравнения z2-z(X{ + Х2 + ai + сс2)+(А.|Л.2 + СХ|Л,2 +а2А,|) = 0. Оба эти корня положительные.

Тогда условные средние значения длительности периода занятости имеют вид Фп - Ф12 ~^2(ф12ф22 + Ф12Ф21 -Ф11Ф22 + Ф22Ф12) 1 — XiCpi 1 - Х^22 + 1Ф22 3Ф12Ф21) ф22 - ф21 -Х1(ф21ф11 + ф21ф12 - ф22фц + Ф11Ф21) ffi2 —-----т——---—~—г-,

1 - 1 - ^гФ22 + Цг1Ф11Ф22 " Ф12Ф21)

00 где фгу = /ф,у(т)р(тУх. о

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

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

Р/, (w) + (Xl+al )РХ l(w)-alP2l(w) = XlPu, Pi 1М+(А-2 + а2 )Pi\ W -сс2Ри (w) = X2P2l,

00 где Fy = \р^х)р{х)йх. Их надо решить при граничных условиях j (о) = 1, о

Р21(0) = 0.

Достаточно громоздкое решение с использованием преобразования Лапласа дает

Р\ М = М + М + Ф1W

Рц М = ^2^21Ф22 М + hp\ 1Ф21М + Ф2 Ы> где ф,у (w) те же, что и ранее, а функции ф,(и>) имеют вид z2 — Zj z2 — Zj ф2 (w) = e-z, w--. z2 — Zj z2 — Zj

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

Cp! (l - А2Ф22 ) + ф2 • Х2Ф12

11 =

Л, =

1-АчФп -А2Ф22 +А,,А,2(Ф11Ф22 - Ф12Ф21)'

Фг^-АаФпНдУ^! Ф21

2Ф22 +^1^2(фпф22 -Ф12Ф21У

00 где ф, = |ф/(т)р(тУт. о

Нахождение величин п,- ведется так же, как и в главе 3. Находятся величины Ъ} = Pn4\j + РпЧу и

7t j =-—-, Ж 2 =-~-, /И = TtjWj + 7U2W2. rl2+r2l rl2+12l

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

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

Zl'ZX ос" zl-X2-a2)Xl-X2a2 ^

7rr. J z2 — Zi z 1 w и аналогичное выражение для n2(w). Безусловную плотность вероятностей 7i(w) незавершенной работы w можно записать в виде ч а7 щ (w)+a. п7 (w)

7t(wJ = -1 . a,+a2

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

Публикации

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

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

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

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

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

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

6. Глухова Е.В., Орлов А.Б. Средняя длительность периода занятости в однолинейной СМО с дважды стохастическим входящим потоком. //Вторая научно-практическая конференция «Наука и образование». Тезисы докладов. Белово: Филиал КемГУ в г. Белово, 2001. С. 294-296.

7. Глухова Е.В., Орлов А.Б. Расчет безусловной средней длительности периода занятости в однолинейной СМО с дважды стохастическим входящим потоком. //Новые технологии и комплексные решения: наука, образование, производство. Материалы Всероссийской научно-практической конференции. Ч. II. КемГУ, 2001. С. 10-12.

8. Орлов А.Б., Плыгач Е.В., Холкин Д.В. Вычисление на ЭВМ характеристик однолинейной СМО, бесконечнолинейной СМО, СМО с вытеснением заявки. //Сборник трудов VII межрегиональной научно-практической конференции «Научное творчество молодежи». Тезисы докладов. Анжеро-Судженск: Филиал КемГУ в г. Анжеро-Судженске, 2003. С. 100-102.

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

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

1. Межрегиональной научно-методической конференции «Повышение эффективности научных исследований и совершенствование учебного процесса». Анжеро-Судженск 2000.

2. Второй научно-практической конференции «Наука и образование». Белово, 2001.

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

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

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

6. VII Межрегиональной научно-практической конференции «Научное творчество молодежи». Анжеро-Судженск, 2003.

Заключение

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

1. Рассматривается входящий поток событий, который условно называется дважды стохастическим пуассоновским потоком событий с двумя состояниями интенсивности - Л,! и Х2 • Термин «пуассоновский» означает, что при фиксированном значении интенсивности поток заявок является пуассоновским с соответствующей интенсивностью. Для определенности считается, что Aj > Х2 • Между этими состояниями возможны переходы, которые образуют дискретный марковский процесс с непрерывным временем.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

12. Глухова Е.В., Шкуркин А.С. Оценка интенсивности пуассоновского потока событий по наблюдениям над началами периодов занятости в многолинейной СМО. //Математическое моделирование. Кибернетика. Информатика: Сборник статей. Томск: Изд-во ТГУ, 1999. С.47-52

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

29. Клейнрок JI. Теория массового обслуживания. М.: Машиностроение, 1979. 432 с.

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

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

32. Назаров А.А. Асимптотический анализ марковизируемых систем. Томск: Изд-во Том. ун-та, 1991. 158 с.

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

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

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

36. Bremaud P. Point processes and queues. Springer Verlag, New York, 1981.

37. 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. 12221228.

38. Gnedenko B.W., Konig D. Handbuch der Bedienungstheorie. II. Formeln und andere Ergebnisse. 1984.

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

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

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

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

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