Game theory model of tasks distribution during peer-to-peer interaction between the programmers teams

Full Text

В настоящее время многие крупные корпорации переходят на матричную (сетевую) структуру управления. Задачи директивного назначения заданий исполнителям раскрыты в работах [1-3]. В то же время методы директивного управления становятся неэффективными в силу большой неопределенности в окружающей среде и в мотивах поведения исполнителей. В интегрированной информационной среде предприятий получают развитие модели Р2Р (peer-to-peer) взаимодействия [4]. В работе [5] рассмотрены методы управления проектными заданиями в матричной структуре на основе такого взаимодействия исполнителей (акторов), которые представляют собой группы разработчиков, не связанных иерархией подчинения. Также был развит подход к распределению проектных заданий на аутсорсинг с использованием аукционов между акторами Р2Р-сети [6, 7]. Однако механизм проведения таких аукционов при одноранговом взаимодействии раскрыт недостаточно. Выбор модели Рассмотрим процесс распределения и выполнения множества задач (программ) множеством акторов A1, A2, …, AN, каждый из которых в общем случае может представлять собой коллектив (команду) исполнителей - программистов. Все они связаны организационно и информационно одноранговым взаимодействием в Р2Р-сети. Задачи программных проектов можно достаточно легко объединить в группы сравнительно однородных заданий. Это специфика сущности программных проектов. Р2Р-сеть задается в виде тройки: где - множество акторов; - множество одноранговых связей; - способ организации однорангового взаимодействия акторов. Центр планирования и распределения задач (ЦРЗ) осуществляет начальное директивное распределение задач по акторам. Множество всех задач , где I - число задач. Каждой задаче программного проекта соответствует директивный срок выполнения и объем работ , который для программ можно характеризовать метрикой Холстеда [8, 9]. Основу метрики Холстеда составляют четыре измеряемых характеристики программы: - n1 - число уникальных операторов программы, включая символы-разделители, имена процедур и знаки операций (словарь операторов); - n2 - число уникальных операндов программы (словарь операндов); - N1 - общее число операторов в программе; - N2 - общее число операндов в программе. Опираясь на эти характеристики, М. Холстед ввел следующие оценки: а) словарь программы б) длину программы в) объем программы На рисунке представлена структура взаимодействия ЦРЗ и акторов. Поток задач передается акторам через информационно-коммуникационную среду, которая также используется для организации Р2Р-взаимодействия акторов этой сети. Распределение центром задач между акторами сети может реализовываться путем проведения аукциона (торгов) либо по ведомственным правилам компании, либо по регламенту законов 44-ФЗ и 223-ФЗ в случае госзакупок. Каждый актор может при определенных условиях отдать выполнение задачи другому актору путем проведения аукциона среди всех желающих команд. Условия объявления и проведения аукционов будут рассмотрены ниже. В результате в исходной Р2Р-сети могут возникать «виртуальные» команды акторов, которые участвуют в реализации различных программных проектов. Такие «виртуальные» команды могут пересекаться по составу акторов. Следует установить, какова главная цель такой команды. В работе [5] сформулирована и решена задача минимизации суммарных стоимостных затрат проектирования. Но программные проекты часто имеют короткие сроки выполнения, при этом существуют ограничения по календарным датам завершения. Характерный пример - разработка программного обеспечения для новых моделей микропроцессоров или гаджетов, которые анонсируются ежегодно с определенными датами выхода на рынок. При этом стоимость разработки программ на порядок ниже ожидаемого дохода от продажи оборудования и не является критичным фактором. Исходя из изложенного сформулируем задачу минимизации суммарных временных затрат на проектирование в Р2Р-сети потока задач, поступающих из ЦРЗ: (1) где - время выполнения задачи актором An . Структура взаимодействия ЦРЗ и акторов Достижение цели (1) в одноранговой сети акторов происходит путем динамического перераспределения задач, что позволяет наиболее эффективно использовать ресурсы акторов. Как отмечалось выше, для заданного потока задач могут образовываться (в том числе и путем самоорганизации) команды акторов. Каждый актор имеет свои интересы, предпочтения и возможности. В этом случае можно опираться на разработанные в [10, 11] механизмы формирования и управления командами. В данной статье предлагается подход к распределению заданий и дальнейшему аутсорсингу задач программных проектов, базирующийся на теоретико-игровых моделях. Выбор такой постановки обусловлен тем, что в программной инженерии весьма подробно и глубоко изучены механизмы проектирования программ и разработаны метрики процесса проектирования программных систем, что облегчает постановку и решение задачи теоретико-игрового моделирования. Учитывая, что в Р2Р-сети существуют взаимные знания акторов друг о друге и возможность обмена этими знаниями между акторами сети, будем использовать модель рефлексивных игр [12]. Постановка задачи Опишем формальную постановку задачи распределения заданий по исполнителям в Р2Р-сети. Каждый актор An имеет очередь qn задач, принятых к исполнению, но еще не запущенных в проектирование (см. рисунок). Пусть - максимально возможная производительность; - средняя текущая производительность выполнения задач актором An. Тогда время выполнения одной задачи этим актором равно , а средний объем задачи в потоке определяется как Среднее время выполнения задач актором An есть (2) где In - индексное множество всех задач, выполняемых актором An. Следующий вопрос: каково время пребывания задачи zi в очереди qn ? Будем предполагать, что задача из потока помещается в последнюю свободную ячейку заполняемой очереди актора. Выдача задач из очереди на исполнение актору происходит по дисциплине FIFO. Вывод задач из очереди для передачи другим акторам на аутсорсинг через аукцион происходит по дисциплине LIFO. Время пребывания задачи zi в очереди qn равно где Iqn - индексное множество задач, стоящих в очереди qn перед задачей zi. Очевидно, что для любой задачи zi суммарное время нахождения в очереди и исполнения задачи должно быть меньше заданного срока . В равновесном состоянии система, включающая ЦРЗ и Р2Р-сеть акторов, должна успевать обрабатывать непрерывный поток заданий из ЦРЗ. Пусть ��Z - интенсивность потока задач, поступающих из ЦРЗ по пуассоновскому закону; распределение времени выполнения задач акторами является произвольным и характеризуется величиной производительности актора где задается выражением (2). Тогда имеем модель массового обслуживания M/G/1. Для любого момента времени должно выполняться (3) где - суммарная интенсивность поступления задач в Р2Р-сеть. Это значит, что суммарная производительность всех акторов в любой момент времени должна быть больше скорости поступающих задач или равна ей. В противном случае происходит накопление задач в очередях, связанное с задержками работы акторов, а не с плановым накоплением «задела» задач. Теперь определим условие, при котором актор отдает задачу на аукцион другим исполнителям. Предположим, что задача принята актором к исполнению, при этом выполняется условие (3). Однако дальнейший анализ и прогноз работы актора показывает, что высока вероятность увеличения сроков уже имеющихся задач. При этом вводится функция штрафа от величины задержки срока [4]. Это может стимулировать актора к передаче задачи другому исполнителю. Рассмотрим одноранговое взаимодействие акторов в Р2Р-сети. Обозначим: а) - действие n-го актора по выполнению задачи: - если задача передается на аутсорсинг; - если задача остается на выполнение у n-го актора; - действие i-го актора по аукциону: - если актор принимает решение участвовать в аукционе и получает новую задачу; - в противном случае; б) - функция временных затрат на ожидание задач в очереди и последующее выполнение их актором, где - вектор знаний n-го актора о временных затратах других акторов; в) минимальные суммарные временные затраты на обслуживание потока задач - знания о загруженности всех акторов в Р2Р-сети; г) оптимальный вектор действий всех акторов Р2Р сети Каждый актор производит действия при знании которые определяются выражением где и - время ожидания и выполнения задач n-м и j-м акторами. Описание игры Исходный поток задач . 1. Раздача. Каждый актор получает случайным образом или путем торгов задачи: С использованием функции вычисляется величина временных затрат на выполнение задач. 2. Если - объем новой задачи и - объем еще не выполненных к моменту t задач, то n-й актор оценивает риск невыполнения задачи по условию 3. Каждый актор оценивает степень загрузки других акторов Р2Р-сети по знанию 4. Действия игры. Если есть акторы, загрузка которых невысока, а производительность достаточно большая, то n-й актор выставляет задачу на аукцион . Другие акторы также могут выставить свои задачи на аукцион. Формируется пул задач выставленных на аукцион. 5. Акторы принимают решения об участии в аукционе на основе знаний о своей загруженности и загруженности других акторов . 6. В результате аукциона задачи из множества распределяются по акторам, причем некоторые акторы могут получить по несколько новых задач. Формируется новое распределение задач в результате аукциона. 7. Проводится оценка функции 8. Если < то проводится повторная процедура аукциона до достижения на некотором шаге равновесия Нэша. Рефлексивная теоретико-игровая модель распределения задач по акторам с помощью аукционов Будем в дальнейшем использовать относительные значения объемов задач и относительные производительности акторов где V - общий распределяемый объем задач, измеряемый с помощью метрики Холстеда. Формальное определение рефлексивной игры в виде кортежа [11]: где N - множество игроков (акторов); Xi - множество допустимых действий i-го актора; - его целевая функция; - структура информированности акторов; - множество представлений акторов о представлениях других акторов. Равновесием Нэша в условиях общего знания рефлексивной игры называется такой вектор действий акторов, одностороннее отклонение от которого невыгодно ни для одного актора. Целью действий всех акторов в Р2Р-сети является минимизация времени выполнения потока заданий, что обеспечивается решением задачи условной минимизации (4) при ограничениях (5) (6) Условие (5) показывает, что сумма объемов переданных задач равна сумме объемов выигранных задач на аукционе, а (6) требует сохранения общего объема потока задач. Функции в выражении (4) представляются в виде квадратичной производственной функции типа Кобба - Дугласа при этом производительности акторов µn не равны нулю. В работе [11] рассмотрены десять типов моделей формирования команд, ранжированных в зависимости от структуры информированности и субъективной истории игры. Для описываемой в данной статье задачи предпочтительно использовать модель шестого типа, в которой факторами принятия решений будут знания rijk и принятые решения другими акторами: Тогда i-й актор оценивает действия конкурентов и вычисляет свое действие, приводящее к требуемой сумме действий: (7) Пусть первоначально акторы имеют представления и изменяют их в зависимости от субъективной истории. Обозначим - текущее состояние производительности i-го актора в периоде его наблюдения за производительностью других акторов; - состояние производительности других акторов в Р2Р-сети за тот же период времени. Для описания динамики коллективного поведения акторов используется в качестве одного из вариантов гипотеза индикаторного поведения акторов [13]: (8) где - компоненты вектора, которые являются величинами шагов к положению цели, которая заключается в минимизации суммарного времени выполнения потока задач. При структуре информированности rijk выражение (8) превращается в выражение, описывающее динамику представлений i-го актора: а выбор действий i-го актора следует выражению (7). Построенная теоретико-игровая модель используется для проведения имитационного эксперимента при управлении крупными программными проектами, реализуемыми в Р2Р-сети коллективом программистов. Описанная модель соответствует однородным командам программистов. Более точные результаты можно будет получить при построении теоретико-игровой модели неоднородной команды программистов, которой присущи следующие свойства: различный профессионализм акторов; неоднородная квалификация исполнителей; специализированность акторов на узком круге задач и т. п. Методы оценки этих свойств достаточно хорошо развиты в теории метрик программных проектов [8, 9]. Заключение Описанный подход к управлению одноранговым взаимодействием носит общий характер и может быть использован, например, для построения теоретико-игровых моделей при интеллектуальном управлении вычислительным кластером. В этом случае акторами являются вычислительные узлы кластера, которые могут образовывать виртуальные «команды» по выполнению параллельных потоков задач. При этом механизм аукционов между вычислительными узлами может оказаться более эффективным для полного использования ресурсов кластера, чем при директивном управлении со стороны одного управляющего вычислительного узла.

About the authors

Sergey P Orlov

Samara State Technical University

(Dr. Sci. (Techn.)), Professor. 244, Molodogvardeyskaya st., Samara, 443100, Russian Federation

References

Supplementary files