Задание № 4. Задача сетевого планирования и управления

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

Таблица 4.1

Работа	A	B	C	D	E	F	G	H
Непосредственно предшествующие работы	-	A	-	C	B,D	C	E,F	C
Время выполнения (нед.)	2	3	4	3	2	4	3	6
Затраты на выполнение (тыс.грн.)	6	4	15	18	30	20	2	12

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

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

Вопросы:

1. За какое минимальное время может быть выполнен проект?

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

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

4. Какова величина недостатка или перерасхода средств в кон­це четвертой недели, если фактические затраты в этот мо­мент составили 35 тыс. грн.?

Решение

Чтобы решить данную задачу, сначала составляется сетевой график. Из начальной вершины выходят две работы (А и С), так как им не предшествуют никакие работы. Работа В начинается после того, как закончена работа А, а работы D и F - после того, как завершена работа С, т.е. в одной вершине. Две или несколько работ, предшествующих одной работе, свидетельствует о том, что эти несколько работ заканчиваются в одной вершине.

Сетевой график нашего проекта (рис.5.1) будет выглядеть следующим образом:

_{B E}

^{А G}

s ^{C D F} f

^H

Рис.5.1

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

Таблица 5.2

Работа	Непосредственно предшествующие работы	Время выполнения (нед)	Время наиболее раннего		Время наиболее позднего		Полный резерв времени	Общие затраты на выполнение (тыс.грн.)	Удельные затраты на выполнение (тыс.грн./ нед.)
			начала	окончания	начала	окончания
A	-	2	0	2	2	4	2	6	3
B	A	3	2	5	4	7	2	4	4/3 ≈ 1,33
C	-	4	0	4	0	4	0	15	15/4 = 3,75
D	C	3	4	7	4	7	0	18	6
E	B,D	2	7	9	7	9	0	30	15
F	C	4	4	8	5	9	1	20	5
G	E,F	3	9	12	9	12	0	2	2/3 ≈ 0,67
H	C	6	4	10	6	12	2	12	2

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

1. Определяют наиболее раннее время начала и окончания каждого вида работы. Например, t_рн(1,2) = t_рн(А) = t_рн(1,3) = t_рн(С) = 0, так как для любой работы, которая начинается в начальной вершине t_рн(s, j) = 0. Время наиболее раннего окончания работы определяют, прибавляя ко времени начала время выполнения самой работы:

t_ро(А) = 0 + 2 = 2 (нед.), t_ро(С) = 0 + 4 = 4 (нед.).

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

t_рн(В) = t_ро(А) = 2 (нед.); t_рн(D) =t_рн(F) =t_рн(H) =t_ро(С) = 4 (нед.).

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

t_рн(Е) = max {t_ро(B),t_ро(D)} = max {5, 7} = 7 (нед.);

t_рн(G) = max {t_ро(E),t_ро(F)} = max {9, 8} = 9 (нед.).

2. Из наиболее ранних времен окончания работ выбираем наибольшее t_ро(G) = 12 (нед.).

3. Это время является временем наиболее позднего окончания тех работ, которые заканчиваются в последней вершине, т.е. H и G:

t_по(G) = t_по(H) = 12 (нед.).

6. Порядок заполнения следующих двух столбцов (наиболее позднее время начала и окончания) обратный: сначала определяют время окончания работы, а затем вычитая время выполнения самой работы, находят время ее начала. Например, t_пн(G) = 12 - 3 = 9 (нед.); t_пн(H) = 12 – 6 = 6 (нед.).

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

t_по(Е) = t_по(F) = t_пн(G) = 9 (нед.); t_по(В) = t_по(D) = t_пн(Е) = 7 (нед.)

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

t_по(С) = min {t_пн(D), t_пн(F), t_пн(H)} = min {4, 5, 6} = 4 (нед.).

7. Длина критического пути равна наиболее раннему времени завершения проекта или наиболее позднему времени окончания любой работы, завершающей проект: Т = t_ро(G) = t_по(G) = t_по(H) = 12 (нед.).

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

R(А) = 2 – 0 = 4 – 2 = 2 (нед.);

R(G) = 12 – 12 = 9 – 9 = 0 (нед.).

10. Те работы, для которых полный резерв времени равен нулю, лежат на критическом пути. Это работы C, D, E, G (рис.5.1). Длина критического пути равна также сумме выполнения работ, лежащих на критическом пути

Т = t(С) + t(D) + t(E) + t(G) = 4 + 3 + 2 + 3 = 12 (нед.).

Чтобы ответить на вопросы 2 – 4, необходимо определить динамику совокупных затрат для графика выполнения проекта с наиболее ранним (табл. 5.3) и наиболее поздним (табл.5.4) началом всех работ.

Таблица 5.3

Неделя Работа	1	2	3	4	5	6	7	8	9	10	11	12
A	3	3
B			1,33	1,33	1,33
C	3,75	3,75	3,75	3,75
D					6	6	6
E								15	15
F					5	5	5	5
G										0,67	0,67	0,67
H					2	2	2	2	2	2
Затраты в неделю, тыс.грн.	6,75	6,75	5,08	5,08	14,33	13	13	22	17	2,67	0,67	0,67
Общие затраты, тыс.грн	6,75	13,5	18,58	23,66	37,99	50,99	63,99	85,99	102,99	105,66	106,33	107

Таблица 5.4

Неделя Работа	1	2	3	4	5	6	7	8	9	10	11	12
A			3	3
B					1,33	1,33	1,33
C	3,75	3,75	3,75	3,75
D					6	6	6
E								15	15
F						5	5	5	5
G										0,67	0,67	0,67
H							2	2	2	2	2	2
Затраты в неделю, тыс.грн.	3,75	3,75	6,75	6,75	7,33	12,33	14,33	22	22	2,67	2,67	2,67
Общие затраты, тыс.грн	3,75	7,5	14,25	21	28,33	40,66	54,99	76,99	98,99	101,66	104,33	107

Пользуясь полученными выше результатами вычислений и таблицами 5.3 и 5.4, ответим на поставленные вопросы.

Ответы на вопросы:

1. Минимальное время выполнения проекта Т = 12 (нед.).

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

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

4. Величина перерасхода средств в кон­це четвертой недели, так как фактические затраты в этот мо­мент составили 35 тыс. грн., составляет

35 – 23,66 = 11,34 тыс.грн..