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

На правах рукописи

ЛОПАТИН Роман Сергеевич

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

Специальность: 05.13.11 - Математическое и программное

обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

12 дпр гт

Воронеж - 2012

005018311

005018311

Работа выполнена в ФГБОУ ВПО «Воронежский государственный технический университет».

Научный руководитель Олейникова Светлана Александровна,

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

Официальные оппоненты: Блюмин Семен Львович, доктор

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

Авсеева Ольга Владимировна,

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

Ведущая организация ФГБОУ ВПО «Нижегородский

государственный технический университет им. P.E. Алексеева»

Защита состоится 26 апреля 2012 г. в Ю00 часов в конференц-зале на заседании диссертационного совета Д 212.037.01 ФГБОУ ВПО «Воронежский государственный технический университет» по адресу: 394026, г. Воронеж, Московский просп., 14.

С диссертацией можно ознакомиться в научно-технической библиотеке ФГБОУ ВПО «Воронежский государственный технический университет».

Автореферат разослан «19» марта 2012 г.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

Тематика диссертационной работы соответствует научному направлению ФГБОУ ВПО «Воронежский государственный технический университет» «Вычислительные комплексы и проблемно-ориентированные системы управления».

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

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

1) разработать структуру системы, предназначенной для распределенной обработки данных, поступающих от «интеллектуальных агентов»;

2) разработать математическое и алгоритмическое обеспечение, позволяющее интеллектуальному агенту принимать решение о планировании работ;

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

4) реализовать программные средства, позволяющие осуществлять процесс планирования.

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

Тематика работы соответствует следующим пунктам паспорта специальности 05.13.11 «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей»: п.З «Модели, методы, алгоритмы, языки и программные инструменты для организации взаимодействия программ и программных систем» и п. 8 «Модели и методы создания программ и программных систем для параллельной и распределенной обработки данных, языки и инструментальные средства параллельного программирования».

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

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

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

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

4. Программное обеспечение процесса планирования работ, учитывающее параллелизм выполнения отдельных этапов агентами и обеспечивающее автоматизацию процесса планирования.

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

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

Результаты внедрения. Разработанный программный комплекс в составе программных компонент, представляющих собой центр управления и интеллектуальных агентов, апробирован в НОУ ВПО «Международный институт компьютерных технологий» для планирования расписания учебных занятий. Эффект от внедрения заключается в сокращении времени, затрачиваемого на процесс планирования.

Апробация работы. Основные положения диссертационного исследования докладывались на следующих конференциях: I Всероссийской научно-практической конференции «Критические технологии вычислительных и информационных систем» (Воронеж, 2011), IV Международной научно-практической конференции «Перспективы развития информационных технологий» (Новосибирск, 2011), V Международной конференции «Актуальные вопросы современной техники и технологии» (Липецк, 2011), III Международной научно-практической конференции «Применение инновационных технологий в научных исследованиях» (Курск, 2011), Всероссийской научной школе «Информационно-телекоммуникационные системы и управление» (Воронеж, 2011), Международной открытой научной конференции «Современные проблемы информатизации в экономике и обеспечении безопасности» (Воронеж, 2012).

Публикации. По результатам диссертационного исследования опубликовано 13 научных работ, в том числе 3 - в изданиях, рекомендованных ВАК РФ. В работах, опубликованных в соавторстве и приведенных в конце автореферата, лично автором получены следующие результаты: [3] — разработка структуры распределенной системы; [1, 2] -математическое обеспечение для распределенной системы; [5] - оценка возможности распараллеливания работ при формировании расписания; [8, 10] -алгоритмическое обеспечение функционирования системы и ее отдельных компонент; [12,13] - реализация программного обеспечения для процесса планирования.

Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы из 108 наименований. Основная часть работы изложена на 129 страницах, содержит 28 рисунков, 19 таблиц.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

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

Вторая глава посвящена разработке распределенной системы планирования задач, а также математического и алгоритмического ее обеспечения. Пусть имеется р машин М1,...,МР, причем каждая машина j выполняет работы |ф 1,...,р. Каждая работа предназначена для обслуживания некоторой заявки г,, г=1,...,к и требует для своего выполнения одного из я видов ресурсов. Всего имеется г„ единиц ресурса типа ¡, ¡=1,...^. Процесс обслуживания любой заявки представляет собой перечень работ '*уГ1,...> Необходимо составить план-график выполнения работ. Графически данную систему можно отобразить следующим образом (рис. 1).

Опишем данную задачу математически. Пусть качество составленного расписания задается некоторой целевой функцией Р(5(М1),..., 8(МР)), где р-число машин, выполняющих расписание. Здесь Б(М;) - некоторое расписание, составленное для машины j, j=l,...,p. Оно представляет собой множество, каждый элемент / которого определяет время, в которое будет выполняться работа /.

8(ЦНТК,), (1)

Здесь \У|2, ..., у^ - работы, которые необходимо выполнить машине], а Т(\^2),...,Т(\^ ц) - время выполнения этих работ.

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

ТК,)*тК2)*...*тК тДг = 1,...,к. (2)

Еще одно ограничение необходимо ввести для учета количества используемых ресурсов каждого типа. Пусть существует q типов ресурсов: Г],...,гч. Пусть - функция, описывающая количество используемых ресурсов ¡-го типа в момент времени I. Тогда ограничение на ресурсы можно описать следующим образом:

У(м)<г„1 = 1,...,Ч. (3)

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

Гр(5(М,))—>ехи-;

0,(1)

У(1,1)<г„1 = 1,...,я

ТК) # Т(луг2) *... * т(ш,= 1,...,к.

[о, (1)^0.

(4)

[Р(5(мр))->ех1г;

Р Ор(1)

ТК,)*^)*...*^ _„Лг = 1,...,к.

Здесь 01(1),...,0Р(1) - множества, представляющие собой число способов расстановки расписания для машин 1,..., р соответственно.

Алгоритм решаемой задачи можно описать следующим образом (рис.

2).

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

- определить состав системы (т.е. множество ее участников);

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

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

- целевые функции, описывающие интересы и предпочтения участников;

- информированность и порядок функционирования.

Рис. 2. Общий алгоритм планирования загрузки агентов

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

Здесь символами ИА1,..., ИАп обозначены интеллектуальные агенты; CNI (Central - Network Interface) - интерфейс, необходимый для взаимодействия центра с другими компонентами по сети; ANI (Agent - Network Interface) - интерфейс, необходимый для взаимодействия интеллектуальных агентов по сети; БД - база данных, в которой хранится расписание, составляемое на каждом шаге; Средства удаленного доступа к БД - компоненты, предназначенные для организации удаленного соединения пользователей с СУБД FireBird. 3|,...,3t - множество заявок; ОРР- общий разделяемый ресурс.

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

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

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

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

- число способов расстановки данной единицы в расписание -

- коэффициент загрузки машины - f2;

- коэффициент «занятости» заявки -

- коэффициент загрузки ресурсов - £,.

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

- число возможных временных интервалов, когда машина 1 может работать Т(_о6щ;

- число временных интервалов, которые машина \ должна потратить на обслуживание всех заявок Т|_„ет5.

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

Т

I общ

т, ■ (5)

1 _ необ

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

„ Т1 общ -Т1 сост ~2_т(0

—^-• (6)

¡_необ ¡_сост

Здесь Т^сст - число записей, которое уже составлено для данной машины; 2_т(0 - количество запретов, связанное с невозможностью машине \ работать в некоторое время.

Для расчета коэффициента занятости заявки необходимо знать:

- число возможных временных интервалов, когда заявка j может быть обслужена общ',

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

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

Ъ^г., (7)

1 ъ -

Данный коэффициент также должен пересчитываться при составлении расписания. Это можно сделать с помощью характеристики Ъ1ах1, которая показывает время, которое уже запланировано для данной заявки.

Таким образом, на некотором текущем шаге занятость заявки определяется формулой

' ~ 7 - 7 '

^]_необ ^сост

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

- общая величина ресурсов

- необходимый объем ресурсов Як „ео6.

Пусть имеется Цк ресурсов типа к. Тогда общую величину ресурсов можно рассчитать по формуле

Кк_ооШ=Чк-Т, (9)

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

На основании этих двух параметров занятость ресурсов определяется формулой

(10)

к_необ

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

П _ Г)

__1ч1с_общ "•к_сост /11\

к-Г{ ГЙГ" • 1 '

1с_необ к_сост

Здесь Як сост - время, которое уже запланировано для обслуживания заявок с данным видом ресурса.

Число способов расстановки данной единицы нагрузки х=<1, к> определяется как мощность множества Э(х).

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

|D(x) min

T¡ обш-Т| C0CT-z_m(i)

—=-=-->min

T — T.

|_необ i_cocr

■ Zj общ - Zj coct-Z.zQ) . (12)

-—--»min

7 - 7

Rk общ _ Rk cocí , .

—=-=--► min

R-k_Heo6 _ Rk_cocr

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

Последним этапом является выбор наиболее оптимального времени для выбранной для планирования заявки. Этот выбор должен основываться на критерии, выбранном ЛПР. В частности, в работе рассмотрены следующие два критерия:

- равномерная загрузка агента в течение всего рассматриваемого периода;

- использование минимального числа дней в течение рассматриваемого периода.

В качестве ограничения были рассмотрены ограничения на отсутствие окон при обслуживании заявки или работе машины.

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

Третья глава посвящена разработке механизмов, предназначенных для обеспечения

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

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

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

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

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

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

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

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

Перечень команд разрабатываемого языка

№ п/п Команда Символ

1 Статус «активен» А

2 Ошибка Е

3 Указать приоритет Р

4 Значение приоритета V

5 Тупиковая ситуация Т

6 Приостановить расчет Б

7 Требование отменить предыдущее действие С

8 Завершение формирования единицы расписания I

9 Завершение формирования своего расписания Я

10 Завершение формирования расписания р

При этом некоторые команды требуют детализации, которая заключается в необходимости передачи дополнительных числовых значений. В частности, требуется детализация для команд «Значение приоритета», «Завершение формирования единицы расписания» и «Ошибка».

С учетом этого структура передаваемого сообщения должна быть следующей:__

[Ц]

П

А н А о Ид К

И

Здесь: П - поле преамбулы; А_н - адрес назначения; А_о - адрес отправителя; Ид - идентификатор сообщения; К - передаваемая команда; И -информационное поле, уточняющее содержимое команды; 3 - признак завершения.

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

Начало

Нет

Считать строку до символа Т

Пауза

Нет

Считать Ааг п

Считать Мг_0

Считать 10

^^нообх ^^ |Дэ

Считать команду 1пГ

Обработка АсЛ (И М)

^ Останов ^

Рис. 4. Семантическая обработка пришедшего сообщения

Здесь # - символ, которым заканчивается преамбула; Б - считанная строка; ргеашЬ - преамбула; Ас1г_п - адрес назначения; Ас1г_0 - адрес

отправителя; Ip - IP - адрес агента; IP CC - IP - адрес центра; Id -счетчик; ACT - действие; D- множество возможных действий; Inf - информационное дополнение к команде.

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

Рис. 5. Структура центра управления

Система состоит из следующих модулей: Мат_ипк (главный модуль программы); 0^_Макт§_ипк (модуль системы принятия решений центра); ЕсНМЛи! (модуль, предназначенный для редактирования данных в базе); 1п1_Соп_ипк (модуль для организации взаимодействия центра с удаленными компонентами); Оа1аМо<1и1е (модуль, содержащий основные компоненты и запросы для работы с базами данных.

Структура программного средства, реализующего функции интеллектуального агента, представлена на рис. 6.

Рис. 6. Структура интеллектуального агента

Эта система состоит из следующих модулей: Мат_11пк - главный модуль программы; 015_Мак|"гщ_11пк - модуль системы принятия решений центра; ЕЛ^ШЬ - модуль, предназначенный для редактирования данных в базе; 1ш_Соп_ипк - модуль для организации взаимодействия центра с удаленными компонентами; Ба1аМо<1и1е - модуль, содержащий основные компоненты и запросы для работы с базами данных.

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

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

Специальности

Идентификатор специальности

Наименование специальности

Шифр специальности --<р-

Кафедры

Идентификатор кафедры

Единица учебного плана

Наименование кафедры Сокращенное наименование кафедры

—Г"

-тр-

-Дисциплины

Идентификатор единицы УП

Идентификатор дисциплины

Название

Сокращенное название

Идентификатор кафедры (ЯК) Идентификатор специальности (РК) Идентификатор дисциплины (РК) -V

"I

I.

Учебный план

Преподаватели_

Идентификатор преподавателя

Фамилия Имя

Отчество

Идентификатор кафедры (ЯК)

Тип занятий

Идентификатор типа занятий

Наименование типа занятий Сокр наименование тз

Учебная единица

Идентификатор УЕ

Название

идентификатор родителя год поступления уровень

Идентификатор специальности (РК)

Идентификатор учебного плана

Семестр количество часов Идентификатор единицы УП (РК) Идентификатор типа занятии (РК) год

-<р-

Нагрузка

В---•

Идентификатор напЬуэки----

Идентификатор учебного тана (РК) Идентификатор преподавателя (РК) Идентификатор УТЕ (РК)

Расписание

Пары

Идентификатор лары

время начала время окончания номер пары

г—-

Идентификатор расписания

Идентификатор нагрузки (РК) Идентификатор лары (РК) Идентификатор аудитории (РК) Идентификатор дня недели (РК)

Аудитории

Идентификатор аудитории

Номер аудитории Тип аудитории

день недели

Идентификатор дня недели

название сокр название

Рис. 7. Структура базы данных

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

Главное окно интеллектуального агента представлено на рис. 8. Выбрав кафедру, а далее - преподавателя, переходим в личный кабинет. В данном окне в таблице на основании БС^Ь-запросов определены дисциплины, закрепленные за данным преподавателем, а также количество часов каждого типа по данным дисциплинам. В окне можно также ввести критерий пред-

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

Файл аЛорВУЗв Настройки Сграв*а

Выберите кафедру

выберкте преподавателя кафедры

конструировал« и производство радиоаппаратуры Начертательной геометра и машиностроительного черчения Нефтегазовое оборудование и транспортировка Оборудования и технологии сварочного производства Прикладная теоретическая механика Прикладная математика

Проектирована механизмов и падъемиотранспортных машин

М» )Фаг*«лия (Имя (Отчество

1 Чижов Михаил Иванович Ш

2 Мальцева Ирина Сергеевна |!

3 Бобров Алексамар Иванович 1

► 4 Собеиииа Ольга Валерьевна ®

5 Кольцов Атреи : Сергеевич Ш

6 Парк*юв Максим . Викторович 1?

9 Юров Алексеи . Николаевич ||

7 Мочалов Алексей Викторович ||

8 Лопату Роман Сергееееич Д1 ...............1..........¿ш

г

Рис. 8. Главное окно интеллектуального агента Результат планирования можно увидеть на рис. 9.

Собенина Ольга Веларьевна Весенний семестр 2011 г.

Номер ¡Дисциплина |Тип (Группа |Ден ь| Время Числ/Знам

► ЩЦ Мат. логика и ТА 3 ИТ-031 пи 8:0000 —1-' 1 ¡1|

_ 2 Мат. логика и ТА 3 ИТ 091 пи 8:0000 2

_ 3 Мат. логика и ТА 1 ИТ-091 пн 9:35.00 1

_ 4 Мат. логика и ТА 2 ИТ-091 пн 9:35 00 2 |

_ 5 Интеллектуалы*«» поде. САПР 1 ИТ 071 пн 11:3000 2 | |

_ 6 Интеллектуальные поде. САПР 1 ИТ-071 чт 13:30:00 1 |

7 Интеллектуальные пода САПР 1 ИТ-071 чт 13:30:00 2 1 1

_ 8 Интеллектуальные поде. САПР 3 ИТ 071 чт 15:1500

_ 3 Интеллектуальные пода САПР 3 ИТ 071 чт 15:1500 2 | |

10 Интеллектуальные поде. САПР 3 ИТ 071 чт 17:00:00 1

- П Интеллектуалы«^ поде. САПР 3 ИТ 071 чт .17:00.00 2 ! 3

а

Рис. 9. Готовое расписание

Разработанные компоненты распределенной системы зарегистрировал/ ФГНУ <<ЦИТИС>>- Полученная распределенная система внедрена в НОУ ВПО «Международный институт компьютерных технологий» Эффект

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

В процессе выполнения диссертационного исследования были получены следующие основные результаты:

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

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

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

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

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

6. Разработано программное обеспечение, предназначенное для планирования учебных занятий в вузе. Оно включает в себя две программы, первая из которых является центром управления, а вторая - интеллектуальным агентом. Каждая из компонент распределенной системы зарегистрирована в ФГНУ «ЦИТИС».

Основные результаты диссертации опубликованы в следующих работах:

Публикации в изданиях, рекомендованных ВАК РФ

1. Лопатин P.C. Применение математических методов моделирования в задачах составления учебного расписания / P.C. Лопатин, Е.Д. Федорков // Вестник Воронежского государственного технического университета. 2010. Т. 6. № 12. С. 110-113.

2. Лопатин P.C. Математическое обеспечение для распределенной системы планирования работ / P.C. Лопатин, С.А. Олейникова // Вестник Воронежского государственного технического университета, 2011. Т. 7. № 10. С. 33-36

3. Лопатин P.C. Разработка структуры распределенной системы для одной задачи планирования работ / P.C. Лопатин, С.А. Олейникова // Системы управления и информационные технологии. 2011.№3.1 (45). С. 173-176.

Статьи и материалы конференций

4. Лопатин P.C. Модели и алгоритмы составления учебного расписания / P.C. Лопатин // Высокие технологии в технике, медицине, экономике и образовании: межвуз. сб. науч. тр. Воронеж: ВГТУ, 2006. С. 263.

5. Лопатин P.C. Стратегия распределения имеющегося ресурса между элементами системы / P.C. Лопатин, Е.Д. Федорков, А.Н. Чекменев // Высокие технологии в технике, медицине, экономике и образовании: межвуз. сб. науч. тр. Воронеж: ВГТУ, 2008. С. 48.

6. Лопатин P.C. Разработка синтаксиса языка для организации взаимодействия программных систем для одной задачи планирования работ / P.C. Лопатин // Перспективы развития информационных технологий: сб. материалов IV Междунар. науч.-практ. конф. - Новосибирск: НГТУ, 2011. С.239-244.

7. Лопатин P.C. Разработка структуры программной системы для решения одной задачи планирования работ / P.C. Лопатин // Критические технологии вычислительных и информационных систем: сб. тр. - Воронеж: МИКТ, 2011. С. 126-132.

8. Лопатин P.C. Алгоритм функционирования распределенной системы планирования работ / P.C. Лопатин, С.А. Олейникова // Применение инновационных технологий в научных исследованиях: материалы III Междунар. науч.-практ. конф. Курск, 2011. - С. 182-185.

9. Лопатин P.C. Система принятия решений интеллектуального агента распределенной системы / P.C. Лопатин // Информационно-телекоммуникационные системы и управление: материалы Всерос. науч. школы. Воронеж, 2011. С. 4347.

Ю.Лопатин P.C. Разработка алгоритма функционирования интеллектуального агента распределенной системы / P.C. Лопатин, С.А. Олейникова // Актуальные вопросы современной техники и технологии: материалы V Междунар. конф. Липецк, 2011. С. 18-22.

11. Лопатин P.C. Программные инструменты для организации взаимодействия компонентов системы планирования / P.C. Лопатин // Современные проблемы информатизации в экономике и обеспечении безопасности: сб. тр. Междунар. открытой науч. конф. - Воронеж, 2012. С. 33-35.

12. Лопатин P.C. Программа. Центр управления распределенной системы планирования учебных занятий / P.C. Лопатин, С.А. Олейникова. М.: ФГНУ ЦИТИС, 2011. № 50201151280 от 02.10.11.

13. Лопатин P.C. Программа. Интеллектуальный агент распределенной системы планирования учебных занятий / P.C. Лопатин, С.А. Олейникова. М.:

Подписано в печать 16.03.2012. Формат 60x84/16. Бумага для множительных аппаратов. Усл. печ. л. 1,0. Тираж 80 экз. Заказ № ЗА, ФГБОУ ВПО «Воронежский государственный технический университет» 394026 Воронеж, Московский просп., 14

61 12-5/3426

На правах рукописи

ЛОПАТИН Роман Сергеевич

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

Специальность: 05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

ДИССЕРТАЦИЯ

на соискание ученой степени кандидата технических наук

Воронеж - 2012

Содержание

Введение...................................................................................................................4

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

1.1 Особенности организации сложных вычислений с помощью распределенных и многоагентных систем........................................................8

1.2 Особенности межмодульного взаимодействия распределенных систем..................................................................................................................15

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

1.4 Цель и задачи диссертационного исследования...................................37

Глава 2 Разработка структуры распределенной системы планирования работ и математического и алгоритмического обеспечения ее компонент...............38

2.1 Математическое и алгоритмическое описание задачи............................38

2.2 Разработка структуры системы для задачи планирования работ...........45

2.3 Разработка компонент многоагентной системы.......................................49

2.4 Разработка математического обеспечения для выбора единицы расписания..........................................................................................................59

2.5 Разработка математического и алгоритмического обеспечения для выбора оптимального времени выполнения работы......................................67

2.6 Выводы..........................................................................................................71

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

3.1 Разработка надстройки для протокола 1ЛЭР для организации надежного соединения..........................................................................................................72

3.2 Разработка синтаксиса языка взаимодействия между распределенными частями приложения..........................................................................................76

3.3 Разработка семантических процедур для распознавания пользовательского сообщения..........................................................................83

3.4 Программные инструменты для организации межпрограммного

взаимодействия..................................................................................................90

3.5 Выводы..........................................................................................................94

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

4.1 Разработка структуры базы данных...........................................................96

4.2 Программная реализация центра управления.........................................103

4.3 Программная реализация интеллектуального агента.............................107

4.4 Пример функционирования программной системы...............................110

4.5 Выводы........................................................................................................116

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

Список использованных источников................................................................119

Приложения.........................................................................................................130

Введение

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

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

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

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

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

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

Тематика диссертационной работы соответствует научному направлению ФГБОУ ВПО «Воронежский государственный технический университет» «Вычислительные комплексы и проблемно-ориентированные системы управления».

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

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

1) разработать структуру системы, предназначенной для распределенной обработки данных, поступающих от «интеллектуальных агентов»;

2) разработать математическое и алгоритмическое обеспечение, позволяющее интеллектуальному агенту принимать решение о планировании работ;

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

4) реализовать программные средства, позволяющие осуществлять процесс планирования.

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

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

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

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

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

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

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

4. Программное обеспечение процесса планирования работ, учитывающие параллелизм выполнения отдельных этапов агентами и обеспечивающее автоматизацию процесса планирования.

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

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

интеллектуальных агентов, апробирован в НОУ ВПО «Международный институт компьютерных технологий» для планирования расписания учебных занятий. Эффект от внедрения заключается в сокращении времени, затрачиваемого на процесс планирования.

Апробация работы. Основные положения диссертационного исследования докладывались на следующих Международных и Российских конференциях: I Всероссийской научно-практической конференции «Критические технологии вычислительных и информационных систем» (Воронеж, 2011), IV Международной научно-практической конференции «Перспективы развития информационных технологий» (Новосибирск, 2011), V Международной конференции «Актуальные вопросы современной техники и технологии» (Липецк, 2011), III Международной научно-практической конференции «Применение инновационных технологий в научных исследованиях» (Курск, 2011), Всероссийской научной школе «Информационно-телекоммуникационные системы и управление» (Воронеж, 2011), Современные проблемы информатизации (Воронеж, 2012).

Публикации. По результатам диссертационного исследования опубликовано 13 работ, из которых 3 опубликованы в журналах, рекомендованных ВАК РФ. В статьях, опубликованных в соавторстве, лично автором получены следующие результаты: [1] - разработка структуры распределенной системы; [2, 3] - математическое обеспечение для распределенной системы; [5] -оценка возможности распараллеливания работ при формировании расписания; [8, 10] - алгоритмическое обеспечение функционирования системы и ее отдельных компонент; [12,13] - реализация программного обеспечения для процесса планирования.

Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы из 109 наименований. Основная часть работы изложена на 129 страницах, содержит 28 рисунков, 19 таблиц.

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

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

1.1 Особенности организации сложных вычислений с помощью распределенных и многоагентных систем

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

Распределенной называется система, представляющая собой набор независимых компьютеров, представляющийся пользователям единой объединенной системой [3, 8, 17, 75].

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

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

Концепция прозрачности, как видно из таблицы 1.1, применима к различным аспектам распределенных систем [88].

Таблица 1.1. Различные формы прозрачности в распределенных системах.

Прозрачность Описание

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

Местоположение Скрывается местоположение ресурса

Перенос Скрывается факт перемещения ресурса в другое место

Смена местоположения Скрывается факт перемещения ресурса в процессе обработки в другое место

Репликация Скрывается факт репликации ресурса

Параллельный доступ Скрывается факт возможного совместного использования ресурса несколькими конкурирующими пользователями

Отказ Скрывается отказ и восстановление ресурса

Сохранность Скрывается, хранится ресурс (программный) на диске или находится в оперативной памяти

Прозрачность доступа (access transparency) призвана скрыть разницу в представлении данных и в способах доступа пользователя к ресурсам.

Другим важным свойством распределенных систем является открытость. Открытость - это использование синтаксических и семантических процедур, основанных на стандартах [106]. Для

распределенной системы это, прежде всего, использование формализованных протоколов.

Распределенные системы должны также обладать свойством масштарибуемости, которое может проявляться по отношению к размеру, географическому положению, а также к административному устройству систем. Одно из следствий масштабируемости заключается в том, что аппаратные и программные решения для распределенных систем могут быть гетерогенными [38, 78]. А это, в сочетании с независимостью приводит к еще одному важному свойству распределенных систем: системы могут существовать продолжительное время, но их отдельные части могут со временем отключаться [4, 38].

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

Рассмотрим задачи, решаемые распределенными системами. Одна из важных задач распределенных систем - облегчить пользователям доступ к удаленным ресурсам и обеспечить их совместное использование, регулируя этот процесс [63]. Другой важнейшей задачей является увеличение быстродействия при решении сложных задач и, следовательно, уменьшение времени, затрачиваемое на ее решение.

Одной из разновидностью распределенных систем являются многоагентные или мультиагентные системы [76, 77, 83, 84, 100, 107]. В качестве элементов многоагентных систем выступают так называемые интеллектуальные агенты. Интеллектуальный агент может пониматься как метаобъект, наделенный некоторой долей субъектности, т.е. способный манипулировать другими объектами, создавать и уничтожать их, а также имеющий развитые средства взаимодействия со средой и себе подобными.

Иными словами, это «активный объект» или «искусственный деятель», находящийся на заметно более высоком уровне сложности по отношению к традиционным объектам в ООП и использующий их для достижения своих целей путем управления, изменяющего их состояния [89, 90].

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

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