PERT/CPM - IME-USP

1 Pesquisa Operacional - PERT/CPM Notas de Aula - Fernando Nogueira 1 PERT/CPM 1. Introdu o As t cnicas denominadas PERT e CPM foram independentemente desenvolvidas para o Planejamento e Controle de Projetos em torno de 1950, por m a grande semelhan a entre estas fez com que o termo PERT/CPM seja utilizado corriqueiramente como apenas uma t cnica. Os termos PERT e CPM s o acr nimos de Program Evaluation and Review Technique (PERT) e Critical Path Method (CPM). Exemplos de Projetos que podem utilizar PERT/CPM : 1. Constru o de uma planta 2. Pesquisa e desenvolvimento de um produto 3. Produ o de filmes 4. Constru o de navios 5. Instala o de um sistema de informa es 6. Condu o de campanhas publicit rias, entre outras. PERT e CPM utilizam principalmente os conceitos de Redes (grafos) para planejar e visualizar a coordena o das atividades do projeto.

2 Um exemplo cl ssico de aplica o de PERT/CPM o planejamento e gerenciamento da constru o civil. Exemplo (Hiller/Lieberman, pg 468) Suponha que uma empreiteira ganhou uma concorr ncia de $5,4 milh es para construir uma planta industrial. O contrato inclui: - Uma penalidade de $ ,00 se a empreiteira n o completar a constru o em 47 semanas. - Um b nus de $ ,00 se a empreiteira completar a constru o em 40 semanas. De acordo com a experi ncia da empreiteira, a seguinte lista foi elaborada para este projeto: Tabela 1 - Atividades, Atividades Precedentes e Dura o Estimada Atividade Descri o Atividades Precedentes Dura o Estimada (semanas) A Escava o - 2 B Funda o A 4 C Paredes B 10 Pesquisa Operacional - PERT/CPM Notas de Aula - Fernando Nogueira 2 D Telhado C 6 E Encanamento Exterior C 4 F Encanamento Interior E 5 G Muros D

3 7 H Pintura Exterior E,G 9 I Instala o El trica C 7 J Divis rias F,I 8 K Piso J 4 L Pintura Interior J 5 M Acabamento Exterior H 2 N Acabamento Interior K,L 6 A dura o para a execu o da obra 79 semanas se cada atividade for realizada uma por vez.

4 No entanto, existem atividades que podem ser realizadas simultaneamente com outras atividades, podendo com isso, reduzir a dura o da execu o da obra. 2. Constru o da Rede A rede pode ser constru da utilizando os arcos para representar as atividades e os n s para separar as atividades de suas atividades precedentes, por m utilizar os n s para representar as atividades e os arcos para representar as rela es de preced ncia parece ser mais intuitivo. A figura abaixo ilustra a rede para o exemplo dado: Fig. 1 - Rede para o exemplo dado. Pesquisa Operacional - PERT/CPM Notas de Aula - Fernando Nogueira 3 A partir da lista de atividades e das rela es de preced ncia, a rede pode ser facilmente constru da. Para isto, dado uma atividade (n ), basta procurar na lista quais atividades s o suas atividades precedentes.

5 Por exemplo, na rede da figura 1, a atividade J possui as atividades F e I como precedentes, as quais devem ser conectadas atrav s de arcos orientados (setas), indicando assim, a preced ncia. Atrav s da an lise da rede, v rias informa es podem ser obtidas, entre elas, as respostas para duas perguntas cruciais para o planejamento do projeto: 1) Qual o tempo total requerido para completar o projeto se nenhum atraso ocorrer ? 2) Quais as atividades que n o podem sofrer atrasos para que o projeto seja executado sem atraso ("Atividades Gargalos") ? Caminho Cr tico Um caminho atrav s de uma rede uma rota seguindo os arcos a partir do n IN CIO at o n FIM. O comprimento de um caminho a soma das dura es das atividades sobre o caminho. Na rede da figura 1 existem 6 caminhos, que s o dados na tabela abaixo, juntamente com seus respectivos comprimentos: Tabela 2 - Caminhos e seus respectivos Comprimentos Caminho Comprimento (semanas) Inicio-A-B-C-D-G-H-M-Fim 2 + 4 + 10 + 6 + 7 + 9 + 2 = 40 Inicio-A-B-C-E-H-M-Fim 2 + 4 + 10 + 4 + 9 + 2 = 31 Inicio-A-B-C-E-F-J-K-N-Fim 2 + 4 + 10 + 4 + 5 + 8 + 4 + 6 = 43 Inicio-A-B-C-E-F-J-L-N-Fim 2 + 4 + 10 + 4 + 5 + 8 + 5 + 6 = 44 Inicio-A-B-C-I-J-K-N-Fim 2 + 4 + 10 + 7 + 8 + 4 + 6 = 41 Inicio-A-B-C-I-J-L-N-Fim 2 + 4 + 10 + 7 + 8 + 5 + 6 = 42 O Caminho com maior Comprimento o Caminho Cr tico, uma vez que todos os demais Caminhos dever o alcan ar o n FIM antes do Caminho Cr tico.

6 Isto responde a quest o 1) dada acima, ou seja, o tempo total requerido 44 semanas para completar o projeto. As atividades sobre este Caminho s o as Atividades Cr ticas (Atividades Gargalos), ou seja, qualquer atraso em uma dessas atividades ir atrasar a dura o de todo o projeto. J as demais atividades se sofrerem algum atraso poder o ou n o atrasar a dura o de todo o projeto. A figura 2 mostra o Caminho Cr tico. Pesquisa Operacional - PERT/CPM Notas de Aula - Fernando Nogueira 4 Fig. 2 - Caminho Cr tico Programa o de Atividades (Scheduling) A Programa o das Atividades na t cnica PERT/CPM consiste em determinar em que tempo (por exemplo, em que dia, em qual semana,..) uma atividade deve come ar e terminar. A princ pio, o tempo inicial de uma atividade deveria ser igual ao tempo final da atividade precedente.

7 No entanto, atividades que possuem 2 ou mais atividades precedentes necessitam que todas as atividades precedentes estejam completadas para ent o dar in cio a atividade em quest o. J para Atividades N o Cr ticas, o tempo inicial n o precisa ser necessariamente igual ao tempo final da sua atividade precedente, uma vez que esta atividade possui folga (n o pertence ao Caminho Cr tico da Rede). A fim de formalizar este racioc nio, a t cnica PERT/CPM utiliza 4 vari veis que s o: ES = Tempo Inicial Mais Cedo (Earliest Start) EF = Tempo Final Mais Cedo (Earliest Finish) LS = Tempo Inicial Mais Tarde (Last Start) LF = Tempo Final Mais Tarde (Last Finish) De posse dessas vari veis as seguintes regras podem ser definidas: Regra do Tempo Inicial Mais Cedo O tempo Inicial Mais Cedo ESi de uma atividade i igual ao maior Tempo Final Mais Cedo EFj das atividades precedentes j.

8 Ijjij),EF(maxES = (1) Pesquisa Operacional - PERT/CPM Notas de Aula - Fernando Nogueira 5 onde: i conjunto das atividades precedentes atividade i. Regra do Tempo Final Mais Cedo EFi = ESi + Di (2) onde: Di a dura o da atividade i. Regra do Tempo Inicial Mais Tarde LSi = LFi - Di (3) onde: LFi como definido abaixo. Regra do Tempo Final Mais Tarde O tempo Final Mais Tarde LFi de uma atividade i igual ao menor Tempo Inical Mais Tarde LSk das atividades sucessoras k. ikkik),LS(minLF = (4) onde: i conjunto das atividades sucessoras atividade i. Exemplo: C lculo de ES, EF, LS e LF para a Atividade J (divis rias) da Rede da figura 1. 25)23,25max()EF,EFmax(ESIFJ=== (5) 33825 DESEFJJJ=+=+= (6) 33)33,34min()LS,LSmin(LFLKJ=== (7) 25833 DLFLSJJJ= = = (8) Como pode-se perceber, o c lculo do Tempo Inicial Mais Cedo ES fun o dos Tempos Finais Mais Cedos EF precedentes, portanto, a sua obten o realizada calculando os ES's e EF's no sentido do n Inicio para o n Fim (forward pass).

9 J o c lculo do Tempo Final Mais Tarde LF fun o dos Tempos Iniciais Mais Tardes LS sucessores, portanto, a sua obten o realizada calculando os LS's e LF's no sentido do n Fim para o n In cio (backward pass). Outra conclus o importante sobre este exemplo que o Tempo Inicial Mais Cedo (ESJ) igual ao Tempo Inicial Mais Tarde (LSJ), no caso = 25. Isto nos diz que n o h Pesquisa Operacional - PERT/CPM Notas de Aula - Fernando Nogueira 6 folga para iniciar a Atividade J. D mesma forma o Tempo Final Mais Cedo (EFJ) igual ao Tempo Final Mais Tarde (LFJ), no caso = 33. Isto nos diz que n o h folga para terminar a Atividade J. Estas duas conclus es est o coerentes, uma vez que a Atividade J pertence ao Caminho Cr tico da Rede. Pode-se concluir ainda que LF - EF = LS - ES e que estas diferen as s o iguais folga que existe na atividade em quest o.

10 Assim, a folga Si (Slack) para a atividade i dada por: Si = LFi - EFi = LSi - ESi (9) O valor da Folga Si corresponde ao atraso que a atividade i pode sofrer sem comprometer a dura o total determinada pelo comprimento do Caminho Cr tico. A figura abaixo mostra a Rede com todos os seus Tempos Iniciais e Finais Mais Cedos e Mais Tardes e Folgas (obs: a verifica o dos c lculos deve ser realizada pelo leitor). Fig. 3 - Rede, ES's, EF's, LS's, LF's e S s. Pesquisa Operacional - PERT/CPM Notas de Aula - Fernando Nogueira 7 3. Incertezas nas Dura es das Atividades - Metodologia PERT A dura o de cada atividade na pr tica pode ser diferente daquela prevista na elabora o do projeto.