Решение задачи о назначениях для группы разработчиков программного обеспечения

Южный Федеральный Университет

Россия, г. Ростов-на-Дону

При проектировании и реализации любой крупной задачи появляется необходимость в оптимальном распределении работ среди разработчиков. В данный момент среди команд программистов широкое распространение получила методология экстремального программирования. Экстремальное программирование (Extreme Programming, XP) - дисциплина разработки ПО и ведения бизнеса в области создания программных продуктов, которая фиксирует усилия обеих сторон (программистов и бизнесменов) на общих целях [1]. При таком подходе долгосрочное планирование зачастую оказывается бесполезным. Одним из наиболее подходящих методов планирования является постановка и решение задачи о назначениях.

Наиболее эффективным методом решения задачи о назначениях является «венгерский» алгоритм [2]. Приведем решение данной задачи с использованием модифицированного «венгерского» алгоритма. Для начала рассмотрим простой случай с n разработчиками, m задач и равными значениями n и m (n = m).

Рассмотрим исходную матрицу времени выполнения работ.

Таблица 1. Матрица времени выполнения работ

Здесь время выполнения i-м сотрудником j-го задания. Так как в качестве решения необходимо знать, какой разработчик должен выполнять ту или иную работу, то, решение можно записать в виде массива D:

Здесь индекс соответствует номеру работы, а значение соответствует номеру разработчика, назначенного на j-ю работу. На каждом шаге алгоритма будем выбирать для каждой строки минимальное значение. Затем выберем минимальное из этих минимальных. Если минимальные значения совпадают, то берем значения, находящиеся в северо-западном углу (не всегда верно для матриц размерности 2*2) матрицы. Записываем номер строки минимального значения в соответствующую ячейку массива D. Удаляем строку и столбец, на пересечении которых находится найденный элемент. Повторяем шаг с новой матрицей.

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

Так как на каждом из шагов алгоритма значения элементов матрицы не изменяются, то и минимальные значения элементов в строках не поменяются. Таким образом, на первом шаге алгоритма необходимо выбрать по каждой из строк матрицы минимальное значение и номера столбцов, в которых содержатся эти значения. Учтем замечания о выборе минимального элемента для матриц размерности 2*2.

Шаг 1.

(1)

(2)

 (3)

Каждый содержит в себе минимальное значение и индексы столбцов, в которых оно встречается. Вся дальнейшая работа проводится над массивом M. Чтобы не зависеть от порядка следования элементов в массиве M и иметь возможность удалять элементы из массива, модифицируем структуру элемента массива, указанную в (3). Добавим еще номер строки.

(4)

Шаг 2.

Находим с наименьшим . Если таких несколько, то выбираем с наименьшим значением i. Далее, если элементов в массиве больше двух, то занесем i в массив D в ячейку с номером, совпадающим с наименьшим значением j -го элемента. Затем можно удалить из массива М, а все элементы с таким же значением j заменить на элемент с минимальным значением, полученным из столбцов матрицы с другими номерами и вернуться на начало шага 2.

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

Далее рассмотрим ситуацию, когда n > m. Шаги 1 и 2 будут такими же, как и в случае когда n = m. Отличие только в финальном шаге. На последней итерации в массиве M останется n - m + 2 элемента. Основываясь на данных из предыдущих итераций об обработанных i и j, получаем итоговую матрицу размерности (n - m + 2)*2. Для каждой строки матрицы получим суммы первого элемента со вторыми элементами остальных строк. Индексы строк элементов, давших наименьшую сумму, заносятся в соответствующие позиции итогового вектора D.

Теперь перейдем к рассмотрению случая n > m. Данный случай является наиболее тяжелым из всех ранее рассмотренных. В данном случае алгоритм будет применен раз. Первый шаг такой же, как и в предыдущих случаях. На втором шаге вычеркиваем самый левый столбец матрицы, в котором содержится наименьший элемент. Строку, в которой находился этот элемент, помечаем как временно использованный. Далее выбираем минимальный элемент по оставшимся строкам матрицы. Возвращаемся на начало шага 2 и удаляем очередной столбец матрицы. Как только возникнет ситуация, когда останется только одна непомеченная как используемая строка матрицы, то выбираем в ней минимальный элемент и удаляем из матрицы крайний левый столбец, содержащий данный элемент. После этого снимаем пометки на строках и возвращаемся на начало шага 2.

Данная итерация продолжается пока не будут обработаны все столбцы матрицы.

Аналогично первым двум случаям можно исходную матрицу представить в виде массива.

(5)

В отличие от рассмотренных ранее алгоритмов структура элемента будет иной.

 (6)

Здесь параметр u принимает значение 0, если элемент разрешено использовать и значение 1, если элемент временно использован.

Шаг 2 данного алгоритма отличается от рассмотренных, для случаев тем, что элемент не удаляется из массива, а помечается как временно использованный. Данная пометка снимается со всех элементов, как только не найдено более свободных.

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

Для начала рассмотрим случай, когда части основной задачи не зависят друг от друга и могут быть обработаны в любом порядке. Пусть имеется N разработчиков и M типов задач.

Пусть также основная задача распадается на K подзадач:

, (7)

где представляют собой матрицы назначения.

Рассмотрим ситуацию: N = M = K = 3. Тогда имеем три матрицы:

 (8)

Применив шаг 1 алгоритма, для каждой из этих матриц получим три массива:

(9)

Применив алгоритм, далее получим три массива решений:

(10)

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

(11)

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

(12)

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

(13)

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

Следует также заметить, что данная модификация алгоритма является более эффективной. Как известно, временная сложность оригинального алгоритма составляет , либо для модифицированного Эдмондсом и Карпом, либо Томидзавой алгоритмов. Проведя анализ данного алгоритма, можно сказать, что наихудшая оценка временной сложности его составляет . Эффективность алгоритма также достигается тем, что основные вычисления переведены из двумерного множества в одномерное, размерностью m. Также преимуществом данного алгоритма является то, что на каждом последующем шаге обрабатывается все меньшее количество данных, чем на предыдущем. Это делает данный алгоритм не таким чувствительным к размерности матрицы времени/стоимости выполнения работ. Еще один плюс данного подхода заключается в том, что оригинальный алгоритм позволяет работать только с квадратными матрицами. Представленный алгоритм легко реализуется для прямоугольных матриц.

В таблице 2 приведены результаты практической проверки временной сложности алгоритма.

Таблица 2. Время работы алгоритма

экстремальный программирование назначение алгоритм

В заголовках столбцов указаны размерности матриц. Для каждой размерности было сделано по 10 замеров. Время в таблице указано в секундах.

Алгоритм реализован на языке программирования С. Тесты проводились на ноутбуке Acer Aspire 5100. Формулы (3), (4), и (6) были реализованы с использованием типа данных struct. На первом шаге алгоритма формируется двунаправленный список, каждый элемент которого представляет собой такую структуру. Затем, на каждом витке алгоритма из списка удаляется по одному элементу, и происходит пересчет минимальных значений для тех элементов, которые имели минимальный элемент в обработанном столбце.

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

Литература

1. Кент Бек Экстремальное программирование. - СПб.: Питер, 2010.

2. Гинзбург А. И. Экономический анализ: Предмет и методы. Моделирование ситуаций. Оценка управленческих решений: учебное пособие. - СПб.: Питер, 2003. - 622 с.

3. Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ. Introduction to Algorithms. - 2-е изд. М.: «Вильямс», 2006. - 1296 с. - ISBN 0-07-013151-1

4. Дональд Кнут Искусство программирования, том 1. Основные алгоритмы. The Art of Computer Programming, vol. 1. Fundamental Algorithms. - 3-е изд. - М.: «Вильямс», 2006. - 720 с. - ISBN 0-201-89683-4

Размещено на Allbest.ru