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

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

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

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

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

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

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

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

Определим, прежде всего, ожидаемые (ранние) сроки t_i свершения событий (i) сетевого графика.

Рис. 6.

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

;

где – подмножество дуг сети, входящих в событие (j).

Исходное событие означает момент начала выполнения комплекса операций, следовательно, t₁ = 0. Событие (2) свершится спустя 2 единицы времени после свершения события (1), т.к. время выполнения операции (1,2) равно 2. Значит, Событию (3) предшествуют два пути и . Значит,

и т. д.

Расчеты приведены в табл. 4.2.

Значения t_i , , приписаны соответствующим событиям на рис. 6.

Ожидаемый срок свершения события (7) t₇=11 совпадает с критическим временем (суммарной продолжительностью операций, принадлежащих критическому пути). Возвращаясь от завершающего события к исходному, можно выделить операции, принадлежащие критическому пути. Критический путь в нашем примере выделен жирной линией. Увеличение времени выполнения любой операции, принадлежащей критическому пути, ведет к увеличению выполнения комплекса операций. Для некритических операций есть резервы времени.

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

;

,

где – подмножество дуг сети, исходящих из события (i).

В нашем примере .

, т. к. из события (5) исходит одна операция.

.

Из события (4) исходят три операции, поэтому

и т. д. (см. табл. 4.2).

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

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

.

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

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

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

.

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

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

.

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

.

Найдем резервы времени операции (4, 6) сетевого графика (рис. 6):

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

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

Таблица 4.2

N п/п	Сроки свершения событий	Резерв времени, Ri
Ранний, ti	Предельный,

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

Задачи для самостоятельного решения

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

а)

N	Код операции	Продолжительность операции
	0 – 1
	1 – 5
	1 – 2
	1 – 3
	2 – 4
	4 – 5
	3 – 5
	5 – 7
	5 – 6
	6 – 7
	2 – 7
	7 – 8
	8 – 9

б)

N	Код операции	Продолжительность операции
	1 – 2
	1 – 3
	1 – 4
	2 – 5
	2 – 6
	3 – 6
	4 – 6
	4 – 7
	5 – 8
	6 – 8
	7 – 8

4.2.Найти ранний и предельный сроки свершения всех операций, их резервы во времени, критический путь.

а)

б)

Список рекомендуемой литературы

1. Кузнецов Б.Т. Математические методы и модели исследования операций / Б.Т.Кузнецов. – М., 2005.

2. Костевич П.С. Математическое программирование. – Минск, 2003.

3. Кузнецов А.В. Математическое программирование. – Минск, 1984.

4. Пантелеев А.В. Методы оптимизации в примерах и задачах / А.В.Пантелеев, Т.А. Летова– М., 2002.

5. Количественные методы в экономических исследованиях / [М.В.Грачева и др.]; под общ. ред. М.В.Грачевой – М., 2004.