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 |
|
5 |
11 |
|
3 |
12 |
|
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
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
Passo 2
Definindo o modelo em forma de programação linear:
Variáveis:
Variáveis:
-
, para , é o início mais cedo da tarefa . -
é o tempo total do projeto.
Objetivo:
Restrições de precedência (se
depende de
,
):
onde
Restrições de término:
E claro
,
.
Passo 3
Para resolver na prática, fazemos o “forward pass”:
Para cada tarefa ,
Para cada tarefa
e se não tiver predecessor,
Passo 4
Vamos listar as durações
e predecessores de cada tarefa:
-
, pred -
, pred -
, pred -
, pred -
, pred -
, pred -
, pred -
, pred -
, pred -
, pred -
, pred -
, pred
Agora, passo a passo:
Passo 5
Calcular
numa ordem topológica:
-
, (sem predecessors). -
. -
. -
. -
. -
. -
. -
. -
. -
. -
.
Passo 6
Finalmente, o makespan é
Resposta
O tempo mínimo para concluir o projeto é 21 unidades de tempo.