Modelo de Pesquisa Operacional para Minimização de Atraso Máximo

Prévia do material em texto

Aula 42
Módulo 5.5 – P & P Min Atraso Max: Gusek by A.A.
Pesquisa Operacional II
1
S.a.:
MODELO MINIMIZA ATRASO MÁXIMO
Min 
Tmax
Tmax = Max {Ti}, i=1,...,n, e Ti = max{Ci-di,0}
Min Atraso Máximo
2
Função Objetivo: Min Max
Proc.(pi)
Instante(Ci)
Tarefa
3
6
4
MAX = 3
UTILIZANDO ORDEM DOS DADOS
1
2
3
Data(di)
3
9
13
13
6
10
3
3
0
Ti = max{Ci-di,0}
Ordem dos dados: solução
Proc.(pi)
Instante(Ci)
Tarefa
6
4
3
MAX = 0
REGRA EARLIEST DUE DATE (EDD) – SOLUÇÃO ÓTIMA
1
2
3
Data(di)
6
10
13
6
10
13
0
0
0
Ti = max{Ci-di,0}
Heurística EDD
Modelo no GUSEK
Modelo no GUSEK
Modelo no GUSEK
Modelo no GUSEK
	T\T	0	1	2	3
	0			X02	
	1	X10			
	2				X23
	3		X31		
c2
6
c3
10
c1
13
Aula 42
Módulo 5.5 – P & P Min Atraso Max: Gusek by A.A.
Pesquisa Operacional II
8
å
¹
=
=
=
n
j
i
i
ij
n
j
x
,
0
,...,
1
,
0
 
,
1
å
¹
=
=
=
n
i
j
j
ij
n
i
x
,
0
,...,
1
,
0
 
,
1
n
j
n
i
x
M
p
M
C
C
ij
j
i
j
,...,
1
 
,
,...,
1
,
0
 
,
)
(
=
=
+
+
-
³
 
,
,...,
1
 
,
0
n
i
C
i
=
³
 
0
0
=
C
)
1
)(
1
(
+
+
Î
n
n
B
x
n
i
d
C
T
i
i
i
,...,
1
 
,
 
=
-
³
n
i
T
T
i
,...,
1
 
,
 
max
=
³
n
R
T
+
Î