Exact and greedy algorithms of allocating experts to maximum set of programmer teams
Another Title
Точный и жадный алгоритмы распределения экспертов на максимальном множестве групп программистов
Bibliographic entry
Prihozhy, A. А. Exact and greedy algorithms of allocating experts to maximum set of programmer teams = Точный и жадный алгоритмы распределения экспертов на максимальном множестве групп программистов / A. А. Prihozhy // Системный анализ и прикладная информатика. – 2022. – № 1. – С. 40-46.
Abstract
The allocation of experts to programmer teams, which meet constraints on professional competences related to programming technologies, languages and tools an IT project specifies is a hard combinatorial problem. This paper solves the problem of forming the maximum number of teams whose experts meet all the constraints within each team. It develops and compares two algorithms: a heuristic greedy and exact optimal. The greedy algorithm iteratively solves the set cover problem on a matrix of expert competences until can create the next workable team of remaining experts. The paper proves that the allocation greedy algorithm is not accurate even if the set cover algorithm is exact. We call the allocation algorithm as double greedy if the set cover algorithm is greedy. The exact algorithm we propose finds optimal solution in three steps: generating a set of all non-redundant teams, producing a graph of team’s independency, and searching for a maximum clique in the graph. The algorithm of generating the non-redundant teams traverses a search tree constructed in such a way as to guarantee the creation of all non-redundant teams and absorbing all redundant teams. The edges of the non-redundant team independency graph connect teams that have no common expert. The maximum clique search algorithm we propose accounts for the problem and graph features. Experimental results show that the exact algorithm is a reference one, and the double-greedy algorithm is very fast and can yield suboptimal solutions for large-size allocation problems.
Abstract in another language
Распределение экспертов по программистским группам, отвечающее требованиям профессиональной компетенции в сфере программирования, специфицированным в ИТ-проекте, является сложной комбинаторной проблемой. В данной работе решается задача формирования максимального числа групп с включением в них экспертов, обеспечивающих выполнение каждой группой требований к компетенциям. В статье разрабатываются и сравниваются два алгоритма решения задачи: эвристический жадный и точный оптимальный. Жадный алгоритм итеративно решает задачу о покрытии на матрице экспертных компетенций до тех пор, пока не сможет создать работоспособную группу из оставшихся экспертов. В статье доказано, что этот алгоритм не оптимален, даже если задача о покрытии решается оптимально. Алгоритм назначения экспертов является дважды жадным, если он использует жадный алгоритм покрытия множества. Предлагаемый точный алгоритм находит оптимальное решение на трех шагах: создание набора всех не избыточных групп, построение графа независимости групп и поиск максимальной клики графа. Алгоритм генерации групп обходит дерево поиска, построенное так, чтобы гарантировать нахождение всех не избыточных групп и поглощение всех избыточных групп. Ребра графа независимости групп соединяют вершины-группы, не имеющие общих экспертов. В статье предложен алгоритм поиска максимальной клики, учитывающий особенности графа и решаемой задачи. Экспериментальные результаты показывают, что точный алгоритм является оптимальным эталонным, а алгоритм двойной жадности является быстрым и может давать решение.
View/
Collections
- № 1[8]