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

• Автор: Лопатин, Роман Сергеевич
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2012
• Место защиты: Воронеж
• Количество страниц: 146 с. : ил.

Содержание

Введение
Глава 1 Особенности функционирования мультиагентных систем и взаимодействия их компонент
1.1 Особенности организации сложных вычислений с помощью распределенных и многоагентных систем
1.2 Особенности межмодульного взаимодействия распределенных систем
1.3 Особенности задачи планирования загрузки сложных систем
1.4 Цель и задачи диссертационного исследования
Глава 2 Разработка структуры распределенной системы планирования работ и математического и алгоритмического обеспечения ее компонент
2.1 Математическое и алгоритмическое описание задачи
2.2 Разработка структуры системы для задачи планирования работ
2.3 Разработка компонент многоагентной системы
2.4 Разработка математического обеспечения для выбора единицы расписания
2.5 Разработка математического и алгоритмического обеспечения для выбора оптимального времени выполнения работы
2.6 Выводы
Глава 3 Разработка синтаксических и семантических правил языка для организации взаимодействия компонент системы
3.1 Разработка надстройки для протокола ПОР для организации надежного соединения
3.2 Разработка синтаксиса языка взаимодействия между распределенными частями приложения
3.3 Разработка семантических процедур для распознавания пользовательского сообщения
3.4 Программные инструменты для организации межпрограммного
взаимодействия
3.5 Выводы
Глава 4 Программная реализация распределенной системы планирования учебных занятий
4.1 Разработка структуры базы данных
4.2 Программная реализация центра управления
4.3 Программная реализация интеллектуального агента
4.4 Пример функционирования программной системы
4.5 Выводы
Основные результаты работы
Список использованных источников
Приложения

Введение
Организация планирования работы больших систем представляет собой сложный процесс, требующий значительных временных ресурсов. Наличие нескольких центров обслуживания, большое количество работ, жесткие ограничения на ресурсы - все это обуславливает необходимость разработки математического, алгоритмического и программного обеспечения для решения данной задачи.
В связи с возможностью распараллеливания большинства операций, наиболее эффективным способом решения такой задачи является разработка распределенной системы, компоненты которой выполняли бы отдельные операции по планированию.
Разработка параллельных и распределенных вычислений начала интенсивно развиваться в 70-х годах прошлого века. Большой вклад в становление и развитие кластерных вычислений и грид-систем внесли такие ученые, как Г. Пфистер, И. Фостер, К. Кессельман, С. Тики и др. Теория многоагентных систем появилась, в частности, благодаря методам теории принятий решений в команде, одними из авторов которых были Д. Маршак, Р. Раднер и др. Мультиагентные системы получили свое развитие благодаря таким ученым, как С. Рассел, П. Норвиг, И. Шоэм, Д.А. Поспелов, В.Б. Тарасов и многим другим.
Однако, использование распределенных систем применительно к решению задачи планирования задач практически отсутствуют. Почти все виды данных задач отличаются МР-полнотой и требуют существенных временных затрат для своего решения. Данный процесс является итеративным, и на каждой операции выполняется планирование, например, для определенной машины. В связи с этим для больших систем с огромным числом работ целесообразно распараллелить некоторые вычисления и использовать теорию многоагентных систем для организации планирования работ с несколькими машинами.
Таким образом, актуальность диссертационной работы продиктована

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