Стариков А.В., Кущева И.С. Экономико-математическое и компьютерное моделирование: методические указания

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

где максимум берется по всем работам (k, i),

входящим в событие i; t(k,i) – длительность работы

(k,i).

Поздние сроки свершения событий T

(i)

рассчитываются от завершающего к исходному

событию:

1) для завершающего события T

(З)=T

(З),

2) для всех остальных событий

[

]

),()(min)(

),(

jitjTiT

−

∀

где минимум берется по всем работам (i, j), выходящим из события i, t(k,i) –

длительность работы (k,i).

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

сроков событий:

– T

рн

(i,j) = T

(i) – ранний срок начала работы,

– T

ро

(i,j) = T

(i) + t(i,j) – ранний срок окончания работы,

– T

по

(i,j) = T

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

– T

пн

(i,j) = T

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

– R

(i,j) = T

(j) – T

(i) – t(i,j) – полный резерв работы показывает

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

работы (i,j), или отсрочить ее начало, чтобы не нарушился срок

завершения проекта в целом,

– R

(i,j) = T

(j) – T

(i) – t(i,j) – свободный резерв работы показывает

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

работы (i,j), или отсрочить ее начало, не меняя ранних сроков начала

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

– R(i) = T

(j) – T

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

разность между поздним и ранним сроками его свершения.

Путь – это последовательность работ в сетевом графике, в которой

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

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

события. Критический путь – максимальный по продолжительности полный

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

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

Подкритический путь – полный путь, ближайший по длительности к

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

Для проведения анализа временных параметров сетевой модели

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

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

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

(раннее начало и раннее окончание работ). График привязки можно построить

(i)

)

t(i,j

)

t(i,j

)

на основе данных о продолжительности работ. Основное правило составления:

работа (i,j), может выполняться только после того, как будут выполнены все

предшествующие ей работы (k,i).

При поиске критических путей на сетевом графике используются

следующие условия его критичности:

– необходимое условие – нулевые резервы событий, лежащих на

критическом пути,

– достаточное условие – нулевые полные резервы работ, лежащих на

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

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

событий

Задача. Исходные данные для построения заданы в виде таблицы

Текущая работа Предшествующая работа Длительность работы

A – 4

B – 5

C – 2

D A 3

E B 2

F B 4

G D 8

H D 9

J EF 6

K FC 8

L HJ 10

M K 6

Построить сетевую модель и определить критические пути модели.

Решение. Построим сетевую модель (рис. 5.2) по вышеуказанным

правилам:

I 0

2 5 8 9

3 6

Рис. 5.2

Начальными работами являются А, В, С, так как им не предшествуют

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

начального события 1. Далее наносится работа D. Она должна начинаться после

окончания выполнения работы А. Графически работа D изображается стрелкой

выходящей из события 4, которое обозначает завершение работы А. Работы E и

F являются параллельными (обе начинаются после завершения работы B и

предшествуют работе J). Для их распараллеливания вводится фиктивная работа

I и событие 3. Фиктивная работа изображается пунктирной линией и ее

продолжительность равна нулю. Аналогично наносятся другие работы.

Теперь рассчитаем временные параметры событий. Согласно правилу,

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

завершающему. Для исходного события 1, очевидно, t

(1)=0. Для второго

события согласно вышеприведенной формуле

(2) = t

(1) + t(1,2) = 0 + 5 = 5.

Третьему событию предшествует два события (первое и второе) поэтому

(3) = max [t

(0) + t(0,3); t

(1) + t(1,3)] = max [0 +2; 5 + 4] = max [2; 9] =9.

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

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

события

кр

= t

(9) = 26 (дней).

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

справа налево (от завершающего к исходному событию).

Для завершающего события поздний срок свершения события совпадает с

ранним сроком t

(9) = t

(9) =26. Для восьмого события поздний срок свершения

согласно вышеприведенной зависимости будет равен

(8) = t

(9) – t(8,9) = 26 – 10 = 16.

Для седьмого события существуют два последующих события (восьмое и

девятое) поэтому

(7) = min [t

(8) – t(7,8); t

(9) – t(8,9)] = min [16 –9; 26 – 8] = min [7; 18] =7.

Аналогично, определяются поздние сроки свершения для других

событий.

Теперь рассчитываются резервы R(i) событий как разность между

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

события

R(6)= t

(6) – t

(6) = 20 – 12 = 8 (дней).

В итоге получается сетевая модель (рис. 5.3) с рассчитанными

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

I 0

Рис. 5.3

Осталось определить критический путь (пути). Согласно необходимому

условию два полных пути L

=1,4,7,8,9 и L

=1,4,7,9 могут быть критическими,

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

равны нулю. Из сетевого графика видно, что проверять стоит только работы G,

H, L, которыми L

и L

различаются. Проверим достаточное условие

критичности для работ H (7,8) и G (7,9)

(7,9) = t

(9) – t

(7) – t(7,9) = 26 – 7 – 8 = 11

(7,8) = t

(8) – t

(7) – t(7,8) = 16 – 7 – 9 = 0

Раз полный резерв работы H не равен нулю, путь L

= 1,4,7,9 не является

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

критический путь L

= 1,4,7,8,9 длительностью t

кр

= t

(9) = 26 дней.

Задание 2. На основе условия, выданного преподавателем, построить

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

Определить критический путь (пути).

Общие рекомендации

При поиске критических путей следует помнить, что признаком

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

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

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

любой из работ критического пути обязательно приведет к увеличению

первоначальной длительности проекта (T

). Критический путь является полным,

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

Из вышеприведенных соображений следует способ определения

критического пути на графике привязки:

1) найти на графике привязки и выписать работу (i,j), которая

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

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

2) из всех работ сети (k,i), конечное событие которых i совпадает с

начальным событием i работы (i,j), найденной в п. 1), выбрать и выписать ту,

которая на графике вплотную примыкает к работе (i,j),

3) из всех работ сети (l,k), конечное событие которых k совпадает с

начальным событием k работы (k,i), найденной в п. 2), выбрать и выписать ту,

которая на графике вплотную примыкает к работе (k,i),

4) продолжать п. 3) до тех пор, пока не будет найдена исходная работа

сети, т.е. начинающаяся в нулевой момент времени (ее начальное событие

будет иметь номер исходного события сети, например 1).

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

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

удовлетворяющих сформулированным требованиям. В этом случае необходимо

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

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

на поиск критически путей.

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

Задача. Используя исходные данные предыдущей задачи, построить

график привязки сетевой модели, определить критические пути и их

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

работы.

Решение. Для наглядного представления выполнения проекта

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

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

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

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

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

В рассматриваемой задаче работа с кодом (1-2) начинается с нулевой

отметки и, соответственно длительности, будет длиной в 5 единиц. Следующая

работа с кодом (1-3) откладывается также от нулевой отметки. После того как

откладываются все работы, оканчивающиеся в событии 3 (в нашем случае это

работы (1-3) и (2-3)), выбирается самая дальняя точка (в нашем случае это точка

окончания работы (2-3)) и от нее откладываются работы, начинающиеся в

событии 3 (события (3-5) и (3-6)). Аналогично строятся все остальные работы

составляющие сетевую модель.

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

рис. 5.4.

123456789101112131415 1716 18192021222324 2526

1-2

1-3

1-4

2-3

2-5

3-5

3-6

4-7

7-8

5-8

6-9

7-9

8-9

6 9

Код

работы

t,дни

Рис. 5.4

Приступим к поиску критических путей. Начнем с работ, завершающих

проект. На графике привязки (рис. 5.4) единственная работа (8-9) заканчивается

позже остальных в завершающем событии № 9. Запишем эту работу как

критическую

кр1

=. . . (8-9). (5.1)

Далее найдем критическую работу, предшествующую работе (8-9). Код

этой работы должен оканчиваться на 8. Таких работ две – (7-8) и (5-8). Но

только одна из них, работа (7-8) по времени своего окончания вплотную

«примыкает» на графике к началу работы (8-9). Допишем слева найденную

критическую работу (7-8) к выражению (5.1)

кр1

=. . . (7-8);(8-9). (5.2)

Теперь найдем критическую работу, предшествующую (7-8). Код этой

работы должен оканчиваться на 7. Только работа (4-7) по времени своего

окончания вплотную «примыкает» на графике к началу работы (7-8). Допишем

слева найденную критическую работу (4-7) к выражению (5.2)

кр1

=. . . (4-7);(7-8);(8-9). (5.3)

Снова ищем следующую критическую работу. Код этой работы должен

оканчиваться на 4. Работа (1-4) по времени своего окончания вплотную

«примыкает» на графике к началу работы (4-7). С этой работы начинается

критический путь L

кр1

. В итоге получаем

кр1

=(1-4);(4-7);(7-8);(8-9). (5.4)

В другой форме записи L

кр1

=1,4,7,8,9. Для наглядности выделим на

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

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

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

резервов. Рассмотрим некритические работы, начиная с конца табл. 5.1.

Таблица 5.1

Код работы

t(i,j) R

(i,j)

Критичность

1-2 (B) 5 0 1 –

1-3 (C) 2 7 8 –

1-4 (A) 4 0 0 критическая

2-3 (F) 4 0 1 –

2-5 (E) 2 2 3 –

3-5 (I) 0 0 1 –

3-6 (K) 8 0 3 –

4-7 (D) 3 0 0 критическая

5-8 (J) 6 1 1 –

6-9 (M) 6 3 3 –

7-8 (H) 9 0 0 критическая

7-9 (G) 8 11 11 –

8-9 (L) 10 0 0 критическая

Работа (7-9), согласно графику привязки (рис. 5.4) заканчивается в 15-й

день, а завершающее событие 9 сети, в которое она входит, наступает лишь в

26-й день. Т.е. если работа (7-9) задержится на 11 дней, то это не повлияет на

срок выполнения проекта (L

кр

=26 дней). Поскольку (7-9) завершающая работа

сети, то ее полный и свободный резервы равны

(7-9)= R

(7-9)=11.

Работа (6-9) заканчивается в 23-й день, а завершающее событие 9 сети, в

которое она входит, наступает лишь в 26-й день. То есть если работа (6-9)

задержится на 3 дня, то это не повлияет на срок выполнения всего проекта.

Поскольку (6-9) завершающая работа сети, то ее полный и свободный резервы

равны R

(6-9)= R

(6-9)=3.

Работа (5-8) заканчивается в 15-й день, в то время как последующая

работа (8-9) начинается в 16-й день. Следовательно, работа (5-8) может

задержаться на 1 день и это никак не повлияет на время начала последующей

работы (8-9), т.е. R

(5-8)=1.

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

свободного резерва и минимального из полных резервов непосредственно

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

За работой (5-8) следует только критическая работа (8-9) с нулевым

полным резервом. Поэтому, согласно правилу 1

(5-8)= R

(5-8) + R

(8-9)=1+0=1.

Работа (3-6) заканчивается в 17-й день, в этот же день начинается

следующая работа (6-9), т.е. любая задержка выполнения работы (3-6) приведет

к задержке начала работы (6-9). Это означает, что работа (3-6) не имеет

свободного резерва R

(3-6)=0. Но если сдвинуть во времени работу (3-6) на 3

дня, то работа (6-9) также сдвинется на 3 дня и это не нарушит срок

выполнения проекта, так как у работы (6-9) есть временной резерв. Таким

образом, согласно правилу 1

(3-6)= R

(3-6) + R

(6-9)=0+3=3.

Работа (3-5) заканчивается в 9-й день, в этот же день начинается

следующая работа (5-8), это означает, что работа (3-5) не имеет свободного

резерва R

(3-5)=0. Полный резерв согласно правилу 1 будет равен

(3-5)= R

(3-5) + R

(5-8)=0+1=1.

Работа (2-5) заканчивается в 7-й день, в то время как последующая работа

(5-8) начинается в 9-й день. Следовательно, работа (2-5) может задержаться на 2

дня и это никак не повлияет на время начала последующей работы (5-8), то есть

(2-5)=2. Кроме того, поскольку последующая работа (5-8) имеет резерв в 1

день, то, в общем, работу (2-5) можно сдвинуть на 3 дня и это не нарушит

сроков проекта, т.е.

(2-5)= R

(2-5) + R

(5-8)=2+1=3.

Работа (2-3) заканчивается на 9-й день, и в этот же день начинаются

следующие работы (3-5) и (3-6). То есть работа (2-3) не имеет свободного

резерва времени R

(2-3)=0. Поскольку после работы (2-3) следуют две работы с

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

(2-3)= R

(2-3) + min[R

(3-5); R

(3-6)]=0+min[1;3]=0+1=1.

Работа (1-3) заканчивается во 2-й день, а следующие за ней работы (3-5) и

(3-6) начинаются на 9-й день, т.е. R

(1-3)=7. Полный резерв будет равен

(1-3)= R

(1-3) + min[R

(3-5); R

(3-6)]=7+min[1;3]=7+1=8.

Наконец, работа (1-2) заканчивается в 5-й день, а следующие за ней

работы (2-5) и (2-3) начинаются в тот же день, т.е. R

(1-2)=0.

Полный резерв, согласно правилу 1, будет равен

(1-2)= R

(1-2) + min[R

(2-3); R

(2-5)]=0+min[1;3]=0+1=1.

Ненулевые свободные резервы работ обозначены на графике привязки в

виде пунктирной линии (рис. 5.4).

Задание 3. Построить график привязки и определить свободные и полные

резервы каждой работы.

Вопросы для самопроверки

1. Для решения каких задач предусмотрены методы сетевого

планирования?

2. Что называют работой в сетевом планировании? Событием?

3. Какая работа называется действительной? Ожиданием? Фиктивной?

4. Какими способами задаются исходные данные для построения сетевой

модели?

5. Что называют сетевым графиком?

6. Каким образом строится сетевой график?

7. Какие правила необходимо соблюдать при построении сетевого

графика?

8. Что понимается под расчетом сетевых моделей?

9. Какие основные временные параметры определяют при анализе

сетевой модели проекта?

10. Каким образом определяются ранние и поздние сроки наступления

события?

11. Что такое путь в сетевом графике, какие виды путей выделяют при

сетевом моделировании?

12. Какие условия критичности характерны для критического пути?

13. Для чего используется график привязки?

14. Правила построения графика привязки?

15. Принципы вычисления резервов работ.

16. Какова взаимосвязь полного и свободного резервов работы?