Грицюк С.Н., Мирзоева Е.В., Лысенко В.В. Математические методы и модели в экономике

Подождите немного. Документ загружается.

20

С. Н. Грицюк, Е. В. Мирзоева, В. В. Лысенко

мых при помощи сетевого графика. И для сокраще-

ния продолжительности проекта необходимо в первую

очередь сокращать продолжительность работ, лежа-

щих на критическом пути.

Следует отметить, что классический вид сетево-

го графика — это сеть, вычерченная без масштаба

времени. Поэтому сетевой график, хотя и дает чет-

кое представление о порядке следования работ, но

недостаточно нагляден для определения тех работ,

которые должны выполняться в каждый данный мо-

мент времени. В связи с этим небольшой проект пос-

ле упорядочения сетевого графика рекомендуется

дополнить линейной диаграммой проекта. Такая

линейная диаграмма для рассматриваемой сети пока-

зана на рис. 6.6.

При построении линейной диаграммы каждая рабо-

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

длина которого равна продолжительности этой работы.

При наличии фиктивной работы нулевой продолжитель-

ности (в рассматриваемой сети ее нет) она изображает-

ся точкой. События i и j, начало и конец работы (i, j)

помещают соответственно в начале и конце отрезка.

Отрезки располагают один над другим, снизу вверх в

порядке возрастания индекса i, а при одном и том же i —

в порядке возрастания индекса j (на рис. 6.6 вследствие

ограниченности места не показаны работы-отрезки,

выходящие из 2-, 3-, 4- и 5-го событий).

По линейной диаграмме проекта можно определить

критическое время, критический путь, а также резер-

вы времени всех работ.

Так, критическое время комплекса работ равно

координате на оси времени самого правого конца всех

отрезков диаграммы:

кр

= t (11)= 61 (сутки).

Для определения критического пути рассматриваем

работы-отрезки, конечные события которых совпада-

21

Математические методы и модели в экономике

ют с завершающим событием сети (в нашем примере

(9, 11) и (10, 11)). Затем находим отрезок (9, 10),

правый конец которого лежит на одной вертикали (10)

с левым концом одного из рассматриваемых ранее от-

резков (10, 11). Аналогично определяем и другие ра-

боты-отрезки критического пути: (6, 9), ..., (0, 3) (на

рис. 6.6 все они выделены жирным шрифтом).

Рис. 6.6

6.5.5. Временные параметры сетевых

графиков

В табл. 6.4 приведены основные временные пара-

метры сетевых графиков. Рассмотрим расчет и содер-

жание указанных параметров.

22

С. Н. Грицюк, Е. В. Мирзоева, В. В. Лысенко

Начнем с параметров событий. Ранее отмечалось,

что событие не может наступить прежде, чем свершат-

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

(i) свершения i-того события определяется продол-

жительностью максимального пути, предшествующе-

го этому событию: t

(i) = max t(L

пi

), где L

пi

— любой

путь, предшествующий i-тому событию, то есть путь

от исходного до i-того события сети.

Таблица 6.4

Элемент

сети, харак-

теризуемый

параметром

Наименование параметра

Условное

обозначение

параметра

Событие i

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

Поздний срок свершения

события

Резерв времени события

(i)i))

R (i) (i)i))

Работа (i,i,,

j))

Продолжительность работы

Ранний срок начала работы

Ранний срок окончания работы

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

Поздний срок окончания работы

Полный резерв времени работы

Свободный резерв времени

работы

t (i,j)

рн

(i,j)

ро

(i,j)

пн

(i,j)

по

(i,j)

Путь LL

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

Продолжительность

критического пути

Резерв времени пути

t (L) (L)(L)

кр

R (L) (L)(L)

Отсюда следует, что ранний срок свершения собы-

тия i — это самый ранний срок, к которому заверша-

ются все работы, предшествующие этому событию

Если событие i имеет несколько предшествующих

работ (рис. 6.7), то ранний срок свершения события i

находится так:

2

Математические методы и модели в экономике

Рис. 6.7 Рис. 6.8

Пусть B(i) — множество работ, непосредственно

предшествующих событию i. Тогда

(i) = max {t

(k)+ t(k,i)�, (k,i)  B(i). (6.23)

Задержка свершения события i по отношению к

своему раннему сроку не отразится на сроке сверше-

ния завершающего события (а значит, и на сроке вы-

полнения комплекса работ) до тех пор, пока сумма

срока свершения этого события и длины максимально-

го из последующих за ним путей не превысит длины

критического пути.

Поэтому поздний срок t

(i) свершения i-го собы-

тия равен: t

(i) = t

кр

– max t(L

), где L

— любой

путь, следующий за i-м событием, то есть путь от i-го

до завершающего события сети.

Если событие i имеет несколько последующих ра-

бот (рис. 6.8.), то поздний срок свершения события i

удобно находить по формуле:

(i) = min{t

(j) – t(i,j)�, (i,j)  C(i),

где C

– множество работ (i,j), выходящих из вер-

шины i.

При любом поздний срок свершения со-

бытия i находится так: сначала при i = n полагают

(6.24)

2

С. Н. Грицюк, Е. В. Мирзоева, В. В. Лысенко

(n) = t

кр

, затем последовательно для i рав-

ным n-1, n-2,..., 1 вычисляют по формуле (6.24).

Резерв времени i-го события определяется как

резерв между поздним и ранним сроком его свер-

шения:

R(i)= t

(i) – t

(i).

Резерв времени i-го события показывает, на ка-

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

этого события, не вызывая при этом увеличения

времени выполнения комплекса работ.

Критические события резервов времени не име-

ют, так как любая задержка в свершении события,

лежащего на критическом пути, вызовет такую же

задержку в свершении завершающего события.

Из этого следует, что для определения критичес-

кого пути (если он единственный) вовсе не обяза-

тельно перебирать все полные пути сетевого графи-

ка и определять их длины. Определив ранний срок

наступления завершающего события сети, мы тем

самым определим длину критического пути, а вы-

явив события с нулевыми резервами времени, опре-

делим его конфигурацию.

Если критических путей несколько, то выявление

их с помощью критических событий может быть за-

труднительно, так как через часть критических со-

бытий могут проходить как критические, так и не-

критические пути. В этом случае для определения

критических путей следует использовать критичес-

кие работы.

Пример

По рис. 6.9 рассчитать ранние и поздние сроки

свершения событий, а также их резервы. Найти кри-

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

длину.

(6.25)

2

Математические методы и модели в экономике

Рис. 6.9

Решение

Каждую вершину сети разобьем на четыре сектора.

В верхней части сектора отмечаем номер события i, в

левой — ранний срок свершения события i, в правой —

поздний срок свершения события i и в нижней — ре-

зерв времени этого события (рис. 6.10).

Рис. 6.10

Сначала по формуле (6.23) находим ранние сроки

свершения события i и заносим их в левые секторы

сетевого графика. Имеем:

(1) = 0;

(2) = 0 + 15 = 15;

(3) = 15 + 16 = 31;

(4) = 15 + 6 = 21;

2

С. Н. Грицюк, Е. В. Мирзоева, В. В. Лысенко

(5)=31 + 6=37;

(6) = 21 + 5 = 26;

(7) = max{37 + 8; 26 + 6} = 45;

(8) = 26 + 8 = 34;

(9) = max{45 + 2; 26 + 14; 34 + 4} = 47;

(10) = 47 + 3 = 50.

Теперь рассчитаем поздние сроки свершения со-

бытий. Начинаем с последнего события и затем, «пя-

тясь», движемся к первому событию.

Для i = 10 поздний срок свершения события t

(10) =

= t

(10) = 50. Далее по формуле (6.24) имеем:

(9) = 50 – 3 = 47;

(8) = 47 – 4 = 43;

(7) = 47 – 2 = 45;

(6) = min{45 – 6; 47 – 14; 43 – 8} = 33;

(5) = 45 – 8 = 37;

(4) = 33 – 5 = 28;

(3) = 37 – 6 = 31;

(2) = min{31 – 16; 28 – 6} = 15;

(1) = 15 – 15 = 0.

Результаты расчета заносим в правые секторы вер-

шин сети.

По формуле (6.23) рассчитаем резервы времени

каждого события и занесем их в нижние секторы

вершин.

Например:

R(1) = 0 – 0 = 0;

R(2) = 15 – 5 = 0;

R(3) = 31 – 31 = 0;

R(4) = 28 – 21 = 7 и т. д.

Чтобы определить критический путь, фиксируем

события, не имеющие резервов времени. Это события

1, 2, 3, 5, 7, 9, 10. Следовательно, путь 1→2→3→5→7→

9→10 является критическим.

Длина критического пути t

кр

= t

(10) = 50.

Критический путь отмечаем на сетевом графике

двойной стрелкой.

Теперь перейдем к параметрам работ.

2

Математические методы и модели в экономике

Отдельная работа может начаться в ранние, позд-

ние или другие промежуточные сроки. Ранний срок

рн

(i, j) начала работы (I, j) – это наиболее ранний

(минимальный) из возможных моментов начала дан-

ной работы. Он, очевидно, совпадает с ранним сро-

ком наступления ее начального события, то есть

рн

(i, j) = t

(i) (6.26)

Тогда ранний срок t

ро

(i, j) окончания работы (i, j)

определяется по формуле

ро

(I, j) = t

(i) + t(i, j).

Поздний срок t

по

(i,j) окончаний работы (i, j) —

наиболее поздний момент времени окончания этой ра-

боты, после которого остается столько времени, сколь-

ко его необходимо для выполнения всех последующих

работ. И так как ни одна работа не может окончиться

позже допустимого позднего срока своего конечного со-

бытия j, поздний срок окончания работ (i, j) определя-

ется соотношением

по

(i, j) = t

(j),

а поздний срок t

пн

(i, j) начала этой работы — со-

отношением

пн

(i, j) = t

(j) – t(i, j).

Из формул (6.26)—(6.29) видно, что моменты на-

чала и окончания работы тесно связаны с соседними

событиями.

Прежде чем рассматривать резервы времени работ,

обратимся к резерву времени пути. Такие резервы

имеют все некритические пути. Резерв времени пути

R(L) определяется как разность между длиной кри-

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

(6.26)

(6.27)

(6.28)

(6.29)

2

С. Н. Грицюк, Е. В. Мирзоева, В. В. Лысенко

R(L)= t

кр

– t(L).

Он показывает, насколько в сумме могут быть уве-

личены продолжительности всех работ, принадлежа-

щих этому пути. Если затянуть выполнение работ,

лежащих на этом пути, на время, большее, чем R(L),

то критический путь переместится на путь L. Отсюда

можно сделать вывод: любая из работ пути L на его

участке, не совпадающем с критическим путем, обла-

дает резервом времени.

Среди резервов времени работ выделим полный и

свободный резервы времени.

Полный резерв времени R

(i, j) работы (i, j) —

это максимально допустимое время, на которое можно

увеличить продолжительность работы (i,j) или отло-

жить начало ее выполнения так, что это не вызовет

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

резерв времени работы вычисляется по формуле:

(i,j) = t

(j) – t

(i) – t(i,j) =

= t

по

(i,j) – t

ро

(i,j).

Этим резервом можно располагать при выполнении

данной работы, если ее начальное событие свершится

в самый ранний срок и можно допустить свершение

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

Полный резерв времени работы равен резерву мак-

симального из путей, проходящих через данную ра-

боту. При использовании полного резерва времени

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

работ, лежащих на максимальном пути, проходящем

через нее, будут полностью исчерпаны. Этот путь

становится критическим. Резервы времени остальных

путей, проходящих через эту работу, сократятся на

величину использованного резерва.

Если полный резерв времени некоторой работы равен

нулю, то задержка ее выполнения вызовет такую же по

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

(6.30)

(6.31)

2

Математические методы и модели в экономике

Свободный резерв времени R

(i, j) работы (i, j) —

это максимальный запас времени, на который ее можно

отложить (если она была запланирована в ранний срок)

или увеличить ее продолжительность (если эта работа

началась в ранний срок), не изменив при этом раннего

срока ее конечного события.

Этим резервом можно располагать при выполнении

данной работы в предположении, что ее начальное и

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

Свободный резерв времени (i, j) находится по

формуле

(i,j) = t

(j) – t

(i) – t(i, j).

Свободный резерв времени работы является частью

полного резерва. Справедлива формула

(i,j) = R

(i,j) + t

(j) – t

(j).

Если на критическом пути лежит событие j, то

(i,j) = R

(i,j).

Если использовать свободный резерв времени ра-

боты, то длина любого пути, проходящего через эту

работу, сокращается на величину свободного резерва.

На таких путях сохраняются свободные резервы всех

последующих работ.

Свободным резервом времени пользуются для пре-

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

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

ние работ по ранним срокам их начала и окончания,

то всегда будет возможность при необходимости пе-

рейти на поздние сроки начала и окончания работ.

Работы, лежащие на критическом пути, так же как

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

Пример

Вычислить для сетевого графика, изображенного

на рис. 6.9, ранние и поздние сроки начала и оконча-

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

(6.32)

(6.33)