Приоритетные системы с периодической интенсивностью поступлений тема автореферата и диссертации по математике, 01.01.05 ВАК РФ

Введение . 2

Глава I. Некоторые предельные теоремы для системы с абсолютными приоритетами.7

§ I. Описание системы типа М^ (+) | Огъ Ш111 00 с абсолютными приоритетами.7

§ 2. Начальное время ожидания в системе типа > —*

М-гН:) с абсолютными приоритетами и его связь с системой типа МСЖСгШИ .9

§ 3. Периодический режим времен ожидания в системе типа МК)|&(Ш|с~ . 12

§ 4. Условие существования периодического режима начальных и полных времен ожидания в системе типа

1*> с абсолютными приоритетами . 23

Глава П. Обобщение теоремы Хука для системы типа МНЛвШЩоо .30

§ I. Обобщение теоремы Хука на системы типа К* К) |(л-гН I .30

§ 2. Теорема сравнимости виртуальных времен ожидания в системах типа МиЛбШШ«?0 .37

§ 3. Слабая сходимость процессов виртуальных времен ожидания в последовательности систем типа й I & |1 | оо .40

§ 4. Сходимость виртуальных времен ожидания в последовательности монотонно - возрастающих аппроксимаций типа (МиИ) |6гп(-0 И .47

§ 5. Некоторые свойства монотонно - возрастающих аппроксимаций системы .54

§ 6. Обобщение теоремы Хука для системы типа МШ1£ШМ Iе50 .62

Глава П1. Средние значения времен ожидания.71

§ I. Существование математического ожидания у предельного распределения Н ^ , х) в системе типа .71

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

Системы массового обслуживания с периодической интенсивностью поступлений являются математическими моделями многих реальных ситуаций: обслуживание вызовов на телефонной станции, управление садящимися и взлетающими в аэропорту самолетами, обслуживание вызовов на станции скорой помощи и регулирование потоков автомашин на перекрестке - вот далеко не полный пере,-чень явлений, в которых необходима оценка влияния зависимости интенсивности потока от времени на качество работы системы. Необходимость постановок и решения такого сорта задач отмечалась Б.В.1йеденко и И.Н.Коваленко уже в работе [I] . Начало изучения систем с переменной интенсивностью поступлений следует отнести к середине пятидесятых годов, когда Кларк (1956) (2] и Дучак (1956) [ 3) рассмотрели распределение длины очереди в системах с показательно расцределенными длительностями: обслуживания, цричем интенсивность поступления и скорость обслуживания зависит от Времени. Изучение нестационарного решения интегро-дифференвдаль-ного уравнения Такача (4) для системы типа МСЬ) |Сг111 <х> занимался Рейч (1958) ( 5) . В некоторых предположениях он установил связь между граничным и начальным условием для функции распределения виртуального времени ожидания. Ж Ш . Отметим также работу Евдокимовой (6 ] , где находятся условия существования дериодического решения уравнения Такача.

Задача, решаемая в предлагаемой работе, возникла цри попытке построить математическую модель деятельности диспетчера в аэропорту с одной взлетно/посадочной полосой. Модель аэропорта традиционно присутствует почти во всех учебниках по теории массового обслуживания и используется для иллюстрации таких понятий, как "длительность операции", "выходящий поток", "обслуживание группами"^ т.п. (нацример, ( 7) ). Очень интересные математические модели такого сорта были построены Ццрси ( 8) и Белл [ 9) . Последний цроанализцровал различные наблюдения и измерения, производимые для изучения уцравления воздушным транспортом, вывел формулы для стационарных: состояний одноканальной системы с пуас-соновсвим входящим потоком и постоянным временем обслуживания. В 1958г. Галлихер и Уилер в работе (23 ] обратили внимание на необходимость учета периодичности интенсивности движения. Они занимались в основном вычислительной стороной задачи. Интенсивность прибытия самолетов в район Нью-Йорка рассматривается как периодически изменяющаяся с периодом, равным одним суткам« Предполагается, что в течение данных суток время приземления постоянно, но принимает одно из двух различных значений (одна или две минуты). Интенсивность аппроксимируется ступенчатой функцией с шагом, равным I час. Для вычисления стационарных вероятностей того, что в конце [ -го часа в системе находится Ть самолетов, вцраженных через эти вероятности для (¿-1)-го часа, испольаует-ся формула Краммелина. Отметим недостатки, присуще, по нашему мнению, этой модели:

- для того, чтобы пользоваться предложенным алгоритмом, необходимо знание начального распределения;

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

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

Моделью аэропорта с одной взлетно-посадочной полосой может служить система типа М|Ш, Ид ШI (т< > Ол 111 : имеются два пуассоновских потока требований с периодически менявдимися интенсивностями \ (t) и iXi(t) и функциями распределения дремени обслуживания Bi W и ? один обслуживающий црибор и очередь неограничен. Требования первого потока обладают абсолютными приоритетом по отношению к требованиям второго потока, дисциплина обслуживания требований одного потока естественная.

Основной интерес для приложений представляет периодическое распределение времен ожидания, поскольку именно оно описывает качество работы системы, не зависит от начальных условий. Зачисление этого периодического распределения даже для системы MCtjJ^H!00 связано со значительными трудностями (см., например, ( 10 ] ).

В настоящей работе рассматриваются лишь первые задачи в этом нацравлении, которые необходимы для построения аффективного вычислительного алгоритма. В смысле техники и математического аппарата работа опирается на литературу(I) ,(10) , ( II) Л 12) , ( 13) , (14) ,(15) и т.д.

Основные цроцессы, которые изучаются в диссертации - это процессы начального и полного виртуального времени ожидания. Определение этих понятий дается в гл.1. Устанавливается, что с точки зрения процесса начального виртуального времени ожидания требований низшего цриоритета система с приоритетами эквивалентна некоторой системе типа M(t) \6r(t)\ i , в которой распределение времени обслуживания Q(t^) зависит от момента t поступления требования в систему.

Далее, для системы типа M(+)iâ"0t)H находится условие существования цредельного периодического по t" распределения H (t,я) виртуального времени ожидания и предельного рас цре деления времени ожидания п -го требования GfCx) (Г)-?со) . Устанавливаются некоторые полезные соотношения для предельных распределений. Как следствия из этих результатов получаются аналогичные утверждения для систем с приоритетами. Используемый математический аппарат - теория восстановления, теорема Смита дня регенерирующих случайных процессов, усиленный закон больших чисел для цроцессов с независимыми црцращениями.

Во второй главе доказывается аналог теоремы Хука, полезной при построении оценок средних времен ожидания. Сначала эта тео-рева доказывается для системы вида Mtít) | ^ 11 | * (^-ЛЗ/"} в которой времена обслуживания требований данного потока не зависит от моментов поступлений. Чтобы распространить полученное равенство на систему М (t) | (J-Ot) 11 , щщшлось построить для нее аппроксимирующую последовательность систем описанного выше типа. В связи с этим возникла необходимость доказательства теорем непрерывности для периодического расцределения Н (t, %} , представлящих впрочем самостоятельный интерес. Сначала на основании работы Кеннеди (12] устанавливается сходимость в пространстве DCo^aj цроцессов виртуальных времен ожиданий (Теорема 2.6 ] . Отсюда вытекает сходимость в основном конечномерных распределений. Для монотонных аппроксимаций доказывается поточечная сходимость функций распределения. Далее с использованием представления для H(t,x) (формула I.I4) доказывается сходимость периодических расцре делений. Обобщение теоремы Хука устанавливается с помощью предельных переходов. Отсюда удается получить значение среднего по периоду математического ожидания виртуального времени ожидания в системе /^(t) К^Ш I 4 I (Теорема 3.1) и как следствие этого результата для начального виртуального времени ожидания в системе с приоритетами в случае, когда в момент t загрузка системы f(i) независит от времени (следствие 3.1). Находятся также некоторые оценки, когда время обслуживания имеет распределение Эрланга.

В главе Ш для получения оценок математического ожидания полного, времени ожидания в системе с приоритетами используется представление этого случайного процесса через начальное время ожидания, установленное в главе I (теорема I.II).

ЗАКЛЮЧЕНИЕ

Результаты, полученные в работе, могут быть использованы при определении средних времен задержек требований в очереди в приоритетных системах с периодической интенсивностью поступлений в установившемся режиме. Найдены условия существования такого режима. Теорема сравнимости позволяет строить мажорирующие системы и с их помощью получать оценки сверху и снизу. Теорема непрерывности дает возможность приближать функции ЛЮ ступенчатыми, для которых вычислительный алгоритм всегда проще. Например, цри показательном времени обслуживания можно находить явные формулы с помощью известных результатов для систем типа М/М1 IIе*0 С 7) . Оценки для среднего времени ожидания позволяют судить о колебаниях этой величины на периоде.

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

- выделение классов функций ¿ЛШ , для которых с достаточной степенью точности можно пользоваться стационарными решениями;^

- исследование поведения периодических решений в условиях большой и малой загдузки;

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

Завершая работу, автор вцражает глубокую благодарность своим научным руководителям Л.Г.Афанасьевой и А.В.Щхалеау за постановку задачи, истинное руководство, помощь и многочисленные полезные обсуждения. Автор приносит также свою цризнательность сотрудникам кафедр теории вероятностей и математической статистики механико-математического факультета МГУ за обсуждения и советы.

1. Гнеденко Б,В,, Коваленко И.Н. Введение в теорию массового обслуживания. М.: Наука, 1966, 431с.

2. CkARkE А* В. (1456) A túCUtíng, time, process of MarKoV type-* Ann* • Statists 27,pp. 5

3. Евдокимова Г.С. О распределении длительности ожидания в случае периодического входящего потока. Изв. АН СССР, тех. кибернетика, 1974, Я 3, 114 - 118.

4. Саати Т. Элементы теории массового обслуживания и её приложения. М.: Изд-во Советское радио, 1965, 510с.

5. Реа*сеу Т. (194-в) ре/арs In of air traffic,, J- Roy, Azroncuob. Soc * 5 vol .32 > pp. 799 ~ SU •

6. BejlL, G-ЬЛ <44-Ю Theoretical stuoües into tmfftc congestion, part Ж, ßnt. Ministry, of dvü atftatfon, Operation research sect., ORS.JMCA R.ept«3? Jcwe

7. Колмогоров А.H., Фомин C.B. Элементы теории функций и функционального анализа. М.: Наука, 1981, 542с.

8. Ивченко Г.И., Каштанов В.А., Коваленко Й.Н. Теория массового обслуживания, М.: Изд-во Высшая школа, 1982, 256с.

9. Такач I. Комбинаторные методы в теории случайных процессов. М.: Мир, 1971, 264с.

10. Боровков А.А. Теория вероятностей. М.: Наука, 1976, 287с.

11. Феллер В. Введение в теорию вероятностей и её приложения, т.1. М.: Мир, 1964, 498с.

12. Афанасьева JE.Г., Булинская Е.В. Случайные процессы в теории массового обслуживания и управления запасами. М. : Изд-во МГУ, 1980, 110с.

13. Биллингсли П. Сходимость вероятностных мер. М.: Наука, 1977, 351с.20• WhITT W- Ц968) We&K СотГе-крелсе. ù^eoyews j-ок %usica¿s сл b^aéítC. ря* P. Tresis, CoweJJ University

14. Tec/irücoJ report МО. X, Department of ope-KtÎîons №$ e a^cJi , Stanford Un ; vers jty.,)21* Le moine A-X u9&d On %ылиа& oûhû periodic, poisson typist, J. frppA. p^oé. Ig, 899- 900.

15. Штойян Д. Качественные свойства и оценки стохастических моделей. М.: Мир, 1979, 268с.23. gfalli her н°р< AND WHEELER ft- С. ( 1958) nohstcbtiomwf ÍUJUCZJ^ pr&écb-éïlt tres for Icundïnfr congestion of al'KJrfft, OpzHbt'cms ises-earcfy* VoX< 6 ? pp*

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

17. Lémoine A.j. W14-) Он íupo stcáíonawf dt£>trt@utroh& fot-tM s-toóle. CrlIQií '.App¿. pro6.ii.8tf-862*