Auction model in the problem of active programmes management interacting in the form of P2P model

Full Text

Введение. Современные тенденции в области решения проблем управления позволяют рассматривать разнообразные модели организаций [1], например, в последнее время активно применяются матричные структуры управления предприятиями, в которых решения принимаются совместно по результатам согласованного взаимодействия персонала. При построении интегрированной информационной среды такого предприятия с целью автоматизации управления и поддержки принятия решений также необходимо создавать сетевые архитектуры программных комплексов. В частности, широко распространена концепция построения распределенной гетерогенной интегрированной информационной среды с топологией P2P-сети [2], содержащей активные программные компоненты, способные обмениваться сообщениями по принципу «каждый с каждым» [3]. При решении теоретических проблем построения такой среды часто используют принцип аналогии с живыми системами [4], позволяющий рассматривать сообщество ее пользователей и активных программных компонентов как эволюционирующую сложную систему. На практике удается успешно применять эти концепции, например, при разработке и внедрении мультиагентных технологий [5], однако при этом часто возникают проблемы организации управления подобными системами, связанные с невозможностью применять классические методы оптимизации. Одним из перспективных подходов к построению системы косвенного информационного управления является применение методов и средств управления согласованным взаимодействием в многоакторной интегрированной информационной среде [6], направленных на обеспечение ритмичности событий по обмену сообщениями между участниками процесса взаимодействия, в качестве которых могут выступать как сотрудники предприятия, так и программные агенты. В данной статье предлагается применить этот подход при управлении взаимодействием активных программных компонентов в P2P-сети по модели аукциона, что может быть полезным разработчикам интеллектуальных автоматизированных систем планирования ресурсов в различных предметных областях. Применение модели аукциона в задачах управления взаимодействием по распределению ресурсов. Рассмотрим актуальную задачу автоматизации распределения мобильных ресурсов в режиме реального времени на примере интеллектуальной системы планирования в транспортной логистике, являющейся распространенным примером реализации многоакторной интегрированной информационной среды. В рамках такой задачи необходимо планировать поступающие в реальном времени заказы на доставку грузов на транспортные средства, обеспечивая выполнение заказов в срок (с минимальным отклонением от требуемого времени доставки) при максимальной загрузке ресурсов (минимум суммарного пустого пробега). При решении такой задачи бывает полезным вовлечение водителей в процесс принятия решений, что позволяет учитывать специфические критерии назначения каждого заказа. В ответ на такой индивидуальный подход диспетчер рассчитывает на повышение качества выполнения заказов, что сказывается на общем уровне сервиса. Таким образом, диспетчер как бы «продает» заказы водителям, стимулируя лояльность по отношению к компании и повышение качества выполнения работы. Технически реализовать такое взаимодействие можно с помощью современных информационно-коммуникационных технологий, однако при автоматизированном решении этой задачи в случае, когда предпочтения водителей известны, переговоры о назначении заказа можно перенести в виртуальную среду, образованную P2P-сетью активных программ, моделирующих поведение акторов – лиц, принимающих решения. В качестве одной из моделей такого распределения рассмотрим модель аукциона, в котором каждый заказ выступает в качестве лота, а водители – в качестве участников аукциона. Стратегической целью проведения такого аукциона является дополнительная «загрузка» ресурсов, при этом могут увеличиваться риски невыполнения заказов, а итоговое расписание в общем случае не будет консистентным. Аукционом будем называть публичную продажу одного лота по заранее установленным правилам, определяемым центром перед началом аукциона. Роль диспетчера играет центр, который в разные интервалы времени выставляет некоторые ресурсы (лоты), интересные акторам в разной степени. Целью центра является обеспечение максимального суммарного выигрыша от реализации всех лотов за некоторый интервал времени. Победителем аукциона становится актор, выигравший аукцион в соответствии с его правилами. Целью актора является приобретение максимального количества лотов наибольшего интереса при минимальных затратах. При проведении торгов центр может выбирать различные формы аукциона (в зависимости от решаемой задачи). Например, аукцион может быть открытым, когда участники видят ставки всех своих оппонентов, или закрытым, во время проведения которого участники не видят ставки своих оппонентов и не могут изменять свои ставки. При проведении закрытого аукциона заявки подаются «в конвертах» – каждый участник напрямую, не разглашая публично, сообщает центру размер своей ставки. Также выделяют английский, голландский и скандинавский аукционы. Английский аукцион является самым распространенным и предусматривает пошаговое увеличение цены покупателями до того момента, пока не останется единственный победитель. В голландском аукционе торг начинается с максимально высокой цены и ведется с ее понижением, пока не найдется покупатель, согласный купить по объявленной цене. В скандинавском аукционе торги ведутся с фиксированным заранее определенным шагом повышения цены, возможность сделать ставку является платной, а победителем признается участник, сделавший последнюю ставку до момента окончания торгов. Для эффективного решения поставленной задачи планирования транспортных ресурсов необходимо аукцион проводить в несколько итераций, или этапов, на каждом из которых центр будет выстраивать взаимодействие с участниками аукциона по схеме P2P, сообщая им текущую цену, предложившего ее ожидаемого победителя и интервал времени, в течение которого будут собираться контрпредложения. На каждом этапе может быть выбрана своя модель аукциона, однако для простоты определения правил взаимодействия целесообразно выбрать одну из наиболее простых моделей, например в каждую итерацию проводить закрытый английский аукцион первой цены. В этом случае на каждом этапе каждый участник не видит ставки своих оппонентов и не изменяет свою ставку, но по завершении этапа может повысить цену и инициировать новую итерацию. Аукцион завершается в случае, если контрпредложения перестают поступать. В таком аукционе центр может управлять лишь временными характеристиками процесса сбора заявок аналогично тому, как при проведении реального аукциона ведущий увеличивает паузы между первым, вторым и третьим ударами молотка. Такое поведение в реальности провоцирует участников аукциона повышать ставки наперегонки, а в многоакторной среде стимулирует информационное взаимодействие. Таким образом, предлагается: 1) при решении задач организации эффективного распределения ресурсов в распределенной многоакторной среде проводить аукцион в несколько этапов / итераций; 2) в качестве основного механизма управления распределением ресурсов в условиях применения выбранной модели аукциона использовать варьирование интервалов времени торгов по каждому лоту. Модель итерационного аукциона. Рассмотрим единичный лот с базовой ценой , определяемой в начале торгов, который имеет для каждого актора ценность , где – общее количество акторов, участвующих в аукционе. На каждой итерации актор может предложить стоимость , где – номер итерации. Обозначим – длительность каждой итерации. Итерации в данном случае не определяются жестко: будем считать, что каждая рассылка предложений от центра начинает новую итерацию. По результатам каждой итерации центром объявляется решение (одному или нескольким акторам) о назначении новой стоимости лота , которая выбирается равной максимальной среди всех предложенных либо увеличенной на некоторую случайную величину. Аукцион завершается по истечении времени после своего начала: . (1) На каждой итерации центр взаимодействует с акторами по принципу P2P: в каждом сообщении от центра содержится вариант с новой или итоговой стоимостью лота на момент времени : . (2) В ответ актор может выслать новое предложение: , где . (3) Время обдумывания ставки актором можно определить как , . Цели центра по проведению серии из аукционов определим как . (4) Цель каждого актора определим следующим образом: , (5) где – ступенчатая функция Хэвисайда. Это означает, что для актора важно обеспечить максимальное удовлетворение от приобретения лотов минимальными средствами; при этом время, за которое этот результат достигается, существенной роли не играет. Для достижения своей цели центр может управлять длительностью итераций и количеством вовлеченных акторов (то есть определять, кому и когда рассылать предложения ). Для получения максимальной цены лота от акторов центру необходимо организовать соревновательный процесс между акторами, для чего необходимо разработать план по рассылке предложений. Каждый актор также может управлять размером и временем предложения, обеспечивая, таким образом, интерес к себе со стороны центра. С другой стороны, для обеспечения лояльности и равновесных состояний центру может быть выгодно сообщать акторам свой план. В этом случае можно исследовать зависимости между планом центра и стратегиями игроков. При практической реализации описанной выше схемы в задачах автоматизации управления распределением ресурсов может быть полезной также модель распродажи. В настоящее время во многих магазинах существует практика проведения распродаж в несколько этапов в соответствии с моделью голландского аукциона. На каждом последующем этапе стоимость товара уменьшается на определенное количество процентов. Таким образом, с одной стороны магазин пытается как можно быстрее избавиться от застаревшего товара, обновив прилавки и при этом получив максимальную прибыль, с другой стороны – покупатели хотят купить товар по меньшей стоимости. Покупатель не может быть уверенным, что нужный ему товар (его размера, цвета и т. д.) не будет куплен кем-то другим в ближайшее время и что данный этап распродажи не является заключительным. Также магазин может вовсе не понижать дальше цену на определенные товары, тем самым сделав выжидательную тактику покупателя бессмысленной. Таким образом, решается задача проведения множественных итерационных аукционов с единым центром и неопределенным количеством акторов. Существенным упрощением по отношению к рассмотренной выше модели аукциона является отсутствие возможности акторов влиять на стоимость товара, указывая свои предложения. В этом случае время решения становится еще более определяющим фактором: в случае, когда акторы относительно долго не проявляют интереса, центр вынужден сильнее снижать цену на товар, чтобы его стали покупать. Результаты экспериментального исследования. Целью проведенного имитационного эксперимента являлось определение возможности увеличения финальной стоимости лота за счет управления временем итерации. Было проведено два эксперимента в реальном времени с одинаковой длительностью розыгрыша лота, для чего на платформе J2EE была построена программная модель активных компонентов, моделирующая взаимодействие в многоакторной интегрированной информационной среде по схеме P2P. Во время розыгрыша каждого лота центр давал время, через которое акторы должны были сделать новые ставки. Среди предложенных ставок по итогам итерации выбиралась максимальная, относительно которой акторы снова делали ставки. В условиях, когда ставка будет сделана в любом случае, ставки делали все акторы. В игре принимали участие два актора (с увеличением количества акторов цена лота будет возрастать). Величина ставки каждого актора определялась относительно начальной стоимости лота путем прибавления случайной величины, имеющей усеченный нормальный закон распределения. В условиях решаемой задачи процедура принятия решений центром может быть формализована следующим образом. При формировании плана по рассылке предложений центр может уменьшать время последующей итерации пропорционально приросту уровня ставки (чем больше была сделана ставка, тем быстрее центр проводил итерации): . (6) В первом случае (без управления) длительность итераций была одинакова и с учетом реального времени в 41 % лотов было проведено 3 итерации, а в 59 % лотов – 4 итерации (рис. 1). Во втором случае (рис. 2) центр получил возможность управления длительностью итерации (рис. 3). При этом в обоих случаях ни центр, ни игроки не знали времени, отведенного на розыгрыш лота. В результате в среднем за время розыгрыша лота успевало проходить от 5 до 15 итераций. Итоги экспериментов показали, что за счет того, что центр успевает провести больше итераций путем изменения времени каждой итерации, удается увеличить итоговую стоимость лота. Однако анализ разницы стоимостей лотов показывает, что существуют случаи, когда стоимость лота, полученная в результате торгов без управления, была выше. Рис. 1. Ставки по итерациям без управления по времени Рис. 2. Ставки по итерациям с управлением по времени Рис. 3. Количество итераций в эксперименте с управлением по времени Заключение. Проведенные исследования показали возможность применения модели аукциона при решении задач управления распределением ресурсов предприятия в интегрированной информационной среде с топологией P2P-сети. Применение данной модели может быть полезно при построении интеллектуальных систем планирования в транспортной и производственной логистике, а также при решении других проблем поддержки принятия решений в режиме реального времени.

About the authors

Anton V Ivaschenko

S.P. Korolyov Samara State Aerospace University

Associate Professor 34, Moskovskoye sh., Samara, 443086

Andrey M Lednev

Samara State Technical University

Email: andrey.lednev@gmail.com
Postgraduate Student 244, Molodogvardeyskaya st., Samara, 443100

References

Supplementary files