4.2. Описание системы и генерируемого периодического процесса.. 74.
4.3. Глобальная Стабилизация Процесса .77.
4.4. Основной результат .79.
4.5. Доказательство Леммы 4.2 .80.
4.6.
Заключение
.80.
Глава 5. Производственная сеть Кумара-Сейдмана. 82.
5.1.
Введение
и Описание Системы. .82.
5.2. Оптимальный периодический процесс в системе Кумара-Сейдмана 84.
5.3. Параметры, характеризующие оптимальный периодический процесс.88.
5.4. Доказательство Теоремы 5.2.91.
5.5. Оптимальный протокол переключения.94.
5.6. Доказательство Теоремы 5.3.103.
5.7.
Заключение
.105.
Глава 6. Общая сеть.107.
6.1. Периодические процессы с интенсивным обслуживаем буферов. 107.
6.2. Доказательство Утверждения 6.1.110.
6.3. Глобальная стабилизация производственного цикла протоколом переключения .115.
6.3.1 Чисто переключательная фаза (^[ф] = (Э, О). .. .116.
6.3.2 Фазаф с активными буферами ф := = (пь • • • • пз) ф-(©-, .,(c)).116.
6.3.3 Протокол управления.120.
6.4.
Заключение
.121.
Глава 7. Доказательство Теоремы 6.1.122.
7.1. Чисто переключательная фаза = (0,. .¦¦, 0).122.
7.2. Фаза с активными буферами.
Q:=Q№] = (ni,., ne)^(0,., 0).122.
7.3. Функция чувствительности фазы ф с активными буферами. .. 128.
7.4. Строгая доминантность и завершение доказательства Теоремы 6.1134.
Глава 8. Оптимальный метод отслеживания производственного запроса.138.
8.1.
Введение
138.
8.2. Математическая модель односерверной производственной системы 142.
8.3. Оптимальная стратегия управления.144.
8.4. Доказательство Теоремы 8.1.146.
8.5.
Заключение
.150.
Список литературы
154.
Общая характеристика проблемной ситуации, на разрешение которой нацелена работа.
Современный этап технологического прогресса в неуклонно возрастающей степени выражается во внедрении, распространении и совершенствовании распределенных сетевых систем разнообразного назначения. Многие аспекты жизни общества уже неотделимы от сетевых комплексов и технологий. Примеры включают передачу и обработку информации (Интернет, телекоммуникации, локальные компьютерные сети, электронные платежные системы и т. п.), транспорт (транспортные сети мегаполисов, портовых зон, трехмерные транспортные потоки крупных аэропортов, трубопроводный транспорт и пр.), производство (гибкие высокотехнологичные производственные сети как в пределах отдельного предприятия, так и в рамках производственной кооперации фирм, сложные крупномасштабные производственные линии и пр.), логистику, торговлю и многое другое. Сетевые принципы активно применяются и при решении вполне традиционных задач управления. Это объясняется не только преимуществами сетевых технологий как таковых, но и тем, что объединенные в сеть группы относительно автономных агентов способны решать многие задачи более эффективно, чем отдельные даже более мощные устройства. Наконец, многие вполне традиционные системы (например, управления сложными техническими объектами: космическим аппаратом, аэропланом и т. п.) все чаще реализуются как распределенные комплексы датчиков, актуаторов и регуляторов, обменивающихся данными через цифровую сеть.
На фоне возрастающего значения сетевых систем авторитетные группы международных экспертов выделяют разработку методов эффективного управления ими как направление, несущее потенциал инновационного технологического прорыва [27]. Несмотря на все разнообразие подобных систем, с ними связан ряд общих фундаментальных проблем управления. К их числу относится регулирование степени загрузки отдельных линий, маршрутизация потоков, буферирование и управление буферами, распределение сетевых ресурсов между пользователями и др. По сравнению с более традиционными и хорошо изученными объектами управления, сетевые системы характеризуются серией особенностей, серьезно осложняющих работу с ними. Среди них очень высокий порядок системы и связанное с этим 'проклятие размерности', делающее неэффективными многие традиционные подходы, децентрализованный характер управления (решения принимаются многими центрами на основе локальной информации), нерегулярные запаздывания в распространении информации и последствий управляющих воздействий, разнообразные непредсказуемые неопределенности и др. Дополнительные проблемы связаны с тем, что качество работы таких систем естественно оценивать разными критериями, частично противоречащими друг другу.
Хотя на практике многие из обсуждаемых сетевых систем были внедрены сравнительно недавно, на уровне математической абстракции связанные с ними проблемы исследовались и ранее. Это в частности касается эффективного распределения сетевых ресурсов, буферирования и управления буферами. Ряд возникающих здесь вопросов сводим к проблемам, составляющим предмет традиционной теории расписаний (the theory of scheduling and sequencing). К ним относится проблема нахождения оптимального (субоптимального) распределения ресурсов при наличии ограничений. Хотя обширная литература1 на эту тему предлагает ряд проработанных подходов к проблеме, в целом они ориентированы на оптимизацию статических алгоритмов, реализуемых централизованно и как правило в виде временной программы на основе полной информации о текущем состоянии системы и для неизменной и априори известной обстановки. Это противоречит реалиям многих совреее обзором можно ознакомиться в [8,20,25,28,38,43,48,62,63,78]. менных сетевых систем (производственных, информационных, транспортных и др.), которые функционируют в динамичной и непредсказуемой среде и в которых решения принимаются децентрализованно. Следствием является констатируемый в настоящее время принципиальный разрыв между теорией и практикой [29,71,92], квалифицируемый как один из основных тормозов на пути повышения эффективности многих практических сетевых систем. Суть разрыва состоит в том, что для парирования неопределенностей и адаптации к изменчивым условиям на практике применяют алгоритмы управления типа обратной связи (так называемые, интерактивные протоколы управления сетями [6,69]). Однако в настоящее время большинство из них основано на эвристике, что отражает пока все еще скромные возможности теории синтеза таких алгоритмов, которая является хотя и бурно развивающейся, но весьма молодой дисциплинойс ее обзором можно ознакомиться в [77]. Вместе с тем потребность в такой теории была неоднократно подчеркнута анализом основанных на эвристике алгоритмов, в результате которого обнаруживалось, что эти алгоритмы могут порождать контр-интуитивное и сложное поведение замкнутой системы, не соответствующее первоначальным ожиданиям и часто неприемлемое.
Цель исследования. Работа нацелена на преодоление указанного разрыва в части, касающейся потоковых переключательных сетей, то есть сетей, в которых перемещаются потоки агентов, нуждающихся в многократном обслуживании на нескольких серверах (станциях), причем каждый сервер вовлечен в обслуживание нескольких потоков и вынужден переключаться между ними. Цель работы — развитие математической теории и методов синтеза протоколов децентрализованного управления такими сетями, гарантированно обеспечивающими цель управления в динамичной и априори неизвестной обстановке. Основным средством адаптации к априори неизвестной и изменчивой среде функционирования в настоящее время считается динамический интерактивный алгоритм (протокол) управления сетью. В соответствии с ним решения принимаются по принципу обратной связи на основе текущих событий, а распределение сетевых ресурсов постоянно пересматривается в режиме on-line. Такой подход пока недостаточно разработан в существующей теории, в связи с чем синтез практических алгоритмов управления в значительной степени основан на эвристике. Цель исследования: создание фундамента для повышения эффективности управления сетевыми системами посредством продвижения к научной теории синтеза интерактивных динамических протоколов обсуждаемого типа.
Основная задача, на решение которой направлена диссертация. В диссертации рассматриваются жидкостные модели переключательных потоковых сетей. Базовый элемент такой модели — конечный ориентированный граф. Его вершины подразделяются на источники (без входящих ветвей), сток (без исходящих ветвей) и буфера, содержащие очереди на обслуживание. Содержимое буферов называем работой и интерпретируем как жидкость. Работа поступает в систему из источников в виде нескольких непрерывных потоков, впадающих в начальные буферы, затем перемещается по остальным (внутренним) буферам и в конце концов через сток покидает систему. Ветви ориентированного графа указывают порядок перемещения работы, само перемещение из буферов осуществляется серверами. При подключении к буферу сервер изымает его содержимое, которое уходит по исходящим из данного буфера ветвям графа либо в другие буфера, либо через сток за пределы системы. Содержимое необслуживаемого буфера не изымается и при наличии входящих в буфер потоков возрастает. Характерная особенность рассматриваемых моделей — конкуренция между буферами за ресурсы серверов: количество серверов недостаточно для одновременного обслуживания всех буферов. В типичном случае каждый сервер в данный момент времени способен обслуживать только один буфер из своей зоны обслуживания, охватывающей сразу несколько буферов. Это предопределяет необходимость систематического переключения сервера между буферами, причем каждое переключение занимает определенное время, в течение которого сервер не обслуживает ни один из буферов.
В фокусе данной работы находятся проблемы управления потоковыми переключательными сетями. Само управление подобной сетью включает.
1. Определение текущей скорости изъятия содержимого из обслуживаемого буфера;
2. Выбор момента прекращения обслуживания;
3. Выбор следующего буфера.
Перечисленные решения должны быть приняты для каждого сервера. Во многих случаях решение задачи 1 находится сравнительно просто и заключается в обслуживании на максимально возможной скорости. На этом фоне проблема фокусируется на решении задач 2 и 3, то есть на управлении системой за счет переключений серверов. Так как при этом та часть состояния системы, которая характеризует текущие объемы буферов, изменяется с течением времени непрерывно, задача демонстрирует признаки переключательного (дискретного) управления непрерывной динамической системой. Соответствующие алгоритмы относятся к сфере интересов молодой и бурно развиваемой в последнее десятилетие дисциплине — теории управляемых гибридных динамических систем [75].
Охарактеризованная жидкостная потоковая переключательная сеть является популярной (но не единственной) моделью гибких производственных систем и традиционно используется для описания определенных аспектов функционирования автоматизированных высокотехнологичных коммуникационных и компьютерных сетей, транспортных сетей, процессов химической кинетики и т. д. [8,55]. Интерес к жидкостным моделям также мотивирован тем, что они часто описывают поведение средних значений (математических ожиданий) в стандартных стохастических моделях систем массового обслуживания, которые к тому же асимптотически сходятся к жидкостной аппроксимации в определенной ситуации, см., например, [17,18,22,30,31,44−46] и литературу оттуда. Во многих из перечисленных приложений потоки в системе являются дискретными и стохастические модели дают их более адекватное (хотя и приближенное) описание. Вместе с тем такие модели сложнее анализировать, что в случае больших систем, каковыми и является большинство современных сетевых систем, делает получение законченных и содержательных результатов проблематичным. В этом случае жидкостная модель интересна как «первое» приближение, которое делает реалистичным содержательный анализ эффектов, связанных с взаимодействием и координацией множества агентов в большой системе. Вместе с тем достигается это за счет огрубления в описании «локальных» эффектов.
В диссертации основное внимание уделяется следующей задаче. Пусть задан периодический процесс в системе. Необходимо синтезировать интерактивный протокол управления, который делает этот процесс глобально асимптотически устойчивым. При этом под процессом понимаем допустимую эволюцию системы во времени. Его можно трактовать как расписание, указывающее для каждого момента времени содержимое каждого буфера и действие каждого сервера. Интерактивный протокол (алгоритм, политика) управления — это свод основанных на принципе обратной связи правил, которые исходя из текущих событий в системе и ее состояния определяют буфер, который будет обслуживаться следующим (политика очередности), моменты прекращения и инициализации текущего обслуживания и переключения, соответственно (политика переключения), и скорости, на которых происходит текущее обслуживание (политика обслуживания). Протокол должен гарантировать, что после затухания переходных процессов и независимо от начального состояния действительный процесс будет примерно равен заданному, и с течением времени расхождения между ними будут уменьшаться. Эта задача схожа со стандартной сложной задачей в теории автоматического управления, т. е. с. возбуждением заданных колебаний в техническом устройстве: регулятор, основанный на принципе обратной связи, должен сделать желаемую циклическую траекторию глобальным аттрактором.
Исследуемая задача имеет несколько мотиваций. Одной из них является желание сделать, несмотря на неопределенности, качество обслуживания примерно равным качеству, достигаемом на специальном периодическом процессе. Эта особенно интересно, если этот периодический процесс обладает каким-то привлекательным свойством, например, оптимален или субоптимален. Одновременно это системный подход к построению мостика через охарактеризованный ранее разрыв от ранее развитой теории к синтезу интерактивных протоколов. Именно, подразумевая способности теории к нахождению оптимальных или суб-оптимальных периодических временных программ управления (и связанных с ними процессов), развивается метод синтеза интерактивного протокола, обеспечивающего устойчивую генерацию этого процесса в условиях неидеальностей, встречающихся на практике.
В последней главе диссертации исследуется другая задача, а преодоление разрыва происходит в «направлении», противоположном охарактеризованному в предыдущем параграфе. Эта глава идет от распространенного в приложениях «эвристического» протокола к обоснованию его оптимальности.
Текущее состояние вопроса. Проблеме синтеза протоколов посвящена обширная литература. В основном она касается поиска расписаний, то есть временных программ действий, часто оптимальных или субоптимальных (см., например, [8,37,38,43,53,82,100], и литературу оттуда). Этот подход обычно направлен на распределение ресурсов с тем, чтобы оптимизировать качество при заданных ограничениях на обработку потоков, и, как правило, подразумевает, что условия функционирования статичны и известны. Даже при этих упрощающих предположениях такие оптимизационные задачи являются, за редким исключением, ЫР-трудными [68]. Многие из предложенных рецептов в той или иной степени привлекают эвристику. Относящиеся к жидкостным потоковым сетям результаты такого рода [11,24,52,54,60,1011 в основном касаются сетей либо с одним сервером, либо с параллельными серверами, при этом рассматривается упрощающий критерий асимптотической оптимизации.
Являясь фокусом существующей теории [91,99], временная программа не имеет средств адаптации к реальной изменчивой и неопределённой обстановке. Результатом является констатируемый разрыв между теорией и практикой [29,71,92]. На его преодоление нацелено направление, посвященное синтезу динамических интерактивных протоколов, гарантирующих требуемое поведение системы [6, 69]. В соответствии с таким протоколами решения принимаются в зависимости от текущих событий, то есть, на языке теории управления, на основе принципа обратной связи. В число требований включается достижение цели для любых возможных и априорно неизвестных условий функционирования, в частности, начальных условий. Данная задача очень сложна. Частично это связано с тем, что реально приходится иметь дело с очень большими системами, где решение надо принимать децентрализовано на основании локальной информации. Именно поэтому решение задачи синтеза оптимального интерактивного протокола известно лишь для нескольких элементарных сетей. Для более полного обзора этого направления теоретических исследований см. [77].
Вместе с тем анализу интерактивных протоколов было посвящено множество исследований (см., например, [15,17,21,32−34,39,46,49,55,73−75,98] и литературу оттуда). Их типичным объектом являются более или менее эвристические протоколы, часто отражающие сложившуюся на практике тактику и стратегию управления, а их основное направление —- движение от заданного протокола к изучению порождаемого им поведения. При этом неоднократно выяснялось, что протоколы такого рода могут демонстрировать неожиданное и сложное поведение и, что намного хуже, неприемлемое и противоречащее ожиданиям. Например, как теоретически так и методом компьютерного моделирования [9] было установлено, что некоторые стандартные протоколы способны сделать стабилизируемую систему неустойчивой.2 Среди них FIFO (first-in-first-out: после опустошения текущего буфера сервер переключается в тот из альтернативных буферов из своей зоны обслуживания, который начал заполняться раньше других) [16,90], LBFS (last-buffer-first-served: приоритет отдается буферам, расположенным ниже по течению, то есть сервер переключается в буфер п только, если пусты все расположенные ниже по течению буфера из его зоны обслуживания, либо ниже по течению нет буферов из этой зоны), FBFS (first-buffer-first-served: противоположное правило) и некоторые другие схожие правила, основанные на распределении приоритетов между буферами [70,85]. В [59] было доказано то же самое для политики клиреиса (clearing policy: обслуживать буфер на максимальной скорости до его полного опустошения, то есть запрещено прекращать обслуживание буфера, в котором есть работа). Указанный факт установлен для очень простой сети (рассмотренной в Главе 5 диссертации) и при условии мгновенных переключений между буферами. В [80] была предложена политика переключения САБ" (clear-a-fraction: переключаться разрешено только в тот буфер, содержимое которого не меньше, чем заданный процент от общего количества работы в системе). Показано, что она обеспечивает устойчивость стабилизируемых од-носерверных систем, а также так называемых ациклических многосерверпых сетей. Их характеристическая черта — возможность так занумеровать сервера, что работа посещает их в порядке неубывания номера (причем один и тот же сервер может посещаться несколько раз). Однако для циклических сетей, где такая нумерация невозможна, применение этой политики может привести к неустойчивости [59]. В некоторых случаях с этой проблемой удается справиться за счет применения пороговых протоколов (gated protocols) [50,81]. Их основная идея: ориентироваться не на абсолютное содержимое буферов, а па разность между этим содержимым и заранее оговоренным уровнем (gate), в.
2Неустойчивость понимается как неограниченное возрастание с течением времени суммарного количества работы в системе. Стабилизируемость означает, что существует такой алгоритм управления, при применении которого это количество остается ограниченным. Неустойчивость не приемлема и означает неработоспособность системы. частности, не опускать содержимое ниже этого уровня. Смысл этого подхода связан с ожиданием, что такая мера способна уменьшить вероятность нежелательной ситуации, на примере обнаруженной в [59] и повлекшей неустойчивость: сервер переключается в пустой буфер и поэтому неспособен реализовать свою максимальную производительность. В свою очередь это объясняется тем, что исследованная в [59] политика клиренса, управляя каждым сервером независимо от другого, не обеспечивает надлежащую координацию их действий: один из них должен снабдить работой другого, но не успевает это сделать, задержавшись с полной очисткой стороннего буфера.
Введение
порога, во-первых, гарантирует непустоту буфера и во-вторых, дает надежду на снижение вероятности указанной нежелательной ситуации, сокращая время пребывания в «стороннем» буфере. Однако достигается это за счет намеренного заполнения системы работой с незавершенным производственным циклом, в то время как стандартным и общепринятым критерием качества работы рассматриваемых сетей является малый, в идеале минимально возможный суммарный объем такой работы в системе.
Логическим развитием рассмотренной идеи явился предложенный в [89] универсальный протокол управления, который обеспечивает устойчивость стабилизируемой общей сети при минимальных технических предположениях. Этот протокол организует работу системы в виде повторяющихся циклов заданной длительности Т. В течение цикла каждый сервер один раз посещает каждый буфер из своей зоны обслуживания в заранее оговоренной очередности и в конце цикла возвращается в исходный буфер. При этом из каждого буфера он извлекает объем работы, равный «виртуальному лоту», то есть объему, привносимому в систему извне за время Т всеми потоками, в обработку которых вовлечен этот буфер. При этом на предварительном этапе работы алгоритма предлагается накопить во всех буферах объем не меньше виртуального лота. Легко заметить, что эта ситуация будет воспроизводиться в конце каждого цикла, обеспечивая корректность алгоритма. Основной результат [89] показывает, что для стабилизируемой системы указанный протокол с достаточно большим Т обеспечивает устойчивость системы с нестационарными внешними потоками, а при условии их стационарности — сходимость всех траекторий к общему предельному циклу. Однако достигается это за счет усиления отмеченных ранее недостатков пороговых протоколов. Кроме того обсуждаемая политика управления не включает никаких механизмов снижения количества незавершенной работы в системе: в конце каждого цикла ее равно столько, сколько было в начале цикла. Поэтому для многих практических систем эта политика рассматривается скорее как метод доказательства, чем как практический рецепт.
Приведенный краткий обзор не охватывает всех работ, многообразие которых намного больше, однако демонстрирует типичные черты представленных в них исследований. Они как правило начинают с некоторого протокола, в основе которого лежат более или менее эвристические идеи, причем даже в тех случаях, когда эти идеи мотивированы результатами предшествующего строгого анализа. Само исследование посвящено анализу вызванного применением этого протокола поведения системы, то есть порождаемых им процессов. Неоднократно обнаруживалось, что это поведение не соответствует первоначальным ожиданиям, связанным с применявшейся эвристикой. Это ещё раз подчёркивает необходимость строгого метода, гарантирующего, что цель управления будет достигнута. Наконец, отмеченные осложнения коснулись даже самой простой цели управления — обеспечения устойчивости, то есть исключения неограниченного роста очередей на обслуживание. Это наблюдение ставит под сильное сомнение перспективы охарактеризованного подхода в отношении такой более «тонкой» цели, как оптимальность. Неудивительно, что за вычетом небольшого количества работ [7,26,35,40,51], посвященных простейшим системами с двумя буферами, вопросы оптимизации в основном сводились к обсуждению выбора параметров того или иного эвристического протокола. Вместе с тем эти вопросы в последнее время приобретают особую актуальность, например, в связи с усложнением и подорожанием производственных систем.
Системный подход к преодолению упоминавшегося разрыва между теорией оптимальных расписаний и синтезом интерактивных протоколов управления предложен в [64,66]. Он предлагает направление исследований, в определенном смысле противоположное представленному в подавляющем большинстве предшествующих работ: идти не от протокола к процессу, а наоборот — от процесса к протоколу. Именно предполагая заданным некоторый периодический процесс в системе, подход ставит в качестве цели развитие общего метода синтеза интерактивного протокола, который не только порождает этот процесс, но и превращает его в глобальный аттрактор для замкнутой системы. Таким образом, независимо от начальных условий, поведение системы по истечении времени примерно такое же, как и на заданном периодическом процессе. При этом подразумевается, что этот процесс персонифицирует интересующие нас желаемые свойства. В результате эти свойства гарантированы протоколом, если конечно, поставленная задача успешно решена.
Особый интерес представляет, случай, когда используемый периодический процесс оптимален или субоптимален. В этом случае обсуждаемый подход к синтезу динамических протоколов управления жидкостными потоковыми сетями дезинтегрирует проблему на 1) поиск оптимальной временной циклической программы переключения серверов и 2) синтез интерактивного динамического протокола, обеспечивающего сходимость процесса к оптимальной программе независимо от начальных условий функционирования. Последнее гарантирует, что после затухания переходных процессов качество обслуживания примерно то же, что для рассматриваемой периодической программы. Другими словами, оно оптимально в классе всех периодических процессов. Этот вывод, однако, распространяется и на более широкий класс процессов и политик переключения. Дело в том, что как показали многочисленные исследования (см., например, [21,49,73−75,98]), практически все известные политики переключения обеспечивают периодическое поведение системы: все траектории стремятся к единственному предельному циклу. Более того, в [75] этому обстоятельству дано теоретическое объяснение: показано, что сети рассматриваемого класса в принципе, подвержены периодическому поведению в указанном смысле. Отсюда следует, что, в определенном смысле, оптимум в классе периодических траекторий имеет более широкий смысл, являясь оптимумом в классе естественных политик переключения. Отметим также, что хотя задачи поиска оптимальных периодических расписаний в типичных случаях оказываются ЫР-трудными, для их решения предложен ряд методов, подтвердивших свою относительную эффективностьс их обзором можно ознакомиться в [77,82].
Данная диссертация в своей основной части посвящена развитию указанного подхода. При этом в ее фокусе лежат не вопросы поиска оптимальных периодических программ управления, а вторая часть этого подхода: методика синтеза интерактивных протоколов, обеспечивающих глобально устойчивую генерацию заданного периодического процесса в потоковой переключательной сети.
В [64] предложена идея общего подхода к решению сформулированной задачи. Она созвучна методу функций Ляпунова построения обратной связи и = и (х), стабилизирующей управляемую систему х — /(х, и): задавшись некоторым «кандидатом» на роль функции Ляпунова V: Мп —" [0, +оо), обеспечить убывание этой функции на траекториях системы за счет выбора обратной связи ^-(х)/[х, и (х)} < 0 (для х отличных от положения равновесия). В [64] предложено использовать специальную функцию V, которая однако задана неявно и вычисление которой является отдельной и вообще говоря вычислительно затратной задачей. Однако даже после ее нахождения возможность построения требуемого протокола не гарантирована и не подкреплена общей методикой,, а само построение рассматривается как индивидуальная для каждого приложения задача. Известные реализации обсуждаемого подхода ограничены простейшими примерами сетей: односерверной системой с двумя очередями в общей (алгебраической) форме [35], системой Кумара-Сейдмана [59] с конкретными численными значениями параметров [36,66]. а также каскадом таких систем с заведомо слабейшим звеном, на котором по сути концентрируется оптимизация каскада. Типичное для рассматриваемых сетей «проклятие размерности «быстро трансформирует необходимое для реализации метода вычисление функции Ляпунова в трудно, а подчас и вовсе невыполнимую задачу по мере увеличения числа серверов и буферов в сети.
Краткая характеристика вклада диссертации в разработку рассматриваемой проблемы. В диссертации разработан альтернативный подход, во многом мотивированный стремлением к преодолению «проклятия размерности». Он следует методу Пуанкаре, преодолевает «проклятие размерности «за счет глубокой дезинтеграции сетевой системы и оптимальной циклической программы и характеризуется сравнительной простотой применения итоговых результатов. В соответствии с предлагаемым подходом синтез протокола начинается с разделения требуемого периодического процесса на простые части — фазы. Под фазой понимаем некоторую часть процесса без подключений и отключений серверов, хотя и более сложные (гибкие) фазы, охватывающие фиксированную цепочку таких переключений, также разрешены. Протокол предлагает проходить через периодически повторяемый цикл фаз, наблюдаемый на заданном периодическом процессе. Внутри каждой фазы система управляется с помощью индивидуального правила. Это правило определяет текущие скорости обслуживания буферов и моменты прекращения фазы, а в случае гибкой фазы — моменты подключения и отключения внутри этой фазы. Построение правил управления фазами является основной задачей. Для того чтобы решить ее, заметим, что после того, как правило задано, возникает динамический оператор фазы, который переводит состояние системы в начале фазы в состояние в конце этой фазы. Оператором монодромии будем называть композицию этих операторов по всем фазам периодического цикла. Если следить за состояниями системы только в начале циклов, то легко заметить, что их эволюция осуществляется за счет итераций оператора монодромии. В итоге главная задача — обеспечить, чтобы все траектории, сгенерированные этой рекурсией, сходились к положению равновесия, отвечающему требуемому периодическому процессу.
Хотя теория итерационных динамических систем предлагает множество критериев устойчивости положения равновесия, воспользоваться ими не удается в связи с уже упомянутым «проклятием размерности». Дело в том, что в типичном случае оператор монодромии кусочно-аффинен, т. е. аффинен на каждом элементе полиэдрального разбиения фазового пространства. При этом если для динамического оператора отдельной фазы число элементов разбиения в типичном случае невелико, то при формировании оператора монодромии путем последовательной композиции таких операторов это число быстро нарастает и в итоге достигает астрономических значений, особенно при большом числе серверов, буферов в сети и фаз в заданном процессе. Это делает «явное» описание оператора монодромии трудоемким и часто практически невозможным, что наряду с узкой номенклатурой управляющих акций (в основном, переключение серверов) является серьезным препятствием применению известных как критериев устойчивости, так и методов стабилизации итерационных систем. Дело осложняется тем, что на этапе синтеза вообще нет определенного оператора монодромии, и задача состоит в обнаружении и использовании зависимостей между оператором монодромии и правилами управления фазами, которые влияют, в том числе, и на само разбиение.
Для преодоления указанной проблемы работа предлагает новый критерий глобальной устойчивости положения равновесия итерационной системы. Его принципиальная особенность — возможность пофазовой проверки: критерий указывает список свойств таких, что, во-первых, положение равновесия глобально асимптотически устойчиво, если оператор монодромии обладает этими свойствами, и, во-вторых, они наследуются при композиции операторов. Таким образом, цель, преследуемая построением правил управления фазами, непосредственно уже не связано с трудно вычислимым оператором монодромии, на который также влияют правила и всех сопутствующих фаз. Цель, преследуемая при синтезе, становится локальной по своей природе: обеспечить наличие указанных свойств у динамического оператора данной фазы. Таким образом и преодолевается «проклятие размерности»: задача построения правил управления фазами оказывается разрешимой.
Для обоснования вышеуказанного критерия в исследовании разработана общая теория глобальной устойчивости положений равновесия кусочно-аффинных монотонных непрерывных (КАМН) операторов. Она опирается на предложенное понятие дифференциала кусочно-аффинной функции, в целом, лежащее в русле традиций негладкой оптимизации [2], и относительно новое понятие дифференциала в бесконечно удаленной точке. Ядро теории образуют результаты о спектральных свойствах нелинейных положительно однородных кусочно-аффинных операторов. Среди многих обобщений понятия собственного числа на случай нелинейного оператора (см. обзор в [5]), изучается, по-видимому, наиболее прямое обобщение [23]. В отличие от предшествующих исследований, сфокусированных на вопросе разрешимости нелинейных уравнений, в данной работе основное внимание уделено фактам в духе классической теории Фробениуса-Перрона матриц с неотрицательными компонентами.
Развитая теория проиллюстрирована решением задачи синтеза интерактивного протокола оптимального управления для 4 классов жидкостных потоковых сетей, каждый из которых представляет самостоятельный интерес. Для каждого класса доказаны как минимум две теоремы: 1) теорема, указывающая необходимые условия оптимальности процесса (а в случае сети Кумара-Сейдмана, необходимые и достаточные) и 2) теорема, доказывающая, что предложенный протокол управления порождает требуемый периодический процесс в качестве глобального аттрактора.
Первой из упомянутых сетей является система, которая состоит из нескольких постоянно нарастающих очередей на обслуживание и общего для всех очередей сервера, предоставляющего это облуживание. В каждый момент времени он может обслуживать только одну очередь, переключаясь между ними за заданное ненулевое время. Такая система (по английской терминологии 'polling system') моделирует определенные аспекты функционирования высокотехнологичных гибких производственных, коммуникационных, компьютерных, транспортных и др. сетей. Управление обсуждаемыми системами основано на протоколах, т. е. правилах формирования очередности обслуживания и определения моментов переключения сервера и скорости его работы. Даже при упрощающих предположениях задачи оптимизации протоколов сложны и во многих случаях оказываются NP-трудными. В обширной литературе, посвященной теории обсуждаемых систем (обзор [97] приводит более, чем 700 работ, опубликованных до 1994 года, а обзор [1] более, чем 250 работ, опубликованных после 1990 года), а также в алгоритмах, реализованных на практике, широко представлены рецепты, основанные на эвристике.
Известны простые необходимые условия оптимальности процесса, как по критерию максимальной по времени суммарной очереди, так и по критерию средней по времени суммарной очереди. Именно, обслуживание буфера осуществляется на максимально возможной скорости (при пустом буфере это означает — на скорости входящего потока) [35,60]. Более того, по любому процесса легко построить процесс с указанным свойством «интенсивного «обслуживания, который не хуже исходного. Имеется ряд работ, в которых найдено оптимальное либо субоптимальное решение, см. [14,41,57] и приведенную там библиографию. Однако в этих работах как правило делаются специальные предположения либо о системе, либо о допустимых алгоритмах управления. Например, в [41] рассматривалось только управление по открытому принципу (без обратной связи и информации о состоянии), а переключения были разрешены только в целые моменты времени. Автору неизвестны публикации, в которых в общем случае было бы получено решение задачи о построении оптимального интерактивного протокола управления для системы поллинга.
В диссертации предложен интерактивный протокол управления общей системой поллинга, обеспечивающий сходимость всех процессов в замкнутой системе к априори заданному периодическому процессу. Рассматриваемый процесс удовлетворяет упомянутому необходимому условию оптимальности и в остальном произволен. Автору неизвестны прецеденты решения подобной задачи. Предложенное решение может быть использовано для автоматического выведения системы в режимы функционирования, отвечающие оптимальным или субоптимальным временным программам управления (например, найденным в [41]) и их дальнейшего устойчивого поддержания.
В качестве второго приложения дано решение задачи синтеза интерактивного протокола оптимального управления общей односерверной переключательной сетью с разделением ресурсов сервера. Начиная с [56], подобные сети служат популярной моделью вэб серверов и других сетей, в которых возможно одновременное обслуживание одним сервером сразу нескольких очередей, а основным методом управления является переключение сервера между обслуживаемыми наборами очередей [4]. Показано, что оптимальный процесс в такой системе принадлежит специальному классу. Для любого циклического процесса 7Г° из этого класса синтезирован протокол управления, порождающий этот процесс в качестве глобального аттрактора. Последнее гарантирует, что после затухания переходных процессов качество обслуживания примерно то же, что для 7г°. Все относящиеся к данной сети результаты являются новыми. Помимо самостоятельного значения, они иллюстрируют предложенную общую теорию синтеза интерактивных протоколов.
В качестве третьего примера в работе исследована популярная и часто используемая в качестве тестового примера знаменитая производственная сеть Кумара-Сейдмана [59]. В работе [67] была решена задача минимизации среднего количества работы в системе за единицу времени для сети Кумара-Сейдмана со специальными значениями параметров. В диссертации оптимальный процесс в системе Кумара-Сейдмана найден аналитически в общем случае системы, заданной в алгебраической форме. Аналогично в общем случае построен интерактивный протокол управления и доказано, что он обеспечивает сходимость всех процессов к оптимальному периодическому процессу. Этот пример наглядно демонстрирует как применение общей теории, так и построение правил управления при использовании гибких фаз.
Главным примером служит общая многосерверная сеть с произвольным количеством серверов, буферов и продуктовых потоков, и с произвольной топологией. В работе доказано, что внимание можно сфокусировать на периодических процессах, для которых все буферы, обслуживаемые в данный момент, обслуживаются на скоростях, максимальных в текущих условиях, с возможным простоем в конце обслуживания буфера. Дело в том, что это верно для оптимального процесса, и, более того, если это свойство нарушается для заданного периодического процесса, то по нему можно легко построить периодический процесс с лучшим качеством обслуживания и уже обладающий этим свойством. В частном случае односерверной системы это утверждение обосновано, например, в [35,60]. В диссертации утверждение обосновано в полной общности, то есть для произвольной сети с любым числом серверов. Из него вытекает, что можно ограничиться рассмотрением периодических процессов с указанным свойством.
Синтезирован интерактивный протокол управления, порождающий такой периодический процесс и обеспечивающий сходимость к нему всех остальных процессов в системе. Предложенный протокол является в значительной степени децентрализованным и локальным: каждый сервер принимает решения исходя из ситуации на обслуживаемом им буфере. Единственным исключением является принятие решения о прекращении текущей фазы. Выполнив свое задание на фазу, каждый сервер посылает другим серверам однобитовое сообщение «епс!-о?-гш88юп» об этом. При этом он не переходит к выполнению следующей фазы, а переводится в режим «ожидания». К следующей фазе сервера переходят одновременно в момент, когда каждый из них получит сигнал «епс1-о?-гш88Юп, от всех компаньонов. Синтез протокола и доказательство сходимости даны для произвольного периодического процесса с упомянутым ранее свойством, который, однако, удовлетворяет упрощающему предположению: существует промежуток времени, когда любой сервер либо переключается, либо простаивает. Преодоление этого предположения является одной из тем предстоящей работы. Однако даже в его присутствие задача синтеза интерактивного протокола ранее в сравнимой общности не рассматривалась.
В отдельной главе работы исследована оптимальность и эффективность последовательно-соединенной производственной линии, управляемой децентрализованной, основанной на избытке стратегией управления. Основной целью стратегий такого класса является обеспечение того, что суммарное количество производимой продукции соответствует суммарному спросу на продукцию для заданной сети. Основная идея стратегии управления, основанной на избытке, представлена для случая одного производственного сервера. В работе впервые доказано, что эта стратегия является оптимальной. Основные результаты.
• Разработан новый метод синтеза интерактивных динамических протоколов управления многопотоковыми многосерверными переключательными сетями.
• Предложен новый критерий глобальной устойчивости положения равновесия итерационной системы.
• Разработана общая теория устойчивости положений равновесия кусочно-аффинных монотонных непрерывных операторов, обосновывающая прод-. ложенный критерий устойчивости.
• Для иллюстрации предложенного подхода было получено необходимое1 а в случае сети Кумара-Сейдмана и достаточное) условие оптимальности и предложен интерактивный протокол управления, который порождает требуемый процесс в качестве глобального аттрактора для следующих сетей: общая односерверная сетьпотоковая сеть с разделением процессорасеть Кумара-Сейдманаобщая сеть с произвольным числом серверов и буферов.
• Обоснована оптимальность специального протокола управления для последовательно — соединенных производственных линий.
Структура и организация диссертации. Глава 1 излагает математическое описание проблемы, постановку задачи и разработанный подход к её решению. В главе 2 описан и обоснован новый критерий устойчивости положения равновесия итеративных систем. Для иллюстрации предложенного подхода рассмотрены следующие потоковые сети: общая односерверная сеть (Глава 3), система с разделением процессора (Глава 4) и производственная сеть Кумара-Сейдмана (Глава 5). В качестве последнего примера рассмотрена общая сеть с произвольным числом буферов и серверов (Глава 6). Следуя предложенному подходу, для всех рассмотренных сетей сгенерирован протокол управления и доказано, что этот протокол порождает требуемый периодический процесс в качестве глобального аттрактора. Доказательству этого факта посвящена Глава 7. В Главе 8 обоснована оптимальность специального протокола управления, предложенного в [95], обобщающего специальный класс протоколов.
Список используемых обозначений и сокращений.
• К АМН — кусочно-аффинный монотонный непрерывный;
• ОКАМН — однородный кусочно-аффинный монотонный непрерывныйcol Ol,.. ., XN) хг xN J.
• x < у для x = col (xi,., xjsr), y = col (i/i,., ум) понимает покомпонентно, то есть х < у хп < уп Vn;
• х > у определено аналогично;
• х < у и Xi < y? ii? /;
• х '¦= Y7i=i xi для х G.
• |/| — число элементов множества /;
• К1:= {х еМР: х> 0};
• int i? — внутренность множества Е, т. е. совокупность всех точек, входящих в множество вместе с некоторой своей окрестностью;
• N — множество натуральных чисел;
• {ai,., ап} - множество, состоящее из перечисленных элементов.
8.5.
Заключение
.
Основной результат главы — обоснование оптимальности специального алгоритма управления производственными системами, отражающего характерные черты ряда распространенных в реальном производстве тактических правил управления. Эти правила были основаны на здравом смысле и эвристике. Автору неизвестны прецеденты обоснования оптимальности этих правил в предположениях, выраженных изученной в данной главе математической моделью.
Материал данной главы является принадлежащей автору диссертации частью совместной статьи [96]. В остальной части статьи найденный оптимальный алгоритм управления сервером после незначительной модификации применен к линии, состоящей из N производственных серверов с промежуточными буферами ограниченного объема (см. Рис. 20). Модификация.
Рис. 20: Схематическое изображение линии из N производственных серверов. в частности принимает во внимание необходимость удовлетворить ограничения, вытекающие из конечного объема буферов. Итоговый алгоритм управления, отталкивающийся от найденного в данной главе оптимального решения, созвучен ряду широко применяемых на практике протоколов управления производственными системами, в частности, политике Основного Запаса (Basestock) (см. [13] и ссылки оттуда), политике Точки Окружения (Hedging Point)(см. [42] и ссылки оттуда), политике Канбан (Kanban), а также комбинации локальных Конвип (Conwip) политик, каждая из которых применяется к заданному промежуточному серверу. При естественных и частично неизбежных технических предположениях показано, что исследуемый алгоритм управления обеспечивает ограниченную ошибку производственного слежения в условиях неопределенностей как в работе серверов, так и в запросе на продукцию. yi ум ооо.
— Д > уы.
Публикации автора по теме диссертации Статьи в журналах, рекомендованных ВАК:
1] Феоктистова В. Н., Матвеев. А. С. Динамическая интерактивная стабилизация переключательной системы Кумара-Сейдмана. // Вестник СПбГУ, 2009. Серия 1, вып. 3, стр. 86−97.
2] Феоктистова В. Н. Динамическая интерактивная стабилизация потоковых систем с разделением процессора. // Вестник СПбГУ, 2011. Серия 1, вып. 3, стр. 75−80.
3] К.К. Starkov, V. Feoktistova, A.Y. Pogromsky, A. Matveev, J.E. Rooda. Performance analysis of a manufacturing line operated under optimal surplus-based production control. // Mathematical Problems in Engineering. 1−26. 2012, doi: 10.1155/2012/602 094, online.
Другие публикации:
4] V. Feoktistova, A. Matveev. Generation of production cycles in multiple server systems with setup times: The case study. / Proceedings of the 13th IFAC Symposium on Information Control Problems in Manufacturing, Moscow, Russia, 2009, pp. 568−573.
5] V. Feoktistova, A. Matveev, E. Lefeber, J.E. Rooda. Designs of optimal switching feedback decentralized control policies for re-entrant queueing network A case study. / Proceedings of the 10th IFAC Workshop on Intelligent Manufacturing Systems, 2010, pp. 187−193.
6] V. Feoktistova, A. Matveev, E. Lefeber, J.E. Rooda. On Optimal Switching Interactive Decentralized Control of Networked Manufacturing Systems. / Proceedings of the 18th IFAC World Congress, Milan, Italy, 2011, pp. 1 404 814 054.
7] K.K. Starkov, V. Feoktistova, A.Y. Pogromsky, A. Matveev, J.E. Rooda. Optimal production contol method for tandem manufacturing lines, / Proceedin, of the PHYSCON 2011, Leon, Spain, 2011.
