Uma empresa fabricante de manifolds submarinos deseja minimizar o tempo de conclusão de um projeto composto pela execução de 12 tarefas cuja precedência é dada na tabela abaixo. Formule o problema e o resolva. (Dica: use variáveis t(i): tempo mais cedo para se iniciar a tarefa i)
Tarefa Precedência Tempo de <br> Duração
1 1
2 2
3 1 3
4 2,3 2
5 1,4 1
6 2,5 4
7 6 3
8 1,7 2
9 3,6 1
10 1,3,5 5
11 2,7,8 3
12 2,9,11 2

Passo 1

Beleza, o enunciado diz que temos 12 tarefas com durações e precedências, e o objetivo é minimizar o tempo total do projeto. Isso cai na matéria de Programação de Projetos (ou CPM/PERT), onde a gente usa variáveis
t(i): tempo mais cedo que a tarefa i pode começarç
Para resolver, precisamos:
1) Conhecer as durações de cada tarefa;
2) Saber quem depende de quem (precedências);
3) Montar o modelo (um mini‐LP) e depois calcular esses t(i) num “forward pass” para achar o makespan.

Passo 2

Definindo o modelo em forma de programação linear:
Variáveis:
  • t(i)>=0, para i=1,dots,12, é o início mais cedo da tarefa i.
  • T>=0 é o tempo total do projeto.
Objetivo:
min;T
Restrições de precedência (se j depende de i, jinsucc(i)):
t(j)>= t(i)+diforall;(ito j)
onde di é a duração da tarefa i.
Restrições de término:
T>= t(i)+diforall,i
E claro t(i)>=0, T>=0.

Passo 3

Para resolver na prática, fazemos o “forward pass”:
Para cada tarefa j,
t(j)=maxiinpred(j)l[t(i)+dir],
e se não tiver predecessor, t(j)=0. No fim, o makespan T=maxil[t(i)+dir].

Passo 4

Vamos listar as durações di e predecessores de cada tarefa:
  1. d1=1, pred
  2. d2=2, pred
  3. d3=3, pred 1
  4. d4=2, pred 2,3
  5. d5=1, pred 1,4
  6. d6=4, pred 2,5
  7. d7=3, pred 6
  8. d8=2, pred 1,7
  9. d9=1, pred 3,6
  10. d10=5, pred 1,3,5
  11. d11=3, pred 2,7,8
  12. d12=2, pred 2,9,11
Agora, passo a passo:

Passo 5

Calcular t(i) numa ordem topológica:
  1. t(1)=0, t(2)=0 (sem predecessors).
  2. t(3)=t(1)+d1=0+1=1.
  3. t(4)=max,t(2)+d2,;t(3)+d3=max0+2,;1+3=4.
  4. t(5)=maxt(1)+d1,;t(4)+d4=max0+1,;4+2=6.
  5. t(6)=maxt(2)+d2,;t(5)+d5=max0+2,;6+1=7.
  6. t(7)=t(6)+d6=7+4=11.
  7. t(8)=maxt(1)+d1,;t(7)+d7=max0+1,;11+3=14.
  8. t(9)=maxt(3)+d3,;t(6)+d6=max1+3,;7+4=11.
  9. t(10)=maxt(1)+d1,;t(3)+d3,;t(5)+d5=max1,,4,,6+1=7.
  10. t(11)=maxt(2)+d2,;t(7)+d7,;t(8)+d8=max2,,11+3,,14+2=16.
  11. t(12)=maxt(2)+d2,;t(9)+d9,;t(11)+d11=max2,,11+1,,16+3=19.

Passo 6

Finalmente, o makespan é
T=maxi,t(i)+di=max,19+2=21

Resposta

O tempo mínimo para concluir o projeto é 21 unidades de tempo.

Exercícios relacionados