Математическое и компьютерное моделирование процессов планирования и распределения разнородных ресурсов в промышленных сетях тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат наук Фам Ань Минь

• Фам Ань Минь
• кандидат наук
• 2022

Оглавление диссертации кандидат наук Фам Ань Минь

ВВЕДЕНИЕ

ГЛАВА 1 АНАЛИЗ И ИССЛЕДОВАНИЕ ИЗВЕСТНЫХ ПОДХОДОВ ПЛАНИРОВАНИЯ И РАСПРЕДЕЛЕНИЯ РЕСУРСОВ В ПРОМЫШЛЕННЫХ СЕТЯХ

1.1 Концепция и технологии Интернета вещей

1.2 Известные подходы планирования и распределения ресурсов в промышленных сетях

1.3 Обзор исследований по GERT-сетям

1.4 Зависимые и независимые случайные величины в ОЕЯТ-сетях

1.5 Расчет количества ресурсов в промышленных сетях

1.6 Основные результаты

ГЛАВА 2 МАТЕМАТИЧЕСКИЕ МОДЕЛИ, МЕТОДЫ И АЛГОРИТМЫ ПЛАНИРОВАНИЯ И РАСПРЕДЕЛЕНИЯ РАЗНОРОДНЫХ РЕСУРСОВ В ПРОМЫШЛЕННЫХ СЕТЯХ

2.1 Математические модели нахождения вероятности назначения пары операций для выделения ресурсов в промышленных сетях

2.2 Численный метод и алгоритмы определения плотности распределения времени между операциями в промышленных сетях

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

2.4 Численно-аналитический метод и алгоритм планирования и распределения разнородных ресурсов с функционально зависимыми случайными операциями в промышленных сетях

2.5 Сложные зависимости времени и ресурсов в параллельном подходе

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

2.7 Основные результаты

ГЛАВА 3 МЕТОДИКИ ПЛАНИРОВАНИЯ И РАСПРЕДЕЛЕНИЯ РАЗНОРОДНЫХ РЕСУРСОВ В ПРОМЫШЛЕННЫХ

ТЕЛЕКОММУНИКАЦИОННЫХ СЕТЯХ

3.1 Методика планирования и распределения разнородных ресурсов в устройствах обработки информации с упорядоченным набором операций

3.2 Методика планирования разнородных ресурсов в экспоненциальной GERT-сети

3.3 Методика нахождения ресурсов в модели резервного канала

3.4 Методика оценки доступности системы с нефиксированными порогами выделяемых ресурсов

3.5 Методика использования ресурсов для изменения времени выполнения операций

3.6 Методика распределения ресурсов в раскрашенных GERT-сетях

3.7 Основные результаты

ГЛАВА 4 КОМПЬЮТЕРНОЕ МОДЕЛИРОВАНИЕ ПРОЦЕССОВ ПЛАНИРОВАНИЯ И РАСПРЕДЕЛЕНИЯ РАЗНОРОДНЫХ РЕСУРСОВ В ПРОМЫШЛЕННЫХ СЕТЯХ

4.1 Структура комплекса программ компьютерного моделирования промышленных сетей

4.2 Программа расчета временного интервала между операциями TaskTimeModeler

4.3 Программа планирования и распределения разнородных ресурсов с упорядоченным набором операций TasksReordermgModeler

4.4 Программа планирования и распределения разнородных ресурсов с

применением функциональных зависимостей ResourceModeler

4.5. Основные результаты

ЗАКЛЮЧЕНИЕ

СПИСОК ЛИТЕРАТУРЫ

ПРИЛОЖЕНИЕ А

ПРИЛОЖЕНИЕ Б

ВВЕДЕНИЕ

Актуальность темы исследования. В настоящее время технологии Интернета вещей (Internet of Things, IoT) становятся все более популярными. В связи с быстрым ростом количества устройств, подключенных к IoT-сети, необходимо оперативно передавать и обрабатывать большие потоки информации. Поэтому показатели сетевых устройств по скорости обработки информации, передаче данных и эффективности распределения ресурсов нуждаются в улучшении. Также стоит заметить, что стоимость обновления оборудования в IoT-сети достаточно высокая.

Текущая система связи между устройствами IoT-сети построена на основе сетевых устройств инфраструктуры Интернет. Промышленные сети Интернета вещей (Industrial Internet of Things, IIoT) имеют более разнородные устройства, где память и вычислительные мощности считаются важными ресурсами. Путем реорганизации и программирования процессов обработки информации, передачи данных и распределения ресурсов на существующих устройствах может быть достигнута значительная экономия затрат на обновление оборудования. Оценка и анализ процессов планирования и распределения ресурсов способствуют повышению эффективности функционирования промышленных IoT-сетей.

Для анализа и оценки проектов со сложной стохастической структурой в промышленных сетях часто применяется математический аппарат GERT-сетей, благодаря наличию следующих преимуществ: вероятностных ветвлений, допущению возвратов к ранее выполненным операциям и использованию циклов. Промышленные устройства часто характеризуются ограниченными ресурсами (например, памятью, вычислительной мощностью, пропускной способностью и многими другими), что может создавать множество проблем, связанных с нехваткой ресурсов. Следовательно, для управления такими промышленными устройствами требуются технологии, способные управлять ограниченными ресурсами. Расширение функциональных возможностей классической GERT-сети путем добавления параметра ресурса в модель GERT-сети позволяет одновременно проводить оценку и анализ вероятностно-временных и вероятностно-ресурсных харак-

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

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

Степень разработанности темы исследования. Большой вклад в решение задачи планирования и распределения разнородных ресурсов в вычислительных системах и промышленных сетях внесли российские ученые Антамошкина Е.А., Абдуллаев Д.А., Амирсаидов У.Б., Бусленко Н.П., Вентцель Е.С., Воропаев В.И., Девятков В.В., Демкин И.В., Голенко-Гинзбург И., Емельянов А.А., Захаров Г.П., Корячко В.П., Шибанов А.П., Ласло З., Любкин С.М., Максимов Н.А., Овчаров Л.А., Осипчук О.К., Резер В.С., Ситняковский С.Л. А также зарубежные: Анго А., Бертсекас Д, Галлагер Р., Дейкстра Э., Кнут Д.Э. Клейнрок, Л., Феллер В., Шрайбер Т.Дж., Филлипс Д., Alavi S.H., Antkiewicz R., Agarwal M., Bagherpour M., Bevrani H., Chen M., Dyk M., Fatemi Ghomi T.F., Feili H., Jose K.P., Iranzadeh S., Youshanloi K.R., Hashemin S.S., Kasprzyk R., Najgebauer A., Najmoddin M., Pierzchalam D., Pooja Mohan P, Pritsker A.A.B., Razeghi S., Tarapata Z, Wang J., Wyrozebski P., Wyrozebska A, Wirth N.

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

Для достижения этой цели необходимо решить следующие задачи:

- провести исследование и анализ известных подходов планирования и распределения ресурсов в промышленных сетях;

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

- выполнить расчет вероятности назначения пары операций для выделения ресурсов в промышленных сетях;

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

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

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

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

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

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

- разработать методику нахождения ресурсов в модели резервного канала;

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

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

- разработать методику распределения ресурсов в раскрашенных GERT-

сетях;

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

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

Предмет исследования: средства математического и компьютерного моделирования промышленных сетей с разнородными ресурсами.

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

Соответствие паспорту специальности. Содержание диссертационной работы соответствует паспорту специальности 05.13.18 - «Математическое моделирование, численные методы и комплексы программ» по следующим пунктам:

п. 1 «Разработка новых математических методов моделирования объектов и явлений»;

п.2 «Развитие качественных и приближенных аналитических методов исследования математических моделей»;

п.4 «Реализация эффективных численных методов и алгоритмов в виде комплексов проблемно-ориентированных программ для проведения вычислительного эксперимента»;

п.8 «Разработка систем компьютерного и имитационного моделирования». Научная новизна. В работе получены следующие результаты, отличающиеся научной новизной:

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

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

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

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

- комплекс программ компьютерного моделирования процессов планирования и распределения разнородных ресурсов в промышленных сетях на основе моделей ОЕЯТ-сетей, отличающийся учетом параметров ресурсов в модели ОЕЯТ-сети и позволяющий сократить сроки их проектирования и анализа.

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

1 Математические модели, метод и алгоритмы назначения пары операций для выделения ресурсов в промышленных сетях на основе моделей ОЕЯТ-сетей.

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

3 Математические модели определения вероятностно-ресурсных характеристик с учетом важности выделяемых ресурсов в промышленных сетях.

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

5 Комплекс программ компьютерного моделирования процессов планирования и распределения разнородных ресурсов в промышленных сетях.

Степень достоверности результатов. Степень достоверности положений и выводов диссертации определяется:

- отсутствием противоречий с известными научными положениями;

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

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

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

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

- в разработке моделей, методов и алгоритмов назначения упорядоченного набора операций в GERT-сети;

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

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

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

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

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

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

Практическая значимость работы подтверждается актами о внедрении в организациях ООО «Технология и торговля Мегалайн» (Вьетнам) и ООО «Вьетнамское Программное Обеспечение и Технологическое Развитие» (Вьетнам), а также в учебном процессе на кафедре САПР ВС РГРТУ.

Апробация результатов диссертации. Результаты исследований докладывались и обсуждались на следующих всероссийских и международных конференциях: V-VI Всероссийской научно-технической конференции «Актуальные проблемы современной науки и производства» (г. Рязань, 2020, 2021); XXIV-XXVI Всероссийской научно-технической конференции студентов, молодых ученых и специалистов «Новые информационные технологии в научных исследованиях» (г. Рязань, 2019, 2020, 2021); IV-V Международный научно-технический форум «Современные технологии в науке и образовании» (г. Рязань, 2021, 2022); 17th International Symposium «Problems of Redundancy in Information and Control Systems» (REDUNDANCY) (Moscow, 2021), 14th International Conference ELEKTRO (Krakow, Poland, 2022).

Публикации. По итогам проведенных исследований опубликовано 17 научных работ: в том числе 6 статей в изданиях из Перечня ведущих рецензируемых научных журналов и изданий ВАК; 2 статьи в изданиях, входящих в международные базы научного цитирования Web of Science и Scopus; 7 докладов на международных и всероссийских научно-технических конференциях; 1 статья в научно-техническом журнале; 1 свидетельство о регистрации программы для ЭВМ в Роспатент.

Реализация и внедрение результатов работы.

- в ООО «Технология и торговля Мегалайн» (Вьетнам);

- в ООО «Вьетнамское Программное Обеспечение и Технологическое Развитие» (Вьетнам);

- в учебном процессе на кафедре САПР ВС РГРТУ.

Структура и объем диссертации. Диссертационная работа состоит из введения, 4 глав, заключения, списка литературы, 2 приложений, изложенных на 164 страницах (включая 92 рисунка и 11 таблиц). Список литературы содержит 108 наименований.

ГЛАВА 1 АНАЛИЗ И ИССЛЕДОВАНИЕ ИЗВЕСТНЫХ ПОДХОДОВ ПЛАНИРОВАНИЯ И РАСПРЕДЕЛЕНИЯ РЕСУРСОВ В ПРОМЫШЛЕННЫХ СЕТЯХ

1.1 Концепция и технологии Интернета вещей

Четвертая промышленная революция (англ. The Fourth Industrial Revolution), также известная как Индустрия 4.0 (англ. Insustry), формирует концепцию быстрых изменений в технологиях, отраслях и социальных моделях и процессах в 21 веке, обусловленных расширением возможностей подключения и интеллектуальной автоматизацией [45-47]. Индустрия 4.0 строится на основе Индустрия 3.0. История промышленных революций показана на рис

Industry

Механический ткацкий станок, паровой двигатель.

1784

11111111 п

ш

Industry

Первая производственная линия. Массовое производство с использованием электроэнергии.

1870

Industry

Первый программируемый логистический

контроллер. Использование электроники и информационных

технологий для дальнейшей автоматизации.

1969

ий

Industry

Киберфизические системы (соединение реальных объектов с информационными

процессами или виртуальными объектами через информационные сети и интернет).

Сегодня

Рисунок 1.1 - История промышленных революций Первая промышленная революция произошла около 1784 года. Первая промышленная революция характеризовалась использованием энергии воды и пара и механизацией производства.

Вторая промышленная революция зародилась примерно с 1870 года до начала Первой мировой войны. Эта промышленная революция характеризуется

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

Третья промышленная революция возникла примерно в 1969 году, с появлением и распространением информационных технологий (ИТ), использованием электроники и информационных технологий для автоматизации производства.

Концепция «Индустрия 4.0» была впервые представлена на Ганноверской промышленной ярмарке в Федеративной Республике Германия в 2011 году. Индустрия 4.0 - это современная тенденция автоматизации и обмена данными в производственных технологиях. Она принесла много преимуществ и вызовов экономическому и социальному секторам многих стран [45, 46, 66, 86, 96]. Индустрия 4.0 включает в себя Интернет вещей (IoT), Big Data, Облачные вычисления, Автономные роботы, Искусственный интеллект, Аддитивное производство, Моделирование, Кибербезопасность и т.д.

На рисунке 2.2 показаны основные технологии Индустрии 4.0. Они широко используются в промышленности, особенно в производстве.

Рисунок 1.2 - Основные технологии Индустрии

Интернет вещей (Internet of Things, IoT) является свидетельством скорости, с которой происходят изменения в цифровом мире. Интернет вещей - концепция вычислительной сети физических предметов, которые оснащены технологиями для взаимодействия друг с другом, а также с внешней средой, рассматривающая организацию таких сетей как явление, способное перестроить процессы общественные и экономические, исключая часть действий, в которых участвует человек [7]. Интернет вещей предоставляет подробную информацию о времени работы машин на предприятиях. С помощью Интернета вещей наша жизнь становится более умной, удобной, комфортной и взаимосвязанной.

Наиболее важные функции IoT включают искусственный интеллект, возможность подключения, датчики, активное участие и использование небольших устройств. Краткий обзор этих функций приведен ниже:

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

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

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

- Активное взаимодействие. Большая часть современного взаимодействия с подключенными технологиями происходит посредством пассивного взаимодействия. Интернет вещей представляет новую парадигму активного контента, продуктов или услуг.

- Небольшие устройства - устройства, как и предполагалось, со временем стали меньше, дешевле и мощнее. Интернет вещей использует специально созданные небольшие устройства для обеспечения точности, масштабируемости и универсальности.

Преимущества 1оТ охватывают все сферы жизни и бизнеса. Вот список некоторых преимуществ, которые может предложить 1оТ:

- Улучшенное взаимодействие с клиентами. Текущая аналитика страдает от слепых зон и значительных недостатков в точности; и, как уже отмечалось, взаимодействие остается пассивным. IoT полностью меняет это, чтобы обеспечить более насыщенное и эффективное взаимодействие с аудиторией.

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

- Сокращение отходов - 1оТ делает очевидными области улучшения. Текущая аналитика дает нам поверхностное понимание, но 1оТ предоставляет реальную информацию, что позволяет более эффективно управлять ресурсами.

- Усовершенствованный сбор данных. Современный сбор данных страдает из-за своих ограничений и дизайна для пассивного использования. 1оТ вырывает его из этих пространств и помещает именно туда, куда люди действительно хотят пойти, чтобы проанализировать наш мир. Это позволяет получить точную картину всего.

Приложения Интернета вещей появляются во многих аспектах современной общественной жизни. Интернет вещей используется при оказании необходимых услуг в период пандемии Ковид-19 [48]. Возможности и перспективы использования 1оТ технологий в сфере ЖКХ рассмотрены в работе [44]. Система мониторинга качества воздуха 1оТ определяет концентрацию газа [80]. Информация о здоровье пациентов из социальных сетей собирается, а затем оценивается с использованием передовых методов, таких как машинное обучение, для выявления вспышек и распространения в пределах географической области [73]. Модель

умного города с транспортной системой, интегрированном со многими датчиками для управления транспортными средствами, предложена в [85]. Он ориентирован на решение проблемы общественного транспорта и чрезвычайных ситуаций во время высокоприоритетных ситуаций.

На рисунке 1.3 показаны приложения Интернета вещей в различных областях.

Рисунок 1.3 - Приложения Интернета вещей

Архитектура 1оТ

Интернет вещей имеет широкий спектр приложений, и использование Интернета вещей растет очень быстро. В зависимости от различных областей применения Интернета вещей, он работает соответственно тому, как он был спроектирован или разработан. Но у него нет стандартной определенной архитектуры работы, которой строго следуют повсеместно. Архитектура 1оТ зависит от ее функциональности и реализации в различных секторах [88, 104, 107]. В работе [9] рассмотрена шестиуровневая архитектура, основанная на иерархической структуре сетей.

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

ных или облако для обработки, анализа и хранения. На рисунке 1.4 показаны четыре этапа архитектуры 1оТ.

Рисунок 1.4 - Этапы Архитектуры Интернета вещей

Этап 1 (Sensors/Actuators):

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

Этап 2 (Data Acquisition Systems):

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

Этап 3 (Edge Analytics):

После оцифровки и агрегирования данных IoT может потребоваться их дальнейшая обработка, прежде чем они попадут в центр обработки данных, и именно здесь вступает в действие Edge Analytics.

Этап 4 (Cloud Analytics):

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

Технологии и протоколы IoT

Интернет вещей в основном использует стандартные протоколы и сетевые технологии. Основными технологиями и протоколами IoT являются RFID, NFC, low-energy Bluetooth, low-energy wireless, low-energy radio protocols, LTE-A, WiFi-

Direct, CoAP, MQTT, AMQP и DDS. Эти технологии и протоколы поддерживают определенные сетевые функции, необходимые в системе IoT, в отличие от стандартной единой сети общих систем.

NFC и RFID

RFID (Radio Frequency IDentification) и NFC (Near field communication) обеспечивают простые, энергосберегающие и универсальные варианты идентификации и токенов доступа, начальной загрузки соединения и платежей. В технологии RFID используются двусторонние радиопередатчики-приемники для идентификации и отслеживания меток, связанных с объектами. NFC состоит из протоколов связи для электронных устройств, обычно мобильного устройства и стандартного устройства.

Low-Energy Bluetooth

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

Low-Energy Wireless

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

Radio Protocols

ZigBee, Z-Wave и Thread - это радио протоколы для создания низкоскоростных частных сетей. Эти технологии маломощны, но обеспечивают высокую пропускную способность в отличие от многих аналогичных вариантов. Это увеличивает мощность небольших локальных сетей устройств без обычных затрат.

LTE-А

LTE-A, или LTE Advanced, обеспечивает важное обновление технологии LTE (Long Term Evolution), не только увеличивая покрытие, но также уменьшая задержку и повышая пропускную способность. Он придает IoT огромную мощь за

счет расширения его диапазона, причем его наиболее важными приложениями являются транспортные средства, UAV (Unmanned Aerial Vehicles) и аналогичные средства связи.

WiFi-Direct

WiFi-Direct устраняет необходимость в точке доступа. Он позволяет подключаться к P2P (peer-to-peer) со скоростью Wi-Fi, но с меньшей задержкой. WiFi-Direct устраняет элемент сети, который часто ее тормозит, и не снижает скорость или пропускную способность.

Constrained Application Protocol (CoAP)

CoAP - это служебный интернет-протокол для ограниченных устройств. Он предназначен для того, чтобы простые ограниченные устройства могли подключаться к IoT через ограниченные сети с низкой пропускной способностью. Этот протокол в основном используется для межмашинного взаимодействия (M2M) и специально разработан для систем IoT, основанных на протоколах HTTP.

Message Queue Telemetry Transport Protocol (MQTT)

MQTT - это протокол обмена сообщениями, разработанный с помощью Andy Stanford-Clark из IBM и Arlen Nipper из Arcom в 1999 году и предназначенный для связи M2M (Machine-to-Machine). Обычно он используется для удаленного отслеживания в IoT. Его основной задачей является собрать статистику со многих гаджетов и доставить свою инфраструктуру.

Advanced Message Queuing Protocol (AMQP)

AMQP - это протокол программного уровня для среды промежуточного программного обеспечения, ориентированной на сообщения. Он поддерживает надежный устный обмен с помощью примитивов гарантии передачи сообщений.

Data Distribution Service (DDS)

Он обеспечивает масштабируемое, надежное и надежное изменение общей производительности в режиме реального времени и совместимую статистику с помощью метода отправки-подписки. DDS использует многоадресную рассылку для передачи высококачественного QoS приложениям. DDS развертывается на платформах, начиная от устройств с небольшой площадью и заканчивая облаком,

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

Введение диссертации (часть автореферата) на тему «Математическое и компьютерное моделирование процессов планирования и распределения разнородных ресурсов в промышленных сетях»

Проблемы

Хотя IoT обеспечивает впечатляющий набор преимуществ, он также сопряжен со значительным набором проблем. Вот список некоторых его основных проблем:

- Безопасность- IoT создает экосистему постоянно подключенных устройств, обменивающихся данными по сетям. Система предлагает мало контроля, несмотря на любые меры безопасности. Это оставляет пользователей уязвимыми для различных видов злоумышленников.

- Конфиденциальность - сложность IoT предоставляет существенные личные данные в мельчайших деталях без активного участия пользователя.

- Сложность. Некоторые считают системы IoT сложными с точки зрения проектирования, развертывания и обслуживания, учитывая использование в них нескольких технологий и большого набора новых вспомогательных технологий.

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

- Соответствие - IoT должен соответствовать правилам. Из-за его сложности вопрос соответствия кажется невероятно сложным, когда многие считают соответствие стандартного программного обеспечения сражением.

Управление ресурсами в IoT

С момента первого подключения устройства к сети IoT сейчас подключено более 50 млрд устройств [87]. Рост количества IoT-устройств по источникам от Cisco показан на рис. 1.5.

1988 1992 1996 2000 2004 2008 2012 2016 2020

$оик»: Око

Рисунок 1.5 - Рост количества ^^устройств

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

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

эффективного управления ресурсами. Некоторые протоколы управления устройствами включают IPv6 в маломощных беспроводных персональных сетях (6L0WPAN) [83], транспортный протокол телеметрии очереди сообщений (MQTT) [78], протокол ограниченных приложений (CoAP) [71]. Другие действия по управлению включают стандартизацию сред RESTful с ограничениями IETF [98], сопоставление протоколов с CoAP, которое оценивает возможность подключения на разных платформах [69] и т. д. Исследователи предложили несколько решений, но эти независимые решения усложняют работу устройств с ограниченными ресурсами.

Агрегирование данных широко применяется и признано эффективным методом управления ресурсами в распространенных приложениях. В этой области проводится несколько сравнительных исследований, таких как агрегация данных в отношении оптимизации энергопотребления, задержки, срока службы сети и точности данных [95], механизмов агрегации данных, касающихся точности данных, срока службы сети и задержки [100], стратегии агрегирования данных в отношении задержки, избыточности, устранения данных и надежности [94]. Однако работа, о которой сообщалось до сих пор, не имеет систематического изучения. В дополнение к этому были также проведены исследования протоколов агрегации иерархических данных, таких как Power-Efficient Gathering in Sensor Information Systems (PEGASIS), Low-Energy Adaptive Clustering Hierarchy (LEACH), Hybrid Energy-Efficient Distributed clustering (HEED), Minimum Energy Communication Network (MECN), Stable Election Protocol (SEP), Cross-layer protocol и т.д., которые пытаются оптимизировать энергоэффективность за счет использования оптимального выбора головки кластера, формирования цепочек узлов, балансировки нагрузки на кластеры и т.д. Основным преимуществом этих протоколов является увеличение срока службы сети, а недостатком является то, что для формирования кластеров требуется дополнительное время [97].

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

между географически расположенными объектами, низкая вычислительная мощность, ограниченное хранилище и т.д. Простые коммуникационные модели, основанные на распространении потока данных, не могут использоваться для всепроникающего и динамичного поведения приложений. Кроме того, уникальные проблемы, возникающие из-за ограниченности ресурсов устройств 1оТ, препятствуют прямому внедрению традиционных механизмов маршрутизации в средах 1оТ.

Алгоритмы маршрутизации признаны эффективными методами управления ресурсами, особенно в управлении энергопотреблением 1оТ. Чтобы оптимизировать использование энергии и сбалансировать нагрузку на сеть, в среде 1оТ следует разработать эффективные алгоритмы маршрутизации. Как и в схеме маршрутизации на основе иерархического кластера, где передача пакетов от источника к головке кластера осуществляется в основном с использованием нескольких переходов, энергосбережение на сенсорном узле не очень эффективно [99]. Подход адаптивной маршрутизации - это одно из решений, которое выборочно запускает маршруты связи между разнородными узлами 1оТ для оптимизации использования ограниченных доступных ресурсов [67].

В связи с быстрым ростом количества устройств повышаются требования к управлению и контролю сети и увеличивается количество информации, передаваемой в сети. Информация также является одним из видов общественных/экономических ресурсов - факторов производства. Кроме того, чем больше устройств создается и подключается к системе 1оТ, тем больше используется не-возобновляемых природных ресурсов, необходимых для их производства, таких как литий и редкоземельные элементы. Следовательно, требуется найти соответствующие решения для обеспечения развития Индустрии 4.0, но при этом сохранить природные ресурсы земли. В настоящее время поставлены цели устойчивого развития с природой [70, 84]. Баланс между потребностями человека и сохранением ресурсов называется устойчивым развитием. Для обеспечения устойчивости должны следовать следующим принципам: сократить потребление, максимально использовать повторно и перерабатывать отходы по возможности. Поэтому необходимо планировать и распределять ресурсы при их использовании.

1.2 Известные подходы планирования и распределения ресурсов в

промышленных сетях

В процессе проектирования и эксплуатации проекта планирование и распределение ресурсов являются двумя из задач управления ресурсами [4, 40]. Количество подготовленных ресурсов обычно устанавливается в определенном диапазоне. Время также является формой ресурса, и задача планирования часто формулируются таким образом, чтобы проект был выполнен в течение заданного времени. Задача планирования является NP-трудной, и для ее решения используются четыре группы методов: аналитические методы, алгоритмы моделирования, общие эвристические алгоритмы и алгоритмы интеллектуального поиска [92]. Некоторые примеры задач планирования и распределения ресурсов включают: составление расписаний в университетах [65], задачи распределения экипажей авиакомпаний [106] или использование общих компонентов в вычислительных устройствах [82]. В приведенных выше примерах можно выходить некоторые общие черты: часто происходит одновременное распределение времени и одного или нескольких других видов ресурсов (лекторов, аудиторий, бригад, процессоров); количество ресурсов конечно; они являются общими и многоразовыми. Распределение других ресурсов обычно осуществляется с учетом фактора времени. При наличии дополнительных требований по времени выполнения или изменения количества используемых ресурсов расчет усложняется, поскольку решение должно удовлетворять заданным ограничениям.

При описании проектов как сети операций для их анализа можно использовать методы сетевого планирования [13, 26, 43]. Существует большое количество методов сетевого планирования, наиболее распространенными из которых являются следующие:

1. Метод критического пути [15, 76].

Метод критического пути (англ. Critical Path Method, сокращенно CPM) тип техники сетевого анализа прогресса, важный инструмент для эффективного управления проектами. Метод критического пути использует сеть ориентированного графа в теории графов для организации рабочих действий и задач в проекте в

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

Ниже приведены преимущества методов критического пути:

- CPM определяет действия, которые могут выполняться параллельно друг другу.

- CPM показывает действия и их результаты в виде сетевой диаграммы.

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

- CPM помогает в определении резервного времени.

- CPM широко используется в промышленности.

2. Метод оценки и анализа проектов (PERT) [3, 27]

Метод оценки и анализа проектов (англ. Program (Project) Evaluation and Review Technique, сокращенно PERT) используется для определения времени, необходимого для завершения конкретной задачи или действия. Этот метод помогает правильно планировать и координировать все задачи в рамках проекта. Это также помогает отслеживать прогресс или его отсутствие в целом по проекту. В 1950-х годах ВМС США разработали PERT для управления программой.

Преимущества:

- PERT явно определяет и делает видимыми зависимости (отношения приоритета) между элементами структуры разбиения работ.

- PERT облегчает идентификацию критического пути и делает его видимым.

- PERT облегчает идентификацию раннего начала, позднего начала и резерва для каждого действия.

- PERT обеспечивает потенциальное сокращение продолжительности проекта благодаря лучшему пониманию зависимостей, что приводит к улучшенному дублированию действий и задач.

- Большой объем проектных данных может быть организован и представлен в виде диаграммы для использования при принятии решений.

- PERT может обеспечить вероятность завершения до заданного времени.

3. Метод графической оценки и анализа (GERT) [18, 52, 91]

Метод графической оценки и анализа (англ. Graphical Evaluation and Review Technique, сокращенно GERT) является одним из сетевых графиков. Метод был создан Аланом Б. Прицкером в 1966 году. Метод GERT используется в управлении проектами и позволяет проводить вероятностную обработку как сетевой логики, так и оценки продолжительности действий в сложных системах со стохастической характеристикой. Подход GERT устраняет большинство ограничений, связанных с методом PERT/CPM. Основные из них:

- альтернативных путей нет. Все действия должны быть выполнены.

- нет циклов. Невозможно повторить действие, необходимо добавить следующее аналогичное действие

- на диаграмме нет выборов правильной пути.

- масштабирования нет. Невозможно заменить какую-то детальную группу действий одной сводной задачей.

Подробное сравнение методов представлено в работе [103].

1.3 Обзор исследований по GERT-сетям

Для исследования стохастического поведения технических и социальных систем широко применяются GERT-сети. Они включает в себя ряд особенностей, которые отсутствуют в системах PERT и CPM, а именно - наличие вероятностных ветвлений, допущение возвратов к ранее выполненным операциям и использование циклов. Эти особенности GERT-сети предоставляют пользователям возможность более глубоко моделировать и анализировать проекты и системы.

GERT-сети использовались для решения много задач в различных областях, таких как: оценка показателей бизнес-процессов [14], сокращение затрат и времени при формировании распределенных процессов с учетом стохастической реали-

зации процесса [11], оценка надежности программного обеспечения [28], управление уголовным судопроизводством [68], управление инновационным риском на основе имитационного моделирования [8], распределение потребляемых ресурсов в альтернативных стохастических сетях посредством многокритериального принятия решений [77], анализ надежности системы основных шасси самолета [93], определение среднего времени выполнения медиапроекта и оценка продолжительности проектов одного типа [74], анализ и оценка задержек поездов на железнодорожной сети Болгарии [101], численное моделирование бизнес-процессов [84].

Для расширения работоспособности традиционной модели GERT-сети разработаны много модификаций. В работе [81] представлена модифицированная GERT-сеть, демонстрирующая знания о зависимостях между переходными событиями. Модификации GERT-сети включают расширение реализации узлов до двухэтапного процесса. На первом этапе ожидания относительно типа ситуации размещаются на временной шкале. На втором этапе происходит реальная ситуация. В [61] предложена модель Grey GERT-сети для решения проблемы точных значений параметров, поскольку практическая информация ограничена. модель Grey GERT-сети также применяется для оценки надежности системы оборудования [105]. Рассматриваются дополнительные параметры в узлах сети в работе [79]. Это позволяет использовать модифицированную GERT-сеть не только для оценки времени работы сети, но и для оценки работоспособности сети в заданных рамках и при отклонениях от проектных параметров. Новый метод моделирования сети F-GERT, учитывающий нечеткую информацию, предложен в [108].

Исследования последних лет были посвящены решению теоретических проблем. Метод эквивалентных упрощающих преобразований GERT-сетей излагается в статье [58]. В работе [64] рассматриваются вопросы получения плотности распределения выходной величины GERT-сети через формулу обращения с обеспечением точности интегрирования. В статье [62] излагаются вопросы получения плотности распределения для экспоненциальных и равномерно распределенных случайных величин с применением теории аналитических функций комплексного

переменного. Работа [63] посвящена нахождению распределения вероятностей выходной величины GERT-сети, в которой все дуги описываются дискретными распределениями.

Приложения GERT-сети в телекоммуникационной области можно отметить как: повышение надежности телекоммуникационных систем за счет расстановки контрольных точек в программах микроконтроллеров со сторожевыми таймерами [20], оптимизация локальных параметров в компьютерных сетях [55], обеспечение показателей качества компьютерной сети при передаче трафика реального времени [60], нахождение распределения выходной величины GERT-сети со старением информации [21], Определение стохастических характеристик первичной обработки телеметрируемых параметров с отрицательными случайными величинами [59], методы и технологии автоматизации проектирования компьютерных сетей

[19].

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

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

1.4 Зависимые и независимые случайные величины в СЕЯТ-сетях

Независимость является фундаментальным понятием в теории вероятностей, а также в статистике и теории случайных процессов. Два события называются независимыми, если появление одного не влияет на вероятность появления другого. Точно так же две случайные величины независимы, если реализация одной не влияет на распределение вероятностей другой. Зависимые и независимые случайные величины рассматриваются в работе [6].

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

В классической теории ОБЯТ-сетей используются независимые случайные величины.

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

Понятие «зависимости» случайных величин, которым мы пользуемся в теории вероятностей, несколько отличается от обычного понятия «зависимости» величин, которым мы оперируем в математике. Действительно, обычно под «зависимостью» величин подразумевают только один тип зависимости - полную, жесткую, так называемую функциональную зависимость. Две величины X и У называются функционально зависимыми, если, зная значение одной из них, можно точно указать значение другой.

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

Вероятностная зависимость между случайными величинами очень часто встречается на практике. Если случайные величины X и У находятся в вероятностной зависимости, это не означает, что с изменением величины X величина У изменяется вполне определенным образом; это лишь означает, что с изменением величины X величина У имеет тенденцию также изменяться (например, возрастать или убывать при возрастании X). Эта тенденция соблюдается лишь «в среднем», в общих чертах, и в каждом отдельном случае от нее возможны отступления.

В математике функциональной зависимостью переменной У от переменной Х называют зависимость вида у = /(х), где каждому допустимому значению X ставится в соответствие по определенному правилу единственно возможное значение У.

В данной диссертации рассматриваются функциональные зависимости между случайными величинами.

1.5 Расчет количества ресурсов в промышленных сетях

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

В промышленной сети одновременно выполняется множество процессов. Информационное единство поддерживается централизованным банком данных. Время пересылки информации между абонентскими системами считаем пренебрежимо малым по сравнению с временем выполнения отдельных операций. Процесс состоит из некоторого множества операций и описывается стохастической моделью. Узлы сети соответствуют состояниям процесса, а каждая его операция характеризуется условной вероятностью выполнения, математическим ожиданием времени выполнения и его дисперсией. Закон распределения времени выполнения работы примем известным. Операция может быть выполнена любой из N единиц ресурса определенного вида. Каждому виду ресурса соответствует некоторое подмножество операций, реализующихся в различных процессах. Необходимо определить количество единиц ресурса каждого типа таким образом, чтобы вероятность задержки любой из работ из-за нехватки данного ресурса была не выше заданной.

1.6 Основные результаты

Проведен анализ текущего состояния исследований в области расчета ресурсов в стохастических сетях и, в частности, в GERT-сетях.

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

Рассмотрены следующие направления исследований: перспективы использования GERT-сетей, классификация и использование ресурсов в различных областях, возможность выполнения пары операций одной единицей ресурса, применение функционально зависимых случайных величин.

На основе проведенных в главе 1 исследований выделены основные задачи диссертационной работы:

1. Обоснование использования и применения математического аппарата GERT-сетей для исследования процессов планирования и распределения разнородных в промышленных сетях;

2. Нахождение вероятности назначения пары операций для выделения ресурсов в промышленных сетях;

3. Разработка численного метода и алгоритмов определения плотности распределения времени между операциями в промышленных сетях;

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

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

6. Разработка математических моделей определения вероятностно-ресурсных характеристик с учетом важности выделяемых ресурсов в промышленных сетях;

7. Разработка методики планирования и распределения разнородных ресурсов в устройствах обработки информации с упорядоченным набором операций;

8. Разработка методики планирования разнородных ресурсов в экспоненциальной GERT-сети;

9. Разработка методики нахождения ресурсов в модели резервного канала;

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

11. Разработка методики использования ресурсов для изменения времени выполнения операций;

12. Разработка методики распределения ресурсов в раскрашенных GERT-

сетях;

13. Разработка комплекса программ компьютерного моделирования процессов планирования и распределения разнородных ресурсов в промышленных сетях;

14. Практическая проверка основных положений и выводов диссертации.

ГЛАВА 2 МАТЕМАТИЧЕСКИЕ МОДЕЛИ, МЕТОДЫ И АЛГОРИТМЫ ПЛАНИРОВАНИЯ И РАСПРЕДЕЛЕНИЯ РАЗНОРОДНЫХ РЕСУРСОВ В

ПРОМЫШЛЕННЫХ СЕТЯХ

2.1 Математические модели нахождения вероятности назначения пары операций для выделения ресурсов в промышленных сетях

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

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

Каждый из процессов а е А = {аг}, г = 1, т, состоящий из множества операций Бг = {Ъг] |, ] = 1, к , опишем циклическим графом, для которого определим одну

Список литературы диссертационного исследования кандидат наук Фам Ань Минь, 2022 год

ИСТОЧНИК сток/"

Рисунок 2.13 - ОБЯТ-сеть времени окончания операции

Шаг 13. Определить плотность распределения времени окончания выбранной дуги из модели шага 12.

Шаг 14. Конец алгоритма.

Для выполнения шагов 3, 4, 7 и 9 разработан алгоритм для построения ОБЯТ-сети путей, входящих в начальный узел или выходящих из начального узла [2, 10, 54]

Алгоритм 2. Построение ОЕЯТ-сетъ путей, входящих в начальный узел или выходящих из начального узла

Шаг 1. Создать набор узлов У0, VI, У2 и набор дуг Е0, Е1, Е2.

Шаг 2. Добавить начальный узел к набору V2.

Шаг 3. Добавить исходные узлы к набору V0.

Шаг 4. Очистить набор VI и добавить узлы набора V2, которых нет в наборе V0, к VI.

Шаг 5. Если набор VI не пуст, то переходить на шаг 6, в противном случае на шаг 16.

Шаг 6. Очистить набор V2.

Шаг 7. Добавить узлы набора VI к набору V0.

Шаг 8.1. Если задача построения сети путей, входящих в начальный узел, то определить входные дуги для каждой узла в наборе VI и сохранить в набор Е2.

Шаг 8.2. Если задача построения сети путей, выходящих из начального узла, то определить выходные дуги для каждой узла в наборе VI и сохранить в набор Е2.

Шаг 9. Если набор Е2 не пуст, то переходить на шаг 10, в противном случае на шаг 16.

Шаг 10. Очистить набор Е1 и добавить дуги набора Е2, которых нет в наборе E0, к Е1.

Шаг 11. Если набор Е1 не пуст, то переходить на шаг 12, в противном случае на шаг 16.

Шаг 12. Очистить набор Е2.

Шаг 13. Добавить дуги набора Е1 к набору Е0.

Шаг 14.1. Если задача построения сети путей, входящих в начальный узел, то определить начальные узлы для каждой дуги в наборе Е1 и сохранить в набор

V2.

Шаг 14.2. Если задача построения сети путей, выходящих из начального узла, то определить конечные узлы для каждой дуги в наборе Е1 и сохранить в набор V2.

Шаг 15. Если набор V2 не пуст, то повторить шаг 4, в противном случае переходить на шаг 16.

Шаг 16. Построение GERT-сети из набора узлов V0 и дуг Е0.

Шаг 17. Алгоритм заканчивается.

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

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

ли ОБЯТ-сети с упорядоченными наборами дуг, представляющих операции системы.

Системы с параллельными процессами должны определять порядок предоставления ресурсов для выполнения операций. Когда пара операций совместно использует единицу ресурсов - это уменьшает количество необходимых ресурсов. Эти ресурсы являются общими, повторно используемыми, такими как процессора, память или каналы в вычислительных устройствах. Две операции, принадлежащие двум разным процессам, могут обслуживаться единицей ресурсов только в том случае, если одна из них начинается после завершения другой. Для двух операций, принадлежащих одному и тому же процессу, они выполняются единицей ресурсов, если одна операция возникает в то время, когда произошла другая. Чем больше операций выполняет одна и та же единица ресурсов, тем меньше ресурсов требуется. Поэтому необходимо определить упорядоченные наборы операций. Все операции в одном наборе выполняются одной и той же ресурсной единицей. Поскольку система анализируется с помощью ОБЯТ-сети и выбор последующих операций имеет определенную вероятность, упорядоченный набор операций также является вероятностным и должен быть определен. Основные этапы выполняются следующим образом.

1. Построение модели ОБЯТ-сети времени начала и окончания операций.

Алгоритм 1 и 2 используются для построения моделей. Полученные результаты представляют собой две модели ОБЯТ-сети времени начала и окончания рассматриваемых операций.

2. Определение численных характеристик времени начала и окончания операций.

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

Формулы для расчета математического ожидания тЕ и среднеквадратичного отклонения аЕ эквивалентных дуг с использованием теории вероятностей и базовых преобразований [6.18] приведены ниже.

Эквивалентная дула последовательных дуг представляет собой сумму п независимых случайных величин:

п

т

= Ё т ,

(2.35)

Е

'¿=1

п

А=Ё а,

¿=1

При п = 2, то

т = т + т,

(2.36)

2 2 2 аЕ = а1 +а2,

где параметры т являются вероятностью, математическим ожиданием и сред-неквадратическим отклонением первой дуги соответственно. А т2 ,а2 - параметры второй дуги.

Параллельные дуги рассматриваются как смесь случайных величин. Численные характеристики определяются формулами:

п

тЕ = ЁРгтг: ¿=1

пп

Л2 (2.37)

а2Е = £) - тЕ = £Р А) - ЁРг'

=1 =1

т

1 1

V ¿=1 У

(г)

где р1 ,а\' являются вероятностью и вторым начальным моментом г-го величины соответственно.

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

тЕ = Р1т1 + Р2m2,

2 (2.38)

АЕ = РА2 + Р2^22 + Р1т12 + Р2т22 - (Р1т1 + Р2т2 ) ,

где р1 и р2 являются вероятностей первой и второй дуги соответственно.

Тип «дуга-петля» может быть разложена на бесконечно параллельную форму последовательных дуг. Математическое ожидание и среднеквадратичное отклонение типа «дуги-петли» определяются следующим образом:

тЕ = рт + Р1Р2

°Е = Л0"! + Р1Р2

т1 + т2 , т2 Р2 . 1 - Р2 (1 - Р2 )2

(Л + Л )

+

Р2

1 - Р2 (1 - Р2)2

+ Р т2 +

+Р1Р2

( т1 + т2 2т2 ( т1 + т2 ) Р2 т22 (1 + Р2 ) Р2

1 - Р2

(1 - Р2 )2

(1 - Р2 )3

Р1т1 + Р1Р2

т +т

+

т2Р2

1 - Р2 (1 - Р2)2

(2.39)

где р , т ,а1 - параметры прямой дуги, а р2 , т2 ,л2 - параметры петли.

Когда рх + р2 ^ 1, то необходимо делить математическое ожидание и сред-неквадратическое отклонения на вероятность р£ эквивалентных дуг, изображенных в формулах (2.36, 2.38, 2.39).

3. Определение вероятности пары операций, выполненных единицей ресурсов.

Используются формула (2.2) для пары, принадлежащей разным процессам, а формула (2.22) для пары, принадлежащей одному и тому же процессу. Операция вычитания двух случайных величин выполняется путем суммирования положительной одной величины и случайной величины, взятой со знаком «минус». Для реализации механизма вычитания воспользуемся свойствами характеристических функций. Характеристическая функция ха+ъс(С) случайной величины а + ЬС связана с характеристической функцией случайной величины С равенством:

1а+ы(С) = ^\_ ехр{С( а + ЬС)}] =

ехр{Са}Е[ ехр{ (СЬ )С}] = ехр{Са} ),

(2.40)

2

где a и Ь - произвольные числа. Если а = 0 и Ъ = -1 , то:

(2.41)

В модели ОБЯТ-сети для реализации механизма вычитания операций сеть времени начала первой операции соединяется с сетей времени окончания второй операции. Знак математического ожидания всех дуг меняется на противоположный. Вероятность р пары операций разных процессов, выполненных одной

единицей ресурса, можно вычислять по плотности распределения выходной величины сети /Г5 (г):

да 0

Рг.к = 1 /г, (г)dг = 1 - | /„ (г)dг = 1 - ^ (г < 0), (2.42)

0 -да

где (г) - функция распределения выходной величины сети вычитания двух операций.

С помощью численного метода интерполяции многочленами Лагранжа второй степени определены плотности распределения /Г5 (г).

Далее по формуле (2.22) необходимо определить вероятность завершения операции Ъг до начала операции Ъ. Эквивалентная сеть для расчета вероятности пары операций (ЪГ, Ъ8), выполняемых единицей ресурса в одном и том же процессе, показана на рисунке 2.14. Дуга WE является эквивалентной дугой, представляющей операции между Ъ и Ъ . Вероятность рассчитывается, когда производящая функция моментов дуг равна единице.

Рисунок 2.14 - Сеть для расчета вероятности пары операции

в одном процессе

4. Определение всех упорядоченных наборов и вероятности каждого для распределения ресурсов.

Необходимо построить двудольный граф. Узлами графа являются операции с вероятностью Prs большей, чем заданная вероятность Prs . Операции слева

имеют время окончания меньше, чем время начала операций справа. Дуги между узлами показывают возможности последовательности операций. Далее, определить все максимальные соответствия графа. Из максимального соответствия устанавливается упорядоченный набор. Количество наборов каждого максимального соответствия - это количество ресурсов, необходимых для выполнения всех рассматриваемых операций. Вероятность каждого набора вычисляется по формулам (2.21) и (2.24).

5. Расчет объема выделяемых ресурсов.

Объем ресурсов всей системы определяется суммой ресурсов, выделяемых на операции. Для операций, выполненных одной единицей ресурсов, объем требуемых ресурсов равен объему ресурсов для самой ресурсоемкой операции в наборе.

Случайная величина количества выделяемых ресурсов /-го набора R равна:

R = max {¥1,...,¥я}, (2.43)

где Y,...,Y - случайные величины ресурса, необходимых для выполнения операций в /-ом наборе.

Функция Hi и плотность h распределения вероятностей ресурсов /-го набора определяются следующим образом:

я

H, = п G (y) > (244)

j=i

h = П G (y), (2.45)

l=1 Gl(y) j=l, j Ф1

где G (y), g (y) являются функцией и плотностей вероятностей ресурсов, необходимых для выполнения операций в /-ом наборе.

Поскольку ресурсы можно использовать повторно, они учитываются только один раз. В модели GERT-сети, на основе базовых преобразований эквивалентная

дуга максимальной случайной величин E max = max {A, B}, где A, B - случайные величин компонентов, показана на рисунках 2.15 и 2.16. Параметры p,q являются вероятностей выполнения дуг. Две параллельные дуги не учитывают максимальный случай, поскольку в один момент выбирается только одна дуга.

Рисунок 2.15 - Эквивалентная дуга максимальной случайной величины

Рисунок 2.16 - Эквивалентная дуга максимальной случайной величины

типа «дуги-петли»

Из основных этапов математического моделирования предложен алгоритм для планирования и распределения разнородных ресурсов с упорядоченных наборов операций в модели ОБЯТ-сети.

Алгоритм 3. Планирование и распределение разнородных ресурсов с упорядоченными наборами операций:

Шаг 1. Определение операций одного и того же типа ресурса. Шаг 2. Построение модели ОБЯТ-сети времени начала и окончания рассмотренных операций.

Шаг 3. Вычисление численных характеристик выходной величины времени начала и окончания операций

Шаг 4. Нахождение вероятностей р каждой пары операций, выполненных

одной и той же единицей ресурсов.

Шаг 5. Выбор пар операций, имеющихся вероятность р больше заданной вероятности .

Шаг 6. Построение двудольного графа из операций в шаг 5.

Шаг 7. Определение всех максимальных соответствий двудольного графа.

Шаг 8. Установка упорядоченных наборов операций из максимальных соответствий.

Шаг 9. Расчет количества единицей ресурсов, необходимых для выполнения упорядоченных наборов операций.

Шаг 10. Определение вероятности выполнения каждого наборов.

Шаг 11. Построение модели ОБЯТ-сети ресурсов.

Шаг 12. Преобразование сети ресурсов в параллельные пути, содержащие операции в одном наборе.

Шаг 13. Замещение операции того же набора эквивалентной дугой максимальной случайной величин.

Шаг 14. Расчет объем выделяемых ресурсов по каждому варианту максимального соответствия.

Шаг 15. Повторение шаги со 2 до 14 для следующего типа ресурса. Если других типов ресурсов нет, алгоритм заканчивается.

2.4 Численно-аналитический метод и алгоритм планирования и распределения разнородных ресурсов с функционально зависимыми случайными операциями в промышленных сетях

В данном разделе рассматривается задача модернизации классической ОБЯТ-сети. Для каждой операции классической ОБЯТ-сети ставится в соответствие вероятность ее выполнения и аддитивный параметр - чаще всего условное распределение вероятности времени выполнения. Кроме этих параметров введем условное распределение вероятности ресурса, требующегося для выполнения данной операции. Фактически мы вводим еще одну координату измерения. Получаем ОБЯТ-сеть с параметрами вероятности, времени и ресурсов. Инструментом

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

Пусть имеется непрерывная случайная величина времени выполнения Т с плотностью / (t); случайная величина ресурса У выражается через случайную величину Т функциональной зависимостью

Требуется найти закон распределения случайной величины У [5].

Пусть функция ф(Т) строго монотонна, непрерывна и дифференцируема в

интервале (а, Ь) возможных значений случайной величины Т. Функция распределения ресурса О(у) случайной величины У определяется по формуле:

Тогда плотность распределения вероятностей искомой случайной величины

где (р(у) = t есть функция обратная функции ф(Т) = У;

Структура исходной ОБЯТ-сети приводится к единственной эквивалентной дуге методом эквивалентных упрощающих преобразований [18]. На каждой шаге из структуры исключается один узел. Фрагмент «последовательные дуги», «параллельные дуги», «дуга-петля» заменяются эквивалентными дугами. Вычисляются их веса в виде характеристических функций.

Плотность распределения вероятности единственной эквивалентной дуги (у) определяется следующим образом:

У = ф(т).

(2.46)

О (у ) = Р {У < у}.

(2.47)

(2.48)

(2.49)

где %Е(£) - характеристическая функция эквивалентной дуги, £ - действительная переменная.

Для нахождения плотности распределения выходных случайных ОБЯТ-сетей можно использовать численный или аналитический метод.

Численный метод

Для обеспечения условий интегрирования введем нормально распределенную случайную величину с математическим ожиданием /и = 0, дисперсией сг2 = 1 и плотностью ^(у). Найдем плотность распределения §Е(у) = gE(y) + g(y) при условии независимости случайных величин. Тогда плотность вероятности §Е(у)'.

1 +г

йЕ{у) = —\е~^ХЕ(^£, (2.50)

—х

где (£) = %Е(£) ехр (—0,5£2); ехр (—0,5£2) - характеристическая функция величины Я (у); £ - действительная переменная. После нахождения плотности ЙЕ(у) должна быть найдена искомая плотность распределения gE(у). Это достигается использованием тривиального численного метода трансформации законов распределения на основе решения системы линейных уравнений [1].

Аналитический метод

В уравнении (2.49) выполним замену переменных: г = —£. Функцию, получающуюся в результате замены переменных, обозначим через Ф^ (г).

Если функция ф( г) в полуплоскости Яег < 0 удовлетворяет условиям леммы Жордана, то интеграл, взятый вдоль контура Бромвича, равен сумме вычетов функции ф( г) относительно всех ее особенностей [23, 24, 41, 42]:

+ № п

Я(у) = ^- I егУФ*(г)^ = Ё?е?[егУФе(г)]. (2.51)

—к=1

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

нечного числа полюсов, и равномерно относительно arg z стремилась к нулю при | z | ^ да .

Вычет от полюса высокого порядка находится по формуле нахождения вычетов c_j от полюсов z^ порядка n (n > 2)

Г( z - zt )VyO E ( z )"

1 dn-1

lim-

-1 (n -1)! z^ dzn-1

Вычет от простых полюсов найдем по формуле

(2.52)

n

g (y )=Z Res

k=1

^ zk)

= X . (2.53)

t! v (zk)

.К ^),

Применение функциональной зависимости к модели ОБЯТ-сети обычно состоит из двух подходов: параллельного (этап планирования) и последовательного (этап распределения).

Параллельный подход

В параллельном подходе в модели ОБЯТ-сети добавляется величина ресурсов. Соответственно, случайная величина ресурса У выражается через случайную величину времени Т функциональной зависимостью: У = ф(Т). Структура сети

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

Последовательный подход

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

оставшиеся параметры и провести анализ сетевой модели. По результатам исследования сделать оценку распределения ресурсов в сети.

Еще один подход заключается в применении как параллельного и последовательного на одной и той же модели. Но в связи с его сложным характером здесь упоминаться не будет. На рисунке 2.17 показаны последовательный и параллельный подход.

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

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

1. Построение модели ОБЯТ-сети ресурсов. Из исходной модели времени создается новая модель ресурсов с одинаковой структурой для задачи планирования ресурсов от функциональных зависимости времени.

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

у = ф (/),I = 1..п, где п - количество зависимой дуги в модели ОБЯТ-сети.

3. Нахождение функции у) = /, которая является обратной функцией функции у = ф (/).

4. Вычисление производной функции ^'(у).

5. Определение плотности распределения вероятности /-ой зависимой дуги gi (у) по формуле:

а (/) = ОС&Ц = ^ (у)]|й.(у)|, (2.54)

где ^ (у) - функция распределения случайной величины У.

6. Замещение плотности распределения вероятности gi (у) на зависимых

дугах.

7. Преобразование сети по методу эквивалентных упрощающих преобразований или по формуле Мейсона в эквивалентную сеть, состоящую из одной дуги, характеризующейся эквивалентной Ж-функцией ЖЕ (5 ) = рЕМЕ (я), где р£ - вероятность прохождения стока, М^ (я) - эквивалентная производящая функция моментов [52].

7. Определение плотности распределения (у) выходной случайной величины аналитическим или численным методом.

8. Определение плотности распределения определенного типа ресурса при замещении производящих функций моментов остальных типов единицей в эквивалентной Ж-функцией ЖЕ (я).

На рисунке 2.18 приведена блок-схема алгоритма планирования и распределения разнородных ресурсов с применением функциональных зависимостей.

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

Конец

Рисунок 2.18 - Блок-схема алгоритма планирования и распределения разнородных ресурсов с применением функциональных зависимостей При построении модели ОБЯТ-сети и сохранения исходных параметров дуг необходимо выбрать режим расчета. В режиме планирования система фокусируется на отображении связи между временем выполнения операции и ресурсами, необходимыми для выполнения операции. А в режиме распределения система представляет взаимосвязь между основными и зависимыми ресурсами. Некоторые

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

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

При выполнении метода эквивалентных упрощающих преобразований необходимо после каждого преобразования сохранять схему модели, которая понадобиться при отображении результатов. Результатом процесса является сеть с единственной эквивалентной дугой, преобразованная из исходной сети. Данные последней дуги сформированы как механизм двоичного дерева. То есть две дуги в сети путем типовых преобразований ОБЯТ-сети создадут новую эквивалентную дугу. Процесс преобразования повторяется до тех пор, пока в сети не останется только одна дуга. Пример модели ОБЯТ-сети показан на рисунке 2.19.

Исток Б Сток t

Рисунок 2.19 - Пример модели ОБЯТ-сети После выполнения преобразования получается схема двоичного дерева эквивалентных дуг, представленная на рисунке 2.20. В котором узлы ТБ1 дерева являются эквивалентными дугами из двух дуг предыдущего шага метода упрощающих преобразований. Этот метод включает следующие типовые преобразования дуг: параллельные, последовательные и петли. - исходные дуги.

ТЕ 4

(Последовательная)

(Последовательная)

ТЕ1

ТЕЗ (Петля)

ТЕ О

(Последовательная)

ГЕ 2

\У4

\Л0

ЕЕ О

\У1

\Л2

(Последовательная)

\\1

Рисунок 2.20 - Схема двоичного дерева эквивалентных дуг - результат метода упрощающих преобразований Последняя эквивалентная Ж- функция дуги ТЕ4 указанной выше сети имеет

вид:

После определения эквивалентной функции WE (я), переходим к вычислению значения плотности распределений всех ресурсов. Для этого применяется численный метод с использованием формулы обращения и интерполяции характеристической функции многочленом Лагранжа второй степени [51].

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

WE ( я ) = ТЕ4 ( я )

W0 ( я ) W1( я ) W2 ( я ) W4 ( я ) 1 - W1( я ) W2 ( я ) W3( я )

(2.55)

2.5 Сложные зависимости времени и ресурсов в параллельном подходе

В простейшем случае параллельного подхода одна случайная величина зависит от другой случайной величины. Но при дальнейшем расширении множество разных величин можно одновременно зависеть от одной величиной. На рисунке 2.21 показан набор разнородных ресурсов У, зависящих от времени Т.

Рисунок 2.21 - Параллельные функциональные зависимости Существует другой случай, когда первая величина зависит от второй величины, вторая величина зависит от третьей величины и т.д. На рисунке 2.22 представлены последовательные функциональные зависимости, где первая величина -время, остальные - разнородные ресурсы.

Параллельный Подход

Т.Т- Случайные величины Ф. - Функциональные зависимости

Рисунок 2.22 - Последовательные функциональные зависимости

Параллельные функциональные зависимости

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

операции, ф(Т) - функциональная зависимости случайной величины /-ой ресурса

от случайной величины времени Т.

Например, для выполнения операции запоминания информации требуется оперативная память, кэш-память, память на жёстком диске. При этом для простоты будем считать, что объем памяти в вычислительной системе достаточно большой. Для выполнения операции требуется время, задаваемое экспоненциальной величиной с интенсивностью X, т. е. /(?) = Ле~х. Требуемый ресурс оперативной

памяти определяется линейной зависимостью ^ = Ф(Т) = 2Т; запрос на кэшпамять определятся через зависимость У2 = ф2 (Т) = Т2; требования памяти на винчестере - через зависимость 73 = ф (Т) = 4Т. Тогда соответствующими запросами

—

—

по памяти есть плотности: g1 (у) = —е 2 , g2 (у) =—^ е

2 2] у

— —, gз (у ) = 2—е-—у2

Единицы рассчитываются соответствующим образом для каждого типа памяти.

На рисунке 2.23 показаны плотности распределения соответствующих типов памяти, — = 1.

^ , Плотность распределения

О

\

)

;)

\ /

(У )

Ресурс

0 . 2 3 А Ё 5 6 7 8 9 10

Рисунок 2.23 - Плотности распределения ресурсов в модели параллельных

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

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

Последовательные функциональные зависимости

Рассмотрим операцию передачи информации по сети между оконечными точками. Время ее выполнения характеризуется экспоненциальной величиной / (? ) = Хе~х. Поступившая информация обрабатывается, на это затрачивается некоторый объем памяти. От объема памяти, требующейся программисту, зависит и величина необходимых для этого денежных затрат.

Дальнейшее пояснение идеи методики поясняется на примере. Зависимость между временем выполнения операции и величиной памяти определяется функциональной зависимостью между случайными величинами - временем выполнения операции передачи информации и требующейся для обработки памяти. Пусть эта зависимость линейная ^ = 0,5Т. От величины требующейся памяти зависит и

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

образом, для каждого звена между ресурсами справедливо ), / = 1-п,

где 7г - /-ый ресурс выполнения операции.

Определим значение X = 3. Находя обратную функцию и модуль ее производной, получаем первую функциональную зависимость ^ (у ) = 6е_бУ1. Пусть

Г2 = у!^ - функциональная зависимости между ресурсом и затратой. Обратная

функция (р2 = у\. Модуль ее производной |2у2\. Тогда ^ (у2) = |12у2|е"6У2. Плотности распределения вероятностей времени и ресурсов изображены на рисунке 2.24.

Плотность распределения

м У>)

£2 (V )

V - /

Ресур

О 0,2 0,4 0,6 0,8 1,0 1,2 1,4

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

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

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

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

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

Если определено время t прохождения заявки из узла i в узел j и моменты времени контроля времени жизни заявки ах,..., ак_х, ак, ак+],..., ап, то надо найти вероятности P {t < a} того, что время не превысит значение a; вероятности P{t > a2} того, что время превысит значение a2; вероятности P {a^ < t < ak} того, что время попадут в интервалы (ak_р ak), к = 2, n .

На рисунке 2.25 показана плотность f (t) распределения времени достижения заявками узла j GERT-сети (отмечена цифрой 1) и f (t) - условная плотность распределения времени достижения заявками узла j временной GERT-сети за время a < t < a2 (цифра 2), вычисляемая по формуле:

f (t ) = f(t) =_fi£>__(2 56)

Ja--() p{a <t<a} f(a)-f(a,)' (. )

где F (t) - функция распределения вероятностей времени x.

Вероятность

Э2

Рисунок 2.25 - График зависимости вероятности от времени: 1 - плотность распределения вероятностей / (?) от времени, 2 - условная плотность

распределения вероятностей времени при попадании заявки в интервал (^, я2)

В общем случае, дуги в модели GERT-сети могут принимать любой вид непрерывного распределения и любой тип функциональной зависимости. Сначала рассмотрим только линейную функциональную зависимость У = кТ из-за популярности и простоты нахождения обратной функции и ее производной. Проведенные исследования показали, что линейные преобразования экспоненциального и нормального распределений также дают экспоненциальное и нормальное распределение. Если распределение экспоненциальное, то после функционального преобразования имеем:

g(у) = Яхр{-Яу| . (2.57)

Если распределение нормальное, то:

Этим значениям соответствуют производящие функции моментов

/I

М (^ ) =- и М (^ ) = Gxpikms + 0,5к 2| для экспоненциального и нормаль-

Я-кз

ного распределения соответственно.

Экспоненциальное распределение ресурса

Имеется непрерывная случайная величина времени Т с плотностью Яе, где Я - интенсивность обслуживания. Плотность вероятности и функция распределения случайной величины X имеют следующие виды:

/ (г ) = Яе~Я. (2.59)

Р(г) = 1 - е~Я . (2.60)

Пусть а и а2 - фиксированные временные пороги. Рассмотрим следующие события:

- время меньше порогового времени а (г < а);

- время больше порогового времени а (г > а);

- время больше порогового времени а и меньше порогового времени а2,

где а < а2 (а < *< а2) •

В соответствии с каждым из указанных выше событий условные плотности вероятностей времени вычисляются выражениями [22]:

/<* (*)

Г / (*) _ "е~"*

Б (а) 1 -

* < а1

(2.61)

0,

* > а

о, * < а /.а, (* Н I (*) -"е-"* .1 - Б (а1)"

-"а! '

* > а1

(2.62)

/а1 <*<а2 ( * )

/ (*)

о,1 < а

"е-"*

Б (а)- Б (а) е""а1 - е"

-, а < * < а • (2.63)

1,1 > а2

Случайная величина выделяемого ресурса У выражается через случайную величину Т функциональной зависимостью У = ф(Т) • Необходимо найти закон

распределения условной случайной веичины У. Пусть функция ф(Т) строго

монотонна, непрерывна и дифференцируема в интервале всех значений Т. Функция распределения величины У определяется по формуле:

С(у) = Р{У < у}. (2.64)

Событие {У < у} эквивалентно событию {Т < р(у)}, где р(у) = * - функция

обратная функции ф(*) = у. Плотность распределения ресурса У определяется по

формуле:

8 ( у ) = / [р(у)]|р'(у)|. (2.65)

<

<

Определим линейное преобразование У _ кТ, к > 0, где к - постоянный множитель. Обратная функция р(у) = у; а ее производная р'(у) = 1; модуль ~ 1

производной —.

|к|

Для экспоненциальных случайных величин получаем плотность ресурса:

(266)

Плотность распределения ресурсов также является экспоненциальном

Я

распределением с интенсивностью —.

к

Тогда функция распределения ресурсов сформулируется следующим образом:

С (у ) = 1 - е~ ~кУ. (2.67)

Так как Ъ _ ка, то событие {Т < а| эквивалентно событию {У < Ъ|, где Ъ

- фиксированный ресурсный порог, после которого ценность ресурса становится равным нулям.

По формулам (2.61) и (2.66) получаем условную плотность распределения ресурса (у), когда значение случайной величина ресурса У не превысило

значение Ъ:

,у<Ь1

( у ):

-Яу

Яе 1 кj 1 _ g(у) у < Ъ

гт^ ■ к ~ да у < ^ (2.68)

о, у > Ъх

Условная плотность распределения ресурса ^^ (у), когда значение случайной величина ресурса У превысило порог Ъ равна:

0, у < Ъ

gy>ъг ( у ) _

-Яу

ЯеЯ^к > 1 g (у) ■ (2.69)

-ТЯГ- — Д/^ у > Ъ1

е"Яа> к 1 - Р(а)

Если имеем два параметра Ь1 и Ь 2, между которыми находятся все значения