Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:

Сетевое планирование

.pdf
Скачиваний:
22
Добавлен:
17.04.2015
Размер:
306.07 Кб
Скачать

L1= {0, 1, 2, 4, 5, 7, 8, 14, 15} =

32

L2= {0, 1, 2, 4, 5, 8, 14, 15} =

32

L3= {0, 1, 2, 4, 5, 6, 8, 14, 15} =

26

L4= {0, 1, 2, 4, 5, 9, 12, 14, 15} =

35

L5= {0, 4, 5, 7, 8, 14, 15} =

38

L6= {0, 4, 5, 8, 14, 15} =

38

L7= {0, 4, 5, 6, 8, 14, 15} =

32

L8= {0, 4, 5, 9, 12, 14, 15} =

41

L9= {0, 3, 4, 5, 7, 8, 14, 15} =

28

L10= {0, 3, 4, 5, 8, 14, 15} =

28

L11= {0, 3, 4, 5, 6, 8, 14, 15} =

22

L12= {0, 3, 4, 5, 9, 12, 14, 15} =

31

L13= {0, 3, 5, 7, 8, 14, 15} =

26

L14= {0, 3, 5, 8, 14, 15} =

26

L15= {0, 3, 5, 6, 8, 14, 15} =

20

L16= {0, 3, 5, 9, 12, 14, 15} =

29

L17= {0, 3, 6, 8, 14, 15} =

18

L18= {0, 3, 9, 12, 14, 15} =

19

L19= {0, 3, 10, 13, 14, 15} =

20

L20= {0, 3, 10, 11, 14, 15} =

26

L21= {0, 15} =

40

Критическим путем является путь Lкрит{0, 4, 5, 9, 12, 14, 15}=41.

11

PDF создан испытательной версией pdfFactory Pro www.pdffactory.com

 

5

 

 

 

 

 

 

 

 

1

2

 

 

 

7

1

 

 

 

 

 

 

 

 

 

 

 

 

 

3

 

 

 

 

 

 

2

 

 

10

 

 

 

 

 

 

 

 

 

 

8

 

 

 

 

 

 

 

11

 

 

 

 

 

1

 

 

3

 

 

16

4

5

 

 

 

 

 

 

 

 

 

0

 

 

3

 

 

14

 

 

 

2

 

 

2

3

 

3

 

 

6

 

 

 

 

 

 

 

2

 

 

12

 

3

 

2

 

 

 

 

 

 

 

13

 

 

 

 

1

 

 

 

 

 

2

 

 

 

 

 

 

 

 

 

7

 

 

 

5

 

9

 

 

13

 

 

 

 

 

 

 

 

 

 

 

 

7

 

 

 

2

 

2

 

 

 

 

 

 

 

 

 

 

 

 

 

10

 

7

 

15

 

 

 

 

 

 

11

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

40

 

 

 

 

 

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

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

III. Понятие временных характеристик сетевого графа

Основные временные параметры сетевых графов:

Элемент сети,

 

Условное

характеризуемый

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

обозначение

параметром

 

параметра

Событие i

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

tр(i)

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

tп(i)

 

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

R(i)

Работа(i,j)

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

t(i,j)

 

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

tрн(i,j)

 

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

tро(i,j)

 

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

tпн(i,j)

 

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

tпо(i,j)

 

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

Rп(i,j)

 

Частный резерв времени работы первого

R1(i,j)

 

вида

12

PDF создан испытательной версией pdfFactory Pro www.pdffactory.com

 

Частный резерв времени работы второго

 

 

вида

Rс(i,j)

 

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

 

 

Независимый резерв времени работы

Rн(i,j)

Путь L

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

t(L)

продолжительность критического пути

tкр

 

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

R(L)

1. Параметры событий:

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

t p (i) = maxt(Lпi )

Lпi

где Lпi любой путь, предшествующий i-ому событию, то есть путь от исходного до i-го события сети.

Если событие j имеет несколько предшествующих путей, а следовательно, несколько предшествующих событий i, то ранний срок свершения события j удобно находить по формуле:

t p ( j) = max{i, j} {t p (i) + t(i, j)}

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

Поэтому поздний срок tп(i) свершения i-го события равен:

tп (i) = tкр − maxt(Lci )

Lci

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

Если событие i имеет несколько последующих путей, а следовательно, несколько последующих событий j, то поздний срок свершения события I удобно находить по формуле:

tп (i) = min{i, j} {tn ( j) − t(i, j)}

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

R(i) = tn (i) − tp (i)

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

13

PDF создан испытательной версией pdfFactory Pro www.pdffactory.com

2. Параметры работ:

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

Очевидно, что ранний срок tрн(i,j) начала работы (i,j) совпадает с ранним сроком наступления начального (предшествующего) события i, то есть:

t рн (i, j) = t р (i)

Тогда ранний срок tро(i,j) окончания работы (i,j) определяется по формуле:

t ро (i, j) = t р (i) + t(i, j)

Ни одна работа не может окончиться позже допустимого позднего срока своего конечного события i. Поэтому поздний срок tпо(i,j) окончания работы (i,j) определяется соотношением:

tпо (i, j) = tп ( j)

а поздний срок tпн(i,j) начала этой работы соотношением:

tпн (i, j) = tп ( j) − t(i, j)

Резерв времени пути R(l) определяется как разность между длиной критического и рассматриваемого пути:

R(L) = tкр t(L)

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

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

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

Rп (i, j) = tn ( j) − t (i) − t(i, j)

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

R1 (i, j) = tn ( j) − tï (i) − t(i, j)

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

14

PDF создан испытательной версией pdfFactory Pro www.pdffactory.com

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

Rc (i, j) = t ð ( j) − t ð (i) − t(i, j)

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

Rí (i, j) = t ð ( j) − tï (i) − t(i, j)

I. Нахождение временных характеристик сетевого графа бизнес - проекта «Астория»

№ соб

tp(i)

tп(i)

R(i)

0

0

0

0

1

2

8

6

2

7

13

6

3

3

13

10

4

16

16

0

5

17

17

0

6

19

28

9

7

27

30

3

8

28

31

3

9

30

30

0

10

10

25

15

11

17

32

15

12

32

32

0

13

12

33

21

14

34

34

0

15

41

41

0

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

События 0, 4, 5, 9, 12, 14, 15 не имеют резервов времени (резервы времени равны нулю). Эти события образуют критический путь.

Найдем временные характеристики работ:

15

PDF создан испытательной версией pdfFactory Pro www.pdffactory.com

i

j

t(i,j)

Сроки начала и окончания

 

Резервы времени

 

п/п

 

 

 

tpн

tpо

tпн

tпо

Rп

 

R1

Rc

 

Rн

1

0

1

2

0

2

6

8

6

 

6

0

 

0

2

0

3

3

0

3

10

13

10

 

10

0

 

0

3

0

4

16

0

16

0

16

0

 

0

0

 

0

4

0

15

40

0

40

1

41

1

 

1

1

 

1

5

1

2

5

2

7

8

13

6

 

0

0

 

-6

6

2

4

3

7

10

13

16

6

 

0

6

 

0

7

3

4

3

3

6

13

16

10

 

0

10

 

0

8

3

5

2

3

5

15

17

12

 

2

12

 

2

9

3

6

2

3

5

26

28

23

 

13

14

 

4

10

3

9

5

3

8

25

30

22

 

12

22

 

12

11

3

10

7

3

10

18

25

15

 

5

0

 

-10

12

4

5

1

16

17

16

17

0

 

0

0

 

0

13

5

6

2

17

19

26

28

9

 

9

0

 

0

14

5

7

10

17

27

20

30

3

 

3

0

 

0

15

5

8

11

17

28

20

31

3

 

3

0

 

0

16

5

9

13

17

30

17

30

0

 

0

0

 

0

17

6

8

3

19

22

28

31

9

 

0

6

 

-3

18

7

8

1

27

28

30

31

3

 

0

0

 

-3

19

8

14

3

28

31

31

34

3

 

0

3

 

0

20

9

12

2

30

32

30

32

0

 

0

0

 

0

21

10

11

7

10

17

25

32

15

 

0

0

 

-15

22

10

13

2

10

12

31

33

21

 

6

0

 

-15

23

11

14

2

17

19

32

34

15

 

0

15

 

0

24

12

14

2

32

34

32

34

0

 

0

0

 

0

25

13

14

1

12

13

33

34

21

 

0

21

 

0

26

14

15

7

34

41

34

41

0

 

0

0

 

0

Резервы времени критических работ, так же как и резервы времени критических событий, равны нулю: (0,4); (4,5); (5,9); (9,12); (12,14); (14,15).

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

IV. Оптимизация сетевого графа по схеме «Время-стоимость»

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

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

При использовании метода «время-стоимость» предполагают, что уменьшение продолжительности работы пропорционально возрастанию её стоимости. Каждая работа (i,j) характеризуется продолжительностью t(i,j), которая может находиться в

пределах

a(i, j) ≤ t(i, j) ≤ b(i, j)

где a(i,j) – минимально возможная продолжительность работы (i,j), которую только можно осуществить в условиях разработки;

b(i,j) – нормальная продолжительность выполнения работы (i,j).

16

PDF создан испытательной версией pdfFactory Pro www.pdffactory.com

При этом стоимость c(i,j) работы (i,j) заключена в границах от cmin(i,j) (при нормальной продолжительности работы) до cmax(i,j) (при экстренной продолжительности работы):

с(i, j) = c

(i, j) + (b t) *

Cmax (i, j) − Cmin (i, j)

 

 

min

 

 

b a

 

 

 

Найти изменение стоимости

работы

с(i,j) можно при сокращении ее

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

 

 

 

 

с(i, j) = [b(i, j)

- t(i, j)]h(i, j)

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

h(i, j) = Сmax (i, j) − Сmin (i, j) = tgα b a

t(i, j) = min{b t(i, j), Rс }

(допустимый размер увеличения продолжительности данной работы)

tопт (i, j) = t(i, j) + t(i, j)

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

Cопт(i, j) =Cmin(i, j)+(btопт(i, j))*h(i, j)

(оптимальная стоимость)

I. Оптимизация сетевого графа бизнес - проекта «Астория»

методом «время-стоимость»

Проведем оптимизацию сетевого графа.

Граничные значения продолжительностей работ a(i,j) и b(i,j), их стоимости с(i,j), коэффициенты затрат на ускорение работ h(i,j) приведены в таблице.

Первоначальная стоимость работ плана находится по формулеС = åc(i, j) и

составляет С = 42 074 600 руб.

 

i, j

 

 

Стоимость работ нового плана равна Сопт=36 187 167 руб., то есть стоимость

всех работ уменьшилась на величину

С = åC(i, j) − åCопт (i, j) = 5 887 443 руб., т.е.

на 13,99 %.

(i,J )

(i, j)

 

 

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

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

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

Lкрит{0, 4, 5, 9, 12, 14, 15}=41; Lкрит= {0, 15} =41.

17

PDF создан испытательной версией pdfFactory Pro www.pdffactory.com

22

10

13

2

10

12

31

33

21

6

0

-15

 

22

23

11

14

2

17

19

32

34

15

0

15

0

 

23

24

12

14

2

32

34

32

34

0

0

0

0

 

24

25

13

14

1

12

13

33

34

21

0

21

0

 

25

26

14

15

7

34

41

34

41

0

0

0

0

 

26

 

 

 

 

 

 

Свобо

 

Максимальная и

 

Доп-й

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

 

 

разме

 

 

 

 

 

Работа

дный

 

минимальная стоимость

 

 

 

 

Коэффициент

 

 

 

р

 

 

 

 

 

 

работы, в сутки

резерв

 

работы

 

 

 

 

затрат на

 

 

 

 

 

 

 

 

увелич

 

Стоимость

 

 

 

 

 

 

 

времен

 

 

 

 

tопт(i,j)

Сопт(i,j)

ускорение

п/п

 

 

 

 

 

 

 

 

 

ения

работы,

 

 

 

 

 

и

 

 

 

 

работы,

 

i

,j

t(i,j)

a(i,j)

b(i,j)

работы

 

C (i,j)

C (i,j)

 

пр-сти

 

С(i,j)

 

руб./сутки,

 

 

 

работ

 

 

 

 

 

 

 

 

 

, сутки

 

min

max

 

 

 

 

h(i,j)

 

 

 

 

 

 

 

 

 

 

ы

 

 

 

 

 

 

 

 

 

Rc(i,j)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

t(i,j)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1

0

1

2

1

6

0

10 000

15 000

0

2

14 000р.

14 000р.

1 000

2

0

3

3

1

7

0

30 000

50 000

0

3

43 333р.

43 333р.

3 333

3

0

4

16

12

20

0

 

19 000

34 000

 

0

16

26 500р.

26 500р.

1 875

4

0

15

40

36

44

1

 

16 000 000

35 000 000

 

1

41

25 500 000р.

23 125 000р.

2 375 000

5

1

2

5

1

9

0

15 000

20 000

0

5

17 500р.

17 500р.

625

6

2

4

3

1

7

6

15 000

21 000

4

7

19 000р.

15 000р.

1 000

7

3

4

3

1

7

10

1 500 000

4 500 000

4

7

3 500 000р.

1 500 000р.

500 000

8

3

5

2

1

6

12

13 000

19 000

4

6

17 800р.

13 000р.

1 200

9

3

6

2

1

6

14

1 200 000

3 000 000

4

6

2 640 000р.

1 200 000р.

360 000

10

3

9

5

1

9

22

950 000

1 000 000

4

9

975 000р.

950 000р.

6 250

11

3

10

7

3

11

0

50 000

80 000

0

7

65 000р.

65 000р.

3 750

12

4

5

1

1

5

0

 

10 500

13 000

 

0

1

13 000р.

13 000р.

625

13

5

6

2

1

6

0

 

1 100 000

5 300 000

 

0

2

4 460 000р.

4 460 000р.

840 000

14

5

7

10

6

14

0

760 000

980 000

0

10

870 000р.

870 000р.

27 500

15

5

8

11

7

15

0

7 000

15 000

0

11

11 000р.

11 000р.

1 000

16

5

9

13

9

17

0

 

1 157 000

4 783 000

 

0

13

2 970 000р.

2 970 000р.

453 250

17

6

8

3

1

7

6

 

10 000

15 000

 

4

7

13 333р.

10 000р.

833

18

7

8

1

1

5

0

16 000

40 000

0

1

40 000р.

40 000р.

6 000

19

8

14

3

1

7

3

56 000

67 000

3

6

63 333р.

57 833р.

1 833

20

9

12

2

1

6

0

 

450 000

643 000

 

0

2

604 400р.

604 400р.

38 600

21

10

11

7

3

11

0

 

50 000

76 000

 

0

7

63 000р.

63 000р.

3 250

22

10

13

2

1

6

0

24 000

36 000

0

2

33 600р.

33 600р.

2 400

23

11

14

2

1

6

15

2 000

8 000

4

6

6 800р.

2 000р.

1 200

24

12

14

2

1

6

0

 

10 000

20 000

 

0

2

18 000р.

18 000р.

2 000

PDF создан испытательной версией pdfFactory Pro www.pdffactory.com

V. Коэффициент напряженности работы.

Определить степень трудности выполнения в срок каждой группы работ некритического пути можно с помощью коэффициента напряженности работ.

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

t(L ) t'кр

Кн (i, j) =

maх

tкр t'кр

 

где t(Lmax) – продолжительность максимального пути, проходящего через работу

(i,j);

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

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

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

Вычисленные коэффициенты напряженности позволяют дополнительно классифицировать работы по зонам. В зависимости от величины Кн(i,j) выделяют:

Ø критическую

(Кн(i,j)> 0,8)

Ø подкритическую

(0,6<=Кн(i,j)<= 0,8)

Ø резервную

(Кн(i,j)< 0,6)

PDF создан испытательной версией pdfFactory Pro www.pdffactory.com

I. Нахождение коэффициентов напряженности

(i,j):

 

 

 

 

 

 

 

t(Lmax)

t'kp

 

tkp

 

проверка

 

 

 

0, 1

35

 

25

 

41

0,625

0,625

31

 

25

 

41

0,375

0,375

0, 3

 

 

0, 4

 

 

 

 

 

 

 

40

 

0

 

41

0,976

0,976

0, 15

 

 

35

 

25

 

41

0,625

0,625

1, 2

 

 

35

 

25

 

41

0,625

0,625

2, 4

 

 

31

 

25

 

41

0,375

0,375

3, 4

 

 

29

 

24

 

41

0,294

0,294

3, 5

 

 

18

 

7

 

41

0,324

0,324

3, 6

 

 

19

 

11

 

41

0,267

0,267

3, 9

 

 

26

 

7

 

41

0,559

0,559

3, 10

 

 

4, 5

 

 

 

 

 

 

 

32

 

24

 

41

0,471

0,471

5, 6

 

 

38

 

24

 

41

0,824

0,824

5, 7

 

 

38

 

24

 

41

0,824

0,824

5, 8

 

 

5, 9

 

 

 

 

 

 

 

6, 8

32

 

24

 

41

0,471

0,471

7, 8

38

 

24

 

41

0,824

0,824

38

 

24

 

41

0,824

0,824

8, 14

 

 

9, 12

 

 

 

 

 

 

 

10, 11

26

 

7

 

41

0,559

0,559

10, 13

20

 

7

 

41

0,382

0,382

11, 14

26

 

7

 

41

0,559

0,559

12, 14

 

 

 

 

 

 

 

13, 14

20

 

7

 

41

0,382

0,382

14, 15

 

 

 

 

 

 

 

В результате расчетов работы:

(0,1) попадает в подкритическую зону, так как Кн(0,1)= 0,6<0,625<0,8 (0,3) попадает в с зону, так как Кн(0,3)=0,375<0,6 (0,15) попадает в критическую зону, так как Кн(0,15)=0,976>0,8

(1,2) попадает в подкритическую зону, так как Кн(1,2)= 0,6<0,625<0,8 (2,4) попадает в подкритическую зону, так как Кн(2,4)= 0,6<0,625<0,8 (3,4) попадает в резервную зону, так как Кн(3,4)= 0,375<0,6 (3,5) попадает в резервную зону, так как Кн(3,5)= 0,294<0,6 (3,6) попадает в резервную зону, так как Кн(3,6)= 0,324<0,6 (3,9) попадает в резервную зону, так как Кн(3,9)=0, 294<0,6 (3,10) попадает в резервную зону, так как Кн(3,10)= 0, 559<0,6 (5,6) попадает в резервную зону, так как Кн(5,6)= 0, 471<0,6 (5,7) попадает в критическую зону, так как Кн(5,7)= 0,824>0,8 (5,8) попадает в критическую зону, так как Кн(5,8)= 0,824>0,8 (6,8) попадает в резервную зону, так как Кн(6,8)= 0, 471<0,6 (7,8) попадает в критическую зону, так как Кн(7,8)= 0,824>0,8 (8,14) попадает в критическую зону, так как Кн(8,14)= 0,824>0,8 (10,11) попадает в резервную зону, так как Кн(10,11)= 0, 559<0,6 (10,13) попадает в резервную зону, так как Кн(10,13)= 0, 382<0,6

20

PDF создан испытательной версией pdfFactory Pro www.pdffactory.com