Software & Systems

В мультиагентных моделях [1] одним из типов актуальных задач является составление планов выполнения работ агентами и коалициями. Под планом выполнения работ будем понимать перечень намеченных к выполнению работ или мероприятий с определенными последовательностью, объемами и сроками выполнения [2]. Поскольку все факторы, влияющие на планы выполнения работ, практически невозможно учесть, а интересы агентов часто различны, задача составления планов является многокритериальной, с нечетким множеством факторов. Решаются такие задачи, как правило, с помощью теории составления расписаний (ТСР) в два этапа [3]: получение плана путем использования определенного метода на основе исходных условий выполнения работ и формализуемых ограничений и его последующая доработка с целью максимального учета неформализуемых ограничений. Для разработки алгоритма составления планов выполнения работ необходимо формальное описание планов действий агентов и коалиций в коалиционной модели мультиагентного процесса преобразования ресурсов (МППР) [1].

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

В качестве основы алгоритма решения задачи составления планов выполнения работ агентами можно использовать следующие основные эвристические методы ТСР [3]: метод ветвей и границ, алгоритм Литтла, метод случайного поиска. Вследствие ориентации на последующее использование выбранного метода ТСР для решения задач в мультиагентной системе поддержки принятия решений (МСППР) одним из важных критериев метода должна быть его алгоритмическая простота. Среди наиболее простых эвристических методов ТСР, дающих достаточно точные решения, можно выделить метод случайного поиска.

Общее описание прикладной задачи планирования

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

1.     Инициация работ – выявление пожара. Происходят определение агента A1 – координатора работ и выделение ресурсов {Res1, …, Resn} и средств {Mech1, …, Mechm} из общего резерва (Pool) под его координацию. Агент A1 планирует использование собственных ресурсов и средств по определенному алгоритму. Каждый агент Аi должен выделять ресурсы {Res1, …, Resn} и средства {Mech1, …, Mechm} на устранение лесного пожара путем проведения моделирования, исходя из следующих целей:

-      наискорейшая ликвидация лесного пожара: t (Wi)→min;

-      минимизация финансовых затрат (то есть максимизация прибыли агента): S→max;

-      необходимость резервирования максимального количества ресурсов и средств в связи с ненулевой вероятностью возникновения другого пожара: N→max.

2.     Выявление нового пожара. В процессе устранения первого пожара существует вероятность выявления второго в другом месте. При этом в МСППР происходит определение агента A2, который планирует возможность выполнения работы W2 в указанный срок t2 и с имеющимися резервными ресурсами {ResА11, …, ResA1t} и средствами {MechА11, …, MechА1v}. При отсутствии необходимых ресурсов или средств агенту А2 необходимо организовать взаимодействие с другими агентами {Аn, …, Аm} в МАС, в результате которого возможно создание коалиции Kp для совместного выполнения работы W2. При этом прибыль SAj агента Aj определяется соразмерно количеству его ресурсов {ResАj1, …, ResАjt}, участвующих в выполнении работы Wi коалицией Kp. Далее возможно возникновение третьего пожара и т.д.

3.     Возникновение конфликтов. В случае нехватки ресурсов или средств возникает необходимость переговоров (в приведенном примере – агента A2 с агентом A1) на основе выбранных ими стратегий взаимодействий {StrA1, StrA2}. При этом в зависимости от стратегий может потребоваться проведение аукциона (основанного на величине последствий от пожара, Pos). При малой величине последствий часто целесообразно оставить ресурсы и средства в резерве, при большой возможно привлечение дополнительных ресурсов.

Формализация задачи планирования выполнения работ

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

1.     Формирование списков: агентов {A1, …, Aт}; работ {W1, …, Wf}; типов ресурсов {1, …, t}; ресурсов {Res11, …, Resti}; типов средств {1, …, v}; средств {Mech11, …, Mechvj}.

2.     Определение условий выполнения работ {W1, …, Wf}. Взаимосвязи списков из п. 1 определяют следующие условия выполнения работ:

-      агент Ai может управлять выполнением только одной работы Wi;

-      агенты {A1, …, Aт} могут использовать ресурсы любого типа {1, …, t} и средства любого типа {1, …, v} для выполнения работы Wi;

-      агенты {A1, …, Aт} не могут использовать средство Mechk без ресурса Resk для выполнения работы Wi;

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

-      в зависимости от типа {1, …, t} ресурсы могут быть привязаны только к одной работе Wi до ее окончания либо переходить с одной работы Wi на другую Wj;

-      средства всех типов {1, …, v} могут переходить с одной работы Wi на другую Wj.

Условия выполнения работ, не определяющие взаимосвязи списков из п. 1:

-      минимальный шаг выполнения работы Wi – 1 день;

-      ресурсы {Res1, …, Rest} и средства {Mech1, …, Mecht} не могут быть захвачены агентом Aj во время их использования другим агентом Ai (нет агентов, имеющих абсолютный приоритет по захвату ресурсов и средств);

-      для выполнения работы Wi захват средств {Mech1, …, Mecht} не является необходимым;

-      весовой коэффициент Vi необходимости выполнения i-го формализуемого ограничения Ri плана выполнения работ PWi может принимать следующие значения: Vi={1, 2, …, 100};

-      весовой коэффициент Qi необходимости выполнения i-го неформализуемого ограничения Li плана выполнения работ PWi может принимать следующие значения: Qi={1, 2, …, 10}.

Начальное значение суммарного коэффициента несоответствий i-го плана выполнения работ Ki принимается равным сумме всех коэффициентов несоответствия формализуемых ограничений {V1, …, Vn} и неформализуемых ограничений {Q1, …, Qm}:

Ki=                                                  (1)

где N – число формализуемых ограничений, а M – неформализуемых.

3.     Определение формализуемых {R1, …, Rn} и неформализуемых {L1, …, Lm} ограничений; их сообразных весовых коэффициентов несоответствия {V1, …, Vn} и {Q1, …, Qm} (для определения важности).

К формализуемым ограничениям {R1, …, Rn} относятся следующие:

-      R1 (Vi=100): каждая работа должна быть выполнена вовремя (фактическое время выполнения работы T не может быть больше расчетного максимального времени TO, T≤TO);

-      R2 (Vi=10): не должно быть окон в работе ресурсов (окна в работе средств допустимы); число окон в работе ресурсов определяется как сумма свободных ресурсов по всем рабочим дням и рассчитывается по следующей формуле:

R2=                                                    (2)

где D – количество дней, на которые составляется план выполнения работ PWi (текущий день, dÎ(1, D)); wi – параметр незанятости ресурса, wi={1, 0}.

К неформализуемым (или сложноформализуемым ограничениям) {L1, …, Lm} относятся следующие:

-      L1 (Q1=4): загрузка ресурсов одного типа должна быть равномерной с учетом коэффициентов скорости работы, зависящих от дня недели, личных событий, настроения и т.д.;

-      L2 (Q2=1): необходимо техническое обучение ресурсов всех типов, направленное на повышение скорости выполнения работ (с периодичностью и продолжительностью, связанными с типом ресурса, его квалификацией, временем работы, текущей загруженностью и т. д.);

-      L3 (Q3=2): необходимо техническое обслуживание средств (с периодичностью и продолжительностью, связанными с типом средства, его сроком службы, временем эксплуатации и т.д.).

4.     Загрузка исходных данных по работам {W1, …, Wi}:

-      дата возникновения пожара, Db;

-      крайняя дата завершения работ, De;

-      требуемый состав действий, {D1, …, Ds}.

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

Таблица 1

Исходные данные по работам

5.     Формирование параметров работ {W1, …, Wi}:

-      количество ресурсов типа 1, NRes1;

-      параметр привязанности ресурсов типа 1 только  к одной  работе  до  ее  окончания, PRes1= ={1, 0};

-      количество ресурсов типа 2, NRes2;

-      параметр привязанности ресурсов типа 2 только  к  одной  работе  до  ее  окончания,  PRes2= ={1, 0};

-      количество ресурсов типа n, NResn;

-      параметр привязанности ресурсов типа n только к одной работе до ее окончания, PRes3=   ={1, 0};

-      количество средств типа 1, NMech1;

-      количество средств типа 2, NMech2;

-      количество средств типа m, NMechm;

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

Так как каждая работа Wj состоит из действий {D1, …, Di}, состав и очередность которых определены в базе знаний мультиагентной системы (GKB): Wj=D1+D2+…+Dn, то для расчета макси-мального времени выполнения работы (см. табл. 2) используется формула

TO=t1+t2+…+tn,                                                       (3)

где ti – среднее время выполнения действия Di (из GKB).

Таблица 2

Пример расчета параметров работ

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

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

Описание алгоритма.

1.     Генерация случайного плана PWi выполнения работ {W1, …, Wi} (с использованием данных п. 2 и п. 3 данного алгоритма в случае не первого прогона) в виде таблицы используемых ресурсов {Res1, …, Rest} и средств {Mech1, …, Mecht}, в столбцах которой указываются дни проведения работ, а в строках – сами работы. Необходим ежедневный подсчет свободных ресурсов и средств.

Пример плана выполнения работ PWi представлен в таблице 3. В примере принято, что агенты-координаторы {A1, A2, A3, A4} управляют работами {W1, W2, W3, W4} соответственно. Все агенты могут координировать действия собственных ресурсов и средств; всего имеется: 4Res1 (сотрудники МЧС), 2Res2 (пожарные), 1Res3 (лесники), 1Mech1 (спецтехника МЧС), 1Mech2 (пожарные вертолеты). Каждая работа должна начинаться с Res1 и заканчиваться Res3; Res1 может использовать Mech1, а Res2 – Mech2.

Таблица 3

Пример плана распределения ресурсов и средств по работам

В данной таблице выполнение работ W1, W2, W3 начинается в 1-й день, работы W4 – в 3-й день. Крайний срок выполнения работы W1 – 4-й день, работы W2 – далее 5-го дня, работ W3 и W4 – 5-й день. Из таблицы видно, что работу W4 агент A4 не может выполнить с помощью своих ресурсов и средств.

2.     Оценка несоответствия неформализуемым ограничениям {R1, …, Rn}. Расчет суммарного коэффициента несоответствия формализуемым ограничениям Gx производится по следующей формуле: Gx=                                                         (4)

где х – текущий вариант плана выполнения работ; n – количество формализуемых ограничений; fi – число невыполнений i-го формализуемого ограничения; Vi – весовой коэффициент необходимости выполнения формализуемого ограничения Ri плана выполнения работ PWi.

Пример вычисления суммарного коэффициента несоответствия формализуемым ограничениям Gx (на основе данных из таблицы 3): G1=1*100+6*10= =160.

Оценка несоответствия неформализуемым ограничениям {L1, …, Lm} проводится при наличии экспертной подсистемы (ЭС), содержащей информацию по накопленному опыту работы и/или наиболее успешные примеры принятия решений в определенных ситуациях из других регионов РФ. Наличие и полнота данной ЭС не являются обязательными для работы алгоритма, ее цель – получение наилучшего решения путем максимально полного учета неформализуемых ограничений. При отсутствии ЭС – переход к п. 5; определя-    ем Kx=Gx.

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

Пример структуры ЭС.

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

Исходные данные: 1) стаж работы Res21 – 23 го­да, Res22 – 1 год, Res23 –7 лет; 2) возраст Res21 – 53 года, Res22 – 19 лет, Res23 – 39 лет; 3) сегодняшняя дата – 21.05.10; 4) завтра день рождения у Res23.

Информация для поддержки принятия решения: 1) наибольший коэффициент производительности у людей со стажем работы более 5 лет и в возрасте до 45 лет; 2) для послепраздничных дней необходимо учитывать снижение средней производительности ресурсов.

Результирующая интерпретация неформализуемого ограничения: на 22.05.10 (второй день в таблице 3) необходимо Res23 оставить в резерве.

С использованием результирующих интерпретаций неформализуемых ограничений рассчитаем суммарный коэффициент несоответствия неформализуемым ограничениям Hx по следующей фор­муле: Hx=                                                    (5)

где х – текущий вариант плана выполнения работ; m – количество неформализуемых ограничений;   di – число невыполнений i-го неформализуемого ограничения; Qi – весовой коэффициент необходимости выполнения i-го неформализуемого ограничения Li плана выполнения работ.

Пример вычисления суммарного коэффициента несоответствия неформализуемым ограничениям Hx (на основе данных из таблицы 3): H1=1*4=4.

3.     Вычисление суммарного коэффициента несоответствий Kx путем сложения суммарного     коэффициента несоответствия формализуемым ограничениям Gx и суммарного коэффициента несоответствия неформализуемым ограничениям Hx по следующей формуле: Kx=Gx+Hx.                         (6)

Пример: Kx=160+4=164.

4.     Выбор лучшего плана выполнения работ. Если суммарный коэффициент несоответствий     x-го плана выполнения работ Kx меньше соответствующего коэффициента несоответствий y-го плана выполнения работ Ky, ранее выбранного как лучший, Kх

Пример: K1=170, K2=164, K2

5.     Проверка истечения заранее определенного времени работы алгоритма Talg. Если текущее время t

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

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

Литература

1.     Зраенко А.С., Аксенов К.А., Ван Кай. Коалиционная модель мультиагентного процесса преобразования ресурсов // Науч.-технич. ведомости СПбГУ. СПб: Изд-во политехн. ун-та, 2009. № 5. С. 156–161.

2.     Чепасов В.И., Кулов С.К., Раимов Ф.Ф. Алгоритмическая и программная реализация задачи о расписании: учеб. пособие. Оренбург: Оренбург. гос. ун-т, 1999. 192 с.

3.     Шахбазян К.В., Тушкина Т.А. Обзор методов составления расписаний для многопроцессорных систем. Л.: Наука, 1975. С. 229–258.

4.     Береговых Ю.В., Васильев Б.А., Володин Н.А. Алгоритм составления расписания занятий // Искусств. интел. 2009. № 2. С. 50–56.