PERT - Teoria - Professor Morais da Silva

INVESTIGAÇÃO OPERACIONAL
MÉTODOS DE PLANEAMENTO
Capítulo II – Método PERT
António Carlos Morais da Silva
Professor de I.O.
INVESTIGAÇÃO OPERACIONAL (MS – edição de 2007)
i
II.
Método PERT..............................................................................................................................................II-1
1.
Introdução...............................................................................................................................................II-1
2.
Duração da Actividade............................................................................................................................II-1
3.
Estimativas de Tempo - Tempo Esperado da Actividade .......................................................................II-1
4.
Rede do Projecto....................................................................................................................................II-2
5.
Auto Teste ..............................................................................................................................................II-9
6.
Solução do Auto-Teste .........................................................................................................................II-10
7.
Caminho Sub crítico .............................................................................................................................II-12
8.
Auto Teste ............................................................................................................................................II-14
9.
Solução do Auto Teste .........................................................................................................................II-15
INVESTIGAÇÃO OPERACIONAL (MS – edição de 2007)
ii
PERT – Program Evaluation and Review Technique
II. Método PERT
1. Introdução
O método PERT (Program Evaluation Review Technique) parte do princípio que as actividades e as suas
relações de precedência na rede foram bem definidas mas admite incerteza nos tempos de duração de algumas
ou de todas as actividades.
2. Duração da Actividade
Há actividades que têm duração variável e cuja execução continuada permite estabelecer a função de
distribuição dos tempos de execução (média e variância).
Há actividades que nunca foram executadas e sobre as quais não há informação quanto à sua duração. Neste
caso é feita não só uma estimativa do Tempo mais provável ( tm ), associado á execução, mas admite-se um
certo grau de incerteza nesta estimativa. Para quantificar esta incerteza, os técnicos produzem mais duas
estimativas:
• estimativa optimista: se tudo correr pelo melhor o tempo mínimo de execução será “to = tempo optimista”
• estimativa pessimista : se tudo correr mal o tempo máximo de execução será “tp = tempo pessimista “
Nem sempre é fácil estabelecer estas estimativas.
Naturalmente, se o Tempo Mais Provável, tm , está mais perto do Tempo Optimista e se os extremos do intervalo
tiverem a mesma probabilidade de ocorrência, então o “Tempo Médio ou Esperado”, te , em repetições
sucessivas, será mais influenciado pelo Tempo Pessimista pelo que será superior ao Tempo Mais Provável.
3. Estimativas de Tempo - Tempo Esperado da Actividade
O Tempo Esperado (médio) da actividade é uma média ponderada das três estimativas de tempo (optimista,
mais provável e pessimista)com os seguintes pressupostos 1 :
•
os Tempos Optimista (to) e Pessimista (tp) têm igual probabilidade de ocorrência
•
o Tempo Mais Provável (tm) tem uma probabilidade de ocorrência quatro vezes maior que a das outras
duas estimativas
Assim sendo, a expressão para cálculo do Tempo Esperado da actividade (te ) é a seguinte:
te =
t o + 4t m + t p
6
Este Tempo Esperado é o valor médio dos tempos de execução da actividade se esta fosse repetida um elevado
número de vezes.
______________________________________
1
Estes pesos baseiam-se na distribuição BETA (β) escolhida pelos criadores do PERT por ser unimodal, extremos finitos não
negativos e não necessariamente simétrica (a distribuição normal não tem estas duas últimas propriedades).
INVESTIGAÇÃO OPERACIONAL (MS – edição de 2007)
II-1
PERT – Program Evaluation and Review Technique
Quanto maior for o intervalo “Tempo Optimista - Tempo Pessimista” maior incerteza (menos confiança) teremos
associada ao valor do Tempo Esperado. A quantificação desta incerteza é feita pela “Variância” associada ao
tempo esperado considerando que o “Desvio-padrão” da distribuição é um sexto do intervalo entre as estimativas
extremas 2 :
⎛ t p − t0
Vt = ⎜⎜
⎝ 6
⎞
⎟
⎟
⎠
2
4. Rede do Projecto
a.
Caracterização da Actividade (Tarefa)
Para aplicar o método PERT é necessário conhecer para cada tarefa:
•
a sua duração se não há incerteza quanto ao tempo de execução 3 ;
•
a sua duração média e respectiva variância associada se há incerteza quanto ao tempo de execução;
•
a lista de precedências (quais as actividades precedentes, ou seja, as actividades de cuja conclusão
depende o seu início);
b.
Rede “AOA”. Cálculo da rede.
Para cada uma das etapas da rede é necessário conhecer:
•
Tempo Mais Cedo Médio e a Variância associada (TE e VTE ) :
Calcula-se tal como na rede CPM. A variância associada é a soma das variâncias associadas às
parcelas consideradas.
•
Tempo Mais Tarde Médio e a Variância associada (TL e VTL )
Calcula-se tal como na rede CPM. A variância associada é a soma das variâncias associadas às
parcelas consideradas.
•
Folga da Etapa e a Variância associada ( F e VF )
Calcula-se tal como na rede CPM. A variância associada é a soma das variâncias associadas aos
Tempos Mais Cedo e Mais Tarde Médios da etapa
Estes valores registam-se, na etapa, como mostra a figura seguinte:
TE
TL
F
VTE
VTL
VF
______________________________________
2
Quase todos os valores de uma distribuição unimodal estão contidos num intervalo centrado no valor médio e semiabertura
igual a três vezes o desvio padrão.
3
A rede do projecto PERT pode englobar actividades com duração determinística e/ou aleatória
INVESTIGAÇÃO OPERACIONAL (MS – edição de 2007)
II-2
PERT – Program Evaluation and Review Technique
c.
Etapa - Tempo Mais Cedo Médio
Considerem-se os seguintes dados de uma rede PERT:
Duração (dias)
Optimista
Mais Provável
Pessimista
1
4
7
A
Média
Variância
Precedência
-
B
10
4
-
C
12
8
-
D
2
5
14
A
E
3
6
15
B, D
F
4.5
8
C
G
3
0
A
30
E;3;6;15
A rede do projecto é a seguinte:
G;3;0
10
D;2;5;14
A;1,4,7
1
B;10;4
40
C;12;8
20
F;4.5;8
Nota: No arco escrevem-se as 3 estimativas(actividades “A”, “D” e “E”) ou o tempo esperado e a
respectiva variância (actividades “B”, “C” e “F”). A actividade “G” com variância nula tem duração
determinística.
É necessário calcular os tempos esperados e variâncias associadas das actividades com 3 estimativas de
tempo e registá-los na rede para, de seguida, calcular os valores TE e VTE de cada etapa:
•
Actividade “A”
te =
•
to + 4tm + t p
6
2
2
1 + 16 + 7
⎛t −t ⎞
7 −1⎞
2
=
= 4 dias ; Vt = ⎜ p 0 ⎟ = ⎛⎜
⎟ = 1 dia
6
6
6
⎝
⎠
⎝
⎠
Actividade “D”
te =
to + 4tm + t p
6
2
2
2 + 20 + 14
⎛t −t ⎞
=
= 6 dias ; Vt = ⎜ p 0 ⎟ = ⎛⎜ 14 − 2 ⎞⎟ = 4 dias 2
6
⎝ 6 ⎠ ⎝ 6 ⎠
INVESTIGAÇÃO OPERACIONAL (MS – edição de 2007)
II-3
PERT – Program Evaluation and Review Technique
•
Actividade “E”
te =
to + 4tm + t p
2
2
3 + 24 + 15
⎛t −t ⎞
=
= 7 dias ; Vt = ⎜ p 0 ⎟ = ⎜⎛ 15 − 3 ⎟⎞ = 4 dias 2
6
⎝ 6 ⎠
⎝ 6 ⎠
6
Registados os valores obtidos os Tempos Mais Cedo Médios das etapas e as Variâncias associadas, são os
seguintes:
4
1
G;3;0
10
D;6;4
A;4;1
1
B;10;4
10
17
5
9
30
E;7;4
40
0
0
C;12;8
20
F;4.5;8
12
8
Nota: Na etapa 30 o tempo mais cedo médio é de 10 dias percorrendo A e D = 4+6 =10 ou apenas B=10.
Porque há “empate” no TE a variância associada é a mais elevada. Neste caso, a variância (grau de
incerteza) associada à duração do 1º caminho ( 0 + 1 + 4 = 5) é superior à do 2º caminho (0 + 4 = 4)
pelo que se registou 5.
A duração total esperada do projecto é de 17 dias (com variância 9) resultante da soma de valores de
variáveis aleatórias pelo que também é uma variável aleatória.
O que é interessante (e feliz do ponto de vista estatístico) é que Te = 17 dias não tem a mesma distribuição
que os tempos esperados “te” mas segue aproximadamente a distribuição normal.
No exemplo proposto a distribuição dos tempos de duração total do projecto é a seguinte:
≅ 34%
≅ 13%
≅ 2%
dias
11
17
23
INVESTIGAÇÃO OPERACIONAL (MS – edição de 2007)
II-4
PERT – Program Evaluation and Review Technique
O planeador pode assim concluir, por exemplo, que há cerca de 84% de probabilidade de o projecto estar
concluído em 20 dias e se a data limite for de 23 dias há cerca de 97% de probabilidade de a cumprir.
Em regra os valores dos Tempos Mais Tarde Médios de cada etapa são calculados face a uma dada data
limite para que o planeador possa identificar quer o(s) caminhos(s) crítico(s) quer os caminhos sub críticos.
d.
Etapa - Tempo Mais Tarde Médio e Folga Média
Considere-se ser de 20 dias a Data Limite do projecto anterior.
Dispondo deste dado calculam-se os TL médios de forma igual à descrita no método CPM. A cada um deles
associa-se a respectiva variância que resulta da soma das variâncias associadas aos tempos esperados
utilizados para calcular o TL.
No que respeita às Folgas Médias em cada etapa o seu valor é calculado de modo igual ao indicado no
método CPM e a variância associada é igual à soma da variâncias associadas aos TE e TL usados no seu
cálculo.
Retomando o exemplo anterior tem-se sucessivamente:
4
1
G;3;0
10
D;6;4
A;4;1
1
0
B;10;4
10
13
3
17
20
3
5
4
9
9
0
9
30
E;7;4
40
C;12;8
0
F;4.5;8
20
4
7
3
1
8
9
10
12
15.5
3.5
8
8
16
G;3;0
D;6;4
A;4;1
1
0
3
3
0
9
9
B;10;4
10
13
3
17
20
3
5
4
9
9
0
9
30
E;7;4
40
C;12;8
F;4.5;8
20
12
15.5
3.5
8
8
16
Nota: A Data - limite de 20 dias é imposta do exterior pelo que é determinística (variância nula).
Nas etapas Inicial e Final as Folgas Média e Variância são sempre iguais
INVESTIGAÇÃO OPERACIONAL (MS – edição de 2007)
II-5
PERT – Program Evaluation and Review Technique
e.
Rede “AOA”. Actividade Crítica
Na rede PERT uma actividade é crítica se satisfizer, em simultâneo, 3 condições:
•
TEi + duração da actividade (i,j) = TEj
•
Variância de TEi + variância da duração da actividade (i,j) = Variância de TEj
•
serem iguais as Folgas Médias e Variâncias das etapas inicial e final da actividade e iguais às das
etapas inicial e final do projecto.
4
7
3
1
8
9
10
G;3;0
D;6;4
A;4;1
1
0
3
3
0
9
9
B;10;4
10
13
3
17
20
3
5
4
9
9
0
9
30
E;7;4
40
C;12;8
F;4.5;8
20
12
15.5
3.5
8
8
16
Vejamos a criticidade de cada uma das actividades na rede anteriormente calculada:
TEi + Dur = TE j ?
VTE + VDur = VTE ?
F = 3 ∧ VF = 9 ?
Crítica ?
A
0 + 4 = 4; Sim
0 + 1 = 1; Sim
Etapas 1 e 10; Sim
Sim
B
0 + 10 = 10; Sim
0 + 4 = 4; Não
C
0 + 12 = 12; Sim
0 + 8 = 8; Sim
Etapas 1 e 20; Não
Não
D
4 + 6 = 19; Sim
1 + 4 = 5; Sim
Etapas 10 e 30; Sim
Sim
E
10 + 7 = 17; Sim
5 + 4 = 9; Sim
Etapas 30 e 40 ; Sim
Sim
F
12 + 4.5 = 16.5; Não
Não
G
4 + 3 = 7; Não
Não
i
j
Não
Na actividade “B”, apesar de as Folgas Médias e variâncias das etapas inicial e final da actividade serem
iguais às das etapas inicial e final do projecto, a actividade não é crítica pois não satisfaz a 2ª condição
(Variância de TE1 (0) + Variância da duração de “B”(4) = 4 não é igual à Variância do TE30).
A actividade “C” não é crítica porque as suas etapas de arranque e chegada não têm Folga média = 3 dias
com variância 9.
As actividade “F” e “G” não são críticas pois não satisfazem a 1ª condição.
As actividades “A”, “D” e “E” porque satisfazem as 3 condições antes referidas, são actividades críticas e a
sua sucessão constitui o caminho crítico do projecto.
INVESTIGAÇÃO OPERACIONAL (MS – edição de 2007)
II-6
PERT – Program Evaluation and Review Technique
4
7
3
1
8
9
10
G;3;0
D;6;4
A;4;1
1
0
3
3
0
9
9
B;10;4
10
13
3
17
20
3
5
4
9
9
0
9
30
E;7;4
40
C;12;8
F;4.5;8
20
12
15.5
3.5
8
8
16
A duração do projecto tem distribuição normal com Média de 17 dias e variância 9.
O gráfico da distribuição de tempo é o seguinte:
dias
11
17
23
Se o planeador pretendesse estabelecer uma Data - limite a observar com 90% de probabilidade actuaria do
seguinte modo:
1º Na tabela de distribuição normal extrai o desvio tabelar associado a 0.90
Para a probabilidade 0.8997 o desvio tabelar é de z = 1.28 que é aceitável para 0.90.
INVESTIGAÇÃO OPERACIONAL (MS – edição de 2007)
II-7
PERT – Program Evaluation and Review Technique
Sendo “T” a Data - limite, Te = 17 dias o tempo esperado do projecto e VTe a variância associada a relação
destas variáveis com a o desvio tabelar “z” é a seguinte:
z=
T − Te
VTe
No caso corrente, temos Te =17, VTe = 9 e z = 1.28 pelo que a Data - limite procurada é:
1.28 =
T − 17
3
⇒ T = 20.84 dias
Admitindo agora que o planeador pretende saber a probabilidade de observar a Data - limite de 18 dias,
calcularia “z” com T = 18:
z=
18 − 17
3
⇒
z = 0.33
Para este desvio tabelar a tabela da distribuição normal normalizada indica a probabilidade de 0.6293 (63%):
INVESTIGAÇÃO OPERACIONAL (MS – edição de 2007)
II-8
PERT – Program Evaluation and Review Technique
5. Auto Teste
Considere a rede PERT a seguir descrita (durações em dias).
a.
Calcular os tempos de etapa considerando a Data - limite de 46 dias
b.
Calcular a probabilidade de concluir o projecto em 46 dias (efectuar o cálculo com precisão de uma
centésima).
c.
Calcular a Data - limite a observar com a probabilidade de 0.90
INVESTIGAÇÃO OPERACIONAL (MS – edição de 2007)
II-9
PERT – Program Evaluation and Review Technique
6. Solução do Auto Teste
a.
Obtido com o software do autor:
b.
Dados:
T = 46 dias
Te = 44.49 com V = 9.57
Desvio tabelar “z” e probabilidade associada P(z):
z=
T − Te
VTe
=
46 − 44.49
9.57
=
1.51
= 0.49
3.09
P( z ) = P(0.49) = 0.6879
A probabilidade de concluir o projecto no prazo máximo de 46 dias é aproximadamente 68% (arredondar
sempre por defeito).
Com o software do autor obtém-se:
INVESTIGAÇÃO OPERACIONAL (MS – edição de 2007)
II-10
PERT – Program Evaluation and Review Technique
c.
Desvio tabelar “z” para a probabilidade de 0.90:
P(z) = 0.90 ⇒ z = 1.28
Valor da Data - limite “T” a impor:
z=
T − Te
VTe
⇔ 1.28 =
T − 44.49
9.57
⇔ T = 48.45 dias
Data - limite deve ser, no mínimo, 49 dias (arredondar por excesso).
INVESTIGAÇÃO OPERACIONAL (MS – edição de 2007)
II-11
PERT – Program Evaluation and Review Technique
7. Caminho Sub crítico
Pode suceder que no projecto haja caminhos que não sendo críticos tenham variância superior à do caminho
crítico e que, por essa razão, tenham menor probabilidade de observar a data limite do que aquela que é
calculada para o caminho crítico.
Na execução do projecto, se há “pouca sorte” na execução das tarefas de um caminho deste tipo e “sorte” na
execução das tarefas críticas, é perfeitamente possível que a duração total da execução daquele exceda a do
caminho crítico.
Retome-se o exemplo precedente:
4
7
3
1
8
9
10
G;3;0
D;6;4
A;4;1
1
0
3
3
0
9
9
B;10;4
10
13
3
17
20
3
5
4
9
9
0
9
30
E;7;4
40
C;12;8
F;4.5;8
20
12
15.5
3.5
8
8
16
Para a data limite de 20 dias a probabilidade de a duração total do caminho crítico não exceder estes 20 dias é
de 0.84 dado que:
t=
T − Te
V
=
20 − 17
9
= 1 ; P(1) ≅ 0.84
O caminho 1- 20 - 40 (actividades “C” e “F”) tem:
•
duração esperada de 12 + 4.5 = 16.5 dias =
•
variância associada 8 + 8 = 16
Te'
A probabilidade de, neste caminho, observar a data limite de 20 dias é de 0.81 dado que:
t=
T − Te'
V
=
20 − 16.5
= 0.875 ; P (0.875) ≅ 0.81
16
Conclui-se assim que este caminho é sub crítico pois tem a probabilidade de 81% de observar a Data - limite de
20 dias, que é menor do que a de 84% associada à execução das actividades do caminho crítico.
INVESTIGAÇÃO OPERACIONAL (MS – edição de 2007)
II-12
PERT – Program Evaluation and Review Technique
Vejamos como calcular a probabilidade de este caminho sub-crítico passar a ser crítico:
Caminho crítico: Te = 17 dias com variância 9
Caminho sub-crítico: Te' = 16.5 dias com variância 16
Se a duração do caminho sub-crítico ultrapassar 17 dias então passará a ser crítico com a probabilidade
associada ao seguinte desvio tabelar “t”:
t=
Te' − T
VT + VTe
'e
=
16.5 − 17
9 + 16
= −0.1
P (−0.1) = 49.6
Há pois a probabilidade de 49% de o caminho sub-crítico passar a ser crítico durante a execução.
O controlo do projecto deverá ter em atenção esta situação para não ser surpreendido.
INVESTIGAÇÃO OPERACIONAL (MS – edição de 2007)
II-13
PERT – Program Evaluation and Review Technique
8. Auto Teste
Para o arranjo interior de um apartamento uma firma de construção civil dispõe do seguinte plano:
(2 - 0)
(4 - 5 - 6)
10
30
(2 - 0.11)
35
(2-0)
(1 - 0)
(1 - 3 - 5)
(5 - 0.11)
40
(2-3-4)
1
(3 - 3 - 3)
25
(3 - 0.03)
(2 - 0.11)
15
(1- 0 )
20
50
(2 - 3 - 4)
(4 - 0.11)
(4.5 - 2
45
Nos arcos do grafo estão registadas três estimativas de duração da tarefa ou a duração esperada e variância
associada (unidade de tempo = semana).
a.
Verificar se há caminhos sub críticos considerando a data - limite do projecto igual a 15 semanas.
INVESTIGAÇÃO OPERACIONAL (MS – edição de 2007)
II-14
PERT – Program Evaluation and Review Technique
9. Solução do Auto Teste
a.
É necessário obter a duração do projecto e respectiva variância. Feito o cálculo obtêm-se os seguintes
resultados:
O caminho crítico é 1 - 15 - 20 - 25 - 30 - 35 - 50 com duração de 14 semanas e Variância associada igual a
0.36.
A data - limite de 15 semanas é observada com a probabilidade associada ao desvio tabelar:
t=
T − Te
V
=
15 − 14
0.36
= 1.67 ; P(1) ≅ 0.95
A condição necessária, mas não suficiente, para que um caminho seja sub crítico, é ter uma variância
associada á duração total que seja superior à que está associada à duração do caminho crítico.
Só os caminhos, a seguir descritos, satisfazem esta condição necessária:
Caminho
1 - 10 - 25 - 50
1- 10 - 25 - 30 - 40 - 50
1 - 10 - 25 - 30 - 35 - 50
1 - 10 - 25 - 45 - 50
1- 15 - 20 - 25 - 45 - 50
1 - 15 - 20 - 45 - 50
Variância de Te
0.44 > 0.36
0.55 > 0.36
0.66 > 0.36
2.55 > 0.36
2.25 > 0.36
2.22 > 0.36
Testando a probabilidade de execução das tarefas destes caminhos no prazo da data limite de 15 semanas,
são sub críticos os seguintes caminhos:
INVESTIGAÇÃO OPERACIONAL (MS – edição de 2007)
II-15