Автоматика и телемеханика, № 8, 2022

Робастное, адаптивное и сетевое

управление

(igor@kalyaev.net),

А.И. КАЛЯЕВ, канд. техн. наук (anatoly@kalyaev.net)

(Южный федеральный университет, Таганрог)

МЕТОД И АЛГОРИТМЫ АДАПТИВНОГО

МУЛЬТИАГЕНТНОГО ДИСПЕТЧИРОВАНИЯ РЕСУРСОВ

В ГЕТЕРОГЕННЫХ РАСПРЕДЕЛЕННЫХ

ВЫЧИСЛИТЕЛЬНЫХ СРЕДАХ¹

Настоящая статья посвящена созданию новых метода и алгоритмов

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

ных системах на примере облачных вычислительных сред (ОВС), обеспе-

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

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

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

кретной полученной задаче. Для этого предлагается применять мульти-

агентный подход к организации процесса диспетчирования: в состав каж-

дого элемента ОВС вводится программный агент, располагающий наибо-

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

теля, множество таких агентов совместно осуществляют подбор наиболее

подходящих задач и подзадач с учетом имеющейся информации. Описа-

ны принципы построения и метод работы адаптивного мультиагентного

диспетчера ресурсов ОВС, алгоритмы работы агентов ресурсов и задач,

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

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

Ключевые слова: распределенная вычислительная среда, облачная вы-

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

вычислений.

DOI: 10.31857/S0005231022080062, EDN: AHCWSW

1. Введение

Наблюдаемое в последние годы бурное развитие технологий передачи дан-

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

ванных на использовании множества распределенных в пространстве вычис-

лительных ресурсов с применением сервис-ориентированного подхода, обес-

¹ Работа выполнена в рамках Государственного задания Санкт-Петербургского поли-

технического университета Петра Великого (проект № 075-01429-22-02).

100

печивающего ¾вычисления по требованию¿. Эти возможности породили но-

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

ме облачных вычислений, предполагающей организацию распределенных вы-

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

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

нет [1]. В настоящее время облачные вычислительные среды (ОВС) находят

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

личных предметных областях: физика; химия и биология; фармакология и

фармацевтика; материаловедение; нефтегазодобыча и т.п. [2, 3]. При этом

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

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

Одним из главных преимуществ ОВС является абстрагирование пользо-

вателя от выбора конкретных аппаратных ресурсов: он просто предоставляет

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

ворим об облачных системах, речь обычно идет о минутах или часах. В общем

виде ОВС состоит из множества различных вычислителей, это обусловлено

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

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

уже установленным), более низкой востребованностью определенных уско-

рителей (GPU, FPGA) и т.д. Такая гетерогенная структура, с одной сторо-

ны, позволяет повысить эффективность работы ОВС за счет использования

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

ную производительность при решении определенных задач, но, с другой сто-

роны, делает существенно более значимым распределение решаемых задач

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

ОВС [4].

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

• ОВС должна обеспечивать решение некоторого множества различных

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

при этом поступающие задачи в общем виде могут обладать сложной внут-

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

эффективность решения каждой из которых может в сильной степени зави-

сеть от типа используемого вычислительного ресурса);

• узлы ОВС могут со временем изменять свои характеристики в зависи-

мости от множества факторов, например с связи с изменением температуры

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

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

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

ных параметров элементов ОВС при распределении задач для повышения

эффективности их выполнения и об актуальности проблемы эффективного

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

ОВС, состоящих из идентичных вычислителей.

101

Современные исследования в области распределения задач в гетероген-

ных средах с изменяющимися со временем параметрами в основном базиру-

ются на предсказании. Например, в [5] авторы описывают мультиагентный

алгоритм Deep-Q-network (DQN), базирующийся на централизованном мно-

гоагентном обучении с подкреплением (Multiagent Reinforcement Learning

MARL), который предполагает обучение с подкреплением для оптимизации

времени и стоимости распределения и выполнения задач, при этом агенты

наследуют эвристики для применения в сформированных нейронных сетях.

Авторы [6] представляют генетический алгоритм с эффективной настройкой

(Genetic Algorithm with Efficient Tune-In

GAETI) для выполнения дли-

тельных вычислений на удаленных вычислительных системах с улучшением

времени решения. В [7] авторы предлагают метод гибридной оптимизации

роя частиц, предполагающий распределение на базе недоминирующей сорти-

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

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

с подкреплением [8-14], где совместно применяются концепция равновесия в

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

ством ограничений и множеством целей. Общим недостатком рассмотренных

подходов является необходимость наличия накопленной статистической ин-

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

ной системы.

В некоторых из рассмотренных подходов применяются мультиагентные

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

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

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

петчера составляют виртуальное расписание. В настоящей статье предлага-

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

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

щения элементов ОВС в множество физически распределенных агентов,

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

агентами.

В [15, 16] описывается подход к мультиагентной организации диспетчи-

рования ресурсов в гетерогенных ОВС, позволяющий реализовать распре-

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

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

организация диспетчера позволяет эвристически обеспечить квазиоптималь-

ное распределение ресурсов ОВС, адаптивно учитывающее их актуальные

параметры, что обеспечивает возможность применения широкого перечня

оборудования. Другими преимуществами указанного подхода являются воз-

можность оперативного масштабирования ОВС, а также увеличенная отка-

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

вания.

Однако применение подхода, предложенного в [15, 16], предполагает, что

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

102

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

параметрах ОВС, указание ими неадекватного времени решения приводит к

невозможности выполнения задач, что, в свою очередь, приводит к снижению

эффективности работы ОВС в целом [17]. Настоящая статья посвящена раз-

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

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

задано, при этом целью работы диспетчера ОВС становится минимизация

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

тельных ресурсов.

2. Формальная постановка задачи

Как было сказано выше, множество пользователей в случайные моменты

времени отправляют в ОВС множество различных задач Z =< Z₁, . . . , Z_M >.

Под задачей будем понимать некоторое множество информационно зависи-

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

вычислительную трудоемкость. Формально каждая такая задача Z_l ∈ Z мо-

жет быть представлена в виде ацикличного графа G_l(Q_l, X_l) (рис. 1), верши-

ны q_j ∈ Q_l которого соответствуют некоторым подзадачам O_j , принадлежа-

щим множеству подзадач O =< O₁, . . . , O_c >, а дуги x(q_j , q_j+1) ∈ X_l опреде-

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

шины q_j и q_j+1 соединены дугой x(q_j, q_j+1), то это означает, что данные, полу-

ченные в результате решения подзадачи O_j , приписанной вершине q_j, явля-

ются исходными данными для подзадачи O_j+1, приписанной вершине q_j+1).

Будем считать, что каждой вершине q_j ∈ Q_l приписаны тип решаемой подза-

дачи O_j ∈ O и ее вычислительная трудоемкость v_j, оцениваемая числом эле-

Рис. 1. Граф G_l(Q_l, X_l) задачи Z_l.

103

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

ге x(q_j, q_j+1) ∈ X_l приписан объем данных d_j ,_j+1, передаваемых от подзада-

чи O_j, приписанной вершине q_j, подзадаче O_j+1, приписанной вершине q_j+1

(рис. 1).

В состав ОВС входит множество гетерогенных вычислительных ресурсов

R =< R₁,... R_N >. Будем считать, что каждый ресурс R_i ∈ R может решать

некоторый набор (подмножество) типов подзадач O_i =< O₁, . . . O_L > ⊆O

(i = 1, . . . , N), причем реальная производительность ресурса R_i при реше-

нии подзадачи O_j ∈ O_i (j = 1, . . . , L) составляет S_i(O_j ) (операций в секун-

ду). В общем случае реальная производительность различных ресурсов

ОВС при решении идентичных подзадач O_j может быть различной, т.е.

S_p(O_j) = S_c(O_j) (p = 1,... ,N; c = 1,... ,p - 1,p + 1,... ,N). Будем считать,

что известна пропускная способность Y_p (байт/с) канала связи ресурса R_i

(i = 1, . . . , N) с облачной инфраструктурой.

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

∑

ни решения задач множества Z T_Z = T (Z_i), где T (Z_i) время решения

i=1

задачи Z_i путем выбора определенного распределения их подзадач по вычис-

лительным ресурсам R =< R₁, . . . , R_N > с учетом оперативной оценки их

текущей производительности при решении той или иной подзадачи и про-

пускной способности канала связи с облачной инфраструктурой.

Решение сформулированной таким образом задачи распределения ресур-

сов ОВС по поступающим задачам множества Z классическими методами,

например методами динамического и линейного программирования [18-20],

является сложной задачей из-за того, что вычислительные ресурсы гетеро-

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

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

дач различных задач множества Z между ресурсами R =< R₁, . . . R_N > с

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

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

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

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

рования [21].

3. Метод адаптивного мультиагентного

диспетчирования ресурсов

Прежде чем приступить к описанию предложенного метода мультиагент-

ного диспетчирования ОВС, расширим понятие ¾нити¿, введенное в [15, 16].

Как и раньше, под нитью, будем понимать некоторую последовательность

вершин H_f =< q^f1 , . . . , q^fk > графа G_l(Q_l, X_l) задачи Z_l ∈ Z, в которой вер-

шины q^fj и q^fj+1 (j = 1, . . . , k - 1) соединены дугой x(q^fj , q^fj+1) (рис. 2).

Иными словами, нить определяет некоторую последовательность подзадач

задачи Z_l, в которой каждая последующая подзадача использует в качестве

104

Рис. 2. Нить H_f в графе G_l(Q_l, X_l) задачи Z_l.

исходных данных результат выполнения предыдущей подзадачи. При этом

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

следовательно. Под длиной T_f нити H_f будем понимать суммарное время,

затрачиваемое на ее решение, определяемое как

∑

T_f = (T(O_i) + T_i,i+1),

i=1

где T (O_i)

время решения подзадачи O_i, приписанной вершине q^fi ∈ H_f

(i = 1, . . . , k); T_i,i+1

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

шения подзадачи O_i, ресурсу, решающему следующую подзадачу O_i+1, при-

писанную вершине q^fi+1 ∈ H_f , причем

v_i

T (O_i) =

S_p(O_i)

где v_i трудоемкость подзадачи O_i; S_p(O_i) реальная производительность

ресурса R_p, решающего подзадачу O_i;



0,

если подзадачи O_i и O_i+1 решаются





одним и тем же ресурсом R_p ∈ R,

T_i,i+1 =

dfr,r+1



, если подзадачи O_i и O_i+1 решаются

 Y_p

различными ресурсами R_p и R_c,

105

Рис. 3. Структура ОВС.

где d^fi,i+1

объем данных, передаваемых от подзадачи O_i подзадаче O_i+1;

Y_p пропускная способность канала связи ресурса R_p.

Если вся нить H_f выполняется одним и тем же ресурсом R_p, то ее длина

будет составлять

∑

d^fk,k+1

v_i

(1)

T_f =

S_p(O_i)

Y_p

i=1

где d^fk,k+1 объем данных, приписанный исходящей (конечной) дуге нити H_f

(рис. 3).

При этом кратчайшее время выполнения задачи Z_l ∈ Z будет, в первую

очередь, зависеть от длины критического пути в графе G_l(Q_l, X_l), т.е. нити,

суммарная трудоемкость вершин которой максимальна [22].

В [15, 16] предложен мультиагентный подход к диспетчированию, пред-

полагающий, что каждый ресурс R_j (i = 1, . . . , N) обладает программным

агентом AR_i, осуществляющим поиск работы для ¾своего¿ ресурса R_j. Для

этого агент AR_i периодически опрашивает выделенный ресурс

¾доску объ-

явлений¿ (ДО), на которой пользователи размещают свои задачи. В случае

106

обнаружения на ДО некоторой задачи Z_l ∈ Z агент AR_j делает попытку вой-

ти в состав сообщества R_l ⊆ R по его решению, принимая на себя исполнение

наиболее длинной нити, что он может реализовать с помощью ¾своего¿ ре-

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

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

не задано, поэтому, кроме агентов AR_i (i = 1, . . . , N), представляющих раз-

личные ресурсы R_j ∈ R (j = 1, . . . , N), предлагается ввести в состав мульти-

агентного диспетчера дополнительно к ним агентов задач AZ_j (j = 1, . . . , M),

по сути являющихся ¾представителями пользователей¿ и ответственных за

сокращение времени выполнения своей задачи (рис. 3).

Для решения пользовательской задачи в ОВС выполняются следующие

шаги:

1. Пользователь формирует свою задачу Z_l ∈ Z в виде графа G_l(Q_l, X_l) и

размещает на ДО.

2. Каждой задаче Z_l ∈ Z, поступившей на ДО, назначается агент AZ_l.

3. Агент AZ_l задачи Z_l с помощью алгоритмов поиска критического

пути [23] выделяет в графе G_l(Q_l, X_l) наиболее трудоемкую нить H₁ =(

)

∑

=< q¹¹,... ,q^1k >, для которой значение V₁ =

v¹

максимально, где v¹ⁱ

i=1

(j = 1, . . . , k)

трудоемкость подзадачи O_i, приписанной вершине q¹ⁱ ∈ H₁,

и устанавливает возможный (желательный) момент времени начала ее ис-

полнения t^1н = t_тек, где t_тек текущий момент времени. После этого нить H₁

выставляется на ДО для исполнения.

4. Агенты AR_j различных ресурсов R_j (j = 1, . . . , N) последовательно

опрашивают ДО в поисках работы.

5. При обнаружении нити H₁, выставленной агентом AZ_l, агент AR_j оце-

нивает эффективность участия в ее решении.

6. Для этого агент AR_j выбирает в нити H₁ =< q¹¹, . . . , q^1k > поднить H^11j =

=< q¹¹,... ,q^1b > ⊆H₁ (b ≤ k), вершинам которой приписаны подзадачи множе-

ства O_i, т.е. подзадачи, выполняемые ресурсом R_j (рис. 4).

Агент AR_j имеет на базе информацию о том, когда закончит выполнять

запланированные задачи (момент времени t^1нj), определяет момент, когда он

сможет начать работу над поднитью H^11j, и время t^1кj окончания исполнения

поднити H^11j, причем

∑

v¹ⁱ

d^1b,b+1

(2)

t^1кj = t^1нj +

S_j(O_i)

Y_j

i=1

где v¹ⁱ

трудоемкость подзадачи O_i, приписанной вершине q¹ⁱ ∈ H^11j (i =

= 1, . . . , b); S_j (O_i)

производительность ресурса R_j при решении подзада-

чи O_i; d^1b,b+1 объем данных, приписанных конечной дуге x(q^1b, q^1b+1) подни-

ти H^11j ; Y_j пропускная способность канала связи ресурса R_j .

107

Рис. 4. Распределение операции нити H₁ между агентами AR_j (j = 1, . . . , N).

Выбранная поднить H^11j, с приписанными ей моментами времени начала

исполнения t^1нj и окончания исполнения t^1кj , передается агентом AR_p агенту

AZ_l задачи Z_l в качестве ¾оферты¿ по его участию в исполнении нити H₁.

7. По прошествии некоторого таймаута агент AZ_l задачи Z_l среди всех

поступивших ¾предложений¿ выбирает наиболее подходящее поднить H^11p,

¾предложенную¿ агентом AR_p, для которой значение величины

^b v¹ⁱ

E_p =ⁱ⁼¹

t^1кp - t^1н

максимально, где v¹ⁱ трудоемкость подзадачи O_i (i = 1, . . . , b), приписанной

вершине q¹ⁱ ∈ H^11p; t^1н желательное время начала исполнения нити H₁, уста-

новленное агентом задачи AZ_l; t^1кp момент времени завершения исполнения

поднити H^11p агентом AR_p.

8. Поднить H^11p, для которой значение E_p максимально, закрепляется за

агентом AR_p, о чем ему направляется соответствующее сообщение от аген-

та AZ_l, и агент AR_p включается в состав сообщества R_l по выполнению

задачи Z_l. В графе G_l(Q_l, X_l) задачи Z_l каждой вершине q^1j (j = 1, . . . , b)

поднити H^11p приписывается номер p ресурса R_p, за которым закреплено ее

исполнение, а также момент времени ее исполнения t^1j, определяемый как

∑

v¹ⁱ

(3)

t^1j = t^1нp +

S_p(O_i)

i=1

108

где v¹ⁱ трудоемкость подзадачи O_i, приписанной вершине q¹ⁱ; S_p(O_i) про-

изводительность ресурса R_p при решении подзадачи O_i.

9. Агент AZ_l задачи Z_l исключает вершины q¹¹, . . . , q^1b поднити H^11p

из нити H₁, в результате чего формируется новая (укороченная) нить

H²¹ =< q^1b+1,... ,q^1k > (рис. 4), а первой вершине q^1b+1 этой нити приписывает-

ся номер агента AR_p, от которого должны поступить исходные данные для ее

выполнения, а также возможное (желательное) время начала ее исполнения

t^2н = t^1кp, где t^1кp

время окончания исполнения поднити H^11p, определяемое

согласно выражению (2).

После этого нить H²¹ выставляется агентом AZ_l на ДО для исполнения.

10. В дальнейшем агенты различных ресурсов R_j (i = 1, . . . , N) оценивают

свои возможности по участию в исполнении нити H²¹. При этом агент AR_j

(j = 1, . . . , N) выделяет поднить H^21j =< q^1b+1, . . . , q^1m > ⊆H²¹ (m ≤ k) (см.

рис. 4), вершинам которой приписаны подзадачи подмножества O_j ⊆ O, вы-

полняемого ресурсом R_j , а также определяет момент времени начала ее ис-

полнения t^2нj , (т.е. момент, когда он может приступить к ее исполнению, при-

чем t^2нj ≥ t^2н), а также момент времени окончания ее исполнения t^2кj, опреде-

ляемый как

∑

v¹ⁱ

d^1m,m+1

(4)

t^2кj = t^2нj +

S_j(O_i)

Y_j

i=b+1

Выделенная таким образом поднить H^21j направляется агентом AR_j аген-

ту AZ_l задачи Z_l в качестве ¾предложения¿ по участию в выполнении ни-

ти H²¹.

11. По прошествии определенного таймаута агент AZ_l задачи Z_l выбирает

наилучшее ¾предложение¿ того агента AR_c, предлагающего к исполнению

поднить H^21c =< q^1b+1, . . . , q^1m > (m ≤ k), для которой величина

^m v¹ⁱ

(5)

E_c =^b+1

t^2кc - t^2н

максимальна.

Вершины поднити H^21c закрепляются за агентом AR_c, о чем ему направ-

ляется соответствующее сообщение, и агент AR_p включается в сообщество R_l

по решению задачи Z_l. Кроме того, в каждой вершине q^1j (i = b + 1, . . . , m)

графа G_l(Q_l, X_l) приписывается номер c ресурса R_c, за которым закреплено

ее исполнение, и момент времени t^1jc ее исполнения, определяемый как

∑

v¹ⁱ

(6)

t^1j = t^2нc +

S_c(O_i)

i=b+1

где v¹ⁱ трудоемкость подзадачи O_i, приписанной вершине q¹ⁱ; S_c(O_i) про-

изводительность ресурса R_c при решении подзадачи O_i.

109

Рис. 5. Граф G^1l(Q^1l, X^1l) задачи Z_l, модифицированный агентом AZ_l.

12. После этого агент задачи AZ_l формирует новую нить H³¹ =

=< q^1m+1,... ,q^1k >, путем исключения из нити H²¹ вершин поднити H^21c, т.е.

H³¹ = H²¹/H^21c, и первой вершине q^1m+1 этой нити приписывает возможное (же-

лательное) время начала ее исполнения t^3н = t^2кc, где t^2кc

момент времени

завершения поднити H^21c, определяемый согласно (4).

Далее нить H³¹ вновь выставляется агентом задачи AZ_l на исполнение и

т.д. до тех пор, пока не окажется, что очередная нить пуста H^k1 = ∅. Это

говорит о том, что все вершины нити H₁ закреплены за агентами различных

ресурсов R_j (i = 1, . . . , N).

13. После этого агент AZ_l задачи Z_l исключает нить H₁ из графа за-

дачи G_l(Q_l, X_l), в результате чего формируется новый граф G^1l(Q^1l, X^1l) =

= G_l(Q_l,X_l)/H₁ (рис. 5).

В обновленном графе G1l (Q1l , X1l ) агентом AZ_l определяется наиболее тру-

доемкая нить H₂ =< q²¹, . . . , q^2r > (рис. 5) для дальнейшего распределения

между агентами ресурсов R_j (i = 1, . . . , N), в результате чего всем верши-

нам нити H₂ =< q²¹, . . . , q^2r > в графе G_l(Q_l, X_l) будут поставлены в соответ-

ствие номерам ресурсов R_j , за которыми закреплено их исполнение, а также

моменты времени t^2f (f = 1, . . . , r) их исполнения.

14. Поскольку нить H₂ =< q²¹, . . . , q^2r > является ветвью нити H₁ =

=< q¹¹,... ,q^1k > (т.е. конечная вершина q^2r нити H₂ инцидентна одной из вер-

шин q^1b нити H₁) (см. рис. 5), то требуется оценить погрешность времени за-

вершения нити H₂ для определения актуальности времени начала работы над

инцидентной ей вершиной q^1b нити H₁. Поэтому агент AZ_l задачи Z_l сравни-

110

Рис. 6. Граф G^2l(Q^2l, X^2l), модифицированный агентом AZ_l.

вает момент времени t^2к завершения исполнения нити H₂, определяемый как

d^2r,r+1

(7)

t^2к = t^2r +

Y_j

где t^2r момент времени, приписанный конечной вершине q^2r нити H₂; d^2r,r+1

объем передаваемых данных, приписанный дуге, исходящей из вершины q^2r;

Y_j

пропускная способность канала связи ресурса R_j, приписанного вер-

шине q^2r;

с моментом времени t^1b-1, приписанным вершине q^1b-1 нити H₁. Если оказы-

вается, что t^2к > t^1b-1, то это означает, что данные, получаемые в результате

выполнения подзадач нити H₂ и необходимые для решения подзадачи, при-

писанной вершине q^1b ∈ H₁, поступят позже, чем данные, также необходимые

для решения подзадачи вершины q^1b и получаемые в результате выполнения

подзадачи вершины q^1b-1 нити H₁. В этом случае агент задачи AZ_l произво-

дит корректировку графика исполнения нити H₁ путем смещения моментов

времени, приписанных ее вершинам q_b, . . . q_k, на величину Δt = t^2к - t^1b-1.

15. Агент AZ_l задачи Z_l формирует обновленный граф задачи

G^2l(Q^2l,X^2l) = G^1l(Q^1l,X^1l)/H₂

путем исключения из рассмотрения вершин нити H₂ (пометив их как ре-

шаемые), в этом графе (рис. 6) определяет наиболее трудоемкую нить H₃ и

отправляет на ДО.

В процессе работы ОВС распределение вершин (подзадач) графа задачи

Gl(Ql, Xl) продолжается далее до тех пор, пока они все не будут распределе-

ны, т.е. очередной граф будет пуст G^dl(Q^dl, X^dl) = ∅. В результате всем вер-

шинам q_i ∈ Q_l графа задачи G_l(Q_l, X_l) будут приписаны номера ресурсов R_j

111

q_1f

q_i

q_rf

tнfp

t_к

Рис. 7. Исполнение поднити H^mf агентом AR_p.

(j = 1, . . . , N), отвечающих за их исполнение, а также планируемые моменты

времени t_i их исполнения, т.е. будет построен график решения задачи Z_l.

16. После этого агент задачи Z_l сообщает пользователю планируемый мо-

мент времени t^kl выполнения его задачи Z_l, который определяется как

d_k,k+1

(8)

t^kl = t_k +

Y_p

где t_k момент времени, приписанный конечной вершине q_k графа G_l(Q_l, X_l);

d_k,k+1

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

вершины q_k; Y_p пропускная способность канала связи ресурса R_p, закреп-

ленного за вершиной q_k.

В случае согласия пользователя агент AZ_l сообщает всем агентам ресур-

сов R_j (i = 1, . . . , N), задействованным в выполнении данной задачи (т.е. вхо-

дящим в сообщество R_l), о необходимости выполнения принятых на себя под-

задач согласно установленному плану (временному графику).

17. Когда агент AR_p ресурса R_p получает подтверждение от агента AZ_l

задачи Z_l о необходимости выполнения закрепленной за ним поднити H^mf =

=< q^f1,... ,q^r > графа задачи G_l(Q_l,X_l), он включает подзадачи, приписан-

ные вершинам поднити H^mf, в свой график работы.

18. При наступлении момента времени t^нp начала исполнения поднити

H^mf агент AR_p приступает к выполнению последовательности подзадач O^fi

(i = 1, . . . , r), приписанных вершинам q^fi ∈ H^mf (рис. 7). Если для выполне-

ния очередной подзадачи O^fi необходимы исходные данные, поступающие от

других ресурсов, то агент AR_j первым делом проверяет их наличие. Если

требуемые исходные данные еще не поступили, агент AR_j переходит в ре-

жим ожидания.

19. По факту получения необходимых данных агент AR_p осуществляет

решение подзадачи O^fi (i = 1, . . . , r) с помощью ¾своего¿ ресурса R_p. После

выполнения всех подзадач O^fi , приписанных вершинам q^fi (i = 1, . . . , r) под-

нити H^mf, агент AR_p отправляет агенту AZ_l задачи Z_l сообщение о работе над

последовательностью подзадач поднити H^mf и передает результат ее следую-

щему ресурсу R_p, исполняющему смежную с ней вершину графа G_l(Q_l, X_l).

112

20. Агент AZ_l осуществляет проверку соблюдения временного графика

выполнения агентом AR_p подзадач нити H^mf путем сравнения запланирован-

ного времени t^к завершения поднити H^mf, определяемого как t^к = t^r +dr,r+1Yp

(рис. 7) (где t^r

момент времени, приписанный конечной вершине q^r под-

нити H^mf; d^fr,r+1 объем передаваемых данных, приписанных исходящей из

вершины q^r дуге; Y_p пропускная способность канала связи ресурса R_p),

с текущим временем t_тек.

Если t_тек > t_к, то это означает, что возникла задержка в выполнении вре-

менного графика решения задачи Z_l, о чем агент AZ_l сообщает пользова-

телю. Кроме того, агент AZ_l актуализирует временной график исполнения

последующих вершин q_r, q_r+1, . . . , q_k графа задачи G_l(Q_l, X_l) путем смещения

моментов времени на величину Δt = t_тек - t^к (см. рис. 5).

21. После того, как все подзадачи задачи Z_l решены (т.е. агент задачи

получил подтверждения от всех агентов сообщества R_l об успешном завер-

шении всех принятых на себя поднитей), агент AZ_l сообщает пользователю

об успешном решении его задачи Z_l, после чего задача Z_l снимается с ДО.

Для применения на практике описанных ранее принципов мультиагентно-

го диспетчирования гетерогенной ОВС были разработаны алгоритмы работы

агентов задачи и вычислительного ресурса.

4. Алгоритм работы агента задачи при мультиагентном

диспетчировании ресурсов

Как только граф G_l(Q_l, X_l) задачи Z_l передается на ДО, ему назначается

агент AZ_l, который находит в графе задачи G_l(Q_l, X_l) самую трудоемкую

нить H₁ =< q¹¹, . . . , q^1k > и устанавливает желательный (возможный) момент

времени начала ее исполнения t^1н = t_тек, после чего выставляет нить H₁ на

исполнение на ДО (см. рис. 4).

После того, как агенты ресурсов R_j (i = 1, . . . , N) проанализируют воз-

можность своего участия в выполнении нити H₁ и направят свои ¾предложе-

ния¿ агенту AZ_l задачи Z_l, последний выбирает ¾предложение¿ того аген-

та AR_p, который может обеспечить выполнение поднити H^11p =< q¹¹, . . . , q^1b >

⊆H₁, имеющий наибольшее значение

^b v¹ⁱ

E_p =ⁱ⁼¹

t^1кp - t^1н

где v¹ⁱ (i = 1, . . . , b)

трудоемкость подзадачи O_i, приписанной вершинам

q¹ⁱ ∈ H^11p; t^1кp

момент времени завершения исполнения поднити H^11p аген-

том AR_p, определяемый с помощью выражения (2).

Агент AR_p включается в сообщество R_l по решению задачи Z_l, а в графе

Gl(Ql, Xl) всем вершинам поднити H^1p приписывается номер агента ARp,

113

отвечающего за их исполнение, а также моменты времени их исполнения,

определяемые с помощью выражения (3).

Агент AZ_l исключает поднить H¹¹ из нити H₁, в результате чего фор-

мируется новая нить H²¹ ⊆ H₁, которой агент AZ_l приписывает возможный

момент времени начала ее исполнения t^2н, определяемый временем исполне-

ния поднити H^11p, т.е. t^2н = t^1кp (см. рис. 4). После этого нить H²¹ выставляется

агентом AZ_l на ДО для исполнения.

После этого агент AZ_l ожидает предложения агентов AR_j (j = 1, . . . , N)

по работе над нитью H²¹ и выбирает ¾предложение¿ того агента AR_c, кото-

рый обеспечивает выполнение такой поднити H^21c =< q^1b+1, . . . , q^1m > (m ≤ k),

для которой значение E_c (см. выражение (4)) максимально. Выбранный

агент AR_c включается в сообщество R_l, а в графе G_l(Q_l, X_l) вершинам этой

поднити H^21c приписываются его номер, время их исполнения t^j1, определяе-

мое с помощью выражения (5).

Описанный процесс продолжается до тех пор, пока не будут распределе-

ны все вершины (подзадачи) нити H₁, т.е. пока не окажется, что очередная

поднить пуста H^m1 = ∅.

Далее агент задачи AZ_l исключает из графа G_l(Q_l, X_l) нить H₁, в резуль-

тате чего формируется новый граф G^1l(Q^1l, X^1l) = G_l(Q_l, X_l)/H₁, и выделяет

в последнем наиболее трудоемкую нить H₂, которая выставляется на ДО

на исполнение (см. рис. 5). После того как все вершины (подзадачи) ни-

ти H₂ =< q²¹, . . . , q^2r > будут разобраны агентами AR_j (j = 1, . . . , N), в гра-

фе G_l(Q_l, X_l) им будут приписаны номера соответствующих агентов AR_p,

а также время их исполнения t²ⁱ (i = 1, . . . , r). После этого агент задачи AZ_l

должен проверить согласованность времени поступления исходных данных

для подзадачи O_b, приписанной вершине q^1b нити H₁, инцидентной конеч-

ной вершине нити H₂. Для этого агент задачи AZ_l сравнивает момент вре-

мени t^2к завершения исполнения нити H₂, определяемый с помощью выра-

жения (7), с моментом времени t^1b-1 исполнения предыдущей вершины q^1b-1

нити H₁ (см. рис. 5). Если t^2r > t^1b-1, то это означает, что данные, получае-

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

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

нения операции O_b-1, приписанной вершине q_b-1 нити H₁. В этом случае

агент задачи AZ_l должен скорректировать моменты времени исполнения всех

последующих вершин q^1b, . . . , q^1k нити H₁ путем их увеличения на величину

Δt = t^2к - t^1b-1.

Далее нить H₂ исключается из графа задачи G^1l(Q^1l, X^1l), в результате чего

формируется новый граф G^2l(Q^2l, X^2l) = G^1l(Q^1l, X^1l)/H₂, в котором вновь вы-

деляется наиболее трудоемкая нить H₃, которая выставляется агентом AZ_l

на ДО для исполнения (см. рис. 6). Процесс продолжается до тех пор, пока

все вершины графа задачи G_l(Q_l, X_l) не будут закреплены за агентами AR_j

(j = 1, . . . , N) и им будут приписаны планируемые моменты времени их ис-

полнения. По завершению данного процесса агент AZ_l задачи Z_l сообщает

114

пользователю планируемый момент времени t^kl решения его задачи Z_l, опре-

деляемый с помощью выражения (7).

Если предложенное время решения задачи удовлетворяет пользователя, то

агент AZ_l отправляет всем агентам, включенным в сообщество R_l, команду

на выполнение операций.

Формализуем алгоритм, соответствующий описанному выше процессу:

Алгоритм 1

1. j = 1; G^jl (Q^jl, X^jl ) = G_l(Q_l, X_l); R_l = ∅.

2. В графе G^jl (Q^jl , X^jl ) выделяется наиболее трудоемкая нить H_j =

∑

=< q^j1,... ,q^jk >, для которой значение V_j =

v^ji максимально, где v^ji тру-

i=1

доемкость операции O^ji, приписанной вершине q^ji (i = 1, . . . , k).

3. m = 1; H^mj = H_j; t^mн = t_тек.

4. Нить H^mj выставляется агентом AZ_l на ДО для исполнения.

5. r = 1; p = 0; E_p = ∞.

6. Агент AZ_l получает ¾предложение¿ от агента AR_r об исполнении под-

нити H^mjr =< q^j1, . . . , q^jb > ⊆H^mj (b ≤ k), а также моменты времени t^mнr начала

и t^mкr завершения ее исполнения.

^b v^ji

7. Если E_r =^m=1t_кr-tmн ≥Ep,гдеvi трудоемкостьвершиныqi (i=1,...,b),

то перейти к 9, иначе

8. E_p = E_r; p = r.

9. r = r + 1; если r ≤ N, то перейти к 6, иначе

10. Агент AR_p включается в сообщество R_l по выполнению задачи Z_l и

за ним закрепляется выполнение нити H^mjp. В графе G_l(Q_l, X_l) вершинам

нити H^mjp приписывается номер агента AR_p, а также время их исполнения

∑

v_i

t^jf = t^mнp +

(f = 1, . . . , b).

S_p(O_i)

i=1

11. H^m+1j = H^mj/H^mjp; если H^m+1j = ∅, то перейти к 13, иначе

12. m = m + 1; t^mн = t^bf +db,b+1 ; перейти к 4._Y

13. Если j = 1 или t^jk ≤ t^j-1f-1, где t^к

момент времени завершения ни-

ти H_j; t^j-1b-1

момент времени исполнения вершины q^j-1b-1 нити H_j-1 =

=< q^j-11,... ,q^r-1 >, вершина q^j-1b которой инцидента конечной вершине q^jk

нити H_j, перейти к 15, иначе

14. В графе G_l(Q_l, X_l) вершинам q^j-1b, q^j-1b+1, . . . , q^r-1, нити H_j-1 приписыва-

ется новое плановое время их исполнения t^j-1i = t^j-1i + ΔT (i = b, b + 1, . . . , r),

где ΔT = t^jk - t^j-1b-1.

115

О корректировке времени исполнения вершин q^j-1b, . . . , q^r-1 нити H_j-1 со-

общается агенту AR_c, за которым закреплено их исполнение.

15. G^j+1l(Q^j+1l, X^j+1l) = G^jl (Q^jl , X^jl )/H_j , если G^j+1l(Q^j+1l, X^j+1l) = ∅, то пе-

рейти к 17, иначе

16. j = j + 1, перейти к 2.

17. Отправить пользователю уведомление о расчетном времени t^kl =

= t_k + dk,k+1Ypрешения, где tkмомент времени исполнения конечной верши-

ны q_k графа G_l(Q_l, X_l), d_k,k+1 объем результирующих данных, приписан-

ных дуге, исходящей из конечной вершины q_k; Y_p пропускная способность

канала связи ресурса R_p, за которым закреплено выполнение вершины q_k.

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

задачи Z_l агент AZ_l отправляет всем сообществам R_l команду на исполнение

их операций.

19. Если от агента AR_p ⊆ R_l поступило сообщение о завершении исполне-

ния закрепленной за ним нити H^mjp =< q^j1, . . . , q^jb >, то агент AZ_l сравнивает

планируемый момент времени t^к завершения данной нити, определяемый как

время исполнения, приписанное конечной вершине

t^к = t^jb +db,b+1Yp(гдеtb

q^1b ∈ H^mip; d^jb,b+1

объем данных, приписанный исходящей дуге нити H^mip), с

текущим временем t_тек. Если t_тек > t^к, то пользователю сообщается о задерж-

ке времени решения его задачи Z_l на величину Δt = t_тек - t^к, а планируемое

время исполнения всех последующих вершин графа G_l(Q_l, X_l) увеличивается

на величину Δt.

20. Если конечная вершина q^jb нити H^mjp является конечной вершиной q_k

графа G_l(Q_l, X_l), то пользователю направляется сообщение о завершении ре-

шения его задачи и результаты ее решения.

21. Задача Z_l помечается на ДО как решенная.

5. Алгоритм работы агента вычислительного ресурса

при мультиагентном диспетчировании ресурсов

Основной целью работы агента вычислительного ресурса AR_p является

поиск задач для загрузки ¾своего¿ ресурса R_p полезной работой. Для этого

он периодически опрашивает ДО и в случае обнаружения новой нити H^mj, вы-

ставленной на исполнение агентом AZ_l задачи Z_l, делает попытку включения

в состав сообщества R_l по его выполнению. Для этого агент AR_p выделяет

в нити H^mj =< q^j1, . . . , q^jk > поднить H^mjp =< q^j1, . . . , q^jb > (b ≤ k) подзада-

чи, приписанные вершины которой входят в множество O_p, т.е. в множество

подзадач, выполняемых ресурсом R_p (см. рис. 4).

Агент AR_p определяет момент времени t^mнp, когда он может приступить

к исполнению поднити H^mjp, т.е. когда он освободится от исполнения ранее

закрепленных за ним операций, а также момент времени t^mкp окончания ис-

полнения поднити H^mjp, определяемый согласно выражению (2).

116

Выделенная таким образом поднить H^mjp направляется агенту AZ_l зада-

чи Z_l в качестве ¾предложения¿ агента AR_p по участию в сообществе R_l

по выполнению задачи Z_l. Если ¾предложение¿ агента AR_p наилучшее среди

всех поступивших, т.е. значение E_p, определяемое с помощью выражения (5),

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

нити H^mjp за ним.

Как только наступает запланированный момент t^mнp начала исполнения ни-

ти H^mjp, агент AR_p осуществляет ее выполнение (см. рис. 7). Перед тем, как

перейти к очередной подзадаче O^ji, приписанной вершине q^ji (i = 1, . . . , b) ни-

ти H^mjp, агент AR_p проверяет наличие требуемых для ее исполнения исходных

данных. Если какие-либо исходные данные еще не поступили, то агент AR_p

переходит в режим ожидания. Как только все исходные данные, необходи-

мые для решения подзадачи O^ji, поступают, агент AR_p инициирует решение

подзадачи O^ji с помощью ¾своего¿ ресурса R_p. После выполнения всех подза-

дач, приписанных вершинам нити H^mjp, агент AR_p сообщает агенту задачи Z_l

о завершении исполнения нити H^mjp.

Формализуем алгоритм, соответствующий описанному выше процессу:

Алгоритм 2

1. Агент AR_p опрашивает ДО в поисках работы для ¾своего¿ ресурса R_p.

2. Если агент AR_p обнаружил на ДО выставленную на исполнение агентом

AZ_l нить H^mj =< q^j1, . . . , q^jk > задачи Z_l, то он выделяет в нити H^mj поднить

H^mjp =< q^j1,... ,q^jb > (b ≤ k), вершины которой удовлетворяют условию O^ji ⊆

⊆ O_p (j = 1,...,b), где O^ji подзадачи, приписанная вершине q^ji нити H^mjp.

3. Агент AR_p рассчитывает моменты времени t^mнp, когда он может присту-

пить к исполнению нити H^mj, и t^mкp завершения нити как

∑

d^jb,b+1

v^ji

t^mкp = t^mнp +

S_p(O_i)

Y_p

i=1

4. Полученные значения направляются агенту AZ_l.

5. Если агент AR_p получает от агента AZ_l подтверждение о его включе-

нии в сообщество R_l, то он в момент времени t^mнp приступает к выполнению

вершин нити H^mjp =< q^j1, . . . , q^jb >.

6. Введем индекс i = 1.

7. Агент AR_p проверяет наличие всех исходных данных, необходимых для

решения подзадачи O^ji , приписанных вершине q^ji ∈ H^mjp. Если исходные дан-

ные еще не поступили, агент AR_p переходит в режим ожидания.

8. Как только все необходимые исходные данные поступили, агент AR_p

решает подзадачу O^ji с помощью ¾своего¿ ресурса R_p.

9. i = i + 1, если i < b, то перейти к 7, иначе

117

10. Агент AR_p сообщает агенту задачи Z_l о завершении выполнения под-

задач нити H^mjp.

11. Переход к 1.

6. Исследование эффективности предложенных метода

и алгоритмов

Для проведения экспериментальных исследований предложенных в статье

метода и алгоритмов была разработана распределенная программная модель

ОВС с мультиагентным диспетчером, состоящая из программных агентов ре-

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

министратора.

Интерфейс визуальной оболочки пользователя представлен на рис. 8.

С целью развертывания разработанной распределенной программной мо-

дели ОВС с мультиагентным диспетчером был собран экспериментальный

стенд, состоящий из 10 вычислительных модулей, включающих в себя от 1

до 16 физических процессорных ядер, объединенных общей сетью с пропуск-

ной способностью до 1000 мегабит в секунду.

Рис. 8. Визуальная оболочка пользователя.

118

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

мультиагентного диспетчера ОВС при решении поступающих задач потре-

бовалось провести исследование работы ОВС в различных режимах работы.

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

сложную систему, для полноценного исследования такой системы необходи-

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

работы ОВС оценивалась с применением критерия Y отношения суммар-

ного времени решения всех задач множества Z с применением предложенных

в настоящей статье алгоритмов к суммарному времени решения всех задач

множества Z с применением распределения, полученного с помощью алгорит-

мов распределения задач, предложенных в [16], выраженного в процентах.

Чем меньше будет значение критерия Y, полученного при исследовании, тем

эффективнее работают предложенные алгоритмы.

Значение критерия Y будет в большой степени зависеть от таких пара-

метров ОВС как: количество вычислительных ресурсов (ВР) в ОВС; про-

изводительность ВР; пропускная способность канала связи ВР с облачной

инфраструктурой; частота появления новых пользовательских задач на ДО;

количество пользовательских задач, направленных в ОВС; количество под-

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

объемы данных, передаваемых между подзадачами.

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

тиагентного диспетчирования ОВС, необходимо оценить значение крите-

рия Y для всевозможных комбинаций перечисленных выше параметров. Од-

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

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

ло их комбинаций будет ограниченным. Поэтому была разработана методика

проведения экспериментов, позволяющая сократить общее количество экспе-

риментов, необходимое для оценки критериев и эффективности работы пред-

ложенных алгоритмов, без существенного снижения их достоверности [24].

При этом были предложены следующие интервалы изменения параметров

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

альным условиям, было решено ввести 20%-ное значение возможной погреш-

ности параметров): параметр P1 количество вычислительных ресурсов в

ОВС (10, 100, 500, 1000); параметр P2 количество решаемых в ОВС поль-

зовательских задач (10 (малое), 50 (среднее), 100 (большое)); параметр S1

производительность ресурсов ОВС (низкая (-)

10, высокая (+)

100); па-

раметр S2 пропускная способность каналов связи между ресурсами ОВС

(низкая (-)

10, высокая (+)

100); параметр S3 трудоемкость поль-

зовательских задач (низкая (-)

10, высокая (+)

100); параметр S4

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

10, вы-

сокая (+)

100); параметр T1 - количество подзадач в задаче (от 5 до 25).

Разбиение экспериментов было предложено реализовать следующим образом.

Комбинации параметров Р1 и Р2 определяют серию экспериментов. В рам-

ках каждой из серий проводится по 16 экспериментов (один эксперимент для

119

каждой из комбинаций параметров S1, S2, S3 и S4), каждый из экспериментов

проводится по три раза с различными значениями параметра Т1.

Наименьшее значение 14% критерия Y было получено при P1 = 50, P2 =

= 1000, S1 = 10, S2 = 10, S3 = 100, S4 = 10, что подтверждает высокую эф-

фективность разработанных алгоритмов для небольших ОВС с высокой за-

грузкой. Наиболее высокое значение 84% критерия Y было получено при

P1 = 1000, P2 = 10, S1 = 10, S2 = 100, S3 = 100, S4 = 100, что соответству-

ет слабо загруженной задачами ОВС, содержащей большое количество вы-

числительных ресурсов, являющейся наименее подходящей для примене-

ния предложенных в статье эвристических метода и алгоритмов. Итоги

всех проведенных экспериментов показывают, что среднее значение крите-

рия Y составило 53%. Это позволяет сделать вывод, что в общем виде даже

при большом количестве ресурсов в ОВС предложенные в настоящей ста-

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

множества Z.

7. Заключение

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

лагаемого мультиагентного метода диспетчирования ресурсов в ОВС явля-

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

лительным возможностям гетерогенных ресурсов, входящих в ее состав. По

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

лачной среды в данном случае упрощаются требования к служебным серве-

рам (доскам объявлений), что позволяет существенно снизить стоимость об-

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

среды.

Предложенные в статье метод и алгоритмы позволяют повысить эффек-

тивность и гибкость использования вычислительного оборудования в ОВС за

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

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

буют от пользователей дополнительной информации о необходимом времени

решения задач.

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

1. Alam T. Cloud Computing and its role in the Information Technology // IAIC Trans-

actions on Sustainable Digital Innovation (ITSDI). 2020. Vol. 1. No. 2. P. 108-115.

2. Батаев А.В. Оценка мирового рынка облачных технологий в финансовой сфе-

ре // Вектор экономики. 2019. № 6. С. 91-91.

3. Караев А.В., Емельянов Д.О., Барановская Т.П. Актуальность и особенности

внедрения ИТ-сервисов с применением облачных технологий // Информацион-

ное общество: современное состояние и перспективы развития. 2020. С. 387-390.

120

Fink A., Homberger J. An ant-based coordination mechanism for resource-

constrained project scheduling with multiple agents and cash flow objectives //

Flexible Services and Manufacturing Journal. 2013. Vol. 25. No. 1. P. 94-121.

Verma A., Kaushal S. A hybrid multi-objective Particle Swarm Optimization for

scientific workflow scheduling // Parallel Comput. 2017. Vol. 62. P. 1-19.

Yuan X., Liu J., Wimmers M.O. A multi-agent genetic algorithm with variable

neighborhood search for resource investment project scheduling problems // IEEE

Congress on Evolutionary Computation (CEC). IEEE, 2015. P. 23-30.

Bertsekas D.P. Feature-based aggregation and deep reinforcement learning: A survey

and some new implementations // IEEE/CAA J. Autom. Sin. 2019. Vol. 6. No. 1.

P. 1-31.

Habibi F., Barzinpour F., Sadjadi S. Resource-constrained project scheduling prob-

lem: review of past and recent developments // J. Project Management.

2018.

Vol. 3. No. 2. P. 55-88.

Mao H., Alizadeh M., Menache I., Kandula S. Resource management with deep

reinforcement learning // HotNets 2016 - Proceedings of the 15th ACM Workshop

on Hot Topics in Networks. 2016. P. 50-56.

10.

Xue L., Sun C., Wunsch D., et al. An adaptive strategy via reinforcement learning

for the prisoner’s dilemma game // IEEE/CAA J. Autom. Sin. 2018. V. 5. No. 1.

P. 301-310.

11.

Zhan Y., Ammar H.B., Taylor M.E. Theoretically-grounded policy advice from

multiple teachers in reinforcement learning settings with applications to negative

transfer // IJCAI International Joint Conference on Artificial Intelligence.

2016.

Vol. 2016-Janua. P. 2315-2321.

12.

Wang H., Huang T., Liao X., et al. Reinforcement Learning for Constrained Energy

Trading Games with Incomplete Information // IEEE Trans. Cybern. 2017. Vol. 47.

No. 10. P. 3404-3416.

13.

Zheng L., Yang J., Cai H., et al. Magent: A many-agent reinforcement learning

platform for artificial collective intelligence // Proceedings of the AAAI Conference

on Artificial Intelligence. 2018. Vol. 32. No. 1. P. 8222-8223.

14.

Lowe R., Wu Y.I., Tamar A., et al. Multi-agent actor-critic for mixed cooperative-

competitive environments // Advances in neural information processing systems.

2017. Vol. 30. P. 1-12.

15.

Каляев И.А., Каляев А.И., Коровин Я.С. Алгоритм мультиагентного диспетчи-

рования ресурсов в гетерогенной облачной среде // Вычислительные техноло-

гии. 2016. Т. 21. № 5. С. 38-53.

16.

Каляев А.И., Каляев И.А. Метод мультиагентного диспетчирования ресурсов

в облачных вычислительных средах // Известия Российской академии наук.

Теория и системы управления. 2016. № 2. С. 51-57.

17.

Каляев И.А., Капустян С.Г. Метод мультиагентного управления ¾умным¿

интернет-производством // Робототехника и техническая кибернетика. 2018.

№ 1. С. 34-48.

18.

Аблялимов О.С. О решении задачи оптимизации методом динамического про-

граммирования // Universum: технические науки. 2020. № 9-1(78). С. 16-18.

19.

Канцедал С.А., Костикова М.В. Динамическое программирование для задачи

коммивояжера //Автоматизированные системы управления и приборы автома-

тики. 2014. № 166. С. 15-20.

121

20. Колемаев В.А. Математическая экономика. М.: ЮНИТИ - ДАНА, 2002.

21. Kalyaev А.I., Korovin Y.S. Adaptive Multiagent Organization of the Distributed

Computations / AASRi Procedia. 2014. Vol. 6. P. 49-58.

(URL: http://dx.doi.org/10.1016/j.aasri.2014.05.008)

22. INTRODUCTION TO ALGORITHMS, Second Edition Thomas H. Cormen,

Charles E Leiserson, Ronald L. Rivest, Clifford Stein. (URL: http://www.mif.vu.lt/

-valdas/ALGORITMAI/LITERATURA/Cormen/Cormen.pdf).

23. Рейнгольд О., Нвергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и

практика. М.: Мир, 1980.

24. Каляев А.И., Хисамутдинов М.В. Программа и методики экспериментальных

исследований методов и алгоритмов работы распределенной вычислительной

системы с помощью программной модели // Наука и современность: сбор-

ник материалов V Международной научно-практической конференции. 2016.

С. 44-45.

Статья представлена к публикации членом редколлегии А.А. Галяевым.

Поступила в редакцию 15.10.2021

После доработки 14.02.2022

Принята к публикации 28.04.2022

122