двухуровневая модель задачи формирования ресурсов и календарного планирования программного проекта в условиях запаздывания
Клименко А.Б., сидоров и.Д.
Научно-исследовательский институт многопроцессорных вычислительных систем имени академика А.В. Каляева ФГАОУВПО «Южный федеральный университет», Институт компьютерных технологий и информационной безопасности ИТА ЮФУ, г. Таганрог, Россия
DELAYED soFTwARE project
resource allocation and scheduling problem bilevel model
Klimenko A.B., sidorov I.D.
Scientific Research Institute of Multiprocessor Computer Systems of Southern Federal University, Institute of Computer Technology and Information Security of Southern Federal University, Taganrog, Russia
Задачи формирования минимального количества ресурсов и календарного плана работ с ограничением на время их выполнения актуальны и решаются во многих сферах
человеческой деятельности. Известные модели, однако, не позволяют учесть особенностей процесса производства программного обеспечения, что делает актуальным построение новой формальной модели задачи. В статье проведен краткий анализ аналогов, представленных в литературе, и построена модель задачи формирования ресурсов и календарного планирования как задача двухуровневого программирования.
ключевые слова: распределение ресурсов, календарное планирование, программный проект, задача двухуровневого программирования, расписание, формирование минимального набора ресурсов, планирование проекта.
The minimal resource forming and scheduling problem with the time constraint is actual and solved through many human activity areas. However, well-known models of the problem don't take into account the software development process features, so the new model formalization is actual. In the paper below the prototypes analysis is done and the new model of the minimal resource forming and scheduling problem with the time constraint as a bilevel programming problem is presented.
Keywords: resource allocation, planning, software project, bilevel programming problem, scheduling, minimal resource forming, project planning.
введение
В настоящее время, когда разработка программного обеспечения (ПО) приобрела черты промышленного производства, возросла актуальность вопросов планирования и распределения
ресурсов (людей). Использование облегченных методологий производства ПО не умаляет важности вопроса, поскольку:
■ основные концепции agile-методологий направлены в основном на реализацию возможности оперативного реагирования на изменения требований со стороны заказчика либо на возникающие изменения инфраструктуры рынка ПО. Сокращение длительности итераций позволяет улучшить гибкость процесса, но не означает отказ от планирования;
■ завершение проекта к сроку критично как для заказчика, так и для фирмы-изготовителя.
Таким образом, большинство проектов все же предполагает наличие планирования, в частности, распределения подзадач проекта по исполнителям. Календарные планы могут быть скорректированы на протяжении всех контрольных точек проекта как ответная реакция на внутренние или внешние события, такие, как: болезнь/увольнение сотрудников, изменение требований (что влечет за собой изменение графа задач, назначенных на исполнение), изменение ограничений на время выполнения проекта или изменения инфраструктуры рынка ПО [2, 3, 5]. Изменение календарного графика выполнения проекта связано с перераспределением решаемых задач по исполнителям, но, помимо этого, специфика программных проектов позволяет привлекать новых исполнителей путем найма или перевода с другого проекта. [4]
Возможность такой ситуации специфична для проектов, выполняемых людьми. Если вести речь о производстве, к примеру, на конвейере, то вполне очевидно, что добавить новое устройство
в конвейер несопоставимо труднее, чем нанять нового исполнителя для программного проекта. Более того, для программного проекта число исполнителей, доступных для найма, можно полагать ничем не ограниченным - особенно в условиях развития интернет-технологий и возможности удаленной работы.
Таким образом, для любой точки перепланирования, которая является реакцией на событие[8], решается задача не только перераспределения подзадач по исполнителям, но одновременно и формирование множества исполнителей с возможным привлечением новых кадров путем найма или перевода с другого проекта. При этом необходимо учесть ограничение на время выполнения проекта, а также по возможности минимизировать его общую стоимость.
Данная статья посвящена вопросу формализации описанной выше задачи в виде двухуровневой модели математического программирования (bilevel programming problem). Далее будет приведен краткий обзор наиболее известных моделей, используемых при планировании программных проектов, выделены особенности поставленной задачи и вопросы, которые не решают рассмотренные математические модели, и обоснована необходимость формализации задачи как двухуровневой в отличие от известных одноуровневых моделей.
1. особенности задачи формирования ресурсов и календарного планирования программного проекта
Для дальнейшей формализации постановки задачи ФРКП программного проекта рассмотрим наиболее важные особенности процесса:
■ определяющим ресурсом является исполнитель (разработчик);
■ при разбиении основной задачи проекта на подзадачи предполагается, что в каждый момент времени одну задачу решает один исполнитель;
■ как правило, оплачивается время исполнителя, проведенное на проекте;
■ производительность исполнителя непостоянна и зависит от многих факторов;
■ зависимость производительности разработчика от стоимости работы произвольна и зависит от состояния рынка рабочей силы.
Перечисленные особенности являются основополагающими для следующих заключений:
■ невозможно перемещение ресурсов между задачами таким образом, чтобы одновременно над задачей работало более одного исполнителя, и точно также невозможно убавление ресурсов на задаче с остатком меньше 1. Использование в качестве определяющего ресурса производительность исполнителей либо их стоимость также нецелесообразно, поскольку предполагается однозначное соответствие характеристик исполнителям. Иными словами, ресурсы имеют дискретный характер и в данной ситуации единственный способ изменения назначения работы ресурсу - перемещение ресурса полностью на другую работу;
■ так как оплачивается суммарное время исполнителей, возможно, нецелесообразным становится соблюдение огра-
ничения по времени выполнения проекта в формулировке «должен быть завершен без превышения времени Т». Наоборот, сокращение общего времени, затраченного на проект, может привести к его удешевлению даже в условиях увеличения количества оплачиваемых исполнителей.
Помимо уже перечисленного, следует отметить следующее:
■ так как в случае невозможности решения задач проекта к указанному сроку или ранее всегда есть возможность привлечения дополнительных ресурсов путем найма или перемещения с другого проекта, будет считать, что ограничения на ресурсы отсутствуют. Формально это можно описать множеством исполнителей относительно большой мощности;
■ исполнители внутри проекта подразделяются на группы так называемых «экспертов», «новичков» и «обучающих экспертов»[4]. При этом производительность исполнителей зависит как от времени работы на проекте (процесс обучения «новичков»), так и от численного соотношения в группах и не является линейной.
Далее рассмотрим кратко близкие по смыслу задачи, освещенные в открытой печати.
2. модели задач фркп
Будем различать задачу календарного планирования и задачу ФРКП: если в задаче календарного планирования необходимо произвести привязку работ к устройствам и времени, то реше-
нием задачи ФРКП должен быть и календарный план, и ресурсы, необходимые для этого. Среди наиболее близких по смыслу задач можно выделить модели, описанные в работах: McGee A., Markarian M. [7], Levy F., Thompson G., Wiest J [6], а также в работе Барского А.Б. [1].
По результатам обзора публикаций, представленных в открытой печати, можно предположить, что статья [7] содержит одну из первых постановок задачи управления ресурсами в инженерных проектах. Здесь считается заданным время выполнения комплекса связанных работ и количество ресурсов(людей) каждого вида Nk(t) в любой момент времени. Число людей, необходимых для выполнения операций, связаны с временем их выполнения линейно, то есть:
U =c.. - ky, d.<=y. <=D;
ij V j if V ^ V if
Также задана линейная зависимость стоимости выполнения операции от времени ее выполнения:
S. =a - b y., d.<=y. <=D .
if if if if if if if
Задача заключается в определении количества людей на каждой операции таким образом, чтобы количество ресурсов в момент времени t не превышало заданного количества соответствующего вида, комплекс был выполнен за время T и стоимость его выполнения была минимальной.
Если рассматривать постановку данной задачи в аспекте перечисленных выше особенностей ведения программного проекта, можно выделить следующие ключевые моменты, которые делают предлагаемую модель малоприменимой: во-первых, уже было
показано [4], что в программных проектах зависимость времени выполнения работ от количества выделенных для этого людей не является линейной. Во-вторых, на финальной стадии декомпозиции основной задачи проекта каждому исполнителю ставится в соответствие множество задач, в один и тот же момент времени возможно решение исполнителем только одной задачи. Следовательно, невозможно вести речь о назначении нескольких людей на одну работу. Кроме того, обратная зависимость стоимости операции от ее длительности предполагает, что с увеличением времени выполнения операции ее стоимость уменьшается, тогда как в случае почасовой оплаты исполнителей на программном проекте увеличение времени выполнения операции не уменьшает, а наоборот, увеличивает ее стоимость.
Еще одной близкой по смыслу постановкой задачи ФРКП является [6]. Здесь производится минимизация максимального количества устройств, необходимого для решения комплекса задач за время Т и речь идет не о суммарной стоимости проекта, а о м
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.