Модели сетевого планирования и управления

Модели сетевого планирования и управления

1. Общая характеристика сетевого планирования и управления

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

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

За рубежом система СПУ известна как система РЕRТ (Рrоgram Еvaluation and Review Тechnique - метод анализа и оценки программ) или СРМ (Critical Рath Мethod - метод критического пути).

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

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

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

Работа характеризует любое действие, требующее затрат времени или ресурсов. Работами считаются и процессы, не требующие затрат времени и ресурсов, а устанавливающие зависимости выполнения работ. Такие работы называются фиктивными. Работа обозначается парой чисел (i,j) где i - номер события, являющимся начальным для данной работы, j - номер события, являющимся конечным для данной работы, в которое она входит. Работа не может начаться раньше, чем свершится событие, являющееся для нее начальным. Каждая работа имеет свою продолжительность t(i,j). Работы на графах обозначаются дугами (стрелками), фиктивные работы обозначаются пунктирными стрелками.

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

Путь - цепочка следующих друг за другом работ (дуг), соединяющих начальную и конечную его вершины. Полный путь L - путь, начало которого совпадает с начальным событием сети, а конец - с завершающим. Продолжительность пути определяется суммой продолжительностей составляющих его работ. Путь, имеющий максимальную продолжительность, называют критическим (обозначение L_кр). Продолжительность критического пути обозначается как t_кр_. Работы, принадлежащие критическому пути, называются критическими. Их несвоевременное выполнение ведет к срыву сроков всего комплекса работ.

Сетевая модель должна удовлетворяет следующим требованиям:

Не должно быть событий с одинаковыми номерами.

Для каждой работы (i,j) должно выполняться i <j

Должны быть только одно начальное и одно конечное события.

Должны отсутствовать циклы, т.е. замкнутые пути, соединяющие событие с ним же самим.

При выполнении этих требований можно приступать к вычислениям числовых характеристик СМ. Исходные числовые данные СМ представляются в виде таблицы длительности выполнения каждой работы.

Характеристики элементов сетевой модели

При расчетах для сетевой модели определяются следующие характеристики ее элементов.

Характеристики событий

1. Ранний срок свершения события tp(0) = 0, tР(j) =тахi{tр(i) + t(ij)}, j=1--N характеризует самый ранний срок завершения всех путей, в него входящих. Этот показатель определяется «прямым ходом» по графу модели, начиная с начального события сети.

2. Поздний срок свершения события t_п(N) = t_р(N), t_п (i) = min_j {(t_п(j)-t(ij)}, i=1--(N-1) характеризует самый поздний срок, после которого остается ровно столько времени, сколько требуется для завершения всех путей, следующих за этим событием. Этот показатель определяется «обратным ходом» по графу модели, начиная с завершающего события сети.

3. Резерв времени события R(T) = t_п(i) - t_р(i) показывает, на какой максимальный срок можно задержать наступление этого события, не вызывая при этом увеличения срока выполнения всего комплекса работ.

Резервы времени для событий на критическом пути равны нулю, R(i) = 0.

Характеристики работы (i,j)

Ранний срок начала работы: .

Ранний срок окончания работы:

Поздний срок начала работы:

Поздний срок окончания работы:

Резервы времени работ:

* полный резерв - максимальный запас времени, на который можно отсрочить начало или увеличить длительность работы без увеличения длительности критического пути. Работы на критическом пути не имеют полного резерва времени;

* частный резерв - часть полного резерва, на которую можно увеличить продолжительность работы, не изменив позднего срока ее начального события;

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

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

Замечания. Работы, лежащие на критическом пути, резервов времени не имеют. Если на критическом пути L_кр лежит начальное событие i работы (i,j), то R_п(i,j)=R_l(i,j). Если на L_кр лежит конечное событие j работы (i,j), то R_п(i,j)=R_c(i,j). Если на L_кр лежат и событие i, и событие j работы (i,j), а сама работа не принадлежит критическому пути, то R_п(i,j)=R_c(i,j)=R_п(i,j)

Характеристики путей

Продолжительность пути равна сумме продолжительностей составляющих ее работ.

Резерв времени пути равен разности между длинами критического пути и рассматриваемого пути.

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

В сетевой модели можно выделить так называемый критический путь. Критический путь L_кр состоит из работ (i,j), у которых полный резерв времени равен нулю R_п(i,j)=0, кроме этого, резерв времени R(i) всех событий i на критическом равен 0. Длина критического пути определяет величину наиболее длинного пути от начального до конечного события сети и равна . Заметим, что в проекте может быть несколько критических путей.

3. Коэффициент напряженности работ

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

где t(L_тах(i,j)) - продолжительность максимального пути проходящего через работу (i,j);

t'_кр - продолжительность отрезка пути L_тах(i,j), совпадающего с критическим путем.

Видно, что К_н(i,j) < 1. Чем ближе К_н(i,j) к 1, тем сложнее выполнить данную работу в установленный срок. Напряженность критических работ полагается равной 1. Все работы сетевой модели могут быть разделены на 3 группы: напряженные (К_н(i,j) > 0,8), надкритические (0,6 < К_н(i,j) < 0,8) и резервные (К_н(i,j) < 0,6).

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

2. Анализ проектов. Метод CPM

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

Работа	Непосредственно предшествующая работа	Время выполнения
A	-	tA
B	-	tB
C	B	tC
D	A, C	tD

В первом столбце указаны наименования всех работ проекта. Их четыре: A, B, C, D. Во втором столбце указаны работы, непосредственно предшествующие данной. У работ A и B нет предшествующих. Работе C непосредственно предшествует работа B. Это означает, что работа C может быть начата только после того, как завершится работа B. Работе D непосредственно предшествуют две работы: A и C. Это означает, что работа D может быть начата только после того, как завершатся работы A и C. В третьем столбце таблицы для каждой работы указано время ее выполнения. На основе этой таблицы может быть построено следующее графическое описание проекта.

Из приведенных выше определений и соотношений непосредственно следует:

1) Длина критического пути равна T.

2) Если R(i,j) = 0, то работа (i,j) лежит на критическом пути; если R(i,j)?0, то работа (i,j) не лежит на критическом пути.

3) Если время начала работы (i,j), которая не лежит на критическом пути, отложить на срок меньший, чем r(i,j), то наиболее раннее время наступления последующего события не изменится.

4) Если время начала работы (i,j), которая не лежит на критическом пути, отложить на срок меньший, чем R(i,j), то время, необходимое на выполнение всего проекта, не увеличится.

Контрольные вопросы.

1. Правила построения сетевых графиков.

2. Определение пути в сетевом графике, виды путей, важность определения критического пути.

3. Какова взаимосвязь полного и свободного резервов работы?

4. Как можно найти критических путь в сетевой модели, без непосредственного суммирования длительностей работ?

5. Чему равно наиболее раннее время наступления события?

6. Метод CPM разработан для ...

§ описания проектов, путем указания всех работ, предшествующих данной работе;

§ описания проектов, путем представления каждой работы в виде пары узлов сети;

§ минимизации издержек на сокращение продолжительности проекта;

§ нахождения критического пути для проектов с заданным временем выполнения каждой работы;

§ нахождения критического пути для проектов с неопределенным временем выполнения работ.

3. Варианты заданий по теме «Метод CPM»

Вариант 1

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

Дисциплина	Непосредственно предшествующая дисциплина	Время изучения в днях
A	-	4
B	-	6
C	A	2
D	A	6
E	C, B	3
F	C, B	3
G	D, E	5

Найдите:

§ минимальное время, за которое можно выполнить программу;

§ длину критического пути;

§ количество дисциплин находящихся на критическом пути;

§ резерв времени изучения дисциплины F.

Вариант 2

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

Работа	Непосредственно предшествующая работа	Время выполнения
A	-	4
B	-	6
C	-	5
D	B	2
E	A	9
F	B	4
G	C, D	8
H	B, E	3
I	F, G	5
J	H	7

Постройте графическое представление проекта.

Найдите:

§ длину критического пути;

§ сколько работ находится на критическом пути;

§ резерв выполнения работы F.

Вариант 3

Рассмотрите следующую сеть проекта (продолжительность работ показана в неделях):

Работа	Непосредственно предшествующая работа	Время выполнения
A	-	5
B	-	3
C	A	7
D	A	6
E	B	7
F	D, E	3
G	D, E	10
H	C, F	8

Найдите:

§ за какое минимальное время может быть выполнен проект;

§ сколько работ находится на критическом пути;

§ на сколько недель можно отложить выполнение работы D без отсрочки завершения проекта в целом;

§ на сколько недель можно отложить выполнение работы С без отсрочки завершения проекта в целом.

Вариант 4

Проект пусконаладки компьютерной системы состоит из восьми работ. Непосредственно предшествующие работы и продолжительность выполнения работ показаны ниже.

Работа	Непосредственно предшествующая работа	Время выполнения
A	-	3
B	-	6
C	A	2
D	B, C	5
E	D	4
F	E	3
G	B, C	9
H	F, G	3

Найдите:

§ критический путь;

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

§ сколько работ на критическом пути;

§ чему равно наиболее раннее время начала работы C;

§ на сколько можно отложить выполнение работы C без отсрочки завершения проекта в целом;

§ чему равно наиболее позднее время окончания работы F;

§ на сколько можно отложить выполнение работы F без отсрочки завершения проекта.

Вариант 5

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

Работа	Содержание работы	Непосредственно предшествующая работа	Время выполнения (недель)
A	Определить место строительства	-	6
B	Разработать первоначальный проект	-	8
C	Получить разрешение на строительство	A, B	12
D	Выбрать архитектурную мастерскую	C	4
E	Разработать смету затрат на строительство	C	6
F	Разработать проект строительства	D, E	15
G	Получить финансирование	E	12
H	Нанять подрядчика	F, G	8

Найдите:

§ критический путь;

§ сколько работ находится на критическом пути (фиктивные работы не учитываются);

§ через какое минимальное время после принятия решения о реализации проекта можно начать работу по строительству библиотеки;

§ на сколько недель можно отложить выбор архитектурной мастерской;

§ чему равно наиболее позднее время завершения работы по обеспечению финансирования.

4. Анализ проектов. Метод PERT

Для того, чтобы использовать метод PERT, для каждой работы i, время выполнения которой является случайной величиной, необходимо определить следующие три оценки:

Оптимистическое время - время выполнения работы i в наиболее благоприятных условиях.

Наиболее вероятное время - время выполнения работы i в нормальных условиях.

Пессимистическое время - время выполнения работы i в неблагоприятных условиях.

Учитывая, что время выполнения работы хорошо описывается бета - распределением, среднее или ожидаемое время t_i выполнения работы i может быть определено по формуле

Если время выполнения работы i известно точно и равно, то

Располагая указанными выше тремя оценками времени выполнения работы, мы можем также рассчитать общепринятую статистическую меру неопределенности - дисперсию или вариацию var_i времени выполнения работы i:

Если время выполнения работы i известно точно, то = var_i = 0.

Пусть Т - время, необходимое для выполнения проекта. Если в проекте есть работы с неопределенным временем выполнения, то время Т является случайной величиной. Математическое ожидание (ожидаемое значение) времени выполнения проекта Е(Т) равно сумме ожидаемых значений времени выполнения работ, лежащих на критическом пути. Для определения критического пути проекта может быть использован метод CPM. На этом этапе анализа проекта время выполнения работы полагается равным ожидаемому времени t_i. Вариация (дисперсия) общего времени, требуемого для завершения проекта, в предположении о независимости времен выполнения работ равна сумме вариаций работ критического пути. Если же две или более работы взаимозависимы, то указанная сумма дает приближенное представление о вариации времени завершения проекта.

Распределение времени T завершения проекта является ассимптотически нормальным со средним Е(Т) и дисперсией (T). С учетом этого можно рассчитать вероятность завершения проекта в установленный срок T0. Для определения вероятности того, что T?T0, следует использовать таблицу распределения величины z=(T0-E(T))/(T), которая имеет стандартное нормальное распределение.

Пример 1.

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

Работа	Содержание работы	Непосредственно предшествующая работа	Оптимистическое время ai	Наиболее вероятное время mi	Пессимистическое время bi
A	Подготовить конструкторский проект	-	4	5	12
B	Разработать маркетинговый план	-	1	1,5	5
C	Подготовить маршрутные карты	A	2	3	4
D	Построить прототип	A	3	4	11
E	Подготовить рекламную брошюру	A	2	3	4
F	Подготовить оценки затрат	C	1.5	2	2.5
G	Провести предварительно тестирование	D	1.5	3	4.5
H	Выполнить исследование рынка	B, E	2.5	3.5	7.5
I	Подготовить доклад о ценах	H	1.5	2	2.5
J	Подготовить заключительный доклад	F,G,I	1	2	3

1. Определите критический путь для данного проекта.

2. Чему равно ожидаемое время выполнения проекта?

3. С какой вероятностью проект может быть выполнен за 20 недель.

На следующем рисунке показано графическое представление этого проекта.

Решение.

Используя информацию, указанную в таблице, определим ожидаемое время и вариацию времени выполнения каждой работы проекта. Например, для работы A:

t_A = (a_A + 4 m_A + b_A)/6 = (4 + 4 * 5 + 12)/6 = 6 ;

= var_A = ((b_A - a_A )/6 )² = ((12 - 4)/6)² = 1.78.

Проводя аналогичные расчеты для других работ, получаем следующую таблицу.

Работа	Ожидаемое время ti	Дисперсия	Непосредственно предшествующая работа
A	6	1.78	-
B	2	0.44	-
C	3	0.11	A
D	5	1.78	A
E	3	0.11	A
F	2	0.03	C
G	3	0.25	D
H	4	0.69	B, E
I	2	0.03	H
J	2	0.11	F,G,I

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

Результаты расчетов представлены в следующей таблице.

Работа	Время выполнения	tрн	tро	tпн	tпо	Дисперсия	R
A	6	0	6	0	6	1.78	0
B	2	0	2	7	9	0.44	7
C	3	6	9	10	13	0.11	4
D	5	6	11	7	12	1.78	1
E	3	6	9	6	9	0.11	0
F	2	9	11	13	15	0.03	4
G	3	11	14	12	15	0.25	1
H	4	9	13	9	13	0.69	0
I	2	13	15	13	15	0.03	0
J	2	15	17	15	17	0.11	0

Критический путь для данного проекта включает работы A, E, H, I, J. Длина критического пути равна 6 + 3 + 4 + 2 + 2 = 17. Это означает, что ожидаемое время выполнения проекта составляет 17 недель.

Предполагая, что распределение времени выполнения проекта является нормальным, мы можем определить вероятность того, что проект будет выполнен за 20 недель. Определим дисперсию времени выполнения проекта. Ее значение равно сумме значений дисперсий времен выполнения работ на критическом пути: ²(T)= 1.78+ 0.11 + 0.69 + 0.03 +0.11 = 2.72. Тогда, учитывая, что (T) = 1.65, находим значение z для нормального распределения при T0=20:

z = (T0-E(T))/ (T) = (20-17) /1.65 = 1.82.

Используя таблицу нормального распределения, находим вероятность того, что время T выполнения проекта находится в интервале E(T)??T??T0. На пересечении столбца «1.8» и строки «0.02» таблицы нормального распределения находим значение 0.4656. Следовательно, искомая вероятность того, что время T выполнения проекта находится в интервале 0???T?T0, т.е. вероятность того, что проект будет выполнен за 20 недель при ожидаемом времени его выполнения 17 недель, равна 0.5 + 0.4656 = 0.9656.

Контрольные вопросы.

1. Метод PERT разработан для:

а. описания проектов, путем указания всех работ, предшествующих данной работе

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

в. минимизации издержек на сокращение продолжительности проекта

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

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

2. Объясните суть оптимизации сетевых моделей по критерию «Время - затраты».

3. Какими свойствами должна обладать работа, выбираемая на конкретном шаге для сокращения?

5. Варианты заданий по теме «Метод PERT»

Вариант 1

Ниже даны оценки продолжительности выполнения работ (в днях) применительно к небольшому проекту:

Работа	Оптимистическое время аi	Наиболее вероятное время mi	Пессимистическое время bi
A	4	5	6
B	8	9	10
C	7	7.5	11
D	7	9	10
E	6	7	9
F	5	6	7

Рассчитайте ожидаемое время выполнения и дисперсию для каждой работы. Известно, что критический путь составляют работы B, D, F.

Найдите:

§ чему равно ожидаемое время выполнения работы B;

§ чему равна дисперсия времени выполнения работы D;

§ ожидаемое время выполнения проекта;

§ чему равна дисперсия времени выполнения проекта.

Вариант 2

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

Работа	Непосредственно предшествующая работа	Оптимистическое время аi	Наиболее вероятное время mi	Пессимистическое время bi
A	-	3	5	6
B	-	2	4	6
C	A, B	5	6	7
D	A, B	7	9	10
E	B	2	4	6
F	C	1	2	3
G	D	5	8	10
H	D, F	6	8	10
I	E, G, H	1	4	5

Постройте сеть для этого проекта.

Найдите:

§ каков ожидаемый срок завершения проекта;

§ чему равна стандартная ошибка (корень квадратный из дисперсии) времени завершения проекта;

§ какова вероятность того, что проект будет выполнен за 24 рабочих дня.

Вариант 3

Рассмотрите следующий проект (оценки времени выполнения работ указаны в неделях).

Работа	Непосредственно предшествующая работа	Оптимистическое время ai	Наиболее вероятное время mi	Пессимистическое время bi
A	-	4	5	6
B	-	2.5	3	3.5
C	A	6	7	8
D	A	5	5.5	9
E	B	5	7	9
F	D, E	2	3	4
G	D, E	8	10	12
H	C, F	6	7	14

Найдите:

§ какова ожидаемая продолжительность проекта;

§ какова вероятность того, что проект будет завершен за 21 неделю;

§ какова вероятность того, что проект будет завершен за 25 недель.

6. Оптимизация сетевых моделей по критерию «время-затраты»

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

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

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

6.1. Методика оптимизации сетевых моделей по критерию «Время - затраты»

Целью оптимизации по критерию «Время - затраты» является сокращение времени выполнения проекта в целом. Эта оптимизация имеет смысл только в том случае, когда время выполнения работ может быть уменьшено за счет задействования дополнительных ресурсов, что приводит к повышению затрат на выполнение работ (см. Рисунок 1). Для оценки величины дополнительных затрат, связанных с ускорением выполнения той или иной работы, используются либо нормативы, либо данные о выполнении аналогичных работ в прошлом. Под параметрами работ и понимаются так называемые прямые затраты, непосредственно связанные с выполнением конкретной работы. Таким образом, косвенные затраты типа административно-управленческих в процессе сокращения длительности проекта во внимание не принимаются, однако их влияние учитывается при выборе окончательного календарного плана проекта.

Рисунок 1. Зависимость прямых затрат на работу от времени ее выполнения

Важными параметрами работы (i,j) при проведении данного вида оптимизации являются:

коэффициент нарастания затрат

,

который показывает затраты денежных средств, необходимые для сокращения длительности работы (i,j) на один день;

запас времени для сокращения длительности работы в текущий момент времени ,

где t_T(i,j) - длительность работы (i,j) на текущий момент времени, максимально возможное значение запаса времени работы равно

.

Эта ситуация имеет место, когда длительность работы (i,j) еще ни разу не сокращали, т.е. .

Общая схема проведения оптимизации «время-затраты»

1. Исходя из нормальных длительностей работ , определяются критические L_kp и подкритические L_п пути сетевой модели и их длительности T_kp и T_п.

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

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

Для сокращения выбирается критическая работа с min коэффициентом нарастания затрат k(i,j), имеющая ненулевой запас времени сокращения Z_T(i,j).

Время , на которое необходимо сжать длительность работы (i,j), определяется как

,

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

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

.

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

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

6.2 Пример проведения оптимизации сетевой модели по критерию «Время - затраты»

Проведем максимально возможное уменьшение сроков выполнения проекта при минимально возможных дополнительных затратах для следующих исходных данных (табл.1, Рисунок 2).

Таблица 1

Исходные данные для оптимизации «Время-затраты»

(i,j)	Нормальный режим	Ускоренный режим
	Tн(i,j)	Сн(i,j)	Tу(i,j)	Сп(i,j)
(1,2)	5	5	3	19
(1,4)	6	6	4	12
(2,3)	3	8	1	15
(2,4)	7	10	3	18
(3,5)	6	6	1	9
(4,5)	4	9	1	12
Ск=1,50 руб./день	С0=73,00 руб.

Рисунок 2. Исходная сетевая модель

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

Общие затраты на проект руб.

Длительность проекта дней.

Критический путь или .

Подкритический путь или , дней.

Кроме того, вычислим коэффициенты нарастания затрат и максимальные запасы времени сокращения работ сетевой модели (таблица 2).

Таблица 2

Коэффициенты нарастания затрат работ сети

(i,j)	Zmax(i,j) [дни]	k(i,j) [руб./день]
(1,2)	2	7,00
(1,4)	2	3,00
(2,3)	2	3,50
(2,4)	4	2,00
(3,5)	5	0,60
(4,5)	3	1,00



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

I шаг. Для сокращения выбираем критическую работу (4,5) с минимальным коэффициентом k(4,5)=1,00 руб./день. Текущий запас сокращения времени работы (4,5) на данном шаге равен дня. Разность между продолжительностью критического и подкритического путей дня. Поэтому согласно п.3.2 описанной выше общей схеме оптимизации сокращаем работу (4,5) на ?t¹=min[3,2]=2 дня. Новая текущая длительность работы дня, а запас ее дальнейшего сокращения сокращается до дня. Измененный сетевой график представлен на рисунке 3

После ускорения работы (4,5) возникли следующие изменения.

Затраты на работу возросли на 1,00руб./день*2дня=2,00 руб. и общие затраты на проект составили руб.

Длительность проекта дней.

Критические пути и .

Подкритический путь , дней.

II шаг. Одновременное сокращение двух критических путей можно провести либо ускорив работу (1,2), принадлежащую обоим путям, либо одновременно ускорив различные работы из каждого пути. Наиболее дешевым вариантом является ускорение работ (3,5) и (4,5) - 1,60 руб./день за обе работы, тогда как ускорение работы (1,2) обошлось бы в 7 руб./день. Поскольку , то сокращаем работы (3,5) и (4,5) на ?t²=min[5,1,6]=1 день. Запасы дальнейшего сокращения времени работ сокращаются до и дней. Измененный сетевой график представлен на Рисунок 4.

Рисунок 4. Сетевая модель после второго шага оптимизации

После ускорения работ (3,5) и (4,5) возникли следующие изменения.

Общие затраты на проект составили

руб.

Длительность проекта дней.

Два критических пути и .

Подкритический путь , дней.

III шаг. Поскольку на данном шаге работа (4,5) исчерпала свой запас ускорения, то наиболее дешевым вариантом сокращения обоих критических путей является ускорение работ (3,5) и (2,4) - 2,60 руб./день за обе работы. Сокращаем работы (3,5) и (2,4) на ?t³=min[4,4,6]=4 дня. Запасы дальнейшего сокращения времени работ (3,5) и (2,4) обнуляются. Измененный сетевой график представлен на Рисунок5.



Рисунок 5. Сетевая модель после третьего шага оптимизации

После ускорения работ (3,5) и (2,4) возникли следующие изменения.

Общие затраты на проект составили

руб.

Длительность проекта дней.

Два критических пути и .

Подкритический путь , дней.

IV шаг. Поскольку кроме работы (1,2) все остальные работы критического пути исчерпали свой запас времени ускорения, то единственно возможным вариантом сокращения обоих критических путей является ускорение работы (1,2). Сокращаем работу (1,2) на дня. Запас дальнейшего сокращения времени работы (1,2) обнуляется. Измененный сетевой график представлен на Рисунок 6.

Рисунок 6. Сетевая модель после четвертого шага оптимизации



Рисунок 7 График время-затраты

После ускорения работы (1,2) возникли следующие изменения.

Общие затраты на проект составили руб.

Длительность проекта дней.

Три критических пути , и .

Подкритические пути отсутствуют.

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

Таким образом, при отсутствии ограничений на затраты минимально возможная длительность проекта составляет 7 дней. Сокращение длительности проекта с 16 до 7 дней потребовало 28,00 рублей прямых затрат. В отличие от прямых затрат при уменьшении продолжительности проекта косвенные затраты (С_к=1,50 руб./день) убывают, что показано на графике (см. Рисунок 7). Минимум общих затрат (точка А) соответствует продолжительности проекта 14 дней.

Если же учитывать ограничение по средствам, выделенным на выполнение проекта, С₀=73,00 рубля, то оптимальным является выполнение проекта за 9 дней (точка B).

7. Варианты заданий по теме «Оптимизация сетевых моделей по критерию «Время-затраты»

Задание

Имеются следующие исходные данные: С_н(i,j) - стоимость выполнения работы (i,j), имеющей нормальную продолжительность Т_н(i,j); Т_у(i,j) - время ускоренного выполнения работы (i,j); C_п(i,j) - повышенную стоимость выполнения работы (i,j), имеющей ускоренную продолжительность;С_к - ежедневные косвенные затраты организации, выполняющей проект; С₀ - ограничение по средствам, выделенным на проведение оптимизации. Проведите максимально возможное сокращение времени выполнения проекта с учетом заданного ограничения на денежные средства С₀, отобразите принятое решение на графике затрат.

Вариант 1

Назв. работы	Норм. длительность	Норм. стоимость	Сокр. длительность	Повыш. стоимость
A	8	8	3	10
B	6	3	2	5
C	6	4	1	5
D	8	5	7	7
E	3	5	2	7
F	4	10	1	12
G	7	12	3	17
H	7	4	2	10
I	12	7	8	11
J	9	6	6	9
K	5	3	3	6
	С0=99,00 руб.	Ск=1,20 руб./день

Упорядочение работ

A,E и F - исходные работы проекта, которые можно начинать одновременно;

Работы B и I начинаются сразу по окончании работы F;

Работа J следует за E, а работа C - за A;

Работы H и D следуют за B, но не могут начаться, пока не завершена C;

Работа K следует за I;

Работа G начинается после завершения H и J.

Вариант 2

Назв. работы	Норм. длительность	Норм. стоимость	Сокр. длительность	Повыш. стоимость
A	3	7	1	8
B	4	5	2	8
C	1	8	1	8
D	4	8	1	12
E	5	9	3	11
F	7	10	2	13
G	6	10	2	12
H	5	8	2	9
I	8	10	4	22
	С0=100,00 руб.	Ск=0,90 руб./день

Упорядочение работ

D - исходная работа проекта;

Работа E следует за D;

Работы A, G и C следуют за E;

Работа B следует за A;

Работа H следует за G;

Работа F следует за C;

Работа I начинается после завершения B, H, и F.

Вариант 3

Назв. работы	Норм. длительность	Норм. стоимость	Сокр. длительность	Повыш. стоимость
A	5	13	1	14
B	5	11	2	13
C	4	15	2	17
D	7	14	4	15
E	12	18	6	25
F	3	8	2	10
G	6	16	1	29
H	2	9	1	10
I	8	14	3	18
J	3	5	1	7
	С0=143,00 руб.	Ск=0,60 руб./день

Упорядочение работ

С, E и F - исходные работы проекта, которые можно начинать одновременно;

Работа A начинается сразу по окончании работы С;

Работа H следует за F;

Работа I следует за A, а работы D и J - за H;

Работа G следует за E, но не может начаться, пока не завершены D и I;

Работа B следует за G и J.

ПРИЛОЖЕНИЕ

Таблица нормального распределения.

z 0.00 0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 0.09
0.0¦ .0000 .0040 .0080 .0120 .0160 .0199 .0239 .0279 .0319 .0359
0.1¦ .0398 .0438 .0478 .0517 .0557 .0596 .0636 .0675 .0714 .0753
0.2¦ .0793 .0832 .0871 .0910 .0948 .0987 .1026 .1064 .1103 .1141
0.3¦ .1179 .1217 .1255 .1293 .1331 .1368 .1406 .1443 .1480 .1517
0.4¦ .1554 .1591 .1628 .1664 .1700 .1736 .1772 .1808 .1844 .1879
0.5¦ .1915 .1950 .1985 .2019 .2054 .2088 .2123 .2157 .2190 .2224
0.6¦ .2257 .2291 .2324 .2357 .2389 .2422 .2454 .2486 .2518 .2549
0.7¦ .2580 .2612 .2642 .2673 .2704 .2734 .2764 .2794 .2823 .2852
0.8¦ .2881 .2910 .2939 .2967 .2995 .3023 .3051 .3078 .3106 .3133
0.9¦ .3159 .3186 .3212 .3238 .3264 .3289 .3315 .3340 .3365 .3389
1.0¦ .3413 .3438 .3461 .3485 .3508 .3531 .3554 .3577 .3599 .3621
1.1¦ .3643 .3665 .3686 .3708 .3729 .3749 .3770 .3790 .3810 .3830
1.2¦ .3849 .3869 .3888 .3907 .3925 .3944 .3962 ,3980 .3997 .4015
1.3¦ .4032 .4049 .4066 .4082 .4099 .4115 .4131 .4147 .4162 .4177
1.4¦ .4192 .4207 .4222 .4236 .4251 .4265 .4279 .4292 .4306 .4319
1.5¦ .4332 .4345 .4357 .4370 .4382 .4394 .4406 .4418 .4429 .4441
1.6¦ .4452 .4463 .4474 .4484 .4495 .4505 .4515 .4525 .4535 .4545
1.7¦ .4554 .4564 .4573 .4582 .4591 .4599 .4608 .4616 .4625 .4633
1.8¦ .4641 .4649 .4656 .4664 .4671 .4678 .4686 .4693 .4699 .4706
1.9¦ .4713 .4719 .4726 .4732 .4738 .4744 .4750 .4756 .4761 .4767
2.0¦ .4772 .4778 .4783 .4788 .4793 .4798 .4803 .4808 .4812 .4817
2.1¦ .4821 .4826 .4830 .4834 .4838 .4842 .4846 .4850 .4854 .4857
2.2¦ .4861 .4864 .4868 .4871 .4875 .4878 .4881 .4884 .4887 .4890
2.3¦ .4893 .4896 .4898 .4901 .4904 .4906 .4909 .4911 .4913 .4916
2.4¦ .4918 .4920 .4922 .4925 .4927 .4929 .4931 .4932 .4934 .4936
2.5¦ .4938 .4940 .4941 .4943 .4945 .4946 .4948 .4949 .4951 .4952
2.6¦ .4953 .4955 .4956 .4957 .4959 .4960 .4961 .4962 .4963 .4964
2.7¦ .4965 .4966 .4967 .4968 .4969 .4970 .4971 .4972 .4973 .4974
2.8¦ .4974 .4975 .4976 .4977 .4977 .4978 .4979 .4979 .4980 .4981
2.9¦ .4981 .4982 .4982 .4983 .4984 .4984 .4985 .4985 .4986 .4986
3.0¦ .4986 .4987 .4987 .4988 .4988 .4989 .4989 .4989 .4990 .4990