Máquinas Paralelas em Pesquisa Operacional

Prévia do material em texto

Aula 47
Módulo 5.10 – P & P em Máquinas Paralelas by A.A.
Pesquisa Operacional II
1
MÁQUINAS PARALELAS
IDÊNTICAS
UNIFORMES
NÃO-
RELACIONADAS
As máquinas possuem o mesmo tempo de processamento e preparação .
Os tempos de processamento e preparação são proporcionais ao da máquina + antiga.
Não existe relação entre os tempos de processamento e preparação das  máquinas.
Máquinas Paralelas
2
MÁQUINAS PARALELAS
IDÊNTICAS
UNIFORMES
NÃO-
RELACIONADAS
As máquinas possuem o mesmo tempo de processamento e preparação .
Os tempos de processamento e preparação são proporcionais ao da máquina + antiga.
Não existe relação entre os tempos de processamento e preparação das  máquinas.
Máquinas Paralelas
3
MÁQUINAS
TAREFAS
TEMPO
1
2
3
Máquinas Paralelas
TAREFAS
p1
TEMPO
c1
p2
c2
1
2
3
TEMPO
p3
c3
MAQ. 1
MAQ. 2
pi - tempo processamento tarefa i
Ci - instante término tarefa i
n - número de tarefas
m – número de máquinas
Máquinas Paralelas
TAREFAS
p1
TEMPO
c1
p2
c2
1
2
3
TEMPO
p3
c3
Cmax = Max{c1+c2, c3}
MAQ. 1
MAQ. 2
Máquinas Paralelas
i
j
xij
Variáveis de Decisão
Xij = 1 se a máquina j processa a tarefa i.
xi j
Origem
(Tarefa i)
Destino
(Máquina j)
Máquinas Paralelas
7
S.a.:
MODELO COM MÁQUINAS IDÊNTICAS
Min 
Uma tarefa i é alocada exatamente para uma única máquina j.
Cmax
Minimizar Cmax = Max {Ci}, i=1,...,m
O makespan corresponde ao maior tempo de processamento das tarefas alocadas em todas as j máquinas.
Máquinas Idênticas
Tempo Tarefa não depende da máquina!
8
Máquinas Idênticas
9
Aula 47
Módulo 5.10 – P & P em Máquinas Paralelas by A.A.
Pesquisa Operacional II
10
å
=
=
=
m
j
ij
n
i
x
1
,...,
1
 
,
1
å
=
=
³
n
i
ij
i
m
j
x
p
C
1
max
,...,
1
 
,
mn
B
x
C
Î
³
 
,
0
max