Построение и расчет сетевых графиков. Расчет и анализ сетевых графиков

Расчет сетевых графиков сводиться к численному определению его пара-метров. Поэтому сначала перечислим их.

При расчете сетевых графиков определяются следующие параметры:

Ранние начала и окончания работ;

Поздние начала и окончания работ;

Продолжительность критического пути;

Общие и частные резервы работ.

За расчетную схему (рис. 18.8) выберем расположение работ, закодирован­ных буквами: h - предшествующая работа, i - рассматриваемая работа,j - после­дующая работа.

Рис. 18.8 Расчетная модель

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

Раннее начало работы (рис. 18.9) равно продолжительности максимально­го пути от исходного события графика до начального события данной работы:

​

Рис. 18.9 Модель расчета ранних начал

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

​

Для начальных (исходных) работ:

Раннее начало принимается равным 0;

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

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

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

Позднее окончание любой работы (рис. 18.1 О) равно наименьшему из поздних начал последующих работ:

​

Рис. 18.10 Модель расчета поздних окончаний

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

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

Позднее окончание равно величине продолжительности критического пути:

​

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

​

Общий (или полный) резерв времени работы R;-1 (рис. 18.11) - это макси­мальное время, на которое можно увеличить продолжительность данной рабо­ты или перенести ее начало без увеличения продолжительности критического пути. Он равен разности между одноименными поздними и ранними парамет­рами этой работы:

​

Рис. 18.11 Модель расчета общих резервов

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

​

Рис. 18.12 Модель расчета частных резервов

Частный резерв времени отличается от нуля, если в конечное событие ра­боты входят две и более работы.

Методы расчета сетевых графиков

Сетевые графики можно рассчитывать с помощью компьютерной техники и вручную. В настоящее время известно несколько методов расчета сетевых графиков вручную: табличный метод; расчет на графике - четырехсекторный метод; метод дроби; метод потенциалов и др.

Классическим методом, положившим начало теории расчета сетевых гра­фиков, является табличный метод , или, как говорят, алгоритм расчета сетево­го графика по таблице.

Пример графика для расчета табличным методом приведен на рис. 18.13. В этом случае определение параметров сетевого графика выполняется в таблице.

​

Рис. 18.13 Пример графика для расчета табличным методом и методом потенциалов

Заполнение таблицы ведется в следующем порядке.

1) В первые три графы заносят исходные данные по каждой работе. Необходимо последовательно записывать все работы, выходящие из первого события (по часовой стрелке), затем - все работы, выходящие из второго события:, и т.д.

2) Производят расчет ранних параметров работ построчно сверху вниз.

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

4) Рассчитывают поздние параметры работ. Расчет ведется построчно сни­зу вверх, от завершающих работ до исходных.

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

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

При расчете сетевых графиков табличным методом заполняют следующую таблицу (табл. 18.1).

​

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

Следующей заполняют графу 4. Против каждой работы, записанной в гра­фе 3 из сетевого графика, проставляют её продолжительность t.

Графы 5 (раннее начало работы ТРН) и 6 (раннее окончание работы ТРН за­полняются одновременно. У работ 1-2 и 1-3 предшествующих событий нет; следовательно, их раннее начало равно нулю. Раннее окончание работы равно сумме его раннего начала и продолжительности . Таким образом, в графу 6 вно­сят сумму цифр граф 4 и 5. Для работы 2-4 раннее начало равно раннему окон­чанию предшествующей работы, т.е. работы 1-2 (в графе 2 записано предшест­вующее событие 1); следовательно, раннее начало работ, начинающихся с события 2 (2-3, 2-4), также равно 5 дням. Прибавляя к ранним началам работ их продолжительности, получим их раннее окончание. Если у работы есть два и более предшествующих события (например, работа 4-6), то в этом случае вы­бирают максимальное значение раннего окончания этих работ и заносят в гра­фу 5, и на ее основе определяют ранее окончание.

Максимальное раннее окончание последней работы равно величине кри­тического пути.

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

Общий резерв R (графа 9) определяют как разность между числами в гра­фах 8 и 6 или 7 и 5.

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

Правильность расчета сетевого графика подтверждают проверкой:

Ранние параметры никогда не превосходят по численному значению поздние параметры;

Критический путь должен представлять собой непрерывную последова­тельность работ от исходного события до завершающего;

Величина частного резерва времени работы не должна превосходить ве­личину общего резерва времени;

Позднее начало одной из исходных работ обязательно должно быть ну­левым.

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

Потенциалом i-го события (ТjП) называют величину наиболее продолжи­тельного пути от данного события до завершающего:

​

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

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

​

Рис. 18.14 Запись в секторах при расчете методом потенциалов

​

Рис. 18.15. Пример расчета методом потенциалов

(номера событий соответствуют рис. 18.1 З)

Потенциал события 5 (продолжительность работы 5-6) равен 5 дням. Циф­ру 5 записываем в правый сектор события 5, цифру 6 - в его верхний сектор.

Потенциал события 4 Т4П = 0 + 4 = 4. Для события 2 потенциал определяют следующим образом: от события 3 - Т2П = 11 + О = 11 и от события 4 - Т2П = 4

3 = 7; выбирают наибольшее значение 11. Аналогичным образом рассчиты­вают остальные события. Потенциал исходного события составляет 16 дней, т.е. равен величине критического пути.

Зная потенциал события, позднее окончание работ можно определить по формуле

​

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

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

Четырехсекторпый,метод расчета сетевых графиков

При этом методе каждое событие (рис. 18.16) графиком делится на 4 сек­тора, в которых указываются необходимые расчетные данные.

​

Рис. 18.16 Условные обозначения при четырехсекторном методе расчета

Исходным графиком для расчета четырехсекторным методом служит гра­фик, приведенный на рис. 18.17.

​

Рис. 18.17 Исходный график для расчета четырехсекторным методом

Вначале от исходного события до завершающего определяют все ранние начала работ.

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

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

Дополнительным требованием к критическим работам является требова­ние по соблюдению условия

​

20-12 = 8; 25-5 = 20; 25-11 = 12; следовательно, работы нижнего пути- не­критические.

​

Рис. 18.18 График, рассчитанный четырехсекторным методом

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

​

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

Построение сетевых графиков «вершины-работы»

В последнее время построение сетевых графиков всё чаще выполняют по принципу «вершины-работы», а не по принципу «вершины-события», как это было в предыдущих примерах (рис.18.19).

Для расчета сетевого графика «вершины-работы>> прямоугольник, изобра­жающий работу, делят на 7 частей (рис. 18.20). В верхних трех частях прямо­угольника записывают раннее начало, продолжительность и раннее окончание работы, в трех нижних - позднее начало, резервы времени и позднее оконча­ние. Центральная часть содержит код (номер) и наименование работы.

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

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

​

Рис. 18.19 График типа "вершины-работы"

​

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

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

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

Позднее начало определяют как разность позднего окончания и продолжи­тельности работы.

Полный (общий) резерв времени, равный разности поздних и ранних сро­ков, заносят в числитель середины нижней части.

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

Частный резерв всегда меньше полного резерва работы или равен ему. По­следовательность работ с нулевыми резервами времени является критическим путем сетевого графика.

• 1. Выделить критический путь и найти его длину;
• 2. Определить резервы времени каждого события;
• 3. Определить резервы времени всех работ и коэффициент напряженности работы предпоследней работы

Решение

Для решения задачи применим следующие обозначения.

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

Для определения резервов времени по событиям сети рассчитывают наиболее ранние t p и наиболее поздние t п сроки свершения событий. Любое событие не может наступить прежде, чем свершаться все предшествующие ему события и не будут выполнены все предшествующие работы. Поэтому ранний (или ожидаемый) срок tp(i) свершения i-ого события определяется продолжительностью максимального пути, предшествующего этому событию:

t p (i) = max(t(L ni)) (1)

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

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

t p (j) = max (2)

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

t п (i) = t kp - max(t(L ci)) (3)

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

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

t п (i) = min

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

R(i) = t п (i) - t p (i)

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

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

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

Расчет сроков свершения событий.

Для i=0 (начального события), очевидно tp(0)=0.

i=1: t p (1) = t p (0) + t(0,1) = 0 + 0 = 0.

i=2: t p (2) = t p (1) + t(1,2) = 0 + 8 = 8.

i=3: t p (3) = t p (1) + t(1,3) = 0 + 3 = 3.

i=4: max(t p (2) + t(2,4);t p (3) + t(3,4)) = max(8 + 6;3 + 3) = 14.

i=5: tp(5) = tp(4) + t(4,5) = 14 + 0 = 14.

i=6: max(t p (4) + t(4,6);t p (5) + t(5,6)) = max(14 + 5;14 + 3) = 19.

i=7: t p (7) = t p (6) + t(6,7) = 19 + 9 = 28.

i=8: max(t p (2) + t(2,8);t p (6) + t(6,8);t p (7) + t(7,8)) = max(8 + 18;19 + 5;28 + 4) = 32.

i=9: max(t p (5) + t(5,9);t p (7) + t(7,9)) = max(14 + 2;28 + 4) = 32.

i=10: max(t p (4) + t(4,10);t p (7) + t(7,10);t p (9) + t(9,10)) = max(14 + 4;28 + 2;32 + 0) = 32.

i=11: max(t p (8) + t(8,11);t p (10) + t(10,11)) = max(32 + 12;32 + 4) = 44.

Длина критического пути равна раннему сроку свершения завершающего события 11: t kp =tp(11)=44

При определении поздних сроков свершения событий t п (i) двигаемся по сети в обратном направлении, то есть справа налево и используем формулы (3), (4).

Для i=11 (завершающего события) поздний срок свершения события должен равняться его раннему сроку (иначе изменится длина критического пути): t п (11)= t р (11)=44

i=10: t п (10) = t п (11) - t(10,11) = 44 - 4 = 40.

i=9: t п (9) = t п (10) - t(9,10) = 40 - 0 = 40.

Просматриваются все строчки, начинающиеся с номера 8.

i=8: t п (8) = t п (11) - t(8,11) = 44 - 12 = 32.

Просматриваются все строчки, начинающиеся с номера 7.

i=7: min(t п (8) - t(7,8);t п (9) - t(7,9);t п (10) - t(7,10)) = min(32 - 4;40 - 4;40 - 2) = 28.

i=6: min(t п (7) - t(6,7);t п (8) - t(6,8)) = min(28 - 9;32 - 5) = 19.

Просматриваются все строчки, начинающиеся с номера 5.

i=5: min(t п (6) - t(5,6);t п (9) - t(5,9)) = min(19 - 3;40 - 2) = 16.

i=4: min(t п (5) - t(4,5);t п (6) - t(4,6);t п (10) - t(4,10)) = min(16 - 0;19 - 5;40 - 4) = 14.

Просматриваются все строчки, начинающиеся с номера 3.

i=3: t п (3) = t п (4) - t(3,4) = 14 - 3 = 11.

i=2: min(t п (4) - t(2,4);t п (8) - t(2,8)) = min(14 - 6;32 - 18) = 8.

i=1: min(t п (2) - t(1,2);t п (3) - t(1,3)) = min(8 - 8;11 - 3) = 0.

(0,1): 0 - 0 = 0;

Таблица 1 - Расчет резерва событий

Номер события	Сроки свершения события: ранний tp(i)	Сроки свершения события: поздний tп(i)	Резерв времени, R(i)

Заполнение таблицы 2.

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

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

Так, для работы (1,2) в графу 1 поставим число 1, т.к. на номер 1 оканчиваются 1 работы: (0,1).

Графу 4 получаем из таблицы 1 (t p (i)). Графу 7 получаем из таблицы 1 (t п (i)).

Значения в графе 5 получаются в результате суммирования граф 3 и 4.

В графе 6 позднее начало работы определяется как разность позднего окончания этих работ и их продолжительности (из значений графы 7 вычитаются данные графы 3);

Содержимое графы 8 (полный резерв времени R(ij)) равно разности граф 6 и 4 или граф 7 и 5. Если R(ij) равен нулю, то работа является критической

Таблица 2 - Анализ сетевой модели по времени

Работа (i,j)	Количество предшествующих работ	Продолжительность tij	Ранние сроки: начало tijР.Н.	Ранние сроки: окончание tijР.О.	Поздние сроки: начало tijП.Н.	Поздние сроки: окончание tijП.О.	Резервы времени: полный RijП	Независимый резерв времени RijН	Частный резерв I рода, Rij1	Частный резерв II рода, RijC

Следует отметить, что кроме полного резерва времени работы, выделяют еще три разновидности резервов. Частный резерв времени первого вида R 1 - часть полного резерва времени, на которую можно увеличить продолжительность работы, не изменив при этом позднего срока ее начального события. R 1 находится по формуле:

R(i,j)= R п (i,j) - R(i)

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

R(i,j)= R п (i,j) - R(j)

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

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

R(i,j)= Rп(i,j)- R(i) - R(j)

Критический путь : (0,1)(1,2)(2,4)(4,6)(6,7)(7,8)(8,11)

Продолжительность критического пути: 44

Найдем коэффициент напряженности работы предпоследней работы. Так как длина критического пути 44, максимальный путь, проходящий через работу (1,10) равен 32, тогда

К(1,10)=(32-28)/(44-28)=0,296.

4. Интернет-провайдер в небольшом городе имеет 5 выделенных каналов обслуживания. В среднем на обслуживание одного клиента уходит 25 минут. В систему в среднем поступает 6 акзаов в час. Если свобдных каналов нет, следует отказ. Определить характеристики обслуживания: вероятность отказа, среднее число занятых обслуживанием линий связи, абсолютную и относительную пропускные способности, вероятность обслуживания. Найти число выделенных каналов, при котором относительная пропускная способность системы будет не менее 0,95. Считать, что потоки заявок и обслуживаний простейшие

Интенсивность потока обслуживания:

Интенсивность нагрузки:

с = л * t обс = 6 * 25/60 = 2.5

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

Вероятность того, что обслуживанием:

занят 1 канал:

p 1 = с 1 /1! p 0 = 2.5 1 /1! * 0.0857 = 0.214

заняты 2 канала:

p 2 = с 2 /2! p 0 = 2.5 2 /2! * 0.0857 = 0.268

заняты 3 канала:

p 3 = с 3 /3! p 0 = 2.5 3 /3! * 0.0857 = 0.223

заняты 4 канала:

p 4 = с 4 /4! p 0 = 2.5 4 /4! * 0.0857 = 0.139

заняты 5 канала:

p 5 = с 5 /5! p 0 = 2.5 5 /5! * 0.0857 = 0.0697

Вероятность отказа- это доля заявок, получивших отказ:

Значит, 7% из числа поступивших заявок не принимаются к обслуживанию.

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

В системах с отказами события отказа и обслуживания составляют полную группу событий, поэтому:

p отк + p обс = 1

Относительная пропускная способность Q = p обс .

p обс = 1 - p отк = 1 - 0.0697 = 0.93

Следовательно, 93% из числа поступивших заявок будут обслужены. Среднее число каналов, занятых обслуживанием

n з = с * p обс = 2.5 * 0.93 = 2.326 канала.

Среднее число простаивающих каналов .

n пр = n - n з = 5 - 2.326 = 2.7 канала.

Коэффициент занятости каналов обслуживанием .

Следовательно, система на 50% занята обслуживанием.

Абсолютная пропускная способность

A = pобс * л = 0.93 * 6 = 5.581 заявок/час.

Среднее время простоя СМО .

t пр = p отк * t обс = 0.0697 * 0.417 = 0.029 час.

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

L обс = с * Q = 2.5 * 0.93 = 2.326 ед.

Среднее время пребывания заявки в СМО (формула Литтла).

Число заявок, получивших отказ в течение часа: л * p 1 = 0.418 заявок в час.

Номинальная производительность СМО: 5 / 0.417 = 12.002 заявок в час.

Фактическая производительность СМО: 5.581 / 12.002 = 47% от номинальной производительности.

Определим количество каналов, необходимых для обеспечения работоспособности системы с вероятностью P ? 0.95

Для этого находим n из условия:

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

Расчёт сетевого графика табличным способом производится по формулам, ранее изложенным в разделе 4 (1-10). При определении параметров сетевых моделей аналитическим способом расчёт выполняется в форме таблицы. Рассмотрим особенности расчёта сетевых моделей данным способом (приожениие 1) на примере расчёта параметров сетевого графика, изображенного в задании к данной курсовой работе (вариант 15).

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

Расчёт сетевого графика начинается с определения значений ранних параметров работ. Раннее начало работы 1-2 равно нулю (формула 1), а её раннее окончание по формуле 2.

Раннее начало работ 2-6 и 2-7 (в соответствии с формулой 3) равно раннему окончанию работы 1-2.

Максимальное значение раннего окончания работы 19-21, равное 36, определяет продолжительность критического пути и, следовательно, общую продолжительность выполнения всех работ по исходной сетевой модели. Полученное значение раннего окончания данной работы 19-21 = 36 переносится в графу позднего окончания завершающей работы 20-21.

Позднее начало работы 20-21 определяется в соответствии с формулой 5 (= 34)

Позднее начало работы 20-21 является поздним окончанием предшествующей ей работы 15-20 (=).

Далее расчёт поздних параметров выполняется аналогично, за исключением случаев, когда у работы имеется несколько последующих работ (например, у работы 6-9 имеется две последующих - 9-10 и 9-14). В этом случае, в соответствии с формулой 4, позднее окончание работы 6-9 равно минимальному значению поздних начал последующих работ 9-10 и 9-14.

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

Общий резерв времени работ, согласно формулам 8-9, определяется как разность позднего и раннего окончания либо как разность позднего и раннего начал соответствующих работ. Полезно определить значение общего резерва времени обоими способами, совпадение полученных значений может рассматриваться как дополнительная проверка. Например, для работы 6-7:

Частный резерв времени работы, согласно формуле 10, определяется как разность значения раннего начала последующей работы и значения раннего окончания для данной работы. Например, для работы 6-7:

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

Графический метод расчета сетевых графиков

Расчёт сетевого графика графическим способом ведется аналогично табличному методу (формулы 1-10) , однако графический или секторный способ расчёта параметров сетевого графика предполагает их запись непосредственно на модели (приложение 2). При этом каждое событие (кружок) делится на четыре сектора. Обозначение секторов приведено на следующем рисунке:

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

Для проверки правильности выполненных расчётов следует убедиться в том, что:

• * выявлен непрерывный критический путь;
• * рассчитанные резервы времени имеют неотрицательное значение;
• * значение частного резерва времени для всех работ меньше или равно значению общего резерва времени для данных работ;
• * хотя бы одно значение позднего начала работ (работы), выходящих из первого события, равно нулю.

Для записи результатов расчета принимают одну из следующих форм (рис. 41)

Рис. 41. Изображение событий для расчета на графике:

а - секторный способ; б - метод дроби

1 - раннее свершение события i (раннее начало работы ij);

2 - номер события i;

3 - позднее свершение события i (позднее окончание работы hi;

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

3. 6. 1. Секторный способ расчета сетевого графика

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

Порядок расчета:

1) у исходного события в левом секторе ставят нуль;

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

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

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

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

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

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

7) критический путь проходит через события в которых значения в левом и правом секторах совпадают. Полный и частный резерв времени для работ критического пути равен нулю;

8) резерв времени события равен разности значений правого и левого секторов.

Рис. 42. Сетевой график с результатами расчета секторным методом

3. 6. 2. Расчет параметров сетевого графика методом дроби

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

1) числитель - раннее начало последующей работы, равное наибольшей из сумм ранних начал и продолжительностей предшествующих работ. Раннее начало исходных работ графика принимают равным нулю. Расчет ведут слева направо;

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

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

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

Свободный резерв времени - это числитель у конца стрелки минус числитель у начала стрелки минус продолжительность работы.

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

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

Преимущества методов расчета на графике по сравнению с табличным способом следующие:

1) для расчета на графике не обязательна строгая упорядоченность событий;

2) исключаются ошибки, возникшие при записи в таблицу исходных данных для расчета;

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

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

Недостатки графического расчета:

1) записываемые на графике параметры работ в ходе строительства часто меняются, и в результате исправлений график быстро приходит в негодность;

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

3. 6. 3. Расчет сетевого графика по потенциалам событии

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

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

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

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

Потенциал событий вычисляется по формуле

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

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

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

Основные понятия и определения

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

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

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

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

Ожидание - работа не требующая затрат труда (и других ресурсов), но требующая затрат времени.

Работа на сетевом графике обозначается сплошной линией со стрелкой.

Продолжительность работы указывается числом над стрелкой. Единицей измерения продолжительности работ может быть день, неделя, декада, месяц. Длина стрелки выбирается произвольно. Она не отражает продолжительности работы. Работа обозначается шифрами начального и конечного события (ij ). Продолжительность работы tij .

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

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

I.5. Путь - это любая последовательность робот сетевой модели, в которой конечное событие каждой работы совпадает с начальным событием следующей за ней. Путь обозначается индексом (L ). Продолжительность пути определяется суммой продолжительностей вводящих в данный путь, работ и обозначается t(L ). Различают путь полный (L (J - C )), т. е. путь от исходного со­бытия до завершающего, и путь от любого события до другого L (m 1 - m 2).

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

По построенной сетевой модели для каждой работы определяется ожидаемая продолжительность ее выполнения - t ож, а также дисперсия времени выполнения работы - .

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

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

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

Ниже приведены три разновидности этих формул, которые соответствуют вариантам индивидуальных заданий:

1-й способ ; ;

2-й способ ; ;

3-й способ ; .

Для расчета по этим формулам от ответственных исполнителей получают путем опроса следующие экспертные оценки времени выполнения работ:

а (или tmin ) - минимальная (оптимистическая) продолжительность работы, т. е. оценка продолжительности работы в предположении наиболее благоприятного стечения обстоятельств;

b (или tmax ) - максимальная (пессимистическая) продолжительность работы, т. е. продолжительность работы в предположении наиболее неблагоприятного стечения обстоятельств;

m (или t н. в.) - наиболее вероятная оценка продолжительности работы - оценка продолжительности при наиболее часто встречающихся условиях выполнения работы.

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

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

1. Продолжительность пути

,

где К - количество работ, входящих в данный путь.

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

Продолжительность критического пути

Ткр = t [L (J -C )max ] .

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

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

R (L ) = Tкр - t (L ) .

3. Ранний срок свершения события - срок, необходимый для выполнения всех работ, предшествующих данному событию i

Тр(i ) = t [L (J -i )max ] или Тр(j ) = max .

Ранний срок исходного события сети принимается равным нулю: Тр(J ) = 0 .

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

Тп(i ) = Tкр - t [(i -C )max ] или Тп(i ) = [Тп(j )-tij ]min .

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

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

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

R (i ) = Tп(i ) - Tp(i ) = R (Lmax ) .

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

6. Ранний срок начала работы - это самый ранний из возможных сроков начала работы: t р. н.(ij ) = Tp(i ) .

7. Ранний срок окончания работы - это самый ранний из возможных сроков окончания работы

t р. о.(ij ) = t р. н.(ij ) + tij = Tp(i ) + tij .

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

t п. н.(ij ) = t п. о.(ij ) - tij = Tп(j ) - tij .

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

t п. о.(ij ) = Tп(j ) .

Для работ критического пути:

t р. н.(ij ) = t п. н.(ij ) и t р. о.(ij ) = t п. о.(ij ) .

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

R п(ij ) = Tп(j ) - Tp(i ) - tij .

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

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

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

11. Свободный резерв времени работы - равен разности между ранними сроками наступления событий j и i за вычетом продолжительности работы (ij ):

R c(ij ) = Tp(j ) - Tp(i ) - tij .

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

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

3.12. Коэффициент напряженности работы используется в сетевом планировании для характеристики напряженности сроков выполнения работ и определяется по следующей формуле:

,

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

t ¢(L кр) - продолжительность отрезка пути t (Lmax ), совпадающего с критическим путем.

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

Величина коэффициента напряженности у разных работ в сети лежит в пределах 0 £ Кн(ij ) £ i .

Для всех работ критического пути Кн(ij ) = 1.

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

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

Существует два способа ручного расчета параметров сетевых графиков (причем, в литературе по СПУ встречаются различные разновидности данных способов): непосредственно на графике; табличный способ.

1. Первый способ (расчет параметров непосредственно на графике) предусматривает определение, как правило, следующих параметров, ранних сроков свершения событий, поздних сроков свершения событий, резервов времени свершения событий и критического пути. При расчете по этому способу кружок, изображающий событие, делится на четыре сектора. Верхний сектор отводится для номера события - i , левый сектор для раннего срока свершения события Тр(i ), правый для позднего срока свершения события Тп(i ), а нижний сектор для резерва времени свершения события - R (i )

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

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

Tp(J ) = 0 .

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

Тр(С ) = Тп(С ) .

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

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

Резерв времени события i определяется непосредственно на сети путем вычитания из величины, записанной в правом секторе события Тп(i ) величины, записанной в левом секторе - Тр(i ). Найденная величина и является резервом времени свершения события и записывается в нижнем секторе события.

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

На рис. 1 приведен расчет сети непосредственно на графике.

Рис. 1. Расчет параметров сетевого графика

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

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

Таблица 1

Расчет параметров работ сетевого графика

i -j	Продолжительность работы, tij	Раннее начало работы, t р. н.	Раннее окончание работы, t р. о.	Позднее начало работы, t п. н.	Позднее окончание работы, t п. о.	Резервы времени	Коэффициент напряженности работы, К н
полный, R п	свободный, R с

Анализ и оптимизация сетевого графика

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

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

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

,

где - соответствующее значение функции Ф(Z ), взятое из таблицы нормального распределения; Z - аргумент нормальной функции распределения вероятности.

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

,

где ij кр - последовательность работ, лежащих на критическом пути;

К - количество работ, составляющих критический путь;

Дисперсия работы, лежащей на критическом пути.

Пример. Для графика, изображенного на рис. 1, определить вероятность выполнения проекта в заданный директивный срок, равный 8 ед. времени. Ранее было определено, что расчетный срок выполнения проекта составляет Ткр = 9 ед. Предположим, что также определены и дисперсии работ, составляющих критический путь, пусть например:

тогда и .

Пользуясь таблицей значений функции Лапласа по величине Z = - 1,7 (см. табл. 2), находим искомую вероятность РК » 0,045.

Вывод. При планировании в системах СПУ принято, что если:

0,85 < РК < 0,65 - то это считается границами допустимого риска (то есть считается нормальным положением); при РК < 0,85 - то считается, что опасность нарушения заданного срока очень большая (неприемлема) и необходимо в этом случае и произвести повторное планирование с перераспределением ресурсов с целью минимизации срока выполнения проекта; при РК > 0,65 - считается вероятность слишком велика, то есть на работах критического пути имеются избыточные ресурсы. В этом случае тоже производят повторное планирование с целью сокращения потребных ресурсов.

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

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

Таблица 2

Таблица значений функции Лапласа Рк = Ф (Z )