Методы сетевого планирования и управления в исследовании социально-экономических и политических процессов

 

R1(i,j) = tп(j) – tп(i) – t(i,j)        (11)

или

R1(i,j) = Rп(i,j) – R(i).         (12)

Частный резерв времени второго вида или свободный резерв времени Rс(i,j) работы (i,j) представляет часть полного резерва времени, на которую можно увеличить продолжительность работы, не изменяя при этом раннего срока ее конечного события. Этим резервом можно располагать при выполнении данной работы в предположении, что ее начальное и конечное события свершаются в свои самые ранние сроки (рисунок 11, в).

Rс(i,j) находится по формуле

 

Rс(i,j) = tр(j) – tp(i) – t(i,j)        (13)

или

Rс(i,j) = Rп(i,j) – R(j).         (14)

 

Рисунок 11 – Графическое изображение резервов времени событий и работ

 

Независимый резерв времени Rн работы (i,j) есть часть полного резерва времени, получаемая для случая, когда все предшествующие работы заканчиваются в поздние сроки, а все последующие работы начинаются в ранние сроки (рисунок 11, г):

 

Rн(i,j) = tр(j) – tn(i) – t(i,j)        (15)

или

Rн (i,j) = Rn (i,j) – R(i) – R(j).        (16)

 

Независимые резервы стремятся использовать тогда, когда окончание предыдущей работы произошло в поздний допустимый срок, а последующие работы хотят выполнить в ранние сроки. Если величина независимого резерва, определяемая формулами (15) или (16), равна нулю или положительна, то такая возможность есть. Отрицательное значение Rн (i,j) не имеет реального смысла, так как в этом случае (i,j) работа еще не оканчивается, а последующая уже должна начаться. Фактически независимый резерв имеют лишь те работы, которые не лежат на максимальных путях, проходящих через их начальные и конечные события.

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

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

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

Резерв времени пути R(L) определяется как разность между длиной критического и рассматриваемого пути:

 

R(L) = tkp – t(L).          (17)

 

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

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

Вычислим в качестве примера временные параметры работ для рассматриваемого сетевого графика (см. рисунок 10). Результаты расчетов сведем в таблицу 4.

Вычисление временных параметров работы (i,j) покажем на примере работы (2,4).

Ранний срок начала работы (по формуле (6)): tpн(2,4) = tp(2) = 13(суток); ранний срок окончания работы (по формуле (7)): tpo(2,4) = tp(2) + t(2,4) = 13+10 = 23 (суток); поздний срок начала работы по формуле (9)): tпн(2,4) = tп(4) – t(2,4) = 23 - 10 = 13 (суток); поздний срок окончания работы (по формуле (8)): tпо(2,4) = tп(4) = 23 (суток).

Таким образом, работа (2,4) должна начинаться в интервале [13;13] (суток) и окончиться в интервале [23;23] (суток) от начала выполнения проекта.

Полный резерв работы (2,4) определяется по формуле (10): Rп(2,4) = tп(4) – tр(2) – t(2,4) = 23 – 13 - 10 = 0 (суток).

 

Таблица 4 – Временные параметры работ для сетевого графика, сутки

В сутках

Работа (i,j)	Про-должительность работы t(i,j)	Срок начала и окончания работы				Резерв времени работы
		tрн(i,j)	tро(i,j)	tпн(i,j)	tпо(i,j)	Rп(i,j)	R1(i,j)	Rc(i,j)	Rн(i,j)
(1,2) (1,3) (1,4) (2,7) (2,4) (3,5) (3,7) (4,6) (4,7) (6,7) (6,8) (5,9) (5,7) (7,8) (8,9) (8,10) (9,10)	13 4 5 12 10 7 7 1 3 1 7 6 2 5 7 4 3	0 0 0 13 13 4 4 23 23 24 24 11 11 26 31 31 38	13 4 5 25 23 11 11 24 26 25 31 17 13 31 38 35 41	13 17 23 26 23 24 26 24 26 26 31 38 26 31 38 41 41	0 13 18 14 13 17 19 23 23 24 24 32 24 26 31 37 38	0 13 18 1 0 13 15 0 0 1 0 21 13 0 0 6 0	0 13 18 1 0 0 2 0 0 1 0 8 0 0 0 6 0	0 0 18 1 0 0 15 0 0 1 0 21 13 0 0 6 0	0 0 18 1 0 - 2 0 0 1 0 8 0 0 0 6 0

 

Частный резерв времени первого вида определяется по формуле (11): R1(2,4) = tп(4) – tп(2) – t(2,4) = 23-13-10 = 0 (суток)  или по формуле (12): R1(2,4) = Rп(2,4) – R(2) = 0 - 0 = 0 (суток), т.е. при сохранении общего срока выполнения проекта не может быть задержано выполнение работы (2,4) и последующих работ без затрат резерва времени предшествующих ей работ (в данном случае без затрат резерва времени одной предшествующей           работы (1,2)).

Частный резерв времени второго вида, или свободный резерв времени, работы (2,4) найдем по формуле (13) или (14): Rс(2,4) = tр(4) – tр(2) – t(2,4) =    = 23-13-10 = 0 (суток) или Rс(2,4) = Rп(2,4) – R(4) = 0 – 0 = 0 (суток), т.е. при сохранении общего срока выполнения проекта не может быть задержано выполнение работы (2,4) и предшествующих ей работ (в данном случае   работы (1,2)) без нарушения резерва времени последующих работ.

Независимый резерв времени работы (2,4) определим по формуле (15) или (16): Rн(2,4) = tр(4) – tп(2) – t(2,4) = 23-13-10= 0. Это означает, что работа (2,4) продолжительностью 10 (суток) должна закончиться на 23 сутки после начала комплекса работ, а начаться – на 13 сутки. Подчеркнем, что резервы критических работ (1,2), (2,4), (4,6), (4,7), (6,8), (7,8), (8,9), (9,10), так же как и резервы критических событий, равны нулю.

 

Оптимизационная задача на сетевой модели по критерию стоимости

 

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

 

a(i,j) £ t(i,j) £ b(i,j),        (18)

 

где b(i,j) – нормальная продолжительность выполнения работы (i,j);

a(i,j) – минимально возможная (экстренная) продолжительность работы (i,j), которую только можно осуществить в условиях разработки.

При этом стоимость c(i,j) работы (i,j) заключена в границах от cmin(i,j) – при нормальной продолжительности работы, до cmax(i,j) – при экстренной продолжительности работы.

Изменение стоимости работы Dc(i,j) при сокращении ее продолжительности можно найти следующим образом:

 

Dc(i,j) = [ b(i,j) – t(i,j) ] h(i,j),        (19)

 

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

Коэффициент затрат h(i,j) на ускорение работы (i,j) определяется соотношением:

 

        (20)

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

 

           (21)

уменьшается на величину

      (22)

Оптимизация сетевого графика может быть выполнена по критериям стоимости и времени.

Задачами оптимизации сетевого графика являются:

– минимизация времени выполнения комплекса работ при заданной его стоимости;

– минимизация стоимости комплекса работ при заданном времени выполнения проекта.

Проиллюстрируем решение последней оптимизационной задачи на примере сети (см. рисунок 8). Для решения задачи, кроме продолжительности работ t(i,j), необходимо знать их граничные значения a(i,j) и b(i,j), а также показатели затрат на ускорение работ h(i,j), вычисляемые по формуле (20). Продолжительность каждой работы (i,j) целесообразно увеличить на величину такого резерва, чтобы не изменить ранние (ожидаемые) сроки наступления всех событий сети, т.е. на величину свободного резерва времени Rc(i,j). Значения резервов работ Rc(i,j) были вычислены ранее (см. таблицу 4). Результаты оптимизации рассчитываемой сети представлены в таблице 5.

Отметим, что:

1. в таблице 5 представлены параметры лишь тех работ, которые имеют свободный резерв времени;

 

Таблица 5 – Результаты оптимизации сетевого графика по критерию времени

 

Работа (i,j)	Продолжительность работы, сут.			Свободный резерв времени работы  Rс(i,j), сут.	Стои-мость работы с(i,j), усл.р.	Коэффициент затрат на ускорение работы  h(i,j), усл.р./сут.	Уменьшение стоимости проекта Dс(i,j), усл. р.
	a(i,j)	t(i,j)	b(i,j)
1,4	4	5	9	18	20	1	(9-5)*1=4
2,7	9	12	17	1	25	3	(17-12)*3=15
3,7	4	7	15	15	20	1	(15-7)*1=8
6,7	1	1	5	1	35	2	(5-1)*2=8
5,9	4	6	7	21	20	3	(7-6)*3=3
5,7	1	2	7	13	25	4	(7-2)*4=20
8,10	3	4	6	6	40	5	(6-4)*5=10
Итого					185		68

 

2) стоимости с(i,j) остальных работ следующие: с(1,2)=35; с(1,3)=40; с(2,4)=30; с(3,5)=35; с(4,6)=25; с(4,7)=30; с(6,8)=40; с(7,8)=30; с(8,9)=35; с(9,10)=20 (усл. р.);

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

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

 

с = 185 + 35 + 40 + 30 + … + 20 = 505 усл.р.

 

Стоимость нового плана равна: c – Dc = 505 – 68 = 437 (усл.р.), т.е. уменьшилась на 13,4 %. Новый сетевой график представлен на рисунке 12.

Рисунок 12 – Результат оптимизации сетевого графика

 

На полученном в результате оптимизации сетевом графике появился новый критический путь длиной 45 (суток), а именно: 1®2®7®6®8®9®10.

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

Итак, в результате оптимизации сети мы пришли к плану, позволяющему осуществить выполнение комплекса работ в срок tкр = 45 (суток) при минимальной его стоимости с = 437 усл. р.

 

Многокритериальная оптимизационная задача на сетевой модели по критериям стоимости и времени

 

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

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

В случае оптимизации при нефиксированной величине критического пути, предположим, что сетевой график выполнения комплекса работ построен. Для каждой работы установлены ее наибольшие продолжительности b(i,j) и минимальные затраты. Следовательно, продолжительность критического пути будет наибольшей, а стоимость выполнения проекта – наименьшей (минимальной). Необходимо сократить критический путь до некоторого минимально возможного значения при минимальном возрастании  стоимости выполнения всего комплекса работ.

Эвристический алгоритм оптимизации сетевого графика по критериям стоимости и времени сводится к следующему.