- 2 -
ВВЕДЕНИЕ
Системы массового обслуживания с периодической интенсивностью поступлений являются математическими моделями многих реальных ситуаций: обслуживание вызовов на телефонной станции, управление садящимися и взлетающими в аэропорту самолетами, обслуживание вызовов на станции скорой помощи и регулирование потоков автомашин на перекрестке - вот далеко не полный перечень явлений, в которых необходима оценка влияния зависимости интенсивности потока от времени на качество работы системы. Необходимость постановок и решения такого сорта задач отмечалась Б.В.1Реденко и И.Н.Коваленко уже в работе [I] . Начало изучения систем с переменной интенсивностью поступлений следует отнести к середине пятидесятых годов, когда Кларк (1956) (2} и Лучак (1956) (.3] рассмотрели распределение длины очереди в системах с показательно распределенными длительностями обслуживания, причем интенсивность поступления и скорость обслуживания зависит от времени. Изучение нестационарного решения интегро-дифференциального уравнения Такача (4) для системы типа ИСЮ | Сг 11 | оо занимался Рейч (1958) ( 5} . В некоторых предположениях он установил связь между граничным и начальным условием для функ-
ции распределения виртуального времени ожидания ^ Ш . Отметим также работу Евдокимовой ( 6 ) , где находятся условия существования периодического решения уравнения Такача.
Задача, решаемая в предлагаемой работе, возникла цри попытке построить математическую модель деятельности диспетчера в аэропорту с одной взлетно/посадочной полосой. Модель аэропорта традиционно присутствует почти во всех учебниках по теории массового обслуживания и используется для иллюстрации таких понятий, как "длительность операции", "выходящий поток", "обслуживание группами"^ т.п. (нацример, ( 7] ). Очень интересные математические
- 3 -
модели такого сорта были построены Пцрси ( 8) и Балл [ 9) . Последний проанализировал различные наблюдения и измерения, производимые для изучения управления воздушным транспортом, вывел формулы для стационарных состояний одноканальной системы с пуас-соновскпм входящим потоком и постоянным временем обслуживания.
В 1958г. Галлихер и Уилер в работе (23 ] обратили внимание на необходимость учета периодичности интенсивности движения. Они занимались в основном вычислительной стороной задачи. Интенсивность прибытия самолетов в район Нью-Йорка рассматривается как периодически изменяющаяся с периодом, равным одним суткам* Предполагается, что в течение данных суток время приземления постоянно, но принимает одно из двух различных значений (одна или две минуты). Интенсивность аппроксимируется ступенчатой функцией с шагом, равным I чао. Для вычисления стационарных вероятностей того, что в конце I -го часа в системе находится )г самолетов, вцраженннх через эти вероятности для (1-1)-го часа, испольаует-ся формула Краммелина. Отметим недостатки, присущие, по нашему мнению, этой модели:
- для того, чтобы пользоваться предложенным алгоритмом, необходимо знание начального распределения;
- если в аэропорту одна взлетно-посадочная полоса, то время посадки самолета существенно зависит от направления подхода,
и стало быть является случайной величиной;
- при использовании одной полосы для взлета и посадки, нужно изучать систему с двумя типами требований (садящиеся и взлетающие самолеты), причем требования одного типа (садящиеся) имеют приоритет по отношению к требованиям другого типа.
Моделью аэропорта с одной взлетно-посадочной полосой может служить система типа М|Ш, МаI, Оъ. 111 : имеют-
ся два пуассоновских потока требований с периодически мевялци-
- 4 -
мися интенсивностями Д, (t) и и функциями распределения
времени обслуживания Bi (V и (ЗДх) ; один обслуживающий прибор и очередь неограничена. Требования первого потока обладают абсолютными приоритетом по отношению к требованиям второго потока. Дисциплина обслуживания требований одного потока естественная.
Основной интерес для приложений представляет периодическое распределение времен ожидания, поскольку именно оно описывает качество работы системы, не зависит от начальных условий. Вычисление этого периодического распределения даже для системы Мф|<тН1°° связано со значительными трудностями (см., например, (10) ).
В настоящей работе рассматриваются лишь первые задачи в этом направлении, которые необходимы для построения эффективного вычислительного алгоритма. В смысле техники и математического аппарата работа опирается на литературу (I) , (10) Д II) Д12) ,
( 13) ,(14) Д 15) и т.д.
Основные процессы, которые изучаются в диссертации - это процессы начального и полного виртуального времени ожидания. Определение этих понятий дается в гл.1. Устанавливается, что с точки зрения процесса начального виртуального времени ожидания требований низшего приоритета система с приоритетами эквивалентна некоторой системе типа M(t)l<x(i)l) 1°° , в которой распределение времени обслуживания зависит от момента t поступ-
ления требования в систему.
Далее, для системы типа M(+)l6rCt)H \°° находит-
ся условие существования предельного периодического по f распределения Н (t,x) виртуального времени ожидания и предельного рас цределения времени ожидания п. -го требования Qix) .
Устанавливаются некоторые полезные соотношения для предельных распределений. Как следствия из этих результатов получаются аналогичные утверждения для систем с приоритетами. Используемый ма-
- 5 -
тематический аппарат - теория восстановления, теорема Смита для регенерирующих случайных процессов, усиленный закон больших чисел для процессов с независимыми приращениями.
Во второй главе доказывается аналог теоремы Хука, полезной при построении оценок средних времен ожидания. Сначала зта теорема доказывается для системы вида |Д (1) | £т* 11 | с*? > в которой дремена обслуживания требований данного потока не зависит от моментов поступлений. Чтобы распространить полученное равенство на систему М(+) I (т(^) III00 » ДРИшлось построить
дня нее аппроксимирующую последовательность систем описанного выше типа. В связи с этим возникла необходимость доказательства теорем непрерывности для периодического распределения Н ^ * х) , представляющих впрочем самостоятельный интерес. Сначала на основании работы Кеннеди (12] устанавливается сходимость в пространстве процессов виртуальных времен ожиданий (Теорема
2.6 ] . Отсюда вытекает сходимость в основном конечномерных распределений. Для монотонных аппроксимаций доказывается поточечная сходимость функций распределения. Далее с использованием представления для Н(1,Х) (формула 1.14) доказывается сходимость периодических распределений. Обобщение теоремы Хука устанавливается с помощью предельных переходов. Отсюда удается получить значение среднего по периоду математического ожидания виртуального времени ожидания в системе /'''К'ОКцШ I { | оо (Теоре-
ма 3.1) и как следствие этого результата для начального виртуального времени ожидания в системе с приоритетами в случае, когда в момент t загрузка системы ?а) независит от времени (следствие 3.1). Находятся также некоторые оценки, когда время обслуживания имеет распределение Эрланга.
В главе Ш для получения оценок математического ожидания полного,. времени ожидания в системе с приоритетами используется цред-
- 6 -
ставлевие этого случайного процесса через начальное время ожидания, установленное в главе I (теорема 1.11).
Т.е. глава I диссертационной работы содержит описание приоритетной системы, вводит понятия начального и полного времен ожидания. Устанавливает связь между ними. Здесь же задача определения начального времени ожидания сводится к исследованию виртуального времени ожидания в системе МШ I бг(+)! 1!00 •
Глава П посвящена обобщению теоремы Хука. Для нее доказательства устанавливаются теоремы сравнимости и непрерывности.
В главе Ш предлагаются некоторые оценки для средних времен ожидания.
- 7 -
ГЛАВА I
НЕКОТОРЫЕ ПРЕДЕЛЬНЫЕ ТЕОРЕМЫ ДНЯ СИСТЕМЫ С АБСОЛЮТНЫМИ
ПРИОРИТЕТАМИ
§ I. Описание системы типа | (~г^ Ш 111с*3
с абсолютными приоритетами
Рассмотрим одноканальную систему массового обслуживания, в которую поступают 'Ь независимых пуассоновских потоков требований, причем интенсивность и -го потока АбН;) (1—1,^) является периодической с периодом I от времени, т.е. Л^(П+1:)=;Х1Д+.) при всех целых П , Время обслуживания требования I -го потока определяется моментом его поступления в систему: если требование поступило в момент t » то его время обслуживания не зависит от времен обслуживания других требований и моментов их поступлений и имеет функцию распределения •
Здесь J3.lt »/У периодична по ^ с периодом, равным единице. Требования I -го потока обладает абсолютным приоритетом по отношению к требованиям 6+4 -го...,'б- -го потоков, т.е. если в момент прихода требования I -го потока на приборе находится требование i+i -го, 6+2 -го..., или'! -го потоков, его обслуживание прерывается, оно становится во главе очереди требований данного потока и поступившее требование занимает прибор. Вытесненное требование дообслуживается, когда в системе не остается требований высшего приоритета. Внутри одного потока дисциплина обслуживания естественная.
Если бы требование I -го потока поступило бы в систему в момент t , то в этот момент полностью определялось бы минимальное время ожидания: длина промежутка времени с момента Ь виртуального прибытия до момента, когда система освободится от вызовов с )-го типа, поступивших в систему до момента £
- Київ+380960830922