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

В СПУ под работой понимается:

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

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

Предположим, что при составлении некоторого проекта выделено 10 событий:1,2,3,4,5,6,7,9,10,11 и 17 связывающих их работ: (1,2), (1,3), (1,4), (2,7), (2,4), (3,6), (3,7), (4,5), (4,7), (5,7), (5,9), (6,10), (6,7), (7,9), (9,10), (9,11), (10,11). Необходимо составить и упорядочить сетевой график. Как следует из перечня работ, исходным событием сетевого графика является событие 1 (ему не предшествуют никакие работы), а завершающим – событие 11 (за ним не следует ни одна работа). Построим сетевой график от исходного события к завершающему, разместив между ними промежуточные события в определенном порядке, соответствующем их номерам (рисунок 6). Свяжем события работами-ребрами в соответствии с их перечнем. Полученный сетевой график удовлетворяет сформулированным ранее правилам, предъявляемым к его построению. Однако он не полностью упорядочен.

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

Рисунок 6 – Первоначальный вариант сетевого графика

 

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

Начальное событие 1 отнесем к событиям первого уровня. Для определения событий второго уровня вычеркнем мысленно из графика (рисунок 6) работы, выходящие из события 1. Тогда события 2 и 3 составят второй уровень сетевого графика, т.к. в них не входит ни одна работа–ребро. Вычеркнув работы, выходящие из событий 2 и 3, получим события 4 и 6, относящиеся к третьему уровню.

Продолжая процедуру вычеркивания, получим четвертый уровень с событием 5, пятый уровень – с событием 7, шестой уровень – с событием 9, седьмой уровень - с событием 10 и, наконец, восьмой уровень с событием 11. Получим частично упорядоченный сетевой график, т.к. событие 5 принадлежит четвертому уровню и имеет номер меньше, чем событие 6 из третьего уровня. То же можно сказать о событиях 9, 10 и 11 (рисунок 7).

 

Рисунок 7 – Частично упорядоченный сетевой график

 

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

Рисунок 8 – Упорядоченный сетевой график

 

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

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

- путь 1-2-4-6-8-10 продолжительностью 13+10+1+7+4=35 суток;

- путь  1-2-4-6-8-9-10 продолжительностью 13+10+1+7+7+3=41сутки;

- путь  1-3-5-7-8-9-10 продолжительностью 4+7+2+5+7+3=28 суток;

- путь 1-2-4-7-8-9-10 продолжительностью 13+10+3+5+7+3=41сутки;

- путь  1-4-7-8-10 продолжительностью 5+3+5+4=17 суток и т.д.

Продолжительность критического пути 1-2-4-6-8-9-10  и 1-2-4-7-8-9-10 составляет 41сутки. Определив критический путь, мы тем самым установили критические события сети и критические работы.

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

 

 Расчет временных  параметров сетевого графика

 

В таблице 3 приведены основные временные параметры сетевых графиков. Рассмотрим содержание и расчет указанных параметров. Начнем с параметров событий.

Ранний (ожидаемый) срок tp(i) свершения i-го события определяется продолжительностью максимального пути, предшествующего этому событию:

 

tp(i) = max(t(Lпi)),          (1)

 

 

где Lпi - любой путь, предшествующий i-му событию, т.е. путь от исходного до i-го события сети.

Если событие j имеет несколько предшествующих путей, а следовательно, несколько предшествующих событий i, то ранний срок свершения события j удобно находить по формуле

 

tp(j) = max[tp(i) + t(i,j)].          (2)

 

Таблица 3 – Основные временные параметры сетевых графиков

 

Элемент сети, характеризуемый параметром	Наименование параметра	Условное обозначение параметра
Событие i	Ранний срок свершения события Поздний срок свершения события Резерв времени события	tp(i) tn(i) R(i)
Работа (i,j)	Продолжительность работы Ранний срок начала работы Ранний срок окончания работы Поздний срок начала работы Поздний срок окончания работы Полный резерв времени работы Частный резерв времени работы первого вида Частный резерв времени работы второго вида или свободный резерв времени работы Независимый резерв времени работы	t(i,j) tpн(i,j) tpо(i,j) tпн(i,j) tпо(i,j) Rп(i) R1(i,j)   Rc(i,j)   Rн(i,j)
Путь	Продолжительность пути Продолжительность критического пути Резерв времени пути	t(L) tкр R(L)

 

Поздний (или предельный) срок tп(i) свершения i-го события равен:

 

tn(i) = tkp – max(t(Lci)),          (3)

 

где Lci- любой путь, следующий за i-м событием, т.е. путь от i-го до завершающего события сети.

Если событие i имеет несколько последующих путей, а следовательно, несколько последующих событий j, то поздний срок свершения события i удобно находить по формуле

 

tn(i) = min[tп(j) – t(i,j)].           (4)

 

Резерв времени R(i) i-го события определяется как разность между поздними и ранними сроками его свершения:

 

R(i) = tn(i) – tp(i).                    (5)

 

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

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

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

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

Рисунок 9 – Расположение временных параметров непосредственно на сетевом графике

 

При определении ранних сроков совершения событий tp(i) двигаемся по сетевому графику слева направо и используем формулу (1) и (2). Для первого события i = 1 очевидно tp(1) = 0.

Для i = 2  tp(2) = tp(1) + t(1,2) = 0 + 13 = 13(суток), т.к. для события 2 существует только один предшествующий путь Ln2:1 ® 2.

Для i = 3  tp(3) = tp(1) + t(1,3) = 0 + 4= 4 (суток), т.к. для события 3 существует только один предшествующий путь Ln3:1 ® 3.

Для i = 4 tp(4) = max{tp(1) + tp(1,4); tp(2) + tp(2,4} =  = max{0+5;13+10}=max{5;23}=23(суток), т.к. для события 4 существует два предшествующих пути Ln4:1 ® 4, 1 ® 2 ® 4 и два предшествующих события.

 Для i = 5  tp(5) = tp(3) + t(3,5) = 4 + 7 = 11(суток), т.к. для события 5 существует только один предшествующий путь Ln5: 3 ® 5.

Аналогично рассчитаем ранние сроки свершения остальных событий и запишем их в левой части каждого кружка сетевого графика (рисунок 10). Длина критического пути равна раннему сроку свершения завершающего события 10: tкр = tp(10) = 41(суткам).

При определении поздних сроков свершения событий по сети в обратном направлении, т.е. справа налево, используем формулы (3) и (4). Для i = 10 (завершающего события) поздний срок свершения должен быть равен его раннему сроку (иначе изменится длина критического пути): tp(10) = tp(10) = 41(суткам).

Для i = 9 tn(9) = tn(9,10) = 41-3 = 38(суток), т.к. для события 9 существует только один последующий путь Lc9: 9→10.

Для i = 8 tn(8) = min{tn(9) – tn(8,9); tn(10) – tn(8,10)} =  min{38-7;41-4} = min{31;37} = 31(сутки), т.к. для события 8 существуют два последующих пути Lc8: 8 ® 9 ® 10, 8 ® 10 и два  последующих события: 9 и 10.

Для i = 7 tn(7) = tn(7,8) = 31-5 = 26(суток), т.к. для события 7 существует только один последующий путь Lc7: 7→8.

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

По формуле (5) определим резервы времени i-го события:

R(1) = 0; R(2) = 13-13 = 0; R(3)=17-4=13 и т.д.

Резерв времени события 3 R(3)=13 означает, что время свершения события 3 может быть задержано на 13 суток без увеличения общего срока выполнения проекта. Анализируя сетевой график с временными параметрами                    (см. рисунок 10), видим, что не имеет резервов времени события 1, 2, 4, 6, 7, 8, 9 10. Эти события и образуют критический путь (на рисунке 10 он выделен жирным шрифтом).

 

Рисунок 10 – Сетевой график с временными параметрами

 

Теперь перейдем к параметрам работ.

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

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

 

tpн(i,j) = tp(i).            (6)

 

Тогда ранний срок tpo(i,j) окончания работы (i,j) определяется по формуле

 

tpo(i,j) = tp(i) + t(i,j).                    (7)

 

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

 

tno(i,j) = tn(j),             (8)

 

а поздний срок tnн(i,j) начала этой работы – соотношением

 

tnн(i,j) = tп(j) – t(i,j).           (9)

 

Среди резервов времени работ выделяют четыре их разновидности.

Полный резерв времени Rn(i,j) работы (i,j) показывает, насколько можно увеличить время выполнения данной работы при условии, что срок выполнения комплекса работ не изменится. Полный резерв Rn(i,j) определяется по формуле

 

Rn(i,j) = tп(j) – tp(i) – t(i,j).        (10)

 

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

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