Visão retrospectiva
Disciplina UnB/FACE/ADM
Origens remotos da GP
 A teoria dos grafos teve em Leonhard Euler em 1736 uma de
suas primeiras abordagens e eventualmente representa uma
das mais remotas fontes para o surgimento da atual gestão por
processos.
 Euler na ocasião resolveu o problema das pontes de Sete
pontes de Königsberg
O Dilema das pontes de Königsberg
No século XVIII na então cidade de Königsberg (hoje Kaliningrado, Rusia) existia
um conjunto de sete pontes no local onde a cidade é cortada pelo rio Prególia, e
existem duas grandes ilhas
Visão gráfica do dilema das sete pontes
Os caminhos ou arestas constituem as atividades que caracterizam o
processo de atravessar as pontes desde os vértices que constituem os pontos
de origem e destino das pontos que estas são atravessadas.
Sete pontes de Königsberg
 Hoje Kaliningrado é banhada pelas aguas do mar
Báltico e faz fronteira com a Polonia e Lituania.
Königsberg (Kaliningrad) no Mapa Nórdico
O desafio matemático das 7 pontes
 Discutia-se, no século XVIII nas ruas de Königsberg, a possibilidade de
atravessar todas as 7 pontes da cidade, sem repetir nenhuma. E Euler
para solucionar o desafio usou um raciocínio considerado simples.
Transformou os caminhos em arestas (a borda que divide dois planos) e suas
interseções em nodos ou vértices.
 Então percebeu que só seria possível atravessar o caminho inteiro passando
uma única vez em cada ponte se houvesse exatamente zero ou dois pontos de
onde saísse um número ímpar de caminhos. A razão de tal coisa é que de cada
ponto (nodo-vértice) deve haver um número par de caminhos (arestas), pois
será preciso um caminho para "entrar" e outro para "sair". Os dois pontos com
caminhos ímpares referem-se ao início e ao final do percurso, pois estes não
precisam de um para entrar e um para sair, respectivamente.
 Se não houver pontos com número ímpar de caminhos (arestas), pode-se (e
deve-se) iniciar e terminar o trajeto no mesmo ponto, podendo esse ser
qualquer ponto (vértice) do grafo. Isso não é possível quando temos dois
pontos (nodos-vértices) com números ímpares de caminhos, sendo
obrigatoriamente um o início e outro o fim.
Um cubo para contar arestas
(caminhos) e nodos (vertices)
A teoria dos grafos é um ramo da
matemática que estuda as relações
entre os objetos de um
determinado conjunto. Para tal
são empregadas estruturas
chamadas de grafos, G(V,A), onde:
• V é um conjunto não vazio de
objetos denominados vértices e
• A é um conjunto de pares não
ordenados de V, chamado arestas.
Quantos planos são intersectados?
•Aparentemente temos 6 planos
•Intersectados por 12 arestas
•Que formam 8 vértices - nodos
Em nosso caso o tipo de Grafo que interessa para a Gestão de Processoss é aquele
cujas arestas ou caminhos a representar atividades são setas, logo representam
direção. Sendo os vértices seus nodos da rede de processos.
O CPM ou método do Caminho Crítico: uma aplicação
da Teoria dos Grafos no mundo das Organizações
 Considera-se que foi em 1957 que a Dupont reforçou a
liderança de seu mercado pela implementaçao de
técnica que lhe permitia programar e executar com
grande economia, o complexo processo realizar a
manutenção de suas fábricas químicas, interrompendo
e reiniciando a produção de modo ímpar. O Método foi
desenvolvido numa joint-venture com a Rand
Corporation.
 Afirma-se houve uma economia de um milhão de
dolares no primeiro ano de utilização do CPM.
Diagrama de Redes - Atividades e eventos
 Atividade (Tipo Tarefa): execução efetiva de
uma operação, consumindo tempo e/ou
recursos. Ex.: concretagem, alvenaria.
 Evento (Acontecimento): constituído de
marcos que caracterizam determinados
instantes de um planejamento. Não
consumidos nem tempo e/ou recursos. Ex.:
Início de concretagem, fim de alvenaria.
Atividades paralelas e fantasmas
 Entre dois
eventos
sucessivos
somente pode
existir uma única
atividade. Para
evitar confusão, é
criada a atividade
fantasma (não
consome tempo
nem recursos).
1
Pedro lê jornal
15
Pedro
toma café
Pedro
toma banho
2
3
4
10
10
Maria prepara café
20
1
Pedro
toma banho
10
Pedro
lê jornal
2
15
4
Maria
prepara café
20
Pedro
toma café
3
5
10
Atividades dependentes
1
Pedro compra
pó de café
15
Maria prepara café
com leite
3
Luis compra
leite
2
4
10
15
A atividade 3-4 é dependente de 1-3 e 2-3
Atividades independentes
1
Pedro compra
pó de café
3
20
15
5
25
Luis compra
leite
2
Maria prepara café
com leite
Luisa prepara
coalhada
4
5
A atividade 4-6 é independente de 1-3
6
Como funciona o CPM
 O método do caminho crítico determina a
FOLGA ou a FLEXIBILIDADE NO
AGENDAMENTO de cada atividade
calculando a data mais cedo de início, e a data
mais cedo de fim, a data mais tarde de início e
a data mais tarde de fim.
 O caminho crítico é aquel mais longo do
projeto. Qualquer atividade com folga igual a
zero é considerada uma atividade de caminho
crítico.
Caminho Crítico
 Sequência de atividades tais que FT (folga total) =
Zero para cada uma. Ademais, é o caminho (ou
caminhos) cujo somatório de duração constitui a
duração do projeto. Ou então, é o caminho (ou
caminhos) de maior duração da rede.
 É definido por uma sequência de eventos tais que
a diferença TT (tempo mais tarde) - TC (tempo
mais cedo) de cada evento é o menor valor, entre
todos os outros não pertencentes ao caminho
crítico.
Começando a Montar a Rede
segundo publicação do Dpto de Eng da Produção UFSC
 Criar uma tabela das atividades indicando sua duração. E complementar os dados de DATA
inicio (cedo e tarde) e DATA fim (cedo e tarde), mais a folga total, ou seja a diferença do tempo
tarde menos o cedo. Para tal é preciso construir a rede especificada à seguir.
 O desenho de um diagrama mostrando as interdependências de cada atividade permitirá: na
etapa de AVANÇO das datas de inicio e fim CEDO calculadas adicionando o tempo do nó
inicial da rede para o nó final. E à seguir na etapa RETORNO serão calculadas as datas inicio e
fim TARDE calculadas subtraindo o tempo do nó final da rede para o nó inicial.
 Como consequência deste cálculo ira surgir a identificação do caminho crítico composto pelas
atividades cuja folga total seja zero. Ou seja aquelas nas quais qq atraso irá ter impacto no
tempo total.
 E ainda aquelas atividades com folga serão significadas de modo a propiciar algum
remanejamento de recursos que tente reduzir as atividades de caminho crítico a seu menor
número.
Realizando o Cálculo
 A determinação das datas de início e término das atividades de um projeto requer
cálculos que considerem de modo abrangente a rede de relações das diversas atividades
do projeto.
 Estes cálculos são realizados diretamente nessa rede, utilizando-se operações ora de
soma (no movimento de avanço) ora de subtração (no movimento de retorno). O cálculo
da rede ira conquistar a definição do caminho crítico do projeto.
 Este cálculo divide-se em duas etapas: avanço e retorno.
 No avanço, os cálculos são feitos no sentido do nó inicial da rede para o nó final da




rede.
 No retorno, o sentido dos cálculos é inverso.
Em cada nó, ou evento, são computados os seguintes valores:
• Cedo do Evento e o • Tarde do Evento
O cedo de um evento corresponde à data mais cedo para dar início à execução das
atividades que emanam deste evento, contada a partir do início do projeto,
considerando-se que todas as atividades que chegam até este evento não sofram atrasos
na execução.
O tarde de um evento corresponde à data mais tarde possível para atingir o evento sem
que o projeto sofra atrasos.
Calculando o Cedo e o Tarde
 Os valores de cedo e tarde do evento são incluídos na
própria rede, junto ao número do evento.
 Sendo o cedo do evento inicial igual a zero e no evento fina
o tarde será igual ao cedo desse evento.
Onde i é a identificação do evento
Ci é o Cedo do Evento –
Calculado na Etapa de Avanço
Ti é o Tarde do Evento –
Calculado na Etapa de Retorno
Modelo de Rede para praticar o cálculo de Avanço (Cedo) e Retorno
(Tarde), respectivamente para data de início e de fim possibilitando o
cálculo da Folga total e consequentemente identificar o caminho crítico
Tabela resumo
PDI – Primeira Data de Inicio – PDT (Término)
UDI – Última Data de Início – UDT (Término)