MÉTODO DO CAMINHO CRÍTICO PERT/CPM - Caetano Método PERT/CPM •Duração de atividades probabilística? –A: melhor tempo (otimista) –B: pior tempo (pessimista) –M: tempo

PESQUISA OPERACIONAL II

Prof. Dr. Daniel Caetano

2019 - 1

MÉTODO DO CAMINHO CRÍTICO PERT/CPM

Objetivos

• Compreender o Problema do Caminho Crítico (CPM) e as folgas

• Compreender o método de solução CPM

• Compreender o tratamento das incertezas

• Atividade Aula 9 – SAVA!

Material de Estudo

Material Acesso ao Material

Apresentação http://www.caetano.eng.br/ (Pesquisa Operacional II – Aula 9)

Biblioteca Virtual Pesquisa Operacional (Taha) – Seção 6.5

Recursos na Web https://www.ime.usp.br/~rvicente/PERT_CPM.pdf https://blogdaqualidade.com.br/metodo-do-caminho-critico/

https://www.ime.usp.br/~rvicente/PERT_CPM.pdf

https://blogdaqualidade.com.br/metodo-do-caminho-critico/







O PROBLEMA DO CAMINHO CRÍTICO

Problema do Caminho Crítico

• Problemas de Programação de Produção

– Atividades inter-relacionadas com duração finita

• CPM: durações determinísticas

• PERT: durações probabilísticas

• Tempo total de projeto

• Caminho Crítico

– Sequência de atividades críticas

– Atraso em uma, atraso no projeto

Método do Caminho Crítico

• Atividades: arcos

– Nós são início e término das atividades

• Tempos mais cedo

• Tempos mais tarde

1 2

4

3

5

A,5

C,2 D,2

B,4 E,1

0 5

7

9

10

10

8

9

5 0


• Atividades: arcos

– Nós são início e término das atividades



• Caminho crítico

1 2

4

3

5

A,5

C,2 D,2

B,4 E,1

0 5

7

9

10

10

8

9

5 0


• Atividades Fictícias: dependência

– Se B precisa finalizar antes de D...



1 2

4

3

5

A,5

C,2 D,2

B,4 E,1

0 5

9

9

11

11

9

9

5 0


• Atividades Fictícias: dependência

– Se B precisa finalizar antes de D...



• Caminho crítico

1 2

4

3

5

A,5

C,2 D,2

B,4 E,1

0 5

9

9

11

11

9

9

5 0

ALGORITMO CPM

Método do Caminho Crítico (CPM)

• Passos

1. Obter cronograma de dependências

2. Traçar o diagrama das atividades (rede)

3. Calcular os tempos “mais cedo” na ida (máximos)

4. Identificar o tempo total

5. Calcular os tempos “mais tarde” na volta (mínimos)

6. Identificar o caminho crítico: sem folga

7. Identificar as folgas


1. Obter cronograma de dependências



1

2

3

A,10

B,7



1

2

3

A,10

B,7

4

C,5



1

2

3

A,10

B,7

4

C,5 4

D,3



1

2

3

A,10

B,7

4

C,5 5

D,3 6

E,2



1

2

3

A,10

B,7

4

C,5 5

D,3 6

E,2

7

F,1



1

2

3

A,10

B,7

4

C,5 5

D,3 6

E,2

7

F,1

8

G,14


3. Calcular os tempos “mais cedo” na ida

1

2

3

A,10

B,7

4

C,5 5

D,3 6

E,2

7

F,1

8

G,14

0

10

7

15 18 20

21 35


4. Identificar o tempo total

1

2

3

A,10

B,7

4

C,5 5

D,3 6

E,2

7

F,1

8

G,14

0

10

7

15 18 20

21 35


5. Calcular os tempos “mais tarde” na volta

1

2

3

A,10

B,7

4

C,5 5

D,3 6

E,2

7

F,1

8

G,14

0

10

7

15 18 20

21 35

35 21

20 18 15 10

20

0



1

2

3

A,10

B,7

4

C,5 5

D,3 6

E,2

7

F,1

8

G,14

0

10

7

15 18 20

21 35

35 21

20 18 15 10

20

0



1

2

3

A,10

B,7

4

C,5 5

D,3 6

E,2

7

F,1

8

G,14

0

10

7

15 18 20

21 35

35 21

20 18 15 10

20

0


7. Identificar as folgas

1

2

3

A,10

B,7

4

C,5 5

D,3 6

E,2

7

F,1

8

G,14

0

10

7

15 18 20

21 35

35 21

20 18 15 10

20

0

Exercício

• Aplique o método CPM:

Exercício


1

2

A,3

0

17

3

4

5

B,2

C,4

D,3

6

E,2 7

F,4 8

G,2

9

H,1

10

I,2

11 J,4

3

3

3

4

4

5 9 11 13 17

13 11

13

11 10

0

3

3 5 9

Exercício


1

2

A,3

0

17

3

4

5

B,2

C,4

D,3

6

E,2 7

F,4 8

G,2

9

H,1

10

I,2

11 J,4

3

3

3

4

4

5 9 11 13 17

13 11

13

11 10

0

3

3 5 9

Exercício

• Aplique o método CPM (design alternativo):

1

2

A,3

0

17

3

5

B,2

C,4

D,3

6

E,2 7

F,4

8

G,2

H,1

10

I,2

11 J,4

3

3

3

5 9

11

13 17

13

11 10

0

3

3 5 9

Departamento de Engenharia de Transportes Escola Politécnica da Universidade de São Paulo

PTR2451 – Economia e Planejamento de Sistemas de Transportes Otimização de Oferta: Problemas de Transporte e de Transbordo

REDES PERT

Método PERT/CPM

• Duração de atividades probabilística?

– A: melhor tempo (otimista)

– B: pior tempo (pessimista)

– M: tempo normal (mais provável)

• Considera-se 𝐷 o tempo para o CPM:

• Probabilidade do tempo para um nó

– É possível determinar!

– Cálculo complexo!

𝐷 =𝐴 + 4.𝑀 + 𝐵

6

Método PERT/CPM

• Exemplo de dados para o PERT/CPM

Departamento de Engenharia de Transportes Escola Politécnica da Universidade de São Paulo

PTR2451 – Economia e Planejamento de Sistemas de Transportes Otimização de Oferta: Problemas de Transporte e de Transbordo

REPRESENTAÇÃO ALTERNATIVA PARA O CPM

Representação Alternativa

• Inícios/fins separados

1 2

A,10

C,5 5 6

E,2 7 8

3

B,7 4

D,3 5 6

F,1 9 10

G,14 11 12 0

0

0

0

10

10

7

15

15 18

18 20

20 21

21 35

35 21

21 20

20 0

0 10

10 15

15 18

18

20 13

Representação Alternativa

• Inícios/fins separados

1 2

3

A,10

B,7 4

C,5 5

D,3

6

E,2 7

F,1

8

G,14

5 6

9 10

11 12 0

0

0

0

10

10

7

15

15 18

18 20

20 21

21 35

35 21

21 20

20 0

0 10

10 15

15 18

18

20 13

CONCLUSÕES

Resumo

• CPM: identificar atividades críticas

– Fácil de aplicar!

– Durações determinísticas

• PERT: Durações probabilísticas

• TAREFA: Exercícios Aula 9

• Problema do Fluxo Máximo

– Como escoar o máximo de produto?

– Ford-Fulkerson

PERGUNTAS?

EXERCÍCIO

Exercício (para casa)

• Identifique o caminho crítico e as folgas:

Atividade Predecessor Duração (dias)

A: Movimento de Terra - 3

B: Fundação A 4

C: Estrutura B 3

D: Paredes C 5

E: Laje C 2

F: Telhado E 5

G: Elétrica D, E 3

H: Hidráulica D, E 5

I: Habite-se F, G, H 3

Documents

MÉTODO DO CAMINHO CRÍTICO PERT/CPM - Caetano Método PERT/CPM •Duração de atividades probabilística? –A: melhor tempo (otimista) –B: pior tempo (pessimista) –M: tempo