Точный и жадный алгоритмы распределения экспертов на максимальном множестве групп программистов

Аннотация

Распределение экспертов по программистским группам, отвечающее требованиям профессиональной компетенции в сфере программирования, специфицированным в ИТ-проекте, является сложной комбинаторной проблемой. В данной работе решается задача формирования максимального числа групп с включением в них экспертов, обеспечивающих выполнение каждой группой требований к компетенциям. В статье разрабатываются и сравниваются два алгоритма решения задачи: эвристический жадный и точный оптимальный. Жадный алгоритм итеративно решает задачу о покрытии на матрице экспертных компетенций до тех пор, пока не сможет создать работоспособную группу из оставшихся экспертов. В статье доказано, что этот алгоритм не оптимален, даже если задача о покрытии решается оптимально. Алгоритм назначения экспертов является дважды жадным, если он использует жадный алгоритм покрытия множества. Предлагаемый точный алгоритм находит оптимальное решение на трех шагах: создание набора всех не избыточных групп, построение графа независимости групп и поиск максимальной клики графа. Алгоритм генерации групп обходит дерево поиска, построенное так, чтобы гарантировать нахождение всех не избыточных групп и поглощение всех избыточных групп. Ребра графа независимости групп соединяют вершины-группы, не имеющие общих экспертов. В статье предложен алгоритм поиска максимальной клики, учитывающий особенности графа и решаемой задачи. Экспериментальные результаты показывают, что точный алгоритм является оптимальным эталонным, а алгоритм двойной жадности является быстрым и может давать решение