Содержание к диссертации
Введение
Глава I. Методы расчета характеристик адаптирующихся систем массового обслуживания 13
I.I. Расчет характеристик адаптирующейся системы массового обслуживания с резервным прибором 13
1.2. Приближенный расчет характеристик адаптирующихся СМО с переменной интенсивностью обслуживания 30
1.3. Приближенный расчет характеристик адаптирующейся системы массового обслуживания динамическими приоритетами . 43
Выводы 57
Глава П. Оценка интенсивности входящего потока заявок и адаптивное управление системой массового обслуживания . 58
2.1. Автоматы-адаптеры для систем массового обслуживания 58
2.2. Адаптивная оценка интенсивности дважды стохастического пуассоновского процесса 73
2.3. Некоторые характеристики предложенных автоматов-адаптеров 93
Выводы - 105
Глава Ш. Имитационная модель и практическое использование результатов работы 106
3.1. Использование результатов работы 106
3.2. Имитационная модель адаптирующейся СМО 114
3.3. Описание программ 120
3.4. Анализ результатов численных расчетов 132
Выводы 155
Заключение 156
Литература., 164
Приложение , 177
- Расчет характеристик адаптирующейся системы массового обслуживания с резервным прибором
- Приближенный расчет характеристик адаптирующейся системы массового обслуживания динамическими приоритетами
- Адаптивная оценка интенсивности дважды стохастического пуассоновского процесса
- Имитационная модель адаптирующейся СМО
Введение к работе
Актуальность проблемы. Развитие вычислительных систем и систем передачи информации выдвинуло, проблему оптимизации их функционирования. Необходимость решения задач оптимального управления этими системами дала толчок новому направлению в теории массового обслуживания - управлению системами массового обслуживания J65j. Большинством авторов управляемая система массового обслуживания рассматривается в предположении, что все ее параметры заранее известны и не меняются со временем [65, 74]. Однако для реальных систем, т.е. наиболее интересных с точки зрения приложений, такое предположение не всегда справедливо. В такой ситуации естественно при управлении системой пользоваться адаптивным подходом [6IJ. Таким образом, возникает задача адаптации системы к меняющимся условиям с целью оптимизации ее функционирования. Ниже рассматриваются примеры таких систем. 1°. Вычислительные комплексы. Функционирование вычислительных комплексов хорошо описывается методами теории массового обслуживания и.является одним из основных ее приложений [Э, 30, 33, 52, 64, 67, 83]. Вычислительные комплексы работают в условиях неполной информации о внешней среде, т.е. потоках задач, предназначенных для решения [52, 63, 64, 83J. Во многих случаях параметры этих потоков заранее неизвестны либо меняются со временем, возможно, даже случайным образом. Более того, со временем могут меняться вероятностные свойства потока ЦэЗ]. В то же время структура вычислительного ком- плекса обычно позволяет осуществить перестройку элементов системы и, следовательно, открывает большие возможности для адапта ции. "Не будет преувеличением сказать, что будущие большие вычислительные комплексы и сети попросту не смогут существовать без мощного обеспечения алгоритмами адаптации, поддерживающими их в оптимальном состоянии независимо от изменений среды и самих вычислительных систем" L62J 2°. Системы обработки информации.
Система обработки информации отличается от обычного вычислительного комплекса лишь спецификой решаемых задач и, следовательно, для этой системы также актуальны проблемы, описанные выше [ч],
3°. Сети связи.
При проектировании сетей связи возникают задачи оптимального управления потоками и каналами связи. Для их решения широко используются модели.и методы теории массового обслуживания [29, 35, 43, 71, 92J. В реальных условиях управление сетью связи происходит в"условиях неопределенности. Параметры нагрузок заранее неизвестны, кроме того, через случайные интервалы времени могут выходить из строя отдельные узлы и линии связи. В этой ситуации для обеспечения эффективности функционирования сети необходимо использовать адаптивное управление сетью [в, 35, 71, 73].
Точный расчет характеристик адаптирующихся систем массового обслуживания является очень сложной математической задачей. В связи с этим возникает потребность в приближенных методах расчета.
Цель работы. При выполнении данной работы ставились следующие задачи:
I. Разработать методы приближенного расчета характеристик адаптирующихся систем массового обслуживания с резервными при борами или.переменными интенсивностями обслуживания.
2. Разработать метод приближенного расчета характеристик адаптирующихся систем массового обслуживания с динамическими приоритетами и с формированием очередей.
3. Предложить и исследовать автоматы-адаптеры для управления системой массового обслуживания в условиях неполной инфор-мации о входящих потоках. В случае, когда входящий поток описывается дважды стохастическим пуассоновским процессом, предложить и исследовать адаптивную оценку его интенсивности. Предложить метод расчета характеристик систем массового обслуживания, использующих данные способы адаптации.
4. Создать имитационную модель адаптирующейся системы массового обслуживания и комплекс программ, реализующих предложенные методы расчета характеристик системы.
5. Провести имитационное моделирование функционирования адаптирующихся систем массового обслуживания с целью проверки качества, приближения предложенных методов расчета.
Работа выполнялась в соответствии с разделом І.І2.І0.І.Г "Адаптивные системы управления", координационного плана НИР АН СССР по комплексной проблеме "Кибернетика" на 1982-1985 г.г. на проведение НИР "Разработка теории управляемых систем массового обслуживания".и в рамках хоздоговорной темы "Путь-ПТ", заключенной Сибирским Физико-Техническим институтом с организацией п/я A-I332.
Состояние проблемы. Изучение управляемых систем массового обслуживания (ОАО) началось в конце 60-х г.г. Понятие управляемой СМ0 было введено О.И.Бронштейном и В.В. Рыковым L9J- Система массового обслуживания задается Ц элементами: входящими потоками требований, механизмом и длительностями обслуживания, структурой системы, дисциплиной обслуживания. В управляемой СМО эле менты системы допускают применение управляющих воздействий. Большинство авторов рассматривают управляемую СМО и решают задачи оптимального управления ею в предположении, что параметры потоков и состояние системы в каждый момент времени известны. В этих предположениях решен ряд задач об оптимальном (в смысле некоторого критерия качества, например, минимизации определенной функции потерь) выборе параметров обслуживания [2, 7, 14, 91, 96, 98, IIIJ. Параметр обслуживания может принимать несколько фиксированных значений [2, 98либо изменяется в ограниченном интервале [_9I, IHJ. Задачи оптимального включения резервного прибора решались в [8, 21, 79, 80, 85, 90, 105].
В случае, когда параметры входящих потоков неизвестны либо изменяются со временем, для управления системой необходимо использовать адаптивный подход (,52, 61, 62, 63, 64]. В настоящее время работ по адаптирующимся СМО опубликовано мало (автору известно не более 30). Большинство авторов для адаптивного управления системой использует вероятностные автоматы [10, 76J либо произвольные автоматы-адаптеры. Вопросы назначения оптимальных приоритетов с помощью вероятностных автоматов изучались в [10, II, 27, 42, 45, 60, 68]. В работах [22, 34, 45-49] вероятностные автоматы использовались для адаптации интенсивности обслуживания [24, 45, 48, 49], управления включением резервного прибора [22, 46], диспетчеризации входящих потоков j2, ІЗ, 19, 34, 47, 48]. Оптимальность предложенных алгоритмов адаптации доказывалась либо на основе свойств используемых автоматов [45-48, 68J, либо результатами моделирования на ЭВМ [10, II, 13, 24_].
В случае, когда оптимальное управление системой в условиях полной информации определяется лишь параметрами потоков и обслуживающих приборов, естественно определять управление, используя вместо истинных значений параметров их оценки на данный момент _ [l7, 18, 20, 21j. Полученное управление будет оптимальным, если оценки параметров сходятся к истинным значениям.
Адаптивные алгоритмы управления СМО в байесовской ситуации предложены и исследованы в \2Х, 50, II0J. В работах \1, 35, 37, 53, 54, 58, 64, 77, 83, 89, I07J предлагались и исследовались различные алгоритмы адаптации в системах массового обслуживания.
Во всех цитированных выше работах по адаптации в СМО не было получено в явном виде ни одно.й. характеристики адаптирующейся системы массового обслуживания. В случае, когда эти характеристики входили в функцию потерь, для них использовались приближенные выражения ви где SCj характеристика системы при реализации і -ой структуры» Pi вероятность реализации этой структуры- Формулы такого вида использовались, например, для вычисления среднего времени ожидания заявок [53 J. Получить точные явные выражения характеристик адаптирующихся СМ О не представляется возможным в силу сложности этой задачи. В самом деле, поведение числа заявок в системе описывается случайным блужданием по ft, ч-іерной целочисленной решетке, а даже исследование случайных блужданий-на плоскости сопряженно с очень большими математическими трудностями _40, WJ. Вместе с тем при анализе адаптирующихся СМО желательно пользоваться более точными формулами, чем (13.
Необходимо отметить работы, посвященные СМО, управляемым случайными процессами. Именно, параметры входящих потоков и обслуживающих приборов таких систем (или сами законы распределения длительностей обслуживания и интервалов между приходами заявок) зависят от состояния некоторого дискретного случайного процесса. Хотя авторы этих работ не касаются вопросов адаптации в СМО, задача расчета характеристик адаптирующихся СМО очень близка задаче расчета характеристик подобных систем. В ряде случаев можно непосредственно перенести результаты этих работ на случай адаптирующихся СМО,задав определенным образом управляющий процесс.
Система M/M/I, управляемая марковской цепью с конечным числом состояний, рассматривалась в [ЭО, 87, 97, 100, I03j. Получены условия существования стационарного режима [102, ЮЗ]. В случае, когда управляющая цепь Маркова содержит всего 2 состояния, найдены распределение числа заявок в системе и средняя длина очереди [87, 97J. В этом же случае (2 состояния управляющей цепи) найдена средняя длина очереди и для системы M/G-/I [55]. Система М/(гА, управляемая марковской цепью, изучалась также в [82, 99, 104J. В работе [59] предложен метод расчета средней длины очереди в системах массового обслуживания, управляемых особого вида полумарковским процессом. В работах [72, 88, I08J изучалась СМО с несколькими входными потоками и прибором, пере-ключающимся с обслуживания одной очереди на другую по произвольным законам,
Для приближенного анализа СМО в условиях большой загрузки (т.е. при близкой к нулю вероятности простоя приборов) часто используется аппроксимация длины очереди диффузионным случайным процессом [21, 30, 51, 93, 94]. В частности, с использованием диффузионной аппроксимации получены приближенные формулы для характеристик систем U/0-/I [9] и M/G/I/W[93], управляемых марковской цепью с конечным числом состояний,
Одной из возможных моделей входящего потока реальной системы является дважды стохастический пуассоновский процесс, т.е. пуассоновский процесс, интенсивность которого является случайным процессом. Для адаптивного управления системой массового обслуживания, на которую поступает такой поток заявок, необходимо иметь на каждый момент времени оценку интенсивности этого потока. Уравнения для оптимальной в среднеквадратическом оценки интенсивности дважды стохастического пуассоновского процесса были получены в работах [78, 86, I06J однако решить эти уравнения не представляется возможным в силу их сложности. Задача об обнаружении момента разладки пуассоновского процесса решалась в [55, 57, I09J. Кроме этого, различные вопросы, связанные с оцениванием интенсивностей два?кды стохастических пуассоновских процессов и полей рассматривались в [81, 84, 95, IOl].
Содержание работы. В первой главе предлагаятоя и рассматриваются методы приближенного расчета характеристик адаптирующихся СМО. В первом параграфе предложен метод расчета стационарного распределения числа заявок в адаптирующейся однолинейной СМО с резервным прибором. Рассмотрены также модификации метода, учитывающие инерционность процесса на выходе адаптера. Во втором параграфе предложен метод приближенного расчета средней длины очереди в адаптирующихся СМО с.переменными интенсивностями обслуживания. Метод обобщен на случай многолинейной адаптирующейся СМО с резервными приборами и переменными интенсивностями обслуживания. В третьем параграфе предложен метод приближенного расчета характеристик адаптирующихся СМО с динамическими приоритетами или с формированием очередей.
Во второй главе предлагаются и исследуются способы оценки интенсивностей входящих потоков заявок. В первом параграфе предлагается четыре автомата-адаптера и найдено для каждого из них стационарное распределение вероятностей состояния, а также рас сматривается их применение в адаптирующихся СМО. Во втором параграфе предлагается и исследуется адаптивная оценка интенсивности дважды стохастического пуассоновского процесса. В третьем параграфе определяются параметры предложенных автоматов-адаптеров и адаптивной оценки интенсивности потока, необходимые для расчета характеристик адаптирующихся СМО, в которых рни используются.
В третьей главе рассматривается техническая реализация методов, предложенных в первых двух главах. В первом параграфе Ьписано применение методов приближенного расчета адаптирующихся СМО для расчета характеристик системы обработки информации. Во втором параграфе предлагается имитационная модель адаптирующейся СМО. В третьем параграфе дано описание программы имитационного моделирования и программ, реализующихс предложенные методы расчета характеристик адаптирующихся СМО. В четвертом параграфе приведен анализ рещультатов, полученных при расчете характеристик адаптирующихся СМО по предложенным методам, и при имитационном моделировании.
Методика исследования. Для решения задач расчета характеристик адаптирующихся СМО и автоматов-адаптеров использовались методы теории массового обслуживания, теории случайных процессов. Для проверки полученных результатов проводилось имитационное моделирование на ЭВМ.
Научная новизна. I. Впервые разработаны методы приближенного расчета характеристик адаптирующихся систем массового обслуживания с резервными приборами, переменными интенсивностями обслуживания, динамическими приоритетами. Методы годятся для широкого класса адаптеров.
2. Предложено: несколько автоматов-адаптеров для адаптивного управления системой массового обслуживания. Исследованы их характеристики и применение в адаптирующихся ОНО,
3. Предложена и исследована адаптивная оценка интенсивности дважды стохастического пуассоновского процесса.
Практическая ценность. Предложенные методы могут использоваться для расчета характеристик вычислительных комплексов, систем обработки информации, сетей связи. Для расчета характеристик этих систем может использоваться также предложенная имитационная модель адаптирующейся СМО. Для адаптации к входящим потокам заявок в реальных системах можно использовать предложенные автором автоматы-адаптеры. Предложенные методы расчета характеристик адаптирующихся СМО и имитационная модель адаптирующейся СМО реализованы в виде программ на языках F0RTR/\V-iy и PL/1 и были использованы для расчета характеристик системы обработки информации, разрабатываемой в п/я A-I332. Эти программы были переданы п/я A-I332 в соответствии с хоздоговрной темой иПуть-ПТ" и используются там для расчета, характеристик разрабатываемых систем обработки информации.
Публикация. По тематике диссертации опубликовано 9 печатных работ [пг-іго]. Материалы диссертации.были также изложены в отчетах по госбюджетной НИР и хоздоговорной НИР, выполняемым в Сибирском $изико-Техкическом институте:
1. Управляемые и адаптивные системы массового обслуживания. Отчет (промежуточный) по НИР "Разработка управляемых систем массового обслуживания" (шифр "УСМ0")./СФТИ, руководитель НИР Горцев A.M., }Ь ГР 0I82506III2. - Томск, 1981. - 212 с. (Депонирован в ВНТИЦ, инв. № 02320080543).
2. Управляемые и адаптивные системы массового обслуживания Отчет (промежуточный) по НИР "Разработка теории управляемых систем массового обслуживания" (шифр "УСМО О./СФТЙ, руководитель НИР Горцев A.M., №.ГР 0І82506Ш2. - Томск, 1983. - 92 с.
3. Разработка алгоритмов управления потоками зявок в многомашинной вычислительной системе. Отчет (промежуточный) по НИР "Путь-ПТ-І /СФТИ, руководитель НИР Горцев A.M., № ГР 0I824037D74.-Томск, 1982. - 234 с.
4. Разработка алгоритмов управления потоками заявок в многомашинной вычислительной системе. Отчет (заключительный) по НИР "Путь-ПТ"./СМИ, руководитель НИР Горцев А.М.",№ ГР 0I824037D74.-Томск, 1983. - 186 с.
Апробация работы. Основные положения диссертации и отдельные ее результаты- докладывались и обсуждались:
1. На П-ом Всесоюзном совещании-семинаре "Оптимизация динамических систем" (г.Минск, сентябрь, 1980 г.).
2. На областном семинаре "Математические методы в задачах управления" (г.Пенза, май 1981 г.).
3. На Всесоюзном научно-практическом семинаре "Прикладные аспекты управления сложными системами" (г.Кемерово, март 1983г.).
4. На Всесоюзной конференции "Теория адаптивных систем и ее применения" (г.Ленинград, май 1983 г.).
5. На УЇЇ семинаре по проблемам непрерывности и устойчивости стохастических моделей (г.Саратов, июнь 1983 г.).
6. На ХП Всесоюзной школе-семинаре по адаптивным системам (г.Могилев, январь 1984 г.).
7. На симпозиуме "Математическое обеспечение для автоматизации исследований, идентификации и планирования эксперимента" (г.Харьков, февраль 1984 г.).
Расчет характеристик адаптирующейся системы массового обслуживания с резервным прибором
Рассмотрим систему массового обслуживания с двумя обслуживающими приборами и одним входящим потоком. Поток предполагается простейшим, с неизвестной интенсивностью А. Заявки по прибытии в систему образуют очередь с неограниченным числом мест для ожидания. Один из обслуживающих приборов работает постоянно (если в системе есть заявки), другой включается лишь в определенные моменты времени. Время обслуживания распределено по экспоненциальному закону, с параметром jut для основного прибора и с параметром J&2 для резервного. Поскольку интенсивность входящего потока Я в системе неизвестна, для управления включением и выключением резервного прибора предлагается использовать адаптер, каким-то образом оценивающий Л. Не конкретизируя структуру адаптера, примем следующую модель его работы. Если в системе есть ожидающие обслуживания заявки, адаптер включает резервный прибор с интенсивностью о (т.е. время работы между последним выключением и включением резервного .прибора распределено по экспоненциальному закону с параметром об ). Выключение резервного прибора происходит с вероятностью О в момент окончания им обслуживания. Соответственно с вероятностью р- 1-0 резервный прибор берет на обслуживание очередную заявку. Если заявок в системе нет, резервный прибор выключается. Стохастический граф переходов, соответствующий данной системе, изображен на рис. I.I.I.
Состояние системы будем характеризовать парой чисел ( , /), где у- число заявок в системе, / I, 1-І, если резервный прибор отключен, і-=2, если резервный прибор включен. (0,0) обозначим состояние, когда в системе нет заявок. Тогда для стационарных вероятностей состояния r(.i,f) имеют место следующие уравнения:
Выражая из обеих уравнений С и приравнивая полученные выражения, получим для определения і уравнение
Легко заметить, что z =1 является корнем этого уравнения. Сокращая (ІЛЛІ) на ( - I), получим (& +/ /4 (1 1Л2)
Решение системы (1,1,1)-(1.1.8) существует, если ровно 2 корня уравнения (I.I.I2) лежат в интервале (0,1). По правилу Декарта уравнение (І.І.Ї2) имеет 3 положительных корня. Далее, J-(0)=-# Ws4We6l" tt )+ol( / , r/(J ля существования решения необходимо 7(4) О - Это выполняется при
Заметим, что условие (І.І.ІЗ) переходит в случае 0=0 или U Ов (т.е. когда постоянно работает резервный прибор) в условие а в случае cL O (т.е. когда резервный прибор не включается) в условие Исходя из этого, можно сделать вывод, что для существования стационарного режима работы системы необходимо выполнение условия (1.1.13). Обозначим 2f и корни уравнения (I.I.I2), лежащие в ин тервале (ОД). Тогда решение системы (1.1.1)-(1.1.8) записывает ся в виде . Р( ,к)-АХ\+АЛГ ,j CIII3) где Сі находятся из уравнений (І.І.ІО) после подстановки в них іСі-=1,2). АІ , Ае " неизвестные постоянные, которые вместе с вероятностями (0,0), P(X,I\ / (2,1) определяются из уравнений (1.1.2)-(1.1.5) и условия нормировки (I.I.8).
Недостаток описанного выше метода расчета характеристик адаптирующихся СМО с резервным прибором заключается в том,- что он не учитывает инерционность процесса на выходе адаптера при близких к нулю вероятностях того, что включен либо выключен резервный прибор. Пусть вероятность того, что резервный прибор в произвольный момент времени не обслуживает, близка, к нулю. Учесть инерционность процесса на выходе адаптера можно» уменьшая вероятность выключения резервного прибора Ц с увеличением времени его беспрерывной работы, т.е. задать Of q(i.) , где время С- отсчитывается от момента последнего включения резервного прибора и Я if) - неубывающая функция. Однако в этом случае процесс перехода системы из состояния в состояние, очевидно, перестает быть марковским. Таким образом, учесть время работы резервного прибора можно лишь косвенно. Это.можно сделать тремя способами:
1) по числу заявок, обслуженных резервным прибором с момента его последнего включения;
2) по числу заявок, поступивших за время работы резервного прибора;
3) по числу заявок, обслуженных основным прибором за время работы резервного прибора.
Приближенный расчет характеристик адаптирующейся системы массового обслуживания динамическими приоритетами
-Рассматривается система массового обслуживания с одним обслуживающим прибором и двумя входящими потоками. Входящие потоки -простейшие, с параметрами Ц и #з По прибытии в систему заявки каждого потока образуют свою очередь. Обозначим длины очередей в момент Z соответственно 1(т) и ($). Обслуживающий прибор подключается к обслуживанию той или иной очереди по следующему правилу: если в момент t j(i) ty(i( c)}d( t))1 то прибор обслуживает 1-й поток, если J() Щ (i-WfdCt)) , то второй. Ы(4)-состояние адаптера в момент t , Q(&,%) - произвольная непрерывная и неубывающая по ОС функция. Обслуживание экспоненциальное, с параметром Ш для заявок І -го потока.Аналогичные рассуждения можно провести для случая, когда границей раздела областей / и $г является произвольная функция {/= 6j(Xjat) . Формулы для этого случая полностью аналогичны приведенным выше, но гораздо более громоздки. В частности, для произвольной 6j(x,oC) не берутся интегралы (1.3.0»(1.3.5).
В случае, когда процесс о() непрерывен, можно предложить несколько методов приближенного расчета плотности распределения /5(аг»у) в зависимости от характера изменения 0 (І). В самом общем случае, считаем oC(t) диффузионным процессом с постоянным коэффициентом диффузии и коэффициентом сноса $(t). Уравнение ФоккераЧІланка для совместной стационарной плотности распределения fl(X,V,oO В области R имеет вид
Поскольку система рассматривается в случае больших загрузок, то можно пренебречь величинами порядка О (i-p) . Уравнение принимает вид
Делая в этом уравнении замену получим, что ty{.o( ,% ,S} удовлетворяет обыкновенному дифференциальному уравнению второго порядка
Однако получить решение отого уравнения в явном виде когда в нем фигурирует произвольная функция $(и), не представляется возможным. Функция p(cL) , исходя из физического смысла задачи, должна удовлетворять следующим очевидным ограничениям:
Подобрать такую функцию р (Ы), которая удовлетворяла бы этим ограничениям, и позволяла в.;явном виде получить решение уравнения (1.3.8) в достаточно простой форме, не удалось. В простейшем случае уравнение (1.3.8) сводится к гипергеометрическому [H5J и k= m=-f/jjt Міс т() - функция Гигеккера [б9]. Таким образом, даже в этом простейшем случае /э(х, ,оО получить в явном виде не удается, т.к. сложность выражения (1.3.9) делает невозможным нахождение из граничных условий и условий сшивания неизвестных функций \ff (tf)} 9 (%
Пусть cl( b) изменяется медленно, так, что точка (эс} у) , соответствующая состоянию системы, успевает "догнать" перемещающуюся в соответствии с изменением с&() границу раздела областей
Если граница раздела задается уравнением Q&fQ()-if то это накладывает на приращение процесса Ы(6) за время 4о(р при малых S ограничение
Неравенство: (1.3.10) должно выполняться для любых неотрицательных X. и oL .
При этих предположениях можно определить плотность распределения /)(#, г) следующим образом: вначале найти условную плотность распределения pfa, U \ of ) ,ф а за.тем усреднением по Ы-найти интересующую нас Р ")- Пусть,для простоты, Cj(,d)-dSC. Обозначим Cf(o ty)=р(х, и/ ) и воспользуемся для ее отыскания методом пограничного слоя 51].
Адаптивная оценка интенсивности дважды стохастического пуассоновского процесса
Одной из моделей входящего потока реальной системы является дважды стохастический пуассоновский процесс, т.е. пуассоновский процесс, интенсивность которого является случайней процессом, В данном параграфе предлагается и исследуется адаптивная оценка интенсивности такого процесса, которая может использоваться для управления системой.
Пусть поступающий в систему массового обслуживания поток заявок - пуассоновский, с интенсивностью Я[) . Я(т) -стационарный в широком смысле случайный процесс. Возьмем оценку Л (t) в виде Act) На а ) где ifc - с ц &() - некоторая непрерывная функция. Здесь І - текущий момент времени, , ОТ} ... - моменты прихода заявок; перенумерованные в порядке удаления от момента t . Обозначим ЭТО неоднородное уравнение типа Винера-Хопфа, которое решается обычными методами [4 fJ,
Итак, для определения оптимальным образом функции О. (Z-) нам необходимо знать ftl и R GS ). В ситуации, когда они заранее неизвестны (которая наиболее вероятна на практике), предлагается вначале строить их оценки на интервале о(ТЗ »" а затем подставлять их в (2.2.2). Полученная в результате решения этого уравнения функция dT(i:) будет, вообще говоря, случайным про-цессом. Возьмем на СО;ТД вспомогательную функцию:
7
Имитационная модель адаптирующейся СМО
Для проверки результатов, полученных теоретически, а таюяе для подсчета характеристик адаптирующихся СМО в более сложных ситуациях (например, для рекуррентных потоков или произвольных законов распределения времени обслуживания) необходимо иметь имитационную модель системы. Ниже предлагается один из возможных вариантов такой модели, подсчитывающей длины очередей в системе и время пребывания заявок в системе (методов расчета времени пребывания заявки в адаптирующихся системах массового обслуживания пока не существует). Моделируется СИ0 с произвольным числом входящих потоков и обслуживающих приборов. Законы распределения времени обслуживания и интервалов времени между приходами заявок могут быть произвольными. На каждом потоке работает адаптер, который в зависимости от заданного режима его работы задает дисциплину обслуживания в системе либо параметры обслуживающих приборов. Заявки каждого потока по прибытии в систему образуют свою очередь и берутся на обслуживание в порядке поступления. Приборы могут переключаться с потока на поток как с прерыванием обслуживания заявки, находящейся в данный момент на приборе, так и без прерывания. Недообслуженные заявки остаются в системе и берутся на обслуживание в первую очередь. Первый входящий поток является вспомогательным, в моменты прихода заявок этого потока запоминается число заявок каждого потока в системе для последующей статистической обработки. Окончание моделирования происходит, когда в систему пришло по меньшей мере N заявок каждого потока.
Блок-схема модели приведена на рис. 3.2.1. Модель использует следующие внутренние переменные I. Моменты наступления очередного события, а именно:
- моменты прихода следующей заявки каждого потока ;
- моменты окончания обслуживания каждым прибором заявки, находящейся в данный момент на приборе t)i ;
- моменты следующего перехода внутри каждого адаптера J-K .
2. Время прибытия и время пребывания в системе для каждой заявки.
3. Длины очередей.
4. Номера недообслуженных заявок, ожидающих повторного взятия на обслуживание.
5. Номера заявок, находящихся на обслуживании.
6. Число заявок, пришедших в систему, для каждого потока.
7. Номера заявок, стоящих первыми в очередях.
8. Действующая дисциплина обслуживания (для каждого прибора -номер потока, заявки которого он обслуживает).
9. Необходимая или "адаптивная" дисплина обслуживания - та, кото- -руго необходимо установить в данный момент времени согласно состояниям адаптеров. Если приборы переключаются с потока на поток с прерыванием обслуживания заявки, стоящей на приборе, то адаптивная дисциплина обслуживания совпадает с действующей.
10. Текущий момент времени t .
11. Состояние каждого прибора на данный момент времени ("занят", "свободен", или "отключен").
12. Состояние каждого адаптера.
Рассмотрим более подробно каждый из блоков модели и принцип ее работы.
В блоке задания начальных значений задаются начальные значения внутренних переменных и вводятся необходимые внешние данные (законы распределения и их параметры, параметры и типы адаптеров, дисциплины обслуживания и параметры приборов, которые задают адаптеры, число входящих потоков и обслуживающих приборов, и т.д.). Для задания моментов прихода первых заявок каждого потока и моментов первого перехода внутри каждого адаптера происходит обра - 117 щение к блоку генерации случайных чисел.
Входом блока генерации случайных чисел является закон распределения (или такая информация о нем, что блок может выработать случайное число, распределенное по данному закону, с достаточной степенью точности) и его параметр. Выходом блока является случайное число f . Методы его получения определяются физической реализацией модели.
В блоке выбора очередного события осуществляется выбор текущего момента времени t по правилу
Выходом блока являются новое значение текущего момента времени , название события, происшедшего в этот момент времени и информация о нем, а именно:
- для события "приход заявки" - номер потока и порядковый номер заявки, пришедшей в систему;
- для события "конец обслуживания" - номер прибора, номер заявки, которую он обслужил, номер потока, которому эта заявка принадлежит;
- для события "переход адаптера" - номер адаптера, в котором произошел переход из состояния в состояние. В зависимости от характера события происходит переход в какой-то другой блок, обрабатывающий тип события.
Блок обработки события "приход заявки" осуществляет следующие действия:
- увеличиваются на I длина соответствующей очереди и число заявок данного потока, пришедших в систему;
- запоминается время прибытия данной заявки;
- генерируется момент времени прихода следующей заявки данного
- потока по формуле для чего происходит обращение к блоку генерации случайных чисел;
- если пришла заявка первого потока, то запоминается число заявок каждого потока в системе;
- если число пришедших заявок достигло заданного уровня, происходит переход к блоку обработки результатов; в противном случае происходит переход в блок "адаптер" по событию "приход заявки".
Блок обработки события "конец обслуживания" осуществляет следующие действия:
- вычисляется время пребывания обслуженной заявки в системе;
- действующая дисциплина обслуживания для данного прибора сравнивается с адаптивной и, если это необходимо, изменяется;
- в соответствии с действующей (и, возможно, измененной) дисциплиной обслуживания изменяется состояние прибора ("занят" заменяется на "свободен" или "отключен").
Затем происходит переход на блок взятия заявок на обслуживание.
