Содержание к диссертации
Введение
1.1. Общая характеристика особенностей работы 6
1.2. Основные положения и краткий обзор работы 15
ГЛАВА ВТОРАЯ О входных потоках требований в системах с переменной структурой обслуживания
2.1. Неполное описание потоков 24
2.2. Определение квазирегенерирующих потоков. Примеры квазирегенерирующих потоков 28
2.3. Определение регенерирующего входного потока одно родных требований 36
2.4. Применение квазирегенерирующих потоков для описания реальных потоков заявок 44
ГЛАВА ТРЕТЬЯ Фубкционалъно-математшеская модель управления потоками в дискретных системах с переменной структурой обслуживания
3.1. Векторный квазирегенерирующий входной поток систетлы.
Описание динамики обслуживающего устройства и определение алгоритма управления изменениями структур ных состояний 53
3.2. Потоки насыщения и их классификация 62
3.3. Стратегия механизма обслуживания требований и свой ство условных распределений векторного выходного потока 72
3.4. Получение векторного рекуррентного соотношения для случайного процесса образования очередей по потокам и эволюции обслуживающего устройства 82
Общий подход к изучению дискретных систем с переменной структурой обслуживания потеков
4.1. Теоремы об условной марковости систем с переменной структурой обслуживания заявок 90
4.2. Итерационные процессы для условных распределений состояний системы и классификация систем с перемен ной структурой обслуживания
4.3. Неполное описание векторного потока обслуженных системой требований 121
4.4. Условия инвариантности векторного входного потока.. 133
Задача оптимизации алгоритмов управления потоками вызовов в системах с переменной структурой обслуживания
5.1. Формулировка задачи об оптимальном управлении потока ми заявок и определение функционалов Чжуна 143
5.2. Вероятностные свойства функционалов Чжуна 152
5.3. Алгебраические свойства условных математических ожиданий от функционалов Чжуна 163
5.4. Метод вычисления вероятностей достижения с запретами и условных математических ожиданий от функционалов Чжуна. Иллюстративные примеры 172
ГЛАВА ШЕСТАЯ Управление конфликтными истоками в классе однородных алгоритмов с ориентацией и переналадками
6.1. Конструктивные основы задания однородных алгоритмов управления с ориентацией и переналадками 181
6.2. Строение пространства состояний векторного случай ного процесса, определяющего динамику очередей по потокам и эволюцию обслуживающего устройства 189
6.3. О минимальных ограничениях на выбор однородных управляющих алгоритмов с ориентацией и переналадками 197
6.4. Итеративно-мажорантный метод определения необходимых условий существования инвариантного условного
распределения состояний системы 213
6.5. Получение достаточных условий статистической устойчивости однородных алгоритмов с ориентацией и переналадками 224
6.6. Об управлении конфликтными потоками самолетов при организации процесса посадки 235
ГЛАВА СЕДЬМАЯ Управление конфликтными потоками заявок по минимальной информации о состоянии системы с переменной структурой обслуживши
7.1. Определение однородных управляющих алгоритмов с упреждением и получение основных рекуррентных соотношений для процесса обслуживания 245
7.2. Предельные теоремы для случайного процесса обслуживания потоков по алгоритму с упреждением 259
7.3. Классификация в целом системы с переменной структу рой обслуживания потоков по однородному алгоритму с упреждением 270
7.4. Неравенства для времени пребывания в системе синхронного момента наблюдения и управление пересекающимися потоками по алгоритму с упреждением 276
7.5. Системы с переменной структурой обслуживания требований и эффект изменения интенсивности потоков насыщения 288
Заключение 300
Литература
- Определение квазирегенерирующих потоков. Примеры квазирегенерирующих потоков
- Итерационные процессы для условных распределений состояний системы и классификация систем с перемен ной структурой обслуживания
- Алгебраические свойства условных математических ожиданий от функционалов Чжуна
- О минимальных ограничениях на выбор однородных управляющих алгоритмов с ориентацией и переналадками
Определение квазирегенерирующих потоков. Примеры квазирегенерирующих потоков
Среди ситуаций всего процесса обслуживания в первую очередь нужно рассмотреть случайный характер поступления заявок в систему или определить вероятностную структуру входного потока. Известно, что полное математическое описание входного потока однородных требовании можно выполнить двумя эквивалентными способа-ми 138,42,43] . а) с помощью случайного процесса \ЛШ » t Qj 7 Б кото ром »т_ (t) при t 0 определяет случайное число поступивших в систему заявок за числовой промежуток времени L 0, "О и 7 Of) = s Z(t-0) 1(0) = 0 ; б) с помощью векторных случайных последовательностей при TQ = 0 » в которых через т и і , (12-О соответствен но обозначены момент L -го появления и число поступивших заявок в этот числовой момент времени. К такому математическому описанию входных потоков сделаем следующие замечания.
Замечание 2.1. В ряде классических задач теории массового обслуживания используется не вся информация о полном описании входного потока способами а) или б). Так, например, для исследования флуктуации длины очереди в одноканальной системе Ml DM с ожиданием, пуассоновским входным потоком и постоянным временем обслуживания достаточно было задать лишь случайное число требований, поступивших в систему за время обслуживания одной заявки. Аналогичное положение можно обнаружить и при изучении более сложных систем массового обслуживания. В частности, по этому поводу укажем на результаты работ L40 100,-I.01j #
Замечание 2.2. Во многих задачах обслуживания на практике требования входного потока являются неравноправными или неоднородными. С этой целью приведем несколько конкретных примеров: 1. Ожидающий приземления самолет характеризуется моментом появления в аэродромной зоне, скоростью полета, положением по отношению к траектории посадки, стоимостью эксплуатации и т.п. [102] 2. Прибывшие в случайные моменты времени транспортные единицы к перекрестку имеют различную маркировку, например, автомобили бывают легковые и грузовые, головные и ведомые, медленно и быстро движущиеся и т.д. L-L0o 3. Для успешной организации обслуживания больных на дому пунктом скорой помощи важно зафиксировать не только момент получения вызова, но и указать некоторые предварительные сведения о больном (адрес, температуру, возраст, пол и т.п.) LI04J . 4. На телеграфе регистрируется момент поступления телеграммы и отмечается число в ней слов 1.10 t
Эти и множество других примеров показывают, что реальные входные потоки чаще всего недостаточно характеризовать только моментами появления требований в систему или числом поступления заявок за любой числовой промежуток времени [О , О . О необходимости рассмотрения различных обобщений входных потоков одиночных или групповых требований отмечалось в работах l38»42J . При - 26 мером потока более общей структуры может служить поток требова Готі ний, которые появляются в пространстве и во времени L J .
Приведенные факты в замечаниях 2.1 и 2.2 являются частным случаем следующей более общей ситуации. При неполном описании входного потока в виде последовательности случайных векторов на первый план выдвигается задание таких ее свойств, которые обязательно характеризуют признаки или метки требований. Перейдем теперь к определению неполного описания входного потока неоднородных заявок I- .
При наблюдениях за реальным процессом обслуживания конечного числа потоков заявок в дальнейшем будем подразумевать, что с ним можно связать некоторое основное вероятностное пространство ( Q, J , Р ) элементарных исходов со из множества Q с вероятностной мерой Р( ) на (5 -алгебре Т . Вероятностное пространство ( О., J", р ) будет предполагаться полным L-L0O»-09J 2ое рассматриваемые далее случайные объекты (случайные величины и элементы, последовательности случайных векторов, случайные процессы и т.п.) часто без дополнительного на то указания определяются или задаются конструктивно на основном вероятностном пространстве ( Q , 5" , Р ). Обозначим через Ґ строго возрастающую последовательность [ z , L 0 j случайных точек на оси времени 0"t рис. 2.1, которые теперь необязательно совпадают с числовыми моментами X , L О появления требований некоторого потока в систему.
Итерационные процессы для условных распределений состояний системы и классификация систем с перемен ной структурой обслуживания
Неизвестные параметры р , р условного распределения (2.7) были определены из таблицы 2.1 методом максимума правдоподобия L 4 . Этот метод, предложенный Р.Фишером, дает для параметров р , р следующие числовые оценки: р = =0,50819, р = 0,54574. Теперь из таблицы 2.1 непосредственно находим, что мера расхождения хи-квадрат равна приблизительно 0,002 и, следовательно, для числа степеней свободы, равного единице, с вероятностью 0,95 за счет случайных причин мера расхождения окажется не менее 0,0039.
Приведем теперь аналогичный пример на описание транспортного потока машин, которые пересекают некоторую фиксированную точку на Казанском шоссе (г. Горький). В таблице 2.2 приведены последовательные значения . , L = 0,107, которые наблюдались при плохих метеорологических условиях движения на этом шоссе.
Пять выбранных групп 2- = I; "2. = 2; 0=3; ? = 4.5; . 6 и метод максимума правдоподобия позволяют вычислить числовые оценки р = 69/108 и р = 0,59624, которым отвечает величина 0,06 для значения статистики хи-квадрат. Значит, с вероятностью 0,95 следует принять гипотезу о гипотетическом условном распре-делении P(W,( L = ID = 0,36111; Р ({ .=у }) = 0,25711 (0,59624)
Итак, данные наблюдений Бартлетта и наблюдений на Казанском шоссе согласуются с распределением (2.7), которое незначительно отличается от стационарного распределения длины очереди в системе М I МИ .В связи с этим каждую машину с медленным движением можно интерпретировать как обслуживающий прибор для машин с быстрым движением, при этом под временем обслуживания понимается время обгона. Заметим, что при выборе гипотетических условных распределений величин . , 1 0 можно использовать стационарные распределения длин очередей в различных системах массового обслуживания. Далее, зависимость условных распределений случайных величин . ,1 -0 от наблюдений последовательности или, в частности, от погодных условий движения на дороге впервые по существу была замечена инженерами транспортниками при построении управляемых систем массового обслуживания. Инженеры-транспортники при регулировании движения автомобилей через перекресток, как правило, применяют различные управляющие алгоритмы в зависимости от метеорологических условий на дорогах. В простейшем случае библиотека управляющих алгоритмов может состоять из управляющего алгоритма на весенне-летний период времени и управляющего алгоритма на осенне-зимний период времени.
Основная трудность в построении адекватных оценок р =0,50819, р = 0,54572 для параметров р , р распределения (2.7) была вызвана малым объемом выборки, например, транспортной задачи Бартлетта. Поэтому ниже рассматривается другой пример реального потока с большим объемом выборки. В книге 8 приводится таблица из 672-х интервалов между последовательными ошибками, возникающие при передаче двоичной информации по телефону. Эта совокупность интервалов в битах была зарегистрирована Западно-германским отделением фирмы IBM и Почтовым ведомством ФРГ при наблюдении пятнадцатиминутной передачи сообщений по телефону. Графический анализ этих данных позволяет обнаружить тенденцию к группировке ошибок (заявок) и получить на этой основе последовательность значений Х- » I = 0,372 и последователь ность значений 2- » Ь = 0,371. В таблице 2.3 приведены только значения . , і = 0,371. Значения X. , і = 0,372 нетрудно восстановить по данным таблицы 2.3. и по величинам интервалов между последовательными ошибками, приведенным в книге L Заметим, что в таблице 2.3 через ?. обозначено случайное число ошибок (заявок) за числовое значение [ X , .ц) t -го промежутка времени, измеряемого в битах.
Алгебраические свойства условных математических ожиданий от функционалов Чжуна
Эти и другие числовые показатели качества работы классических систем обслуживания, как правило, определяются аналитически либо некоторым алгоритмическим путем. Однако при анализе систем с переменной структурой обслуживания конфликтных потоков зачастую не удается получить даже вычислительный алгоритм, аппроксимирующий эти важные критерии. В первую очередь это обстоятельство объясняется неполным описанием таких систем. К тому же системы с переменной структурой нередко функционируют в условиях большой загрузки, и, следовательно, используемые при этом разнообразные приближенные формулы и численные методы плохо обусловлены, т.е. вычисляют указанные выше целевые характеристики с недостаточной степенью точности. Дело еще усложняется тем, что в условиях большой загрузки среднее время пребывания и среднее число заявок в системе являются слишком большими величинами и тем самым могут оказаться неподходящими целевыми показателями. В связи со сказанным естественно возникает необходимость выбирать в качестве показателей эффективности для некоторых систем с переменной структурой нетрадиционные функционалы на траекториях управляемой условно-марковской цепи {(Г\ , » L 1»
Теперь можно отметить, что рассмотрение (А С00), б) -оптимальных и (Р, ё) -оптимальных управляющих алгоритмов связано с проблемой существования и эффективного построения ( ) -оптимальных управляющих алгоритмов для систем с переменной структурой обслуживания при использовании функционалов R С , /) специального вида. Среди различных типов таких функционалов особое значение для систем с переменной структурой имеют функционалы, которые определяют время достижения векторной последовательностью \ #Y ; L. - 0 } некоторого подмножества XX С Г" Х Х при специальных ограничениях на возможные переходы в этой условно-марковской цепи. Перейдем непосредственно к описанию одного класса функционалов "достижения с запретами". С помощью модифицированного лексрікографического метода (см. 4.2) каждому состоянию (Т х zO из пространства поставим во взаимно однозначное соответствие номер N( jX1H ) из множества {0,1,...} .
Определение 5.3. Покрытие ЇІ= i -_ , ft- n $-+} пространства состояний Г Х Х назовем допустимым, если допустимого покрытия 51 следует, что множества Л. і ft , Я. содержат конечное или счетное число состояний и множество ft-в некоторых случаях может быть также пустым. Множества Л_ , Jt0 и tft + будем называть соответственно запрещенным, критическим и достижиглым. Для любых фиксированных элементов Л Є Я. , Кее N(&0) и па Се) є {а : а= 0,4,... ; Рд(ы)({ f= N"4(Ke)i) 3 введем в рассмотрение функционал "достижения с запретами" вида R(ft,He,m(e);f,x Д)=иг {к: К и пг(е), зависящий от последовательности #" .... Этот функционал определяет случайное число шагов, необходимых условно-марковской цепи f у _ _ # для первого перехода после числового момента m (е) во множество tfi через состояние )\Г (Н } tl п на т(е) -ом шаге и не по элементам запрещенного множества &_. Ради сокращения записи будем иногда вместо R(& Нр m(G) Г t писать R ($[ И га(е)) или R(cu) . Если для некоторого СОлеЙ условно-марковский процесс у- у после числового момента m (е) не достигает множества через состояние NJ (Нр)єй10 на т(е) -ом шаге при запрещенном мно - 148 жестве tft _ или указанный случайный процесс не проходит через состояние N (Не)є о на щ(Є)-ом шаге, т.е.{к .к 1 nW гт се:гN" Crt« lf ft-, ггкє ЛЛ = . то по определению полагаем іхі&ф = + (см. L ЛІ } СТр# 26) и, следовательно, R( 0)= 4-00 т для данного tl Є tft семейство функционалов насколько хорошо или плохо система с переменной структурой обслуживания преодолевает критические ситуации, определяемые множествами Si _ И ]ft Q .
О минимальных ограничениях на выбор однородных управляющих алгоритмов с ориентацией и переналадками
Заметим, что не зависит от начального распределения и определяет для стационарного режима условный средний расход системы посадки за произвольный цикл управления. В силу структурных сложностей и особенностей описанной выше математической модели системы посадки неоднородных самолетов пока не существует эффективного подхода к решению задачи аналитического вычисления даже наиболее простого критерия J ( } Л (си)) и к решению проблемы нахождения оптимальных управляющих параметров с, ы. . Именно поэтому использование метода имитационного моделирования на ЭВМ процесса управления посадкой неоднородных самолетов оказалось оправданным и весьма результативным как для приближенного вычисления некоторого выбранного критерия, так и последующего определения, например, путем сокращенного перебора вариантов по параметрам U и U , некоторого (Д(сх0, )- квазиоптимального алгоритма о/иеЛ при заданной точности 0 имита-ционного моделирования. Пусть одним из методов поиска (например, покоординатного подъема I , методом проекции опорных функций у-Щ и т#Дв) оптимальных значений некоторого выбранного критерия IG jQ (A(w)\ А(со)) было выделено некоторое подмножество Л2 алгоритмов о єЛ СЛ,,. При этом путем имитационного моделирования на ЭВМ процесса управления посадкой неоднородных самолетов с некоторой заданной точностью 0 определяется оценка I (of ,QC0 CA (" )), ДС"0) критерия 1С ДСО)(Л(оЛ,ЛСссО) при каждом Є Л и Q (Д((х )) W0 . Алгоритм о Є Az , для кото рого при всех оі єЛ2и Q (A(w))eW выполняется неравенство будем называть (Д(0 ), ) - квазиоптимальным с точностью моделирования , где
Конструктивное задание систем с ориентацией и переналадками только в целом на каждом I -ом цикле управления Поэтому при имитационном моделировании можно несколько модифицировать математическую модель системы посадки нижеследующими ограничениями 1) Случайная последовательность Д = \(t. -О.) ь О\ опре деляется числовым значением Т некоторой постоянной времени,фор мулами f. = i:+Tl ,0.= л). , L ,0 и заданием распределения случайного вектора (т0 - ) со значениями на {t " 0 - t +oo a . Следовательно, имеем V? иУ.(оО=Т ДЛЯ всех. Ради простоты полагаем,что пространство меток Е — \Q Є \ Итак, случайный элемент -Ъ принимает два различных значения е+ ие , определяющих некоторую характеристику произвольного самолета при хорошей летной погоде и соответственно при удовлетворительной летной погоде
Ограничения I), 2), 3) и 4) позволяют при имитационном моделировании определить для стационарного режима оценку J. Qj_ д(си)) среднего времени J. Cd Д(ш)) пребывания произвольного самолета потока П-в системе посадки, зависящей от выбранного алго I о ритмао єЛ и от реализации Д(иОє И0 . Теперь приведенный выше критерий ICo,A(u;)) МОЖНО заменить более естественным критерием который определяет среднее время пребывания произвольного самолета в системе посадки. Двумерные точки (Q CL „) (Q 0 ) являются последовательными векторными числовыми моментами условной регенерации некоторого случайного процесса tC[ (t ) ае (t ) удовлетворяющего ограничениям 1)-4) и описывающего поведение системы посадки неоднородных самолетов. По этой причине моделирующий алгоритм в этой задаче был построен таким образом, что оценка критерия I Со А(цО) получается в результате рассмотрения на цифровой вычислительной машине [\]+ реализаций поведения процесса обслуживания самолетов только в промежутке между двумя последовательными векторными моментами регенерации. Значение параметра N предлагается выбирать из условия поступления в систему посадки за наблюдаемые реализации не менее некоторого фиксированного числа требований, т.е. здесь применяется стратегия Гринберга l-J-SOJ для оценки параметров системы массового обслуживания. В качестве иллюстрации рассмотрим теперь решение задачи о численном выборе параметров ЦТ , oL , ск уп-равляющего алгоритма cL Jx при функционировании аэропорта с несколькими взлетно-посадочными полосами, одной.системой посадки и в хороших метеорологических условиях. Пусть в среднем за сутки к зоне управления посадкой условно-пуассоновским образом прибывают 144 самолета внутренней линии ( Х4 сам/мин =0.1 сам/мин) и 43 самолета международной линии ( Х2 сам/мин =0.03 сам/мин). Интенсивности потоков насыщения П и П 2 при посадке самолетов соответственно равны }ХА сам/мин =0.2 сам/мин и Ц2 сам/мин= = 7 сам/мин. В то же время техническое оборудование системы посадки и условия безопасности воздушного движения самолетов та-ковы, что vn = 2, v. = ц\ = 4, гГ = 28, I мин = I глин, ю. = 5, К, сам = II сам, N caM = 9 сам и 04сам = 2.94 сам. При сделанных допущениях из формулы (6.52) находим Т-Г = 85. За время имитационного моделирования при вычислении оценки J Со/-, Д((А )) прибывают более 6400 самолетов внутренней линии. Для определения такого размера выборки было использовано неравенство Че-бышева. Этот объем выборки гарантирует заданную точность , мин = =1,2 мин при доверительной вероятности 0.95. Путем сокращенного перебора вариантов были определены параметры ot - і и с = о, которым соответствует (Л (ц0- )- квазиоптимальный алгоритм oLM с точностью мин =1.2 мин имитационного моделирования. Алгоритму о( отвечает оценках СоС ДС )) мин среднего времени пребывания произвольного самолета в системе посадки при хорошей летной погоде, равная 33.6 мин. Для сравнения укажем значение этой оценки, равное 36.4 мин, которое соответствует алгоритму eL с числовыми значениями параметров = і/з и с = 0. Отсюда получаем, что 6 мин - -2,8 мин.
