Распределение ресурсов

Задачи распределения ресурсов в отличие от задач учета потребностей ресурсов относятся к оптимизационному типу и могут рассматриваться как для односетевых, так и для многосетевых комплексов работ. По результатам решения задачи распределения ресурсов составляют календарный план выполнения комплекса работ, т. е. для каждой работы указываются даты ее начала и окончания с учетом обуслов­ленной технологией последовательности их выполнения таким образом, чтобы удов­летворялось оптимальное значение целевой функции и не нарушались ограничения, которые определяются при постановке задачи распределения ресурсов. Известно чрезвычайно большое число разнообразных постановок данных задач, которые можно разбить на три основные группы в зависимости от принимаемого критерия оптимальности и вида ограничений:

- задачи распределения ресурсов, при котором обеспечивается минимизация времени осуществления комплекса работ при выпол­нении заданных ограничений на используемые ресурсы;

- задачи распределения ре­сурсов, при котором удовлетворяется наилучшее значение некоторого показателя качества использования ресурсов при заданных сроках выполнения всего комплекса, чаще всего в данной постановке производится минимизация максимальных значе­ний потребляемых ресурсов;

- задачи распределения ресурсов в смешанных поста­новках, где, например, для некоторых сетей в многосетевой разработке минимизи­руется время выполнения комплекса работ при заданных уровнях используемых ресурсов, а для других — минимизируются уровни потребления ресурсов при заданных сроках выполнения комплекса.

Методы решения задач распределения ресурсов можно условно подразделить на: 1) методы математического программирования; 2) эвристические; 3) комбини­рованные. Методы первого направления реализуются средствами целочисленного линейного, нелинейного, динамического и статистического программирования. Ко второму направлению относятся методы, в основе которых лежат эвристические правила (метод последовательного фронталь­ного распределения, метод последовательного растяжения, метод последовательной корректировки плана и т. п.).

Комбинированные методы решения задач распределения ресурсов основываются на сочетании методов математического программирования и эвристических методов и могут быть условно разделены на четыре группы:

1) методы, использующие резуль­тат решения задачи эвристическими методами в качестве исходных данных для даль­нейшего решения с помощью методов математического программирования;

2) методы, осуществляющие предварительное эвристическое разбиение основной задачи на частные задачи, решаемые методами математического программирования;

3) методы, использующие эвристические правила при формировании условий задачи, решаемой методами математического программирования;

4) усеченные методы математического программирования.

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

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

Методы распределения ресурсов с постоянной интенсивностью потребления ресурсов, используемых на работах, можно разделить на две большие группы:

- методы с фиксированной интенсивностью потребления ресурсов;

- методы с фикси­рованным диапазоном возможных значений интенсивностей потребления ресурсов.

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

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

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

Общая модель планирования проекта с распределением ресурсов

Математические модели распределения ресурсов обеспечивают составление календарного плана на стадии исходного планирования. Они реализуются в двух основных постановках в зависимости от принимаемого критерия оптимальности и вида ограничений:

- модель расчета календарного плана многосетевой модели, кото­рый обеспечивает минимизацию максимального отклонения сроков завершения каждого комплекса от директивного или минимизацию сроков завершения каждого комплекса при выполнении заданных ограничений на использование ресурсов и учитывает приоритеты комплексов (1-й тип задачи календарного планирования);

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

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

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

В том случае когда осуществляется предварительное планирование многотемных (многосетевых) комплексов работ, важным моментом является предварительная увязка результатов решения задачи объемного планирования, обеспечивающей формирование плана с установленными технико-экономическими показателями, с задачей календарного планирования, т. е. решение ряда вопросов, связанных с формированием тематического плана, обеспечивающего выполнение основных объемных показателей. Эта проблема является одной из важнейших на этапе предварительного планирования, Ее содержание поясним на модели формирования тематического плана, минимизирующего дисбаланс между структурой располагаемых и потребных ресурсов. Формирование тематического плана сводится к выбору такого набора технологи­чески независимых комплексов работ, которые обеспечивают оптимальный вариант тематического плана, позволяющий улучшить использование располагаемых ресур­сов. При многотемном планировании рассматриваемые комплексы работ могут различаться по степени важности, что приводит к необходимости учета различных уровней приоритетов тем. Введем обозначения: Е — целевая функция; М — плани­руемый уровень объема работ по всем комплексам на планируемый период; j — теку­щий индекс темы (комплекса работ); i — текущий индекс вида ресурсов; n — коли­чество заявочных тем; т — количество планируемых ресурсов; — коэффициент веса важности j -й темы; — норма затрат ресурса вида i на тему вида j; С_j — объем работ по теме j; R_i — располагаемый объем i -го ресурса; x_j = 0, 1 — булевы перемен­ные, если x_j = 1 — тема включается в тематический план, если x_j = 0 — тема не включается в тематический план.

Задача формирования тематического плана может быть решена в двух поста­новках.

1. Выбрать перечень комплексов работ, который бы обеспечил минимальное отклонение суммарных потребных объемных показателей работ по темам от заплани­рованного уровня при условии, что потребные объемы ресурсов не превышают рас­полагаемых объемов; данная задача формализуется как оптимизационная с альтерна­тивными переменными:

(4.1)

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

(4.2)

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

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

Исходное планирование комплекса работ является второй стадией планирования проекта. На стадии исходного планирования осуществляется расчет календарного плана комплекса работ. В процессе расчета исходного плана производится: построение сете­вой модели комплекса работ; привязка сетевой модели к нормативной базе; расчет календарного плана выполнения комплекса работ. Процесс разработки сетевой мо­дели основывается на изучении технологических процессов, которые в дальнейшем формализовано описывают в виде графа. Если сетевая модель отображает сравни­тельно небольшие и несложные программы, то построение сетевой модели осуществля­ется на основе правил построения сетевых графиков. При построении сетевых моделей для больших и сложных программ прибегают к помощи таблицы структурного анализа.

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

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

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

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

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

На рисунке 4.1 представлен план, не сбалансированный по времени и ресурсам, на рисунке 4.2 — план, не сбалансированный по ресурсам, на рисунке 4.3 — полностью сбалансированный план.