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

При анализе сетевого графика прежде всего вычисляют его временные параметры. К основным временным параметрам относятся:

- продолжительность критического пути (критический срок);

- сроки свершения и резервы сетей;

- сроки выполнения отдельных работ и их резервы времени.

Основные временные параметры

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

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

,

где - ранний срок свершения события i

- продолжительность работы i, j

- подмножество, включающее все работы входящие в событие j.

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

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

R(i)=

Резервы времени критических событий=0

Ранний срок начала работы совпадает с ранним сроком свершения событий i.

Ранний срок окончания работы определяется по формуле

Поздний срок окончания работы совпадает с поздним сроком свершения события j

Поздний срок начала работы определяется по формуле

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

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

Критические работы, как и критические события резервов не имеют.

Расчёт временных параметров сетевой модели проводят в 4 этапа:

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

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

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

Данные 3 этапа удобно проводить на сетевом графике

Для этого изображаемое событие делят на 4 сектора

R

N

tп

tp

N – номер события;

t_р - ранний срок свершения события;

t_п – поздний срок свершения события;

R – резерв времени события.

4) строим сводную таблицу временных параметров события

№	Рабо-та i j	Продолжитель-ность работы i j	Ранний срок	Поздний срок	Резерв времени
Оконча-ния работы	Нача-ло рабо-ты	Нача-ло рабо-ты	Окончание работы	Полный	Свобод-ный

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

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

Проведем расчет временных параметров на примере таблицы

А1

А3

А7

А5

А6

А4

А2

№	работа i j	Продолжительность работы i j	Ранний срок	Поздний срок	Резерв времени
Окончание работы	Начало работы	Начало работы	Окончание работы	Полный	свободный
	1,2
	1,3
	2,3
	2,5
	3,4
	4,5
	4,6
	5,6
гр.1

1,2

(y)

.

1,3

2,3

2,5

3,4

4,5

4,6

5,6

(t)

Критический путь составляет 14 дней.

Некоторые оптимизационные задачи сетевого планирования (оптимизация проекта во времени, по ресурсам, по стоимости)

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

Задача оптимизации проекта по времени с использованием дополнительных средств имеет 2 постановки:

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

Пусть задан сетевой график ,

где E -событие;

e – работа.

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

- коэффициенты использования дополнительных средств x_ij.

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

Математическая модель будет иметь следующий вид:

условная функция

(3)

(4)

(5)

Первое ограничение означает, что время завершения проекта не должно быть >

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

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

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

Пятое ограничение – условие неотрицательности.

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

Целевая функция будет иметь вид

Остальные ограничения (2)-(5) такие же как в предыдущей задачи.

Оптимизация проекта по ресурсам.

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

Оптимизация проекта по стоимости.

В общем случае стоимость выполнения работы зависит от её продолжительности. Пусть нормальная продолжительность работы. Ей соответствует минимальная стоимость выполнения работы. минимально возможная продолжительность работы. При этой стоимости работы будет максимальной .

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

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

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

Уменьшение продолжительности на величину приведёт к экономии средств на величину

В данном случае математическая модель задачи примет вид

Если , то оптимизация осуществляется за счёт увеличения продолжительности некритических работ; если > , то за счёт всех работ проекта.

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

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