Комбинированные методы моделирования, расчёта и оптимизации характеристик информационно-вычислительных сетей тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат технических наук Кокорин, Сергей Владимирович

• Кокорин, Сергей Владимирович
• кандидат технических наук
• 2012

Оглавление диссертации кандидат технических наук Кокорин, Сергей Владимирович

Содержание

Список сокращений

Введение

1. Методы и алгоритмы расчёта вероятностно-временных характеристик информационно-вычислительной сети

1.1 Формальная постановка задачи расчёта и оптимизации вероятностно-временных характеристик информационно-вычислительной сети

1.2 Алгоритм расчёта сетей массового обслуживания

1.3 Автоматический выбор моделей узлов

1.4 Расчёт времени пребывания в сети

1.5 Аналитический расчёт высших моментов распределения времени пребывания заявок в замкнутой сети

Выводы

2. Методы и алгоритмы оптимизации вероятностно-временных характеристик информационно-вычислительных сетей

2.1 Актуальность постановки задачи оптимизации ВВХ ИВСет

2.2 Формальная постановка задачи оптимизации характеристик информационно-вычислительных сетей

2.3 Методы локальной оптимизации

2.4 Начальная оценка среднего времени пребывания

2.5 Методы глобальной оптимизации

2.6 Численные эксперименты

2.7 Расчёт и оптимизация вероятностно-временных характеристик информационно-вычислительных сетей с изменяемой структурой

Выводы

3. Имитационные модели информационно-вычислительных сетей

3.1 Задача расчёта вероятностно-временных характеристик информационно-вычислительных сетей средствами имитационного моделирования

3.2 Метод меченых заявок

3.3 Оптимизация вероятностно-временных характеристик имитационной модели ИВСет

Выводы

4. Постановка и исследование прикладных задач расчёта и оптимизации информационно-вычислительных сетей

4.1 Элементы системы мониторинга

4.2 Проверка и анализ исходных данных

4.3 Описание модели скрытых цепей Маркова

4.4 Исследование модели «Ракурс Д»

Выводы

Заключение

Приложение А

А.1 Описание приложения А-МОСТ

А.2 Пример расчётов

Приложение Б

Б.1 Описание приложения С)Ж)р1

Литература

Список сокращений

н.о.р.с.в. — Независимые Одинаково Распределённые Случайные Величины;

ИВС — Информационно-Вычислительная Система;

ИВСет — Информационно-Вычислительная Сеть;

ИТ — Информационные Технологии;

СМО — Система Массового Обслуживания;

СеМО — Сеть Массового Обслуживания;

ТМО — Теория Массового Обслуживания;

ВВХ — Вероятностно-Временные Характеристики;

FIFO — Первый Пришёл Первый Ушёл;

LIFO — Последний Пришёл Первый Ушёл;

PS — Выбор Случайного из Ожидающих;

IS — Разделение Обслуживания Между всеми Ожидающими Заявками;

МОСТ — «Массовое Обслуживание. Стационарный режим.»;

ЦФ —Целевая Функция;

ППП — Пакет Прикладных Программ;

ПЛС — Преобразование Лапласа-Стилтьеса;

GPSS/W — General Purpose Simulation System/World;

A-MOCT — Автоматизированный МОСТ;

ДФР — Дополнительная Функция Распределения; RFID — Radio-Frequency IDentification;

ROI — Показатель Возврата Инвестиций (Return On Investment);

ТСО — Общей Стоимости Владения (Total Cost of Ownership);

QoS — Качества Обслуживания (Quality of Service);

PMB — Реальный Масштаб Времени;

CM — Система Мониторинга;

ИМ —Имитационная Модель;

ЛЦП — Логистическая Цепь Поставок;

ВО — Bit Operations (Битовые Операции);

IF — Conditional Орега1огз(Условные Операторы);

МСЦМ — Модель Скрытых Цепей Маркова;

АПК — Аппаратно-Программный Комплекс.

Введение диссертации (часть автореферата) на тему «Комбинированные методы моделирования, расчёта и оптимизации характеристик информационно-вычислительных сетей»

Введение

Сегодня информатика и ИТ стали одним из основных факторов развития цивилизации и научно-технического прогресса, что привело к появлению и широкому распространению таких фундаментальных понятий, как информатизация, информационное общество и информационная экономика [51]. Информационное общество и информационная экономика как конечная цель информатизации характеризуются активной разработкой и широким, массовым внедрением информационных технологий во все сферы человеческой деятельности: социальную сферу, сферу материального производства, энергетику, здравоохранение, образование, науку, культуру, торговлю, транспорт, связь, военное дело и т.д. [41, 59]. К настоящему времени предприняты определённые попытки оценить роль и влияние информационных технологий (ИТ) на развитие указанных сфер.

Анализ [51] низкой эффективности внедрения и использования средств автоматизации управления на промышленных предприятиях показывает, прежде всего, то, что системы ориентированы в основном на процессы организационного управления и обеспечивают решение офисных задач на стратегическом уровне, где временной горизонт планирования и управления кратен неделям, месяцам и кварталам. Однако на промышленных предприятиях наряду со стратегическим уровнем управления существуют, по крайней мере, ещё два уровня управления (тактический и оперативный), на которых в реальном масштабе времени реализуются производственные процессы в рамках соответствующих технологий. На указанных уровнях вместо обычных компьютеров и ручного ввода данных приходится иметь дело с автоматическими источниками информации: датчиками, контроллерами, ЯБШ-метками, БСАБА-пакетами, фиксирующими и обрабатывающими огромные потоки данных и информации в реальном масштабе времени (РВМ), в которых содержатся сведения о физических процес-

сах, протекающих на самом нижнем (оперативном) уровне иерархии управления производством.

Как показывает детальный анализ, существует прямая логическая взаимосвязь ряда ключевых технологических параметров производственного процесса (уровень АСУ ТП, SCADA-систем) с показателями материально-хозяйственной и финансовой деятельности (уровень ERP-систем). Например, потребление электроэнергии и других энергоресурсов (газ, вода, тепло) в процессе производства напрямую влияют на себестоимость. Текущий расход сырья или простои оборудования могут определять оптимальное время подачи в цех новой партии сырья, а своевременное выявление нарушения технологии позволяет сократить или исключить вовсе дополнительные затраты, связанные с исправлением брака.

На административно-хозяйственном уровне в рамках ERP-системы осуществляется учёт каждой финансовой операции и каждого документа, в то время как на уровне производства (среднем и нижнем уровнях) подобного детального контроля не производят. Однако именно на этих уровнях рождается прибавочная стоимость, осуществляются основные затраты и имеются главные источники экономии, обеспечивается производственный план и требуемое качество продукции, а также работают многие факторы, определяющие эффективность и рентабельность предприятия в целом. В этих условиях из контура автоматизированного контроля и управления предприятием выпадает основное звено — производственный блок.

Несмотря на высокую востребованность в автоматизации перечисленных процессов, в настоящее время, в большинстве реализованных проектов, связанных с созданием интегрированных автоматизированных систем управления промышленным предприятием существует целый пласт функций, не покрываемых ни классом существующих ERP, ни классом АСУ ТП. Современное состояние задач расчёта и оптимизации вероятностно-временных характеристик (ВВХ) информационно-вычислительных сетей (ИВСет) показывает, что процесс авто-

матизации моделирования требует разработки новых методов, моделей и алгоритмов, которые бы позволили отслеживать и управлять состоянием ИВСет в РВМ. Поэтому в представленной работе рассматриваются и предлагаются такие методы моделирования, расчёта характеристик и оптимизации ИВСет, которые превосходят существующие аналоги по соотношению скорости и точности получаемых оценок и способны решать задачи в РВМ.

Объектом исследования является процесс функционирования современных информационно-вычислительных сетей, широко используемых в различных предметных областях в настоящее время. Предметом исследования являются: модели, методы, алгоритмы и методики моделирования, расчёта, и оптимизации вероятностно-временных характеристик ИВСет.

Целью диссертационной работы является повышение оперативности и качества функционирования как существующих, так и перспективных ИВСет на основе разработки и реализации новых моделей и алгоритмов расчёта и оптимизации их ВВХ.

Для достижения сформулированной цели были поставлены и решены следующие основные задачи исследования:

- выполнена содержательная и формальная постановка задачи расчёта и оптимизации ВВХ ИВСет как сетей массового обслуживания (СеМО);

- разработаны аналитические и имитационные модели СеМО для расчёта ВВХ ИВСет численными методами;

- разработаны и исследованы методы оптимизации характеристик СеМО;

- разработаны прототипы программной реализации и созданы интерфейсы для предложенных алгоритмов и моделей;

- решены прикладные задачи расчёта и оптимизации ВВХ ИВСет.

Методы исследования, применяемые в диссертационной работе: дискретно-событийное моделирование, теория массового обслуживания, численная оптимизация, математическая статистика.

Положения, выносимые на защиту

1) Методы аналитико-имитационного моделирования, расчёта различных вероятностно-временных характеристик (ВВХ) ИВСет.

2) Комбинированный метод оптимизации различных ВВХ ИВСет.

3) Результаты решения прикладных задач расчёта и оптимизации ВВХ ИВСет.

Актуальность темы диссертации. Можно привести достаточно много как успешных, так и неудачных вложений в развитие ИВСет за последние годы [25, 40, 41]. К примеру, ИВСет СМ, основанные на ИБЮ-технологии, получили коммерческое распространение относительно недавно, но не смогли обеспечить запланированную прибыль [25] от вложений из-за некорректных оценок требуемых затрат, так как такие модели ограничиваются рассмотрением только физических потоков «простой» структуры (с Марковскими свойствами) и не принимают во внимание многократно возрастающие информационные потоки [20]. Другие имеющиеся внедрения ИВСет опираются на опыт экспертов или на пилотные проекты, и лишь за редким исключением [29] можно встретить варианты использования моделей и методов ТМО либо ИМ.

В указанных условиях особую ценность приобретают вопросы количественного и качественного оценивания эффективности функционирования существующих и создаваемых ИВСет, которые составляют основу любой современной информационной и автоматизированной системы. Традиционно перечисленные вопросы исследовались с использованием систем теории массового обслуживания (ТМО). Однако, в современных условиях для описания, расчёта и оптимизации базовых характеристик ИВСет необходимо учитывать такие свойства сетей, как распределенность, неоднородность, нестационарность и для

этих целей методологических основ систем ТМО становится явно недостаточно. В этих обстоятельствах особую роль приобретают задачи формального описания, расчёта и оптимального выбора параметров неоднородных нестационарных неэкспоненциальных сетей массового обслуживания, которые требуют разработки соответствующего модельно-алгоритмического обеспечения.

В нашей стране, а так же за рубежом в отрасли научных знаний (теории сетей массового обслуживания) к настоящему моменту получено огромное количество интересных фундаментальных и практических результатов [2, 5, 11, 15, 17, 34, 61], к основным недостаткам которых можно отнести вычислительную сложность и наличие ряда жёстких ограничений на поведение моделируемого объекта, что может приводить к запоздавшим или ошибочным прогнозам и, как следствие, к потере прибыли. В современной литературе также часто рассматриваются методы расчёта ВВХ ИВСет, которые опираются на статистическую обработку больших объёмов данных и построение объектов нечёткой логики, на основе кластерного анализа либо алгоритмы моделирования роя (swarm optimizers) [7, 22, 24]. К недостаткам таких подходов можно отнести высокую вычислительную трудоёмкость и требование высокого качества исходных данных, при этом последнее требование особенно сложно выполнить на стадии планирования, так как возможны различные условия внедрения ИВСет, что приводит к проблемам невозможности корректного применения указанных методов в РМВ. Таким образом, в настоящее время существует комплекс задач анализа и синтеза ИВСет, который в рамках разработанных ранее подходов и соответствующего методологического обеспечения не могут быть решены, что определяет актуальность поставленных в диссертационной работе задач создания модельно-алгоритмического обеспечения, расчёта и оптимизации вероятностно-временных характеристик ВВХ ИВСет и показьюает необходимость проведённых в ней исследований. Решение прикладных задач в этой области позволит не только преодолеть обозначенные проблемы, но и шире

поставить вопрос выбора оптимальных параметров, тем самым усилив обоснованность принимаемых решений.

Научная новизна. Задача конструирования корректных моделей и оптимизационных процедур для систем и сетей очередей для произвольных параметров и характеристик в настоящий момент не решена в полном объёме. Анализ возможных вариантов цостроения аналитических моделей ИВСет показал, что при их создании целесообразно ориентироваться на класс моделей ТМО, так как они при расчёте и оптимизации ВВХ ИВСет позволяют:

- широко использовать в ходе расчётов фундаментальные научные результаты, полученные к настоящему времени в теории массового обслуживания (ТМО);

- существенно сократить размерность задач, решаемых в каждый момент времени с помощью их декомпозиции;

- достаточно конструктивно проводить согласование и взаимную интерпретацию результатов, полученных на аналитических и имитационных моделях;

- успешно решать проблему унификации ИВСет;

- обоснованно подходить к анализу времени работы элементов и подсистем ИВСет.

Методы ТМО предназначены для расчёта количественных оценок эффективности, устойчивости текущей структуры и нахождения наиболее узких мест моделируемой системы. Таким образом, использование численных расчётов либо ИМ для оценивания ВВХ моделей ТМО позволяет ставить задачу автоматической оптимизации. Ещё в работах Ф. Келли (1979) [10] и В.М. Вишневского (2003) [34] формулируется и аналитически решается задача минимизации стоимости ресурсов при заданной пропускной способности для замкнутых экспоненциальных сетей, а вопрос численной оптимизации ВВХ по моделям СеМО

поднимался в многочисленных статьях и книгах Дж. Медхи (2010) [15]. Эти работы объединяет наличие ограничений на вид используемых распределений, которые являются очень жёсткими и, если пытаться применять результаты расчётов к моделируемым системам, могут приводить к значительным ошибкам. Для избежания этих проблем в диссертационной работе разработан новый подход к расчёту различных ВВХ ИВСет и их оптимизации для более широкого класса моделей, где оценки ВВХ ИВСет могут быть получены как численными методами, так и из ИМ, что представляет собой весомое преимущество. Сходная задача и аналогичные подходы к решению представлены в работах [19,21, 29,40], но исследования в них ограничиваются лишь одной ЦФ и не представляют возможности вводить дополнительные условия на множестве оптимизируемых параметров, в связи с чем в диссертации исследуется модифицированный подход штрафных функций, которые снимают вышеуказанные ограничения.

Помимо вышесказанного с целью повышения эффективности подхода к решению задач расчёта ВВХ и оптимизации ИВСет автором предлагается сочетать аналитическое и имитационное моделирование, которые компенсировали бы недостатки друг друга, и ввести оптимизацию ИВСет по различным характеристикам на стадии проектирования для того, чтобы получить несколько альтернативных вариантов возможных сценариев внедрения ИВСет. Специально для случая выхода из строя аппаратной части элементов ИВСет [28], в диссертационной работе разработан специальный подход к оптимизации структуры самой ИВСет, который дает возможность использовать ресурсы сети рационально, в отличие от существующих решений, которые используют модели выхода из строя узлов без перестроения структуры сети.

Подводя итог вышесказанному, можно говорить о соответствии предложенного подхода современному уровню развития в области моделирования, расчёта и оптимизации характеристик ИВСет. Всё это позволяет обеспечить наиболее качественные результаты проектирования ИВСет.

Структура диссертационной работы

Во введении представлен краткий анализ текущего состояния проблемы расчёта и оптимизации ВВХ ИВСет с обоснованием её актуальности. Также в обобщённом виде сформулированы основные цели и задачи исследования.

В главе 1 описываются прикладные задачи расчёта ВВХ ИВСет, позволившие сформулировать задачу диссертационной работы. Проводится критический анализ известного алгоритма расчёта ВВХ СеМО и предлагается ряд улучшений, позволяющих повысить его точность и расширить область его применения.

В главе 2 формально определяются ЦФ, описанные во введении, способ задания пространства оптимизируемых параметров, методы оптимизации, а также предлагается комбинированный подход к оптимизации ВВХ ИВСет. Здесь же вводится модель ИВСет с изменяемой структурой и предлагается метод расчёта и оптимизации её характеристик.

В главе 3 рассматривается вариант применения предложенного во второй главе подхода оптимизации в случае, когда модель ИВСет задаётся как имитационная модель (ИМ), анализируются нюансы этого подхода и предлагаются способы преодоления стохастической природы оценок.

В главе 4 приведены примеры решений прикладных задач расчёта ВВХ ИВСет системы мониторинга (СМ) в РМВ посредством использования методов моделирования расчёта и оптимизации характеристик ИВСет.

В заключении описываются достигнутые цели и задачи диссертационной работы, обозначены преимущества разработанных методов и алгоритмов расчёта и оптимизации характеристик ИВСет по сравнению с уже существующими, а так же приведены полученные результаты в области теоретических и прикладных исследований.

В приложение А вынесено описание прототипа разработанной программы А-МОСТ, предназначенного для решения задач расчёта ВВХ моделей однородных систем и сетей массового обслуживания, в приложение Б — описание прототипа программы (^]ЧОр1:, предназначенного для решения задач оптимизации ВВХ ИВСет.

Автор диссертации выражает глубокую благодарность своему научному руководителю Ю. И. Рыжикову за плодотворную совместную работу и наставничество в исследованиях. В рамках рассматриваемой работы можно проследить множество ссылок к его трудам [54, 55, 57, 58], так как одной из наиболее важных характеристик предлагаемых им алгоритмов является их вычислительная эффективность. Разработанные им методы анализа широкого класса задач ТМО нашли свое воплощение в библиотеке МОСТ, который реализует различные аспекты численного расчёта характеристик ТМО и использовался при проведении всех численных экспериментов в рамках диссертационной работы. Разработанные автором методы развивают и расширяют результаты, полученные Ю. И. Рыжиковым в задачах расчёта характеристик моделей ТМО, и применяются для постановки решения задачи оптимизации ВВХ ИВСет.

Также автор работы выражает глубокую благодарность профессору Б. В. Соколову за активное участие в проводимых исследованиях, ценный вклад в постановку прикладных задач и многочисленные указания о направлении поисков решений возникавших сложностей. Особенно ценны были замечания по аспектам создания моделей и выбора методов оптимизации.

1 Методы и алгоритмы расчёта вероятностно-временных характеристик информационно-вычислительной сети

1.1 Формальная постановка задачи расчёта и оптимизации вероятностно-временных характеристик информационно-вычислительной сети

В современных условиях из-за насыщения мирового рынка всеми видами продукции, а также всеобщей доступности высоких технологий (в том числе и в инфосфере), на первый план конкурентной борьбы выдвигается фактор времени. В этой борьбе выиграет только тот, кто сможет успешно синхронизировать в РМВ бизнес-процессы и производство; быстрее разработает и предложит на рынке новый продукт; имеет гибкую, эффективную и высоко автоматизированную технологию управления логистическими процессами, обеспечивающую сокращение циклов поставок и продаж; сократит время обработки заказов; в реальном времени обеспечит контроль расходов ресурсов; осуществит в РМВ оперативное управление и диспетчеризацию производства; сократит время возврата инвестиций; сократит время анализа и принятия решений; обеспечит эффективное управление производственной кооперацией и так далее. Выбор подходящего метода решения задачи зачастую является компромиссом между скоростью, адекватностью и точностью получаемых решений, поэтому на первом этапе проектирования системы необходимо перевести задачу с языка прикладной области на язык методов моделирования, так как для эффективного управления производством необходимо иметь возможность прогнозирования функционирования систем, а это можно сделать средствами, базирующимися на любом методе моделирования, в том числе ТМО.

Одним из методов моделирования, имеющим широкое применение и фундаментальные математические основы, является подход ТМО, для которого уже разработаны численные методы расчёта характеристик ИВСет, отвечающие

требуемым критериям эффективности, но при этом обладающие достаточными ограничениями на область применения, как с точки зрения принципиальной возможности решений, так и с точки зрения скорости счёта. В этой главе будут рассмотрены несколько методов, позволяющих преодолеть указанные проблемы.

Для начала опишем общую модель ИВСет, для чего введём несколько обозначений, которые будут использоваться во всей диссертационной работе только в указанном смысле. Количество узлов в сети обозначим М, нулевым узлом назовём источник заявок, (М +1) — сток. Зачастую два данных узла не являются частью моделируемой сети и представляют собой лишь фиктивную добавку, делающей схему модели более прозрачной. Порядок обслуживания определяется приоритетностью заявки и дисциплиной обслуживания в узле.

Необходимо отметить, что в диссертации разделяются два больших класса моделей: открытые и замкнутые сети. Для открытой сети распределение интервала времени между последовательным появлением заявок является необходимым входным параметром, в то время как для замкнутых сетей данное распределение совпадает с распределением интервалов между уходящими заявками и зачастую является искомой оценочной характеристикой. Зададим интервалы между появлением последовательных заявок одного типа распределением А отдельно для каждого типа заявок (индекс типа обслуживания опускается). Для обозначения начальных моментов А будут использоваться следующие обозначения (аиаг,... ,ая), где д — некоторое выбранное число, определяющее точность аппроксимации распределения. В случае замкнутых сетей входной характеристикой является К — размер популяции (количество постоянно циркулирующих в сети заявок).

Заявки подразделяются на Ь типов, которые определяют порядок обслуживания и логику поведения заявок в сети. Сети, в которых Ь = 1, будем называть однородными. Для каждого типа заявки определена матрица стаци-

онарных вероятностей переходов И = | гг; , где г, у е О, М + 1. Для матрицы Я

предполагаются выполненными следующие естественные условия: г0;м+1 = О, ]=М+1 _

2 гу = 1,где/ е 0,М.

Каждый узел у сети характеризуется количеством каналов и для каждого типа заявок — распределением времени обслуживания В]. Начальные моменты времени обслуживания будем обозначать (Ь/ьЬд, • • •, Ь^).

Обозначим открытую СеМО как замкнутую — как <2' и определим их следующим образом:

0 = (М,А,п,В,Я), 0! - {М,К,п,В,Е). (1.1.1)

Начальные моменты входных распределений уточняются у эксперта либо с помощью метода моментов строятся по имеющимся историческим данным

N -

наблюдений [21]: Ьь = 1/ЛГ У Xе, где к е 1, а. С увеличением числа учитываемых

¿=1

входных моментов повышается точность расчётов, но также повышается их вычислительная сложность и накапливаются ошибки в оценках высших моментов, поэтому во многих задачах достаточно оценить два момента (использование более четырёх моментов нежелательно из-за погрешностей в оценках [54]).

Необходимо учесть, что в отличие от процесса построения и исследования моделей ИВСет, использующего имитационные модели (ИМ), где рассчитываемые характеристики могут значительно отличаться от стационарных, в предлагаемых аналитических моделях оцениваются именно стационарные показатели эффективности функционирования моделируемой сети. Хотя в обоих методах моделирования выбор рассчитываемых характеристик необходимо делать на шаге проектирования алгоритма расчётов исследуемых характеристик. В работах Ю. И. Рыжикова наглядно продемонстрированы вычислительные преимущества методов ускоренного моделирования ИМ [57] и выбора правильной степени детализации для численных методов [55].

Поставим задачу расчёта ВВХ ИВСет. Необходимо по данным параметрам модели сети Q или Q вычислить следующие базовые ВВХ СеМО, к числу которых можно, в первую очередь, отнести:

- стационарное распределение числа заявок в системе (сети) (ps)s€s > где S — множество всех состояний системы (сети);

- моменты (начальные и факториальные) этих распределений;

- стационарное распределение времени ожидания или моменты распределения времени ожидания в очереди в каждом из узлов сети

(<г>ц, . . . , ùJmq)'-,

- стационарное распределение времени пребывания или моменты распределения времени пребывания заявки в сети (vi,...,vq);

- доля времени простоя каналов в узлах или коэффициенты загрузки в каждом из узлов сети (рь... ,рмУ,

- доля отказа пришедшим заявкам в обслуживании в стационарном случае;

- дополнительная функция распределения времени пребывания Pv(t).

Выбор перечисленных характеристик определяется тем, что на их основании становится возможно вычислить все другие характеристики, которые будут рассматривается в главе 2.

При использовании численных и аналитических методов необходимо указать, что в диссертационной работе оцениваются характеристики стационарного состояния системы и предполагается, что интервалы времени между поступлением заявок независимы и одинаково распределены (н.о.р.с.в.), как и время обслуживания в каналах узлов.

Анализ различных подходов [5,21,54] решения задачи расчёта стационарных характеристик аналитических моделей СеМО показал, что большинством

исследователей используют обобщённый алгоритм, состоящий из следующих этапов:

- декомпозиция на подзадачи;

- предобработка входных данных;

- выбор подходящих моделей для подзадач (возможно, одной);

- расчёт подзадачи как изолированной;

- композиция подзадач в единую задачу по иерархии дробления;

- расчёт требуемых оценок для восстановленной задачи.

В аналитических моделях расчёта характеристик узлов СеМО используются следующие аппроксимирующие распределения: экспоненциальное (М), эрлангова типа (Е), эрлангова типа с вероятностным пропуском первой фазы (Р), Кокса (С), гамма (С), гиперэкспоненциальное (с комплексными параметрами) (Я) и гамма-распределение с корректирующим многочленом [54].

М соответствует аппроксимации заданного распределения единственным начальным моментом, Р, С — двумя, Н2 — тремя, а гамма-распределение с поправочным многочленом позволяет аппроксимировать распределение по произвольному количеству моментов. В случае предварительного анализа желательно выбрать наиболее частный вид распределения, для этого можно воспользоваться, например, тестом х2 согласия распределений или другие специальные тесты [44].

Существует несколько подходов к реализации расчётов различных моделей систем массового обслуживания: имитационное, аналитическое моделирование и их комбинации (в работе [40] такой подход называется аналитико-ими-тационным, а в работе [57] — условным имитационным моделированием). Каждый подход имеет свои преимущества и недостатки, так ИМ требуют большие вычислительные мощности и дают лишь статистический результат, но при этом могут быть сколь угодно приближены к описываемым объектам, в то время как

аналитические модели обычно дальше отстоят от реальных систем, но при меньших вычислительных затратах дают более точные результаты, которые не подвержены статистическим погрешностям и в этом смысле более обоснованы и интерпретируемы.

1.2 Алгоритм расчёта сетей массового обслуживания

Для оценки распределения числа заявок в СеМО (2, (У в случае Ь = 1 предпочтительно использовать базовый алгоритм, описанный в [54], поскольку он рассчитывается достаточно быстро, применим к задачам высокой размерности (сотни узлов), позволяет учесть преобразования потоков заявок. Этот алгоритм включает в себя следующие шаги:

1) Аппроксимируются входные данные по методу моментов с помощью экспоненциального, либо гиперэкспоненциального распределения в зависимости от особенностей модели.

2) Задаются начальные значения (Я/), / е 1 ,М для потоков поступающих заявок, которые принимаются простейшими с интенсивностью, определяемой при решении системы уравнений, описывающих условие баланса потоков для открытых сетей:

где Л — суммарная интенсивность потока заявок, поступающих от внешних источников.

Для замкнутых сетей уравнение баланса имеет вид:

м

(1.2.1)

1=1

м

(1.2.2)

м

(1.2.3)

i=l

Л( = Се„ 1 = 1 ,...,м,

(1.2.4)

где а>1 — среднее время ожидания в узлах, а С — константа, связывающая Л,- и вспомогательные переменные {е¡}.

3) Проверяется отсутствие перегрузки во всех узлах сети: Лфц/щ < 1.

4) Вводятся коэффициенты немарковости входящего потока для каждого узла, на первой итерации полагаются равными нулю = 0, г е 1 ,М — в дальнейшем определяемые как £ = /•//{ -И, где — моменты входящего распределения для каждого узла сети.

5) Поочередно для всех узлов решаются следующие подзадачи:

а) оцениваются распределения временных интервалов между поступлением заявок в /-й узел со всех узлов сети;

б) суммируются полученные оценки распределений;

в) рассчитываются новые коэффициенты немарковости

г) определяются невязки Д^ = - для текущей итерации к;

д) узел г рассчитывается как изолированная открытая система массового обслуживания (СМО);

е) рассчитываются оценки распределений интервалов потока заявок, выходящего из ¿-го узла.

6) Проверяется условие шахДг > е, где е — заданный порог невязки, если оно истинно, возвращение к шагу 5.

7) Рассчитываются моменты распределения времени пребывания заявки в узлах при каждом посещении (данный шаг детально представлен в параграфе о расчёте моментов времени однократного пребывания в замкнутой однородной сети).

8) Оценивается значения функции ПЛС (71(5),... ,ум(>?)) в окрестности нуля по моментам распределения времени однократного пребывания заявки в узле.

9) Рассчитываются моменты распределения времени пребывания заявки в СеМО в целом (данный шаг рассматривается подробнее в параграфе 1.4).

Предлагаемый алгоритм позволяет рассчитать все базовые ВВХ СеМО, но необходимо отметить несколько особенностей, которые потребовали доработки алгоритма на 5, 7-9 шагах.

На пятом шаге в подпункте д предлагается рассчитать узел сети как изолированной СМО. В базовом алгоритме имеется ограничение: для всех узлов необходимо задать общий алгоритм численного расчёта. Следует учитывать, что этот численный алгоритм используется на всех итерациях расчёта узлов, а значит при различных значениях параметров, и может оказаться так, что на промежуточной итерации возникнет исключительная для него ситуация, что потребует прекращения расчёта, чтобы избежать этого в диссертационной работе предлагается подход к автоматизации выбора подходящего алгоритма из существующего набора, который в зависимости от конкретных параметров, будет наиболее оптимальным по скорости расчёта.

На седьмом шаге необходимо рассчитывать моменты времени пребывания заявки при однократном посещении узла. Недостатком библиотек, реализующих подобные алгоритмы, является отсутствие расчётных формул для случая замкнутых сетей. В параграфе 1.5 диссертационной работы рассматривается один из возможных подходов расчёта высших моментов для случая замкнутых СеМО, и проверяется точность, получаемых оценок ВВХ СеМО.

Восьмой шаг базового алгоритма зачастую опирается на предположение о гамма-распределении времени однократного пребывания заявки в узле, и затем в девятом шаге используется неустойчивый метод численного дифференцирования для перехода от ПЛС к начальным моментам, что сужает сферу его применимости и вносит дополнительные ошибки. Для избежания указанных недостатков далее, в параграфе 1.4, предлагается разработанный автором алгоритм замещения шагов 8-9 аналитическими формулами перехода от начальных мо-

ментов времени однократного пребывания заявок в узлах к моментам распределения времени пребывания заявок в сети в целом.

1.3 Автоматический выбор моделей узлов

На этапе подбора параметров модели приходится выбирать из большого числа доступных численных методов, которые могут подойти в конкретной ситуации. В библиотеке «Массовое Обслуживание. Стационарный режим.» (МОСТ) реализовано множество численных моделей, которые варьируются от самых частных до общих. Частные модели позволяют получать точные оценки максимально быстро, но применимы к ограниченному классу задач, более общие — применимы в большем числе случаев, но работают медленнее и с большими погрешностям. Тем не менее, каждая модель требует задания своих параметров, а, значит, подвержена ошибкам в случае неточности исходных данных.

Расчёт стационарного распределения числа заявок в СМО является базовой характеристикой для численных методов в библиотеке МОСТ, на основе которой могут быть дополнительно рассчитаны все остальные ВВХ без пересчёта всей модели. Перекрытие областей расчётов моделей можно использовать как хороший тест корректности реализации всех расчётных формул. В качестве примера приведём расчёт стационарного распределения числа заявок для системы М/Ет,!!, проведённый пятью различными способами в рамках единого пакета прикладных программ МОСТ: М/Е/п, М/G/1, С/С/л, М/С/л и имитационный метод, также для сравнения воспользуемся приложением GPSS/W. Рассмотрим модель, для которой в таблице 1.3.1 представлены оценки распределения числа заявок, рассчитанных различными методами с заданными следующими параметрами: входящий поток показательный с интенсивностью 0.8; время обслуживания в узле имеет эрлангово распределение с тремя фазами; интенсивностью каждого из них 1/3. Для такой модели численные методы работают

мгновенно, в то время как имитационным моделям требуются около 17 секунд в случае реализации из пакета МОСТ и несколько минут для того же количества реализаций внутри вРБЗ (107 реализаций). В результате можно увидеть, что все численные методы вне зависимости от используемого внутри алгоритма пришли к одному и тому же результату, а ИМ имеет систематическую ошибку. Подобное поведение ИМ можно отнести к проблемам реализации датчиков случайных чисел на вычислительных машинах.

Таблица 1.3.1 — Сравнение различных методов расчёта м/е3/1

ИМ М/Е/п М/С/1 С/С/п М/С/п

1 0.20074 0.2 0.2 0.2 0.2

2 0.19196 0.192 0.192 0.192 0.192

3 0.15307 0.15232 0.15232 0.15232 0.14235

4 0.11639 0.11551 0.11551 0.11416 0.10555

5 0.87132Е-01 0.86516Е-01 0.86516Е-01 0.85560Е-01 0.78255Е-01

6 0.64966Е-01 0.64574Е-01 0.64574Е-01 0.64125Е-01 0.58020Е-01

7 0.48008Е-01 0.48148Е-01 0.48148Е-01 0.48060Е-01 0.43018Е-01

8 0.35769Е-01 0.35891Е-01 0.35891Е-01 0.36020Е-01 0.31895Е-01

9 0.26692Е-01 0.26751Е-01 0.26751Е-01 0.26996Е-01 0.23648Е-01

10 0.19986Е-01 0.19939Е-01 0.19939Е-01 0.20233Е-01 0.17533Е-01

11 0.14651Е-01 0.14861Е-01 0.14861Е-01 0.15164Е-01 0.13000Е-01

12 0.10923Е-01 0.11076Е-01 0.11076Е-01 0.11365Е-01 0.96383Е-02

13 0.82613Е-02 0.82555Е-02 0.82555Е-02 0.85177Е-02 0.71461Е-02

14 0.62707Е-02 0.61531Е-02 0.61531Е-02 0.63838Е-02 0.52983Е-02

Выбор того или иного численного метода зависит от способа аппроксимации распределений в сети. Для открытых систем, которые используются для расчёта узлов, разработан автоматический метод выбора наиболее подходящей

модели [46], основанный на аппроксимации исходных распределений гамма-распределением.

При расчёте СМО в качестве аппроксимаций входных распределений используются распределения следующих видов: показательное, гиперэкспонеци-альное (#2), эрлангово (Ек), обобщённое распределение Эрланга со случайным обходом первой фазы (Рк), где к — число фаз. Перечисленные распределения обычно называют «фазовыми».

Допустим, некое распределение Т задаётся начальными моментами т\,т.2. Коэффициент вариации к = ^[тЦтх определяет параметр формы данного распределения. Когда I/к2 близок к единице, используется показательное распределение; когда он близок к 2,3 — используется распределение Эрланга. В случаях очень малого и очень большого коэффициента вариации используется гиперэкспоненциальная аппроксимация, в остальных случаях используется распределение Эрланга с нецелым числом фаз — вероятностным обходом первой фазы (рисунок 1.3.1).

гиперэкспоненциальное

Рисунок 1.3.1 — Автоматический выбор типа распределения в зависимости от коэффициента вариации

эрлангово

марковсково

Аппроксимации подбираются независимо для распределений интервалов между заявками и времени обслуживания в канале. Так как не все 16 вариантов

25

могут быть реализованы, то из имеющихся подбирается наиболее близкий вариант, согласно таблице 1.3.2, у которой по строкам выписаны аппроксимированное распределение интервалов между заявками (В), а по столбцам — времени обслуживания (О).

Таблица 1.3.2 — Соответствие аппроксимированных распределений и реализованных численных методов

в\о м е2 #2 Р

м М/М/п М/Е/п М/Н/п М/Р/п

е2 Е/М/п Е/Е/п Е/Н/п Р/Р/п

н2 Н/М/п Н/Н/п Н/Р/п Н/Р/п

р Р/Р/п Р/Н/п Р/Р/п Р/Р/п

Для суммирования двух потоков Н2 аппроксимацию суммарного распределения можно записать в моментах в следующем виде:

2 2

Л = 2+ л^ (1.3.1)

¿=1 ¿=1

где (yi,Лi),(uj,fЛj) — параметры аппроксимации первого и второго распределения, соответственно. Последовательное суммирование любого числа потоков можно выполнить, аппроксимируя #2-законами распределения интервалов суммарного потока и очередного слагаемого.

1.4 Расчёт времени пребывания в сети

Рассмотрим открытую СеМО, заданную пятёркой (М, Л, В, п, Я), где М, Я определены выше, Л — интенсивность входящего потока, В — матрица первых q начальных моментов распределения времени обслуживания в каналах для всех узлов, п — вектор-столбец числа каналов для всех узлов. Полная матрица

вероятностей переходов может быть представлена в форме:

Р О

R =

(1.4.1)

Q т

где <2 — матрица стационарных вероятностей переходов между узлами; Т —

вектор-столбец стационарных вероятностей того, что заявка покинет сеть для

Р.

— вектор-строка вероятностей распределения заявок из источника между узлами.

Начальные моменты (уь у г, •. •, уд) распределения времени пребывания заявки в сети можно определить как

(верхний индекс определяет порядок производной), у(^) — функция ПЛС для распределения суммарного времени пребывания заявки в сети. Можно показать [58], что

где I — единичная матрица размера МхМ; N(s) = diag{j\(s),..., Jm(s)) — Диагональная матрица ПЛС распределения времени пребывания при однократном посещении каждого из узлов; T(s) = N(s) • Q.

Отметим, что этот подход применим к сетям произвольной структуры, в том числе к СеМО с циклами, так как структура матрицы R при таком подходе не важна, что значительно отличает его от других методов. Для расчёта моментов распределения времени пребывания заявки в сети можно воспользоваться формулой (1.4.2). Операцию дифференцирования ПЛС можно реализовать как численным, так и аналитическим методом. Ниже во всех формулах параграфа «для упрощения» будем опускать индекс узла.

Так как ПЛС легко вычисляется для показательно-степенных функций, то, например в [54], предлагается воспользоваться аппроксимацией плотности

Заключение диссертации по теме «Системный анализ, управление и обработка информации (по отраслям)», Кокорин, Сергей Владимирович

Выводы

Анализ разработанных моделей функционирования подсистемы мониторинга проекта «Ракурс Д» выявил ошибки в логике функционирования ИВСет обработки телеметрической информации за счёт расхождений в оценках по ретроспективным базам данным и оценкам, получаемым из модели, тем самым удалось подтвердить соответствие между поведением модели и ИВСет.

Созданная модель ИВСет сбора и обработки телеметрической информации позволила оценить долю заявок, успевающих пройти обработку до появления следующего пакета при заданных характеристиках сети. Для проекта «Ракурс Д» можно говорить, что при штатной работе инфраструктуры реактора в среднем проекты выполняются на пределе возможностей настольного компьютера — лишь 94% всех заявок успевают отработать за отведённые 0.1 секунды, без перегрузки системы, а увеличение числа процессоров либо уменьшение времени обработки отдельного оператора заметно влияют на долю вовремя обработанных пакетов. Моделирование нагрузок в критической ситуации показало, что требуется 3-4 сервера, типа HP ProLiant, для обработки возросшего потока информации.

Для программного проекта «Ракурс Д» можно предложить ещё большую декомпозицию входных параметров, так как это позволит уменьшить число пересчитываемых операторов при появлении каждого нового пакета.

С помощью разработанной модели удалось оценить условия, при которых отклик на изменения состояния ИВСет не нарушает ограничения накладываемых реальным масштабом времени, что также дало возможность проанализировать пригодность оборудования для проведения необходимых расчётов. Рассмотрение необходимых прикладных вопросов предварительной обработки и правил верификации применимости модели к имеющимся исходным данным предоставляет возможность автоматизировать процессы подготовки данных, выявить границы применимости предлагаемых методов.

Для описания нестационарного поведения моделируемой ИВСет, в рамках диссертации предлагается определять участки стационарности моделируемой системы, оценить их продолжительность и проводить расчёты и оптимизацию параметров ИВСет отдельно на каждом участке стационарности в РМВ за счёт использования быстрых приближённых численных методов, предлагаемых в главах 1,2. Анализ проекта «Ракурс Д» показал принципиальную возможность использования предложенного подхода к моделированию функционирования ИВСет, так как запас производительности, созданный благодаря нему, позволяет утверждать, что моделируемые системы могут иметь на порядок больше параметров и при этом оперативно проводить расчёт и оптимизацию их ВВХ.

Заключение

В результате проведённых исследований в диссертационной работе была решена важная актуальная научно-техническая задача моделирования, расчёта и оптимизации ВВХ ИВСет и получены следующие основные результаты:

- проведён критический анализ существующих подходов к постановке и решению задачи моделирования, расчёта и оптимизации ВВХ ИВСет, выбраны и обоснованы пути её решения;

- разработаны аналитические модели СеМО, которые позволяют с требуемой степенью адекватности описать ИВСет и определена область их применения;

- разработана ИМ для расчёта характеристик ИВСет;

- предложены алгоритмы и методы решения задач моделирования, расчёта и оптимизации ВВХ ИВСет;

- разработаны и реализованы прототипы программ для расчёта и оптимизации ВВХ ИВСет;

- проиллюстрирована конструктивность разработанного модельно-алго-ритмического обеспечения на примере задачи анализа существующей ИВСет обработки телеметрической информации.

В сравнении с существующими подходами расчёта и оптимизации характеристик ИВСет разработанные алгоритмы и методы обладают такими преимуществами, как низкие трудозатраты и наличие возможности построения иерархии моделей в зависимости от уровней точности, качества, объёма входных данных и требований к точности ЦФ за счёт минимизации использования ИМ. Расширенная область применимости известных алгоритмов и методов благодаря разработке и реализации более устойчивых методов расчёта характеристик ИВСет дала возможность улучшить результаты задач моделирования оценок этих характеристик и провести расчёт новых характеристик, оценка которых ранее была не возможна. Упор на численные подходы при использовании предложенных алгоритмов и методов позволил оперативно экспериментировать с параметрами модели ИВСет и задавать их не только точно, но и интервально, чтобы в последствии проводить формальную оптимизацию в рамках предпочтительных значений.

В области теоретических исследований автором предложены:

- алгоритм расчёта высших моментов и аппроксимации функции распределения времени пребывания заявок в узлах для однородных замкнутых СеМО при однократном посещении узла, который по сравнению с имеющимися аналогами допускает задание произвольных распределений времени обслуживания в узлах, что расширяет область применения метода оценки ВВХ ИВСет на случай, когда распределения далеки от показательного, как это предполагается во многих существующих моделях;

- подход к исключению шага (этапа) численного дифференцирования для оценки моментов распределения времени пребывания заявок в смешанных неоднородных СеМО, который посредством использования аналитических формул является более точным, менее трудоёмким, не зависящим от выбора шага численного дифференцирования и более устойчивым к изменению входных данных по сравнению с другими подходами;

- метод комбинированной оптимизации ВВХ ИВСет, который в отличие от других методов не требует задания начального приближения, информации о производных и благодаря использованию фундаментальной методологии ТМО применим к широкому классу аналитико-имитационных моделей;

- модифицированный метод ИМ «меченых заявок» для моделирования ИВСет, который использует алгоритмы сокращения зависимостей между учитываемыми наблюдениями, позволяет избавиться от смещённости оценок рассматриваемых характеристик классического алгоритма реализации этого метода и, в сравнении с другими способами реализации ИМ, позволяет получить как оценки с существенно меньшей дисперсией при сопоставимой длительности моделирования, так и доверительные интервалы для них.

В области прикладных исследований автором предложены:

- алгоритм автоматического выбора наиболее подходящей схемы расчёта характеристик СМО в зависимости от параметров, который выбирает из класса расчётных схем, описывающих данную задачу, наиболее узкую схему, позволяющую получить результаты расчёта характеристик оптимальные по точности и времени счёта;

- подход к ограничению пространства параметров, использующий модифицированный метод штрафных функций, который позволяет за счёт выбора метода штрафования задать предпочтительную область параметров и управлять скоростью сходимости метода оптимизации;

- модель смены сценариев стационарного поведения моделируемой ИВСет в терминах МСЦМ, что позволяет предсказывать смену участков стационарности по косвенным признакам и корректно применять численные методы расчёта её характеристик отдельно на каждом из таких участков.

В области реализации и использования результатов исследований автором разработаны:

- программное приложение расчёта ВВХ ИВСет численными методами (А-МОСТ);

- программное приложение оптимизации ВВХ ИВСет численными методами (С)ШрО;

- система имитационного моделирования для проверки качества реализации численных методов и для описания случаев, допускающих изменение конфигурации ИВСет во время моделирования;

- подходы расчёта и оптимизации ВВХ ИВСет, применённые к анализу АПК обработки телеметрической информации «Ракурс Д».

Из вышесказанного следует, что результаты работы могут быть использованы как на этапе проектирования ИВСет для исследования возможностей проектируемой системы и выдачи рекомендаций по характеристикам аппаратной базы и организации процесса функционирования; так и на этапе реализации для поддержки в принятии решений при управлении функционированием ИВСет и при проведении её модернизации, а также для проверки качества функционирования моделируемой системы.

В результате практической реализации были предложены:

- формализация запроса экспертов относительно показателей эффективности моделируемой системы;

- иерархия моделей описания функционирования ИВСет обработки телеметрической информации;

- методы расчёта требуемых ВВХ;

- методы верификации показателей функционирования и проектирования ИВСет;

- подход к предсказанию смены сценариев поведения ИВСет;

- подход к решению задачи выбора необходимого состава и структуры АПК ИВСет;

- подход к оценке чувствительности узлов сети к деградации структуры.

Таким образом, достигнута главная цель диссертационной работы — разработаны алгоритмы и методы, позволяющие сократить сроки при проектировании, внедрении, модернизации ИВСет и дающие возможность повысить уровень целевых и информационно-технологических возможностей, устойчивости функционирования её элементов и подсистем на основе совершенствования и автоматизации методов расчёта и оптимизации её ВВХ.

Список литературы диссертационного исследования кандидат технических наук Кокорин, Сергей Владимирович, 2012 год

Литература

[1] Bhat, U. Narayan. An introduction to queueing theory. Modeling and analysis in applications / U. Narayan Bhat. — Birkhauser, 2008. — P. 268.

[2] Bose, Sanjay K. An Introduction to Queueing Systems / Sanjay K. Bose. — Springer, 2002. — P. 312 p.

[3] Bramson, M. Stability of queueing networks / M. Bramson. — Springer, 2008. — Vol. 5. — P. 169-345.

[4] Brent, R.P. Algorithms for minimization without derivatives / R.P. Brent. — USA, NJ: Prentice-Hall Inc., 1973. — P. 195.

[5] Breuer, L. An Introduction to queueing theory and matrix-analytic methods. / L. Breuer, D. Baum. — Springer, 2005. — P. 278.

[6] Challenges to global RFED adoption / N.C. Wu, M.A. Nystrom, T.R. Lin, H.C. Yu // Technovation. — 2005. — December. — Vol. 26. — P. 1317-1323.

[7] Chen, Hanning. Multi-colony bacteria foraging optimization with cell-to-cell communication for RFID network planning. / Hanning Chen, Yunlong Zhu, Kunyuan Hu II Applied Soft Computing. — 2010. — Vol. 10. — P. 539-547.

[8] Colorni, A. Distributed optimization by ant colonies / A. Colorni, M. Dorigo, V. Maniezzo // Actes de la première conférence européenne sur la vie artificielle,. — Paris, France: Elsevier Publishing, 1991. — Pp. 134-142.

[9] Kamath, M. RAQS: A software package to support instruction and research in queueing systems / M. Kamath, S. Sivaramakrishnan, G. Shirhatti // 4th Industrial Engineering Research Conference Proceedings. — GA: 1995. — Pp. 944-953.

[10] Kelly, F.P. Reversibility and Stochastic Networks. / F.P. Kelly. — Wiley, 1979.

— P. 238.

[11] Kelly, F.P. Network Routing / F.P. Kelly // Phil. Trans. R. Soc. Lond. A,337. — 1991. _ Vol. 337. — Pp. 343-367.

[12] Klimov, R. Simulation-based measurement of supply chain risks / R. Klimov, Ju. Merkuryev // ECMS. — 2008.

[13] Kokorin, S.V. Numerical Methods of Structure Optimization of Homogeneous Queuing Networks / S.V Kokorin, B.Y. Sokolov // Proceeding of the 7th EU-ROSIM Congress on Modelling and Simulation / Ed. by Miroslav Cepek Jan Drchal Miroslav Snorek, Zdenek Buk. — Vol. 2. — 2010. — P. 29.

[14] Matloff, N. Advanced Features of the SimPy Language. — 2008. http:// heather.cs.ucdavis.edu/~matloff/156/PLN/AdvancedSimPy.pdf.

[15] Medhi, Jyotiprasad. Stochastic models in queueing theory / Jyotiprasad Medhi.

— 2 edition. — Elsevier Science & Technology, 2010. — P. 450 p.

[16] Nazareth, J.L. Differentiable optimization and equation solving, a treatise on algorithmic science and the Karmarkar revolution. / J.L. Nazareth. — Springer, 2003. — P. 240.

[17] Neuts, Marcel F. Matrix-analytic methods in queuing theory / Marcel F. Neuts // European Journal of Operational Research. — 1983. — no. 15. — Pp. 2-12.

[18] Nocedal, Jorge. Updating Quasi-Newton Matrices With Limited Storage / Jorge Nocedal // Mathematics of computation. — 1980. — July. — Vol. 35, no. 151. — Pp. 773-782.

[19] Tech. Rep.: / Alex Zhang, Pano Santos, Dirk Beyer, Hsiu-Khuern Tang: Intelligent Enterprise Techno logy Laboratory, 2002.

[20] Qu, Xiuli. A model for quantifying the value of RFID-enabled equipment tracking in hospitals. / Xiuli Qu, Simpson LaKausha T., Paul Stanfield // Advanced Engineering Informatics. — 2010.

[21] Queuing Networks and Markov Chains Modeling and Performance Evaluation with Computer Science Applications / G. Bolch, S. Greiner, H. De Meer, K.S. Trivedi. — USA: A Wiley-lnterscience publication, 2006.

[22] RFID network planning using a multi-swarm optimizer / Hanning Chen, Yun-long Zhu, Kunyuan Hu, Tao Ku // Journal of Network and Computer Applications. — 2010.

[23] Rabiner, Lawrence R. A tutorial on Hidden Markov Models and Selected Applications in Speech Recognition / Lawrence R. Rabiner // Proceedings of the IEEE. — Vol. 77. — 1989. — february. — Pp. 257-286.

[24] Ramaekers, Katrien. Analysis of a production-inventory system with unreliable production facility / Katrien Ramaekers, Janssens Gerrit K. // ECMS. — 2007.

[25] Roh, James Jungbae. Classification of RFID adoption: An expected benefits approach. / James Jungbae Roh, Anand Kunnathur, Monideepa Tarafdar // Information & Management. — 2009. — Vol. 46. — P. 357-363.

[26] Russell, S. J. Artificial intelligence: a modern approach / S. J. Russell, P. Norvig. — Prentice Hall/Pearson Education, 2003. — P. 1080.

[27] Tajima, May. Strategic value of RFID in supply chain management / May Taji-ma // Journal of Purchasing and Supply Management. — 2006. — Vol. 13. — P. 261-273.

[28] Thomas, Nigel. Approximate solution of a class of queueing networks with breakdowns / Nigel Thomas, David Thornley, Harf Zatschler // European Sim-

ulation Multiconference. — Nottingham: 2003. — May. — Pp. 10-16. http://pubs.doc.ic.ac.uk/approx-queueing-breakdowns/.

[29] Yao, David D. Stochastic Modeling and Optimization with applications in Queues, Finance, and supply chains. / David D. Yao, Hanqin Zhang, Xun Yu Zhou. — Springer, 2003.

[30] A model based approach for calculating the process driven business value of RFID investments / Jorg Becker, Lev Vilkov, Burkhard Weiss, Axel Winkelmann // International journal of Production Economics. — 2010. — Vol. 127. — P. 358-371.

[31] Алиев, Т.И. Основы моделирования дискретных систем / Т.И. Алиев. — СПб: СПбГУ ИТМО, 2009.

[32] Башарин, Г.П. Лекции по математической теории телетрафика / Г.П. Ба-шарин. — Изд. Рос. университета дружбы народов., 2004. — С. 186.

[33] Бусленко, Н.П. Моделирование сложных систем / Н.П. Бусленко. — М.: Наука, 1968. — Р. 356.

[34] Вишневский, В.М. Теоретические основы проектирования компьютерных сетей / В.М. Вишневский. — Техносфера, 2003. — С. 512.

[35] Воронцов, Ю.А. Диффузионная аппроксимация многолинейной СМО ограниченной емкости G/G/1/n. / Ю.А. Воронцов // Тезисы докладов XI Всесоюзной Школы семинара по вычислительным сетям. / Научный Совет по комплексной проблеме "Кибернетика"АН СССР. — Рига: 1986. — Pp. 75-80.

[36] Гончаренко, В. А. Модели адаптивного перераспределения нагрузки в кластерных вычислительных системах. / В. А. Гончаренко // Изв. вузов. Приборостроение. — 2008. — Т. 51, № 3. — С. 32—37.

[37] Горцев, A.M. Полусинхронный дважды стохастический поток событий при продлевающемся мертвом времени / A.M. Горцев, Л.А. Нежельская // Вычислительные технологии. — 2008. — Т. 13. — С. 31-41.

[38] Емельянов, В.В. Теория и практика эволюционного моделирования /

B.В. Емельянов, В.В. Курейчик, В.М. Курейчик. — Физматлит, 2003. —

C. 432.

[39] Задорожный, В.Н. Распределение каналов в однородных немарковских сетях с очередями / В.Н. Задорожный // Омский научный вестник. — 1997. — С. 5-10.

[40] Задорожный, В.Н. Методы аналитико-имитационного моделирования систем с очередями и стохастических сетей / В.Н. Задорожный. — Омск, 2011.

[41] Иванов, Д.А. Управление цепями поставок / Д.А. Иванов. — СПб.: Изд-во Политехи, ун.-та, 2009. — С. 660.

[42] Иглхарт, Д. Регенеративное моделирование сетей массового обслуживания / Д. Иглхарт, Д. Шедлер. — М.: Радио и связь, 1984. — С. 136.

[43] Келыпон, В. Имитационное моделирование / В. Кельтон, A. Jloy. — СПб.: Питер (BHV), 2004. — С. 847.

[44] Кобзарь, А.И. Прикладная математическая статистика. Для инжинеров и научных работников / А.И. Кобзарь. — Москва: Физматлит, 2006. — С. 816.

[45] Кокорин, C.B. Имитационная модель приоритетной многоканальной системы массового обслуживания / C.B. Кокорин // Труды IV Всероссийской научно-практической конференции по имитационному моделированию и

его применению в науке и промышленности «Имитационное моделирование. Теория и практика». (ИММОД). — 2009. — С. 146-148.

[46] Кокорин, C.B. Автоматическая сборка программ решения комплексных задач теории очередей. / C.B. Кокорин, Ю.И. Рыжиков // Региональная информатика (РИ-2010). XII Санкт-Петербургская международная конференция «Региональная информатика (РИ-2010)». Труды конференции. — СПОИСУ, 2010. — С. 48.

[47] Кокорин, C.B. Оптимизация параметров сетей массового обслуживания на основе комбинированного использования аналитических и имитационных моделей / C.B. Кокорин, Ю.И. Рыжиков // Приборостроение. — 2010. — Vol. 53. — Pp. 61-66.

[48] Кормен, Т. Алгоритмы: построение и анализ. / Т. Кормен, Ч. Лейзерсон, Р. Ривест. — М.: МЦНМО, 1999. — С. 960.

[49] Моисеев, H.H. Элементы теории оптимальных систем / H.H. Моисеев. — М.: Наука, 1974. — С. 528.

[50] Никифоров, В.В. Выполнимость приложений реального времени на многоядерных процессорах / В.В. Никифоров // Труды СПИИРАН. — 2009. — Т. 8. — С. 255-284.

[51] Охтилев, М.Ю. Интеллектуальные информационные технологии мониторинга и управления структурной динамикой сложных технических объектов. / М.Ю. Охтилев, Б.В. Соколов, P.M. Юсупов. — Москва: Наука, 2006.

[52] Потрясаев, С.А. Динамическая модель и алгоритмы комплексного планирования операций и распределения ресурсов в корпоративной информационной системе .: Ph.D. thesis / СПИИРАН. — 2009.

[53] Реклейтис, Г. Оптимизация в технике / Г. Реклейтис, К. Рэгсдел А. Рей-виндран. — М.: Мир, 1986. — Т. 1. — С. 348.

[54] Рыжиков, Ю.И. Машинные методы расчёта систем массового обслуживания / Ю.И. Рыжиков. — СПб: ВИКИ им А. Ф. Можайского, 1979. — С. 177.

[55] Рыжиков, Ю.И. Теория очередей и управление запасами / Ю.И. Рыжиков. — СПб: Питер, 2001. — Р. 384.

[56] Рыжиков, Ю.И. Имитационное моделирование. Теория и технологии. / Ю.И. Рыжиков. — СПб: Корона принт, 2004. — С. 384.

[57] Рыжиков, Ю.И. Имитационное моделирование: курс лекций. / Ю.И. Рыжиков. — СПб: BKA им. А. Ф. Можайского, 2007. — С. 125.

[58] Рыжиков, Ю.И. Компьютерное моделирование систем с очередями. Курс лекций. / Ю.И. Рыжиков. — СПб: BKA им. А. Ф. Можайского, 2007. — С. 125.

[59] Саати, Т.Л. Элементы теории массового обслуживания и её приложения / T.JI. Саати. — М.: Советское Радио, 1965. — С. 511.

[60] Соколов, Б.В. Комплексное моделирование рисков при выработке управленческих решений в сложных организационно-технических системах. / Б.В. Соколов, P.M. Юсупов // Проблемы управления и информатики. — 2006. — Т. 1.

[61] Уолрэнд, Дж. Введение в теорию сетей массового обслуживания / Дж. Уолрэнд; Ed. by В. Ф. Матвеев. — М.: Мир, 1993. — Р. 336 с.

[62] Чичинадзе, В.К. Решение невыпуклых нелиненых задач оптимизации. Метод пси-преобразования / В.К. Чичинадзе. — М.: Наука., 1983.

[63] Шеннон, Р. Имитационное моделирование систем - искусство и наука / Р. Шеннон. — Мир, 1978. — С. 418.