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

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

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

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

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

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

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

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

Рис. 6.

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

;

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

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

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

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

Ожидаемый срок свершения события (7) t 7 =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

	Сроки свершения событий		Резерв времени, R i
	Ранний, t i	Предельный,

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

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

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

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

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

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

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

Пусть продолжительности выполнения операций известны (Рис. 5.5; продолжительности операций расположены у соответствующих дуг графика).

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

.

В событие (4) входят две дуги, исходящие из событий (1) и (3), для которых ожидаемые сроки свершения найдены. Следовательно, ожидаемый срок свершения события (4)

Аналогично находятся ожидаемые сроки свершения событий (5), (6) и (7). Значения ,
приписаны соответствующим событиям.

Общая формула нахождения ожидаемых сроков свершения событий имеет вид:

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

Ожидаемый срок свершения события (7)
совпадает с критическим временем (суммарной продолжительностью операций, принадлежащих критическому пути). Возвращаясь теперь от завершающего события к исходному, выделим операции, принадлежащие критическому пути. Из трех операций, входящих в событие (7),
определила операция (5,7), выполнение которой начинается после свершения события (5) и продолжается 3 ед. времени. Момент свершения события (5) определила операция (3,5), так как
. В свою очередь момент свершения события (3) определила операция (2,3), а события (2) – операция (1,2). Эти операции на рис. 5.6 выделены жирной линией. Таким образом, критический путь. Увеличение времени выполнения любой операции, принадлежащей критическому пути, ведет к увеличению времени выполнения всего комплекса операций. Напротив, увеличение времени выполнения или задержка с выполнением некритических операций может не отразиться на сроке свершения завершающего события. Так, например, время выполнения операции (4,5) может быть увеличено, или начало ее выполнения может быть отсрочено на 1 ед. времени, и это не отразится на сроке свершения события (5), а, следовательно, и всего комплекса операций.

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

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

В нашем примере
. Определим этот показатель для оставшихся событий. Из события (5) исходит одна операция, следовательно,
. Аналогично
. Из события (4) исходят три операции, поэтому

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

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

.

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

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

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

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

Так резервы времени операции (4,6) сетевого графика составляют (Рис. 5.5):

Рис. 10. Временные параметры событий

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

t P j = t(L Ij). (1)

Максимальное время завершения всех k работ, входящих в j-е событие:

t P i = ( + ). (2)

Для исходного события ранний срок свершения события t P I = 0, для завершающего события t P J = t кр.

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

t ni = t кр - t(L iJ). (3)

Минимальная разница между поздними сроками свершения последующих событий для всех k работ, выходящих из i-го события и длительностью этих работ:

t n i = ( + ). (4)

Поздний срок свершения завершающего события t nJ = t PJ = t кр.

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

R i = t ni - t pi . (5)

События критического пути имеют нулевой резерв времени.

Определим временные параметры событий непосредственно на сетевом графике (рис. 11).

Рис. 11. Расчет временных параметров событий

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

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

Результаты расчета представлены в табл. 2.

Таблица 2

№ события	Сроки свершения события	Резерв события (R i)
t pi	t ni

Расчет временных параметров работ

Для иллюстрации расчетов рассмотрим следующее графическое построение (рис. 12).

Рис. 12. Временные параметры работ и событий

Поздний срок начала работы t n н ij:

t n н ij = t nj - t ij . (9)

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

R nij = t nj - t pi - t ij . (10)

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

R ч ij = t nj - t ni - t ij , (11)

R ч ij = t nij - R i . (12)

Свободный резерв времени работы R с ij – это часть полного резерва, на которую можно увеличить время завершения работы, уложившись в ранний срок свершения ее последующего события:

R с ij = t pj - t pi - t ij , (13)

R с ij = t nij - R j . (14)

Независимый резерв времени работы R н ij – это часть полного резерва, которая используется на увеличение продолжительности только данной работы, при этом все предшествующие работы могут заканчиваться в свои поздние сроки, а все последующие – в ранние:

R н ij = t pj - t ni - t ij , (15)

R н ij = R nij - R i - R j . (16)

Использование независимого резерва не влияет на величину резерва времени других работ.

Частные случаи при расчете резервов:

1. Если на критическом пути лежит событие i, то из выражения (12) следует

R i = 0; R nij = R ч ij .

2. Если на критическом пути лежит событие j, то из выражения (14) следует

R j = 0; R nij = R cij .

3. Если на критическом пути лежат и событие i и событие j, но сама работа не принадлежит критическому пути, то для этой работы все резервы равны

R i = 0; R j = 0; R nij = R ч ij = R cij = R н ij .

Коэффициент загруженности работы К з.

Результаты расчета временных параметров работ представлены в табл. 3.

Таблица 3

Код работы i - j	Длительность работы, t ij	Сроки работы	Резервы времени	Коэффициент загруженности, К з
t рн	t ро	t nн	t no	R n	R ч	R с	R н
1 – 2
2 – 3
2 – 4										0,5
2 – 5										0,23
3 – 5
3 – 6
4 – 6
4 – 9										0,34
5 – 8										0,58
6 – 7
7 – 8
8 – 9
9 – 10

Сетевое планирование в условиях неопределенности

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

1. Оптимистическая (минимальная) оценка t oij .

2. Пессимистическая (максимальная) оценка t nij .

3. Наиболее вероятная оценка t н.в ij .

Тогда среднее (ожидаемое) время выполнения работы определяется выражением

t o ж ij = ,

или, если известны только крайние оценки:

Тема 2. Элементы теории массового обслуживания

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

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

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

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

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

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

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

СМО с простейшими потоками требований обладают следующими свойствами: стационарностью, ординарностью и отсутствием последействия.

Стационарным называется поток, характер которого с течением времени не меняется.

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

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

Если поток требований простейший, то его можно описать количественно с помощью функции Пуассона:

Р к (t) = , (2)

где Р k (t) – вероятность того, что в течение времени t в систему поступит точно k требований на обслуживание (k = 0,1,2 …).

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

где lt – среднее число требований, поступивших на обслуживание за время t.

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

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

КУРСОВАЯ РАБОТА

по предмету: «Математические методы»

на тему: «Основные временные параметры сетевых графиков и их расчеты»

Теория графов – область дискретной математики, которая занимается исследованием и решением разнообразных проблем, связанных с объектом, называемым графом. Граф определяется заданием двух множеств. Первое – X – множество вершин графа. Элементы этого графа можно изобразить в виде точек плоскости или пространства. Второе – U – множество пар элементов из Х. Каждый элемент множества U указывает пару вершин, между которыми существует связь; она может изображаться линией, соединяющей соответствующие вершины графа. При таком изображении требуется, чтобы линия проходила только через вершины, которые она соединяет, и чтобы разные линии могли пересекаться только в вершинах. Иногда в парах составляющих множество U, указывается, какая вершина является первой. В этом случае элементы множества U называются дугами графа (X, U), а сам граф – ориентированным. Если ориентация не указана, то элементы U называются ребрами, а граф (X, U) – неориентированным графом или про сто графом. Элемент U, указывающий на связь вершины с ней самой, называется петлей.

Граф (X, U) называется конечным, если множества X и U состоят из конечного числа элементов. В противном случае граф (X, U) называется бесконечным.

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

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

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

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

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

Ранний срок наступления события, характеризующий наиболее ранний из возможных сроков совершения того или иного события;

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

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

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

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

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

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

Тогда

Поскольку к событию 2 идет только один путь от события 1, то выбирать максимальные продолжительности путей не приходится:

. Сказанное только что относится и к данному расчету. Поиному обстоит дело, когда мы подошли к событию 4. К нему ведут два пути: прямой от события 1 и опосредствованный событием 2. Здесь надо использовать во всей полноте нижеприведенную формулу:

Значит, 4-е событие сможет наступить на 14-й день от общего начала работ (но не через 7 дней, как это может показаться вначале).

Продолжаем расчеты. Очередным является событие 5. К нему ведут два пути: от события 4 и от события 3. Применяем формулу

Аналогично поступаем и с расчетами ранних сроков наступления событий 6 и 7:

Затем рассчитываем

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

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

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

.

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

Определим этот показатель для последующих событий:

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

; ;

В конце рассчитываем

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

Полученный результат говорит о том, что расчеты произведены правильно.

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

Временные параметры сети состоят из временных параметров событий и временных параметров работ. Рассмотрим содержание и алгоритм расчета временных параметров событий .

Временем Т j наступления (или свершения) события j считается момент окончания всех работ, входящих в это событие.

Минимальное (самое раннее) время Т j о наступления события j равно длине максимальному из путей, предшествующих данному событию. Очевидно, что это время является и самым ранним временем начала работ, выходящих из этого события. Например, в последнем примере событие 3 может свершиться не ранее, чем через 11 дней от исходного события, т.к. наибольшая длина пути, предшествующего данному событию (пути (0,2)-(2,3)) равна 11.

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

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

Т j о =maxí Т i о + t ij ý (1)

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

Проиллюстрируем алгоритм вычисления ранних времен на последнем примере.

Принимаем Т 0 о =0. Поскольку в событие 1 входит только одна работа (0,1) продолжительностью t 01 =2, то Т 1 о = Т 0 о + t 01 =0+2=2.

Рассмотрим далее событие 2 (Заметим, что событие 3 пока рассматривать нельзя, так как срок Т 2 о еще неизвестен). Таким образом, Т 2 о =Т 0 о + t 02 =0+5=5. Перейдем теперь к событию 3. Поскольку в него входят три дуги (0,3),(2,3) и (1,3), то

Т 3 о =maxí Т i о + t i3 ý= maxí 0 + 3; 2+4; 5+6ý=11.

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

Т 4 о = Т 2 о + t 24 = 5 + 2 = 7,

Т 5 о = Т 2 о + t 25 = 5 + 1 = 6,

Т 6 о = Т 3 о + t 36 = 11 + 3 = 14,

Т 7 о =maxí Т i о + t i7 ý= maxí7+10; 6+8ý=17,

Т 8 о =maxí Т i о + t i8 ý= maxí6+4; 14+3; 17+5ý=22.

На этом вычисления Т i о заканчиваются.

Теперь от завершающего события к исходному (справа налево) определяем Т i 1 - максимально допустимый (поздний) срок завершения всех работ, входящих в данное событие, при котором критическое время выполнения всего комплекса работ останется неизменным. Если обозначить n – завершающее событие сети, то Т n 1 = Т n 0 является отправной точкой алгоритма вычисления поздних сроков. В общем виде для любого события i,

Т i 1 =min í Т j 1 - t ij ý для всех дуг (i,j). (2)

Вычислим значения Т i 1 на последнем примере (рис.5).

Т 8 1 = Т 8 0 =22,

Т 7 1 = Т 8 1 - t 78 = 22 – 5 = 17,

Т 6 1 = Т 8 о - t 68 = 22 – 3 = 19,

Т 5 1 =min í Т j 1 – t 5j ý= miní17–8; 22 - 4ý=9,

Т 4 1 = Т 7 1 - t 47 = 17 – 10 = 7,

Т 3 1 = Т 6 1 - t 36 = 19 – 3 = 16,

Т 2 1 =min íТ j о - t 2j ý= miní16–6; 7 – 2; 9 - 1ý=5,

Т 1 1 = Т 3 1 - t 13 = 16 - 4 = 12,

Т 0 1 =min íТ j 1 – t 0j ý= miní12–2; 5 – 5; 16 – 3ý=0.

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

R i = Т i 1 - Т i 0 (3)

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

Таблица 1

Номер события	Сроки свершения события	Резерв времени R i
Ранний Т i о	Поздний Т i 1

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

Т j о = Т j 1 (4)

Т j о - Т i о =Т j 1 - Т i 1 = t ij

По существу, эти условия означают, что между ранним сроком начала (окончания) и поздним сроком начала (окончания) критической работы запас времени отсутствует. Условиям (4) удовлетворяют работы (0,2), (2,4), (4,7) и (7,8), т.е. они образуют критический путь, в чем мы и ранее убедились перебором всех полных путей.

Временные параметры работ .

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

R п ij =Т j 1 - Т i 0 - t ij (5)

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

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

Опоздание начала некритической работы (i,j) по сравнению с Т i 0 на всю величину ее полного резерва влечет за собой необходимость начинать все работы, выходящие из события j в наиболее позднее допустимое время Т j 1 наступления этого события.

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

R с ij =Т j 0 - Т i 0 - t ij (6)

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

Для рис. 5 проведем вычисления по формулам (5), (6):

Таблица 2

(i,j)	t ij	Т i 0	Т j 1	R п ij	R с ij
(0,1)
(0,2)
(0,3)
(1,3)
(2,3)
(2,4)
(2,5)
(3,6)
(4,7)
(5,7)
(5,8)
(6,8)
(7,8)

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

Отчетность