XIV Международная студенческая научная конференция Студенческий научный форум - 2022

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

В данной статье рассмотрен венгерский метод, который используется как алгоритм решения задачи о назначениях [1]. Данный алгоритм предполагает представление задачи в виде «матрицы задач», где пересечение строк и столбцов – целевой признак задачи. Целевой признак – это показатель который необходимо оптимизировать. В случае с выполнением задач ИТ-специалистами целевой признак – время работы над задачей.

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

Рассмотрим пример распределения работы между исполнителями на примере программистов в количестве пяти человек и такого же количества задач. На рисунке 1 представлена матрица задач. Элементы данной матрицы – время выполнения задачи в минутах. Строка матрицы – время работы исполнителя над каждой из задач, а столбец – время работы каждого из исполнителей над задачей. В квадратах, приведённых на рисунке 1 и отмеченных цветом, приведено описание задачи, которую необходимо выполнить, а буквенное обозначение – исполнитель. Пересечение буквенного идентификатора и цветного блока является временем выполнения задачи.

Целевая функция задачи о назначениях – сумма значений по времени выполнения конкретной задачи выбранным исполнителем. Данная сумма должна быть минимальной из возможных.

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

Переменные xNM принимают значения 1, если n-й кандидат занимает M-ю вакансию. Если данное условие не выполняется, то xNM=0.

Рассмотрим матрицу задач, приведённую на рисунке. Матрица задач предполагает наличие 5-ти задач, которые необходимо распределить среди 5-ти специалистов таким образом, чтобы суммарное время выполнения всех задач было минимальным.

Рисунок 1 – Матрица задач

Необходимо составить также ограничения на количество выполняемых задач каждым из специалистов. Ограничения представлены следующей системой уравнений. В данной системе уравнений видно, что над одной задачей работает один исполнитель.

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

В задаче необходимо минимизировать функцию (3).

Одним из методов решения задачи о назначениях является венгерский алгоритм [2]. Первый шаг данного алгоритма заключается в редукции матрицы по строкам, второй – по столбцам. Редукция матрицы – поиск минимального элемента по строке, и вычитание этого элемента из каждого элемента этой строки. Редукция по столбцам несёт за собой тот же смысл, что и редукция по столбцам. Таким образом, после проведения данной процедуры матрица преобразуется таким образом, что в каждой строке и в каждом столбце есть как минимум по одному нулевому значению.

На рисунке 2 показан результат проведения операции редукции матрицы по строкам.

Рисунок 2 – Редукция матрицы по строкам

Результат проведения редукции матрицы по столбцам представлен на рисунке 3.

Рисунок 3 – Редукция матрицы по столбцам

Следующая операция данного алгоритма заключается в поиске строк и столбцов с нулевыми значениями и последующем их вычёркивании. В результате проведения такой операции получена матрица, представленная на рисунке 4.

Рисунок 4 – Оптимальная матрица

Следующий этап алгоритма – вычёркивание строк и столбцов матрицы таким образом, чтобы пересечений было как можно меньше и самих вычёркиваний, по возможности, тоже. Далее необходимо выделить те элементы, которые не пострадали от вычёркиваний («свободные» элементы).

На рисунке 5 представлена матрица «свободных» элементов. Из этих элементов необходимо найти минимальный и вычесть его из всех элементов.

(а) (б)

Рисунок 5 – Матрица «свободных» элементов (а), матрица после вычитания (б)

Затем венгерский алгоритм предполагает сложение минимального элемента «свободной матрицы» с элементами начальной матрицы, которые остались на пересечении строк и столбцов после операции вычёркивания. Затем необходимо снова повести редукцию матрицы по строкам.

После проведения данной операции определяем матрицу назначения, которая позволяет вычислить минимальные суммарные затраты по времени. На рисунке 6 представлен результат редукции матрицы по строкам.

Рисунок 6 – Редукция матрицы по строкам на предпоследнем шаге.

Выбранные нулевые значения необходимо сопоставить с исходной матрицей, подставив вместо нулей значения, соответствующие адресу нуля. Полученные значения необходимо сложить для получения решения задачи о назначениях. Результат решения приведённой задачи – 15 + 10 + 180 + 25 + 30 = 260 минут необходимо на решение всех поставленных задач.

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

В крупных ИТ-организациях данный показатель должен измеряться менеджерами по продукту, ответственными за тот или иной проект. Показатель времени выполнения работы можно анализировать при помощи системы контроля версий проекта [3].

Для работы с задачами есть множество различных программ. Одна из популярных – Redmine, которая позволяет осуществлять полный контроль над задачами, а также работу с репозиторием GIT, что позволяет видеть и анализировать все без исключения изменения программного кода. Данная программа также предоставляет управляемый интерфейс, который можно использовать для визуализации работы над задачами в других информационных системах. Данные, полученные из программы Redmine можно использовать для создания системы поддержки принятия решений о распределении задач между ИТ-специалистами.

Список литературы

Венгерский алгоритм, или о том, как математика помогает в распределении назначений [Электронный ресурс]. — 2018. — URL: https://habr.com/ru/post/422009/ (дата обращения 15.12.2021).

Венгерский алгоритм [Электронный ресурс]. — 2020. — URL: https://ru.wikipedia.org/wiki/ (дата обращения 18.12.2021)

Как тимлиду обучить распределенную команду работать с Git [Электронный ресурс]. — 2020. — URL: https://habr.com/ru/post/589715/ (дата обращения 18.12.2021)

Код для цитирования: Скопировать