Общая характеристика изучаемой темы.
Теория массового обслуживания строит и изучает математические модели возникновения очередей из заявок требований в системах, используя для этого аппарат математической кибернетики, теории вероятностей, марковских точечных процессов и математической статистики. Появление теории массового обслуживания исторически связано с необходимостью рассмотрения простейших задач о задержке вызовов в телефонных системах. Такие задачи впервые были описаны на физическом уровне в 1907 г. в работе Ф.В. Ио-ханнсена [1] и частично решены датским математиком А. К. Эрлангом [2]. Именно работы А. К. Эрланга, выполненные в 1909, 1917 и 1923 годах и посвященные построению и изучению математической модели работы автоматических телефонных станций, стали пионерскими в теории массового обслуживания.
Фундаментальные результаты в области теории массового обслуживания были получены в XX веке такими учеными как: Ф. Поллачек, А. Н. Колмогоров, А. Я. Хинчин, Б. В. Гнеденко, Л. Такач, T.JI. Саати, Д. Р. Кокс, У. Д. Смитл, JI. Клейнрок, С. Н. Бернштейн, К. Пальм, Д.Дж. Кендалл, B.C. Королюк, А. Кофман. С точки зрения практической ценности важное место в этой области занимают работы Г. П. Башарина, Ю. К. Беляева, А. А. Боровкова, Н. П. Бусленко, О. В. Вискова, В. М. Золотарева, Г. П. Климова, И. Н. Коваленко, Ю. В. Прохорова, А. Д. Соловьева и др. Основные результаты данных авторов представлены во многих работах, например [3—11].
В ходе становления и развития теории массового обслуживания, а также ее приложений можно условно выделить несколько основных направлений исследований.
Первое направление образуют исследования классической системы массового обслуживания с ожиданием или с потерями, а также различных ее усложнений [12—22]. Напомним, что любую классическую систему массового обслуживания определяют три её составляющих элемента: входной поток, обслуживающее устройство, структура и дисциплина очереди. Исследования по данному направлению связаны в основном с рассмотрением более сложного закона распределения промежутка между последовательными поступлениями требований, более сложного закона распределения длительности обслуживания и, наконец, с рассмотрением более сложной структуры системы (когда задействованы несколько приборов разной производительности, имеется некоторое число ненадежных обслуживающих приборов, введены ограничения на размер очереди, существуют ограничения на время ожидания и на время пребывания требований в системе и т. п.).
Второе направление составляют исследования управляемых систем при обслуживании идентичных требований [23—30]. Данное направление исследований касается систем с изменяемой структурой входного потока требований, систем с управляемым механизмом и длительностями обслуживания, с изменяемым механизмом формирования очереди, систем с управляемой дисциплиной обслуживания и т. п. Общее понятие управляемой системы обслуживания было введено О. И. Бронштейном и В. В. Рыковым. Целью управления в таких системах является оптимизация самых разнообразных параметров, например, среднего числа требований в системе в произвольный момент времени, среднего времени пребывания требований за такт работы системы, т. д. Обзор результатов по управляемым системам массового обслуживания содержится в [31].
В третье направление выделяются исследования процесса обслуживания неоднородных требований [32—47]. Данное направление касается систем с разделением времени, циклических систем, приоритетных систем и т. п.
Исследованию систем с разделением времени посвящены, например, работы [32—34]. Среди работ, посвященных изучению циклических систем массового обслуживания можно отметить следующие [35—43].
Результаты исследования приоритетных систем собраны в [44—48]. Системы приоритетного обслуживания вызывали и вызывают большой интерес. Это в первую очередь связано с тем, что в реальных системах обслуживания присутствуют требования различных типов, например, по характеристикам длительности обслуживания, или по стоимости ожидания в очереди. Задачи, в которых следует принимать в расчет преимущественные требования, встречаются постоянно: междугородний вызов прерывает местный телефонный разговор, к зубному врачу вне очереди принимаются больные с острой зубной болью, самолеты международного класса пользуются преимуществом при посадке, задерживая местные авиарейсы. В последнее время появляются новые исследования в области систем с так называемой «орбитой», на которую отправляются требования, заставшие прибор занятым. Такие требования в случайные моменты времени обращаются с повторными попытками занять прибор и в случае неудачи возвращаются на орбиту. Например, такая система рассматривается в [49].
И, наконец, четвертое направление образуют исследования алгоритмов управления потоками в системах с переменной структурой. Данное направление исследований представляется особенно важным, поскольку именно системы с переменной структурой математически описывают поведение сложных реальных процессов обслуживания с управлением в условиях воздействия случайных факторов. В то же время теория систем с переменной структурой обслуживания потоков посвящена одному из ключевых вопросов общей теории управляемых случайных процессов — проблеме изучения предельных свойств условных распределений дискретных многомерных управляемых случайных процессов специфического вида.
Первые упоминания о результатах исследований простейших моделей систем с ожиданием, в которых динамическое поведение обслуживающего устройства описывается однородным марковским процессом с конечным числом состояний, приводится в работе Парадью [43]. В этих моделях при изменениисостояния обслуживающего устройства происходит изменение интенсивностей поступления и обслуживания требований. Рассматривая процесс обслуживания в таких системах поочередно на промежутках занятости и незанятости, Парадью изучил свойства переходного режима и определил условия существования стационарного движения. Входной поток требований при этом предполагался пуассоновским, а обслуживание заявок — экспоненциальным. Неутс [50] проанализировал подобную систему обслуживания с неэкспоненциальным обслуживанием в предположении, что закон распределения длительности обслуживания каждой заявки не изменяется в процессе обслуживания. В работе Джоэла [51] изучена система с ограниченной очередью, в которой динамика обслуживающего устройства описана условным марковским процессом с двумя состояниями. Вероятностные характеристики переходов между этими состояниями зависят от величины очереди, интенсивность пуассоновского потока заявок и интенсивность экспоненциального обслуживания.
При попытках рассмотреть задачи об управлении потоками требований в системах обслуживания с более сложными структурными изменениями, возникали значительные трудности. В работах Г. П. Климова [52, 53] были рассмотрены вопросы управления независимыми пуассоновскими потоками в системе, в которой допускается неограниченная очередь по любому из потоков. Поведение обслуживающего устройства с течением времени описывается условной марковской последовательностью с конечным числом состояний, равным числу входных потоков заявок. Состояние обслуживающего устройства изменяется в моменты завершения обслуживания требований. Переходные вероятности марковской цепи специальным образом связаны с длинами очередей по каждому из потоков в момент завершения обслуживания. В каждом состоянии обслуживающего устройства разрешено обслуживание требований только из одной определенной очереди. Случайные продолжительности обслуживания требований определяются произвольным законом распределения при конечных значениях двух первых моментов, причем этот закон распределения задается лишь номером состояния обслуживающего устройства. Длительности обслуживания заявок предполагаются независимыми между собой и от входных потоков требований. При определенном состоянии обслуживающего устройства уже обслуженное требование либо направляется в некоторую очередь с вероятностью, зависящей от этого состояния и номера выбранной очереди, либо навсегда покидает систему с вероятностью, зависящей только от указанного состояния. В предположении известной стоимости единицы времени ожидания в каждой очереди одной заявки в [53] предполагается некоторый алгоритм вычисления средних расходов на ожидание заявки в единицу времени в стационарном режиме. При этом оказывается возможным найти по некоторому рекуррентному правилу оптимальные вероятности переходов условной цепи Маркова, которые минимизируют средние потери на ожидание заявок в стационарном режиме. Другие модели задач об управлении потоками заявок в системах с определенными структурными особенностями обслуживающего устройства стали разрабатываться сравнительно недавно. Эти модели в той или иной мере объединяют особенности моделей [49, 52], а исследование в таких задачах, как правило, осуществляется в рамках подхода [52, 54].
К числу первых публикаций, в которых исследуется проблема алгоритмического управления потоками! заявок, и при этом учитываются структурные изменения устройства обслуживания, принадлежит цикл работ М. А. Федоткина [55—57]. Общий подход к анализу и оптимизации систем обслуживания с переменной структурой изложен М.А. Федот-киным в докторской диссертации [58].
Особое внимание среди приложений теории систем обслуживания с переменной структурой занимают задачи о регулировании дорожного движения, что связано с разработкой реальных автоматизированных систем управления транспортом. Актуальность этих задач обусловлена постоянно возрастающим парком автомобилей во всем мире и возникающими в связи с этим весьма острыми экономическими, экологическими и социальными проблемами. К настоящему времени разработано большое число всевозможных алгоритмов управления конфликтными потоками автомобилей на перекрестках. Среди них наиболее известны алгоритмы Данна-Потса [59], Гордона [60], алгоритмы с поиском разрыва [61], алгоритмы управления с прогнозом [62, 63], алгоритмы с жестким переключением [64], а также ряд однородных алгоритмов с обратной связью [65—68]. В работах [65, 69, 70] определены условия существования статистической устойчивости систем управления потоками транспорта, предложены методики определения оптимального управления обслуживанием конфликтных потоков, основанные на итеративных методах Ховарда и Уайта-Швейцера, и изучены свойства оптимального управления. Анализ процессов управления конфликтными потоками для нескольких классов однородных алгоритмов содержится в работах М. А. Федоткина [71—75]. Представляют интерес также работы [76—78] в связи с использованием в них нетрадиционных показателей качества работы системы, называемых функционалами Чжуна, с помощью которых возможно эффективное решение задач оптимизации систем обслуживания с переменной структурой в условиях большой загрузки. Среди известных методов численной оптимизации систем управления дорожным трафиком следует отметить метод Вебстера [79, 80], основанный на эмпирической формуле расчета средних задержек произвольной машины на перекрестке, метод Алсопа [81, 82] и метод имитационного моделирования [83].
Последние годы внимание математиков к теории массового обслуживания в значительной степени стимулировалось необходимостью применения результатов этой теории к важным практическим задачам, возникающим в связи с бурным развитием систем коммуникаций, возникновением информационно-вычислительных систем, появлением и усложнением разнообразных технологических систем, созданием автоматизированных систем управления. Первоначально у ученых интерес вызывал входной поток системы массового обслуживания, характеристики которого исследовались для наиболее простого описания функционирования реальных систем массового обслуживания. Позднее изучался закон обслуживания заявок входных потоков системы. На сегодняшний день уже подробно изучены разнообразные стохастические модели реальных систем и характеристики их функционирования. В современной теории массового обслуживания одним из наиболее актуальных и перспективных направлений является изучение выходных потоков, возникающих в системах массового обслуживания. Первые попытки исследования выходных потоков были сделаны в 60-е годы XX века такими математиками, как Берк [84], Коэн [85], Рейч [86] и Финч [87].
Берк показал, что для стационарного состояния системы MIMIC промежутки времени между требованиями, покидающими систему, взаимно независимы. При этом длительность случайных промежутков времени между моментами, когда требования покидают систему, не влияет на состояние системы в конце этого промежутка. Также, им была доказано следующее утверждение. В системе с п параллельными каналами, пуассоновским входным потоком с параметром Л и одинаковым для каждого канала показательным распределением времени обслуживания с параметром /л в стационарном режиме работы системы выходной поток имеет пуассоновское распределение с параметром Л.
Рейч, используя другие методы, пришел к следующему выводу. Если промежутки времени между требованиями, поступающими в одноканальную систему, и промежутки времени их обслуживания распределены по нормированному закону? с четырьмя степенями свободы, то распределение промежутков времени между требованиями, покидающими систему, не подчиняется закону? с четырьмя степенями свободы. Таким образом, в общем случае выходной поток не будет совпадать с входным потоком даже в стационарном состоянии. Кроме того, в случае одноканальной системы с пуассоновскими входным и выходным потоками Рейч показал, что время обслуживания либо равно нулю с вероятностью единица, либо имеет экспоненциальное распределение. Фактически эта теорема является обратной к теореме Берка.
Финч в свою очередь доказал, что выходной поток будет пуассоновским только в том случае, когда допускается очередь бесконечной длины. Условия на неограниченную очередь, и экспоненциальное время обслуживания являются необходимыми и достаточными для того, чтобы промежутки времени между требованиями в выходном потоке были независимыми.
Попытки изучения свойств выходных потоков продолжаются. Например, в работе [88] найдено распределение числа требований, обслуженных за период занятости в стационарной системе Geom/Geom/1 с дискретным временем. Сделана попытка обобщить полученные результаты на случай непрерывного времени.
Работа [89] посвящена исследованию асимптотики хвостов распределения интервалов между выходами заявок из системы массового обслуживания в случае, когда распределения интервалов между приходами заявок и времен обслуживания заявок являются субэкспоненциальными. Показано, что данная асимптотика в основном определяется более тяжелыми из хвостов распределений. Помимо этого исследована асимптотика хвоста распределения свободного периода в открытой сети массового обслуживания и установлено, что независимо от вида сети эта асимптотика эквивалентна хвосту распределения интервала между приходами заявок в сеть.
В статьях [90, 91] рассматривается однолинейная система массового обслуживания с произвольным распределением времени обслуживания, неограниченной очередью и неординарным входным потоком требований (моменты поступления требований образуют процесс восстановления). Найдены формулы для преобразований Лапласа совместных распределений различных характеристик данной системы, в частности длины периода занятости и числа требований, обслуженных на периоде занятости. В работе [92] также изучается распределение периода занятости и числа требований, обслуженных в течение периода занятости, но уже для однолинейной системы с дискретным временем, пакетным геометрическим входящим потоком и дискретным распределением длин требований.
В работе [93] авторы изучают распределение промежутков времени в выходящем потоке не обслуженных требований в пакетной системе Gx / G /1 с некоторой дисциплиной, допускающей потери требований, а также в ее дискретном аналоге.
Чаще всего в этих и других работах выходной поток пытаются описывать аналогично входному, используя один из следующих способов:
1) задают случайный процесс {?(/) — / > 0}, где ф) при t > 0 определяет случайное число обслуженных заявок за промежуток времени [0, t) и ?(/) = ?(/- 0), <^(0) = 0;
2) указывают случайную векторную последовательность {(т/, i > 1}, в которой через г/ и ?/ обозначены соответственно /-Й момент появления и число требований, обслуженных системой в этот момент времени;
Следует отметить, что эквивалентность трех вышеперечисленных способов доказана в [9]. Если для описания выходного потока использовать один из предложенных способов, то в общем случае не удается найти конечномерные распределения процесса. Это становится возможным только в исключительно редких случаях [8]. Таким образом, задача исследования распределения выходного потока в общем случае является трудноразрешимой проблемой. Почти очевидно, что выходной поток существенно зависит от системы массового обслуживания, в которой он формируется. Следовательно, в описание выходного потока необходимо включать некоторые элементы самой системы массового обслуживания. Более того, целесообразно следить не за отдельным требованием, а за некоторой случайной группой заявок. Впервые такой подход был предложен в работах М. А. Федоткина [94—96] и назван нелокальным описанием потоков требований.
Основные задачи и содержание работы.
В данной работе рассматриваются два типа неклассических систем управления конфликтными потоками требований: циклическая система и система с приоритетами. Целью работы является построение математической модели и изучение свойств выходных потоков, возникающих в данных неклассических системах массового обслуживания.
Актуальность предложенного направления исследований в первую очередь связана с широким применением задач и методов теории массового обслуживания в организации производства и при создании крупных информационных систем (систем по обработке и передаче информации). Как правило, информационные системы имеют сложную структуру и состоят из двух и более подсистем, объединенных некоторым образом. Если в такой структуре имеется последовательное соединение, то выходной поток одной подсистемы является входным для другой. В этом случае закономерно возникает вопрос изучения выходного потока подсистемы, а точнее проблема исследования распределения выходного потока, который затем является входным для следующей системы. Между тем на настоящий момент проблема выходных потоков остается малоизученной и результаты в этой области получены только для некоторых простейших систем массового обслуживания.
В отличие от большинства известных трудов в этой области, для построения математической модели выходных потоков автор использует так называемое нелокальное описание потока требований, впервые предложенное М. А. Федоткиным [94—96]. В описание выходных потоков включены такие элементы самой системы массового обслуживания как состояния обслуживающего устройства и величины очередей. Стоит отметить, что функционирование рассматриваемых систем управления в непрерывном времени является сложным процессом, и не является при этом марковским процессом, поэтому изучение характеристик систем и свойств выходных потоков в непрерывном времени является трудноразрешимой задачей. Для решения данной проблемы, как правило, используется метод вложенных цепей Маркова. Суть метода состоит в том, что процесс обслуживания рассматривается в специально подобранные дискретные моменты времени, которые выбираются таким образом, чтобы новый процесс обладал свойством марковости. Однако проблема определения указанных моментов является очень сложной, поскольку не существует определенной методики или алгоритма их выбора. В диссертации проблема выбора специальных моментов времени решается уже на этапе построения математической модели. При построении математических моделей изучаемых неклассических систем массового обслуживания использовался так называемый «кибернетический подход», разработанный А. А. Ляпуновым и С. В. Яблонским [97] и развитый М. А. Федоткиным в ряде работ.
В работе получены новые теоретические результаты в области изучения свойств выходных потоков в неклассических системах массового обслуживания, найдены необходимые и достаточные условия существования стационарного режима функционирования рассматриваемых систем. Помимо этого, посредством имитационного моделирования получены численные оценки для распределений выходных потоков, а также для некоторых характеристик функционирования изучаемых систем.
Диссертационная работа состоит из введения, трех глав, заключения, списка литературы и приложений.
Введение
содержит обзор литературы по изучаемому вопросу и краткую характеристику данной работы с указанием основных научных результатов.
Заключение
.
В работе рассматривались модели систем управления т конфликтными потоками требований для двух классов однородных алгоритмов управления: жесткого циклического алгоритма и алгоритма с упреждением, использующего минимальную информацию о наличии очереди и поступлении заявок. Основные результаты исследования поведения выходных потоков, возникающих в данных неклассических системах управления, приведены ниже.
При построении математических моделей изучаемых систем был применен кибернетический подход, при котором конкретная система обслуживания рассматривается с общих позиций управляющих систем, и выделяются схема, информация, координаты и функция.
С использованием нелокального подхода построены вероятностные модели выходных потоков, возникающих в циклической и приоритетной системах массового обслуживания. В описание выходных потоков включены такие элементы самой системы массового обслуживания, как состояния обслуживающего устройства и величины очередей по потокам. Данные модели представляют собой в первом случае трехмерную, а во втором пятимерную управляемые векторные последовательности.
Для построенных векторных последовательностей сформулированы и доказаны некоторые утверждения. В частности доказано свойство марковости, проведена классификация их состояний, получены рекуррентные соотношения для одномерных распределений, позволяющие находить все конечномерные распределения, а также рекуррентные выражения для производящих функций за один такт и за полный период работы систем.
Проведен анализ асимптотического поведения распределений и доказаны предельные теоремы, устанавливающие необходимые и достаточные условия существования стационарного режима в системах обоих типов. Данные предельные теоремы также являются обоснованием применения в работе метода имитационного моделирования и позволяют существенно сократить время поиска квазиоптимального управления.
Кроме аналитического исследования в работе изучены имитационные модели циклической и приоритетной систем. Получены численные оценки стационарных законов распределения выходных потоков, среднего времени ожидания обслуживания заявки по потокам, длин очередей, длительности переходного процесса. Определены квазиоптимальные параметры функционирования циклической и приоритетной систем по критерию минимизации среднего времени ожидания начала обслуживания произвольного требования. Исследовано поведение оценки среднего времени ожидания начала обслуживания произвольного требования в квазистационарном режиме для различных загрузок систем.
На основе экспериментальных данных также решена проблема Вебстера—Алсопа о задержках в циклических системах массового обслуживания.
Стоит отметить, что кроме задачи описания и исследования свойств выходных потоков при известной системе существует и в некотором смысле обратная задача. Последняя задача возникает, когда по наблюдаемым свойствам выходного потока необходимо восстановить некоторые характеристики самой системы массового обслуживания. Задача такого типа решалась, например, в [120].
