ТЕМА 2. Сетевое планирование

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

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

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

Событие в сетевом графике имеет номер, а работа обозначается двумя номерами (i,j), где i – номер начального события работы, а j – номер конечного события работы (см. рис.2.1). Продолжительность работы обозначается t(i,j).

Рис. 2.1. Изображение работы на сетевом графике.

На основе сетевого графика могут быть решены следующие задачи:

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

Рекомендуемые материалы

2) Определение срока выполнения проекта (критического времени проекта)

3) Выявление возможностей задержки начала каждой работы или удлинения срока ее выполнения

4) Оптимизация времени выполнения проекта или ресурсов, требуемых для его выполнения.

Рассмотрим пример сетевого графика (рис.2.2). Это график проекта некоторой туристической фирмы, включающий комплекс работ по подготовке к участию в выставке. Перечень работ приведен в таблице 2.1.

Рис.2.2. Сетевой график примера

 Таблица 2.1. Перечень работ проекта по организации выставки.

Данный проект включает восемь работ и шесть событий. Сетевой график отражает взаимосвязь работ проекта.

Например, работа (2,3) имеет продолжительность 1 день. Она может быть начата только тогда, когда завершится работа (1,2).

Работа (3,4) имеет продолжительность 5 дней. Она может быть начата только тогда, когда завершатся обе работы, ей предшествующие: (1,3) и (2,3).

Событие 4 состоит в факте окончания обоих работ (2,4) и (3,4) и начала работы (4, 5). Событие 4 не наступит, если хотя бы одна из работ (2,4) или (3,4) не завершена. И т.д.

Событие, с которого начинается выполнение проекта, называется исходным и обозначается I. Исходное событие не имеет предшествующих работ. В примере это событие 1. Событие, которое констатирует факт завершения проекта, называется завершающим и обозначается S. Завершающее событие не имеет последующих работ. В примере это событие 6.  В сетевом графике может быть только одно исходное и только одно завершающее событие.

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

m₁=(1-2-3-4-5-6);

m₂=(1-3-4-5-6);

m₃=(1-2-4-5-6);

m₄=(1-2-6).

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

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

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

В нашем примере определить критический путь легко: нужно перебрать все возможные полные пути, рассчитать продолжительность каждого из них и выбрать наибольший:

t(m₁)=2+1+5+4+5=17;

t(m₂)=4+5+4+5=18;

t(m₃)=2+2+4+5=13;

t(m₄)=2+3=5;

Критическим является полный путь  μ_2, т.к. он имеет наибольшую продолжительность. Критический путь принято выделять на графике жирной линией (рис.2.3.).

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

1) Для каждого события рассчитывают ранний и поздний сроки свершения.

2) На их основе определяют резервы времени всех событий и работ.

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

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

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

, т.е. начало проекта принимается за нулевой момент времени;

, если событию j предшествует только одна работа;

, если событию предшествует несколько работ.

Здесь  i®j – множество работ, заканчивающихся j-м событием (дуги, входящие в вершину j);

– ранний срок свершения события, с которого начинается работа (i,j);

– продолжительность работы (i,j).

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

t_р(1)=0 (Расчет времени начинается с 0)

Событие 2 наступит тогда, когда закончится работа (1,2). Эта работа начнется в момент времени 0 и продлится 2 дня. Поэтому она закончится в 0+2=2 день:

t_р(2)=t_р(1)+t(1,2) =0+2=2.

В вершину 3 входят две стрелки, т.е. событие 3 наступит тогда, когда закончатся обе работы: (1,3) и (2,3). Работа (1,3) начнется в момент времени 0 и продолжится 4 дня. Т.е. она закончится в 0+4=4 день. Аналогично работа (2,3) закончится в 2+1=3 день. Поскольку обе работы должны закончиться, чтобы наступило событие 4, нужно ориентироваться на самую позднюю из них, т.е. взять максимум по входящим в событие работам:

t_р(3)=max{t_р(1)+t(1,3), t_р(2)+t(2,3)}=max{0+4,2+1}=4.

Аналогично находят ранние сроки остальных событий проекта:

t_р(4)=max{ t_р(2)+t(2,4),t_р(3)+t(3,4)}=max{2+2,4+5}=9;

t_р(5)= t_р(4)+t(4,5)=9+4=13;        

t_р(6)= max{t_р(2)+t(2,6), t_р(5)+t(5,6)}=max{2+3,13+5}=18.

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

t_кр=t_р(S).

Таким образом, рассчитав ранние сроки, мы узнали критический срок проекта нашего примера: t_кр=t_р(6)= 18.

Рис.2.3. Сетевой график примера с результатами расчетов.

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

Поздние сроки свершения событий рассчитываются “обратным ходом” от завершающего события к исходному по следующим формулам:

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

, если событием i начинается одна работа;

, если событием i начинается несколько работ.

Здесь i®j – множество работ, начинающихся i-м событием (дуги, исходящие из вершины i);

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

– продолжительность работы (i,j).

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

Для завершающего события:

t_п(6)= t_р(6)=18.

Рассчитывая поздний срок свершения события 5, необходимо учитывать, что этим событием начинается работа (5,6), которая должна быть обязательно закончена к 18 дню. Она длится 5 дней, поэтому самый поздний момент, когда она должна начаться, это 18-5=13 день. Если вдруг событие 5 наступит, скажем,  на 14 день, то работа (5,6) закончится на 14+5=19 день и срок выполнения всего проекта будет сорван. Поэтому можно записать для события 5:

t_п(5)=t_п(6)-t(5,6)= 18-5=13.

Событием 4 начинается одна работа (4,5). Она должна быть закончена к 13 дню для того, чтобы следующая за ней работа успела к критическому сроку. Поэтому работа (4,5) должна начаться не позже, чем на 13-4=9 день. Таким образом,

t_п(4)=t_п(5)-t(4,5)= 13-4=9.

Аналогично рассчитываем поздний срок свершения события 3:

t_п(3)=t_п(4)-t(3,4)= 9-5=4.

Событием 2 начинаются три работы: (2,3), (2,4) и (2,6). Все они должны успеть закончиться вовремя, т.е. работа (2,3) – к 4 дню, работа (2,4) – к 9 дню, а работа (2,6) – к 18 дню. Для этого работа (2,3) должна начаться не позже, чем на 4-1=3 день, работа (2,4) – на 9-2=7 день, а работа (2,6) должна начаться не позже, чем на 18-3=15 день. Чтобы успели все эти работы, нужно, чтобы успела та из них, которая начинается раньше. Поэтому нужно найти минимум по исходящим из события 2 работам:

t_п(2)=min{t_п(3)-t(2,3), t_п(4)-t(2,4), t_п(6)-t(2,6)}=

=min{4-1, 9-2, 18-3}=3.  

Аналогично находится поздний срок свершения события 1, из которого выходят две работы:

t_п(1)= min{t_п(3)-t(1,3), t_п(2)-t(1,2)}=min{4-4, 3-2}=0.

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

Рассчитаем резервы времени событий для нашего примера:

R(1)=t_п(1)-t_р(1)=0-0=0;    

R(2)= t_п(2)-t_р(2)=3-2=1;   

R(3)= t_п(3)-t_р(3)=4-4=0;   

R(4)= t_п(4)-t_р(4)=9-9=0;   

R(5)= t_п(5)-t_р(5)=13-13=0;

R(6)= t_п(6)-t_р(6)=18-18=0.

Таким образом, можно задержать свершение события 2 на 1 день. Остальные события 1, 3, 4, 5 и 6 не имеют резерва времени. Поэтому они принадлежат критическому пути. Если бы ранее мы не выделили критический путь на сетевом графике, то можно было бы провести его сейчас, после расчетов резервов времени событий, через события 1, 3, 4, 5 и 6. Для проверки следует сложить продолжительности работ этого полного пути, которые в сумме должны быть равны критическому сроку:

4+5+4+5=18=t_кр

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

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

Резервы работ определяются на основе параметров свершения событий по следующей формуле:

Рассчитаем резервы работ примера:

R(1,2)=t_п(2)-t_р(1)-t(1,2)=3-0-2=1;

R(1,3)=t_п(3)-t_р(1)-t(1,3)=4-0-4=0;

R(2,3)=t_п(3)-t_р(2)-t(2,3)=4-2-1=1;

R(2,4)=t_п(4)-t_р(2)-t(2,4)=9-2-2=5;

Информация в лекции "5.4. Каноническое проектирование ИС" поможет Вам.

R(2,6)=t_п(6)-t_р(2)-t(2,6)=18-2-3=13;

R(3,4)=t_п(4)-t_р(3)-t(3,4)=9-4-5=0;

R(4,5)=t_п(5)-t_р(4)-t(4,5)=13-9-4=0;

R(5,6)=t_п(6)-t_р(5)-t(5,6)=18-13-5=0.

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

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