Книги по разным темам Pages:     | 1 | 2 | 3 | 4 | П.С. Баркалов, И.В. Буркова, А.В. Глаголев, В.Н. Колпачев ЗАДАЧИ РАСПРЕДЕЛЕНИЯ РЕСУРСОВ В УПРАВЛЕНИИ ПРОЕКТАМИ Москва: ИПУ РАН, 2002. - 65 с.

СОДЕРЖАНИЕ ВВЕДЕНИЕ.......................................................................................................4 ГЛАВА 1. ЗАДАЧИ РЕСУРСНОГО ПЛАНИРОВАНИЯ КОМПЛЕКСОВ РАБОТ.................................................................................5 1.1. ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ..............................................5 1.2. ОПТИМИЗАЦИЯ ПО СТОИМОСТИ.......................................................16 ГЛАВА 2. ДВОЙНАЯ СЕТЕВАЯ МОДЕЛЬ РАСПРЕДЕЛЕНИЯ РЕСУРСОВ......................................................................................................20 2.1. ОПРЕДЕЛЕНИЕ МОМЕНТОВ ОКОНЧАНИЯ ОПЕРАЦИЙ ПРИ ЗАДАННОМ ПОТОКЕ РЕСУРСОВ ПО ГРАФУ ПР..................................................................25 2.2. ПОСТАНОВКА ЗАДАЧИ И ОБСУЖДЕНИЕ МОДЕЛИ..............................34 2.3. ОПТИМИЗАЦИЯ КАЛЕНДАРНОГО ГРАФИКА С УЧЁТОМ ВРЕМЕНИ ПЕРЕМЕЩЕНИЙ БРИГАД.................................................................................35 2.4. ОПТИМИЗАЦИЯ КАЛЕНДАРНОГО ГРАФИКА ДЛЯ РАДИАЛЬНОЙ ТРАНСПОРТНОЙ СХЕМЫ.................................................................................45 2.5. ПРОИЗВОЛЬНАЯ ТРАНСПОРТНАЯ СХЕМА................................................51 ЗАКЛЮЧЕНИЕ..............................................................................................65 ЛИТЕРАТУРА................................................................................................65 3 ВВЕДЕНИЕ Управление проектами представляет собой совокупность методологии, методик моделей, методов, технических и программных средств, применяемых при разработке и реализации проектов, то есть, уникальных процессов, ограниченных во времени и требующих затрат ресурсов. Существенную часть моделей и методов управления проектами составляют задачи построения календарных планов реализации проекта, связанных в основном с распределением ограниченных ресурсов. Задачи распределения ресурсов на сетевых графиках относятся к сложным многоэкстремальным задачам.

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

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

ГЛАВА 1. Задачи ресурсного планирования комплексов работ 1.1. Основные понятия и определения При постановке задач ресурсного планирования предполагается, что проект описан в виде комплекса работ в определенными зависимостями между ними. Зависимости между работами отображаются в виде сетевого графика (сети).

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

Как правило, будем применять изображение комплекса работ в виде вершина - работа.

Для полного описания комплекса работ необходимо задать описание каждой работы.

1 3 (1) (3) 0 (2) (4) 2 а) Ошибка! Ошибка связи.б) Рис. 1.1.

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

Следующей характеристикой работы является ее продолжительность (время выполнения). В простейшем случае работа описывается величиной продолжительности и количеством требуемых для ее выполнения ресурсов. В этом случае будем говорить, что работа выполняется с фиксированной интенсивностью. Тогда объем работы для решения задачи ресурсного планирования не нужен, он используется при контроле хода реализации проекта. Если количество ресурсов на работу может принимать различные значения, то и продолжительность работы тоже может быть разной. При этом, если количество ресурсов в процессе выполнения работы не меняется, то будем говорить, что работа выполняется с постоянной интенсивностью. Для описания работы, выполняемой с постоянной интенсивностью достаточно задать продолжительность работы при различных уровнях ресурсов, то есть зависимость (u), где u - количество ресурсов, выполняющих работу. Отношение W w(u)= (1.1.1) (u) определяет интенсивность выполнения работы (производительность участвующих в работе ресурсов), которую мы будем называть скоростью выполнения работы (или просто - скоростью работы). Из выражения (1.1.1) видно, что скорость измеряется объемом работ, выполняемым в единицу времени. Без ограничения общности можно принять, что скорость работы является неубывающей функцией количества ресурсов.

Заметим, что одновременное увеличение (уменьшение) и объема, и скорости работы в одно и то же число раз не изменяет ее продолжительности. Следовательно, и величина объема, и его единица измерения могут быть выбраны произвольно. Как правило, единица измерения объема выбирается из содержательного смысла.

Наиболее сложным является случай, когда работа может выполняться с переменной интенсивностью, то есть количество ресурсов на работе может меняться в процессе ее выполнения. Для описания работы в этом случае необходимо задать ее объем W и зависимость w = f(u) скорости работы от количества выполняющих ее ресурсов. Обозначим через u(t) количество ресурсов на работе в момент времени t, tн - момент начала работы, tк - момент ее окончания. Имеет место соотношение:

tк [u(t)]d = W (1.1.2) f tн Типичный вид зависимости скорости операции от количества ресурсов приведен на рис. 1.2. Сначала с ростом количества ресурсов средняя производительность растет, а затем она начинает падать.

w u Рис. 1.2.

На практике применяются более простые - либо линейные зависимости вида 0, u < a a, f(u)= a u b,(1.1.3) b, b < u либо степенные вида f(u) = u (как правило, < 1).

Важной характеристикой работы являются затраты ресурсов k S = u()d (1.1.4) tн (прямые затраты сырья, материалов, трудозатраты, финансовые и т.д.). В ряде случаев ограничения наложены на затраты ресурсов на работу. Очевидно, что с ростом затрат продолжительность работ не увеличивается при разумном использовании ресурсов. Определим зависимость продолжительности работы от затрат на ее выполнение при заданной зависимости скорости работы от количества ресурсов, предполагая, что ресурсы распределяются оптимально.

Примем сначала, что зависимость f(u) является вогнутой дифференцируемой функцией, то есть, для любого 0 < 1 и любых u1 и uf(u1 + (1-)u2) f(u1) + (1-)f(u2).

Теорема 1.1. Оптимальному распределению ресурсов соответствует выполнение работы с постоянной интенсивностью.

Доказательство. Пусть работа выполняется за время периодов. Поставим задачу распределить затраты по периодам так, чтобы объем выполненной работы был максимальным, то есть (uk ) max f k=при ограничении u = S, k k=где uk - количество ресурсов в периоде k. Применяя метод множителей Лагранжа получим необходимое условие оптимальности:

f(uk) =, k = 1T.

Следовательно, uk = u для всех k. Учитывая, что u = S и f(u) = W, получаем:

S f = W.(1.1.5) Из этого уравнения определяется зависимость (S) либо S().

Пример 1.1. Пусть f(u) = u, 1. Имеем:

S = W.

Из этого уравнения получаем W S()=.

-WВ случае = 2, S()=.

Заметим, что в случае линейной зависимости (1.1.3) затраты равны объему работы W. Если величину затрат умножить на стоимость единицы ресурса, то получим стоимость работы, которая является основой формирования сметы и бюджета проекта. Если зависимость f(u) имеет произвольный вид (например, задана в конечном числе точек), то строим вогнутую зависимость, максимально близкую к заданной. Способ построения ясен из рис. 1.3.

f(u) В С А вогнутая зависимость u u1 u* uРис. 1.3.

Далее для заданной продолжительности определяем u* и соответственно S = u*, принимая полученную вогнутую зависимость за истинную. представим точку u* как выпуклую линейную комбинацию ближайших точек u1 и u2:

u* = u1 + (1-)u2, 0 < 1.

Очевидно, что f(u*) = f(u1) + (1-)f(u2).(1.1.6) Разделим интервал времени на два: 1 = и 2 = (1-).

Примем u = u1 в интервале 1 и u = u2 в интервале 2. Из условия (1.1.6). Имеем f(u*) = 1f(u1) + 2f(u2) = W, u11 + u22 = [u1 + (1-)u2] = u*, то есть полученное допустимое распределение ресурсов позволяет выполнить весь объем работ с затратами ресурсов S.

Из полученного результата следует важный вывод: для любых зависимостей f(u) и затрат S существует оптимальное распределение затрат во времени с не более чем двумя интервалами постоянства уровней ресурсов. Типичными зависимостями затрат от времени, применяемыми на практике, являются кусочно-линейные (рис. 1.4) и степенные:

Ошибка! Объект не может быть создан из кодов полей редактирования.

S min max Рис. 1.4.

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

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

Это многообразие сводится к двум основным типам:

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

Воспроизводимые, нескладируемые, ненакапливаемые ресурсы сохраняют свою натурально-вещественную форму и по мере высвобождения могут использоваться на других работах. Если эти ресурсы простаивают, то их неиспользование в данный отрезок времени не компенсируется в будущем, т.е. они не накапливаются, поэтому ресурсы второго типа называют еще ресурсами типа мощности. Примерами ресурсов типа мощности являются люди и средства труда многократного использования (машины, станки, механизмы и т.д.).

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

Ограничения на ресурсы, которые можно использовать на работах проекта, определяются функцией наличия (доступности) ресурсов. Если N(t) - функция наличия определяющего ресурса, то ограничения на распределение ресурсов по работам проекта имеет вид:

n (t) u N(t), i i=где ui(t) - количество ресурса на работе i, n - число работ проекта.

Довольно часто работы проекта разбиваются на классы, так что работы одного класса выполняются ресурсами одного вида. Если обозначить Pj - множество работ, выполняемых ресурсами j-го вида, Nj(t) - функцию наличия ресурсов j-го вида, то ограничения на распределение ресурсов записываются следующим образом:

(t) (t), u N j = 1,m.

i j iPj Для накапливаемых ресурсов ограничения задаются в интегральном виде:

t n ui()d S(t).

i=Если ограничены общие затраты S на проект (или ограничена стоимость проекта), то ограничения на ресурсы определяются следующим неравенством:

n s S, i i=где si - затраты ресурса на i-й работе (или стоимость i-й работы).

Задача оптимального распределения ресурсов заключается в определении допустимого по ограничениям распределения ресурсов, минимизирующего заданный критерий оптимальности. Если ограничены ресурсы, то, как правило, ставится задача минимизации продолжительности T проекта, либо задача минимизации упущенной выгоды:

n Ф = ti, c i i=где ti - момент окончания i-й работы, ci - коэффициент упущенной выгоды. Если задан срок завершения проекта, либо допустимая величина упущенной выгоды, то решается в определенном смысле обратная задача - минимизации ресурсов либо затрат.

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

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

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

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

(2) (4) 0 1 2 (1) (3) Рис. 1.5.

Однако, можно определить аналог таких сетей и в представлении вершина - работа, рис. 1.6.

1 2 Рис. 1.6.

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

В сети рис. 1.6. можно выделить три различных фронта работ:

Pages:     | 1 | 2 | 3 | 4 |    Книги по разным темам