Pesquisa Operacional II

Aula 41

Módulo 5.4 – P & P Min Soma Atraso: Gusek by A.A.

MÁQUINA

TAREFAS

p1

TEMPO

c1

p2

c2

d2

d1

1

2

3

Ti = Max{Ci-di, 0} = atraso tarefa i

Li = Ci – di = lateness da tarefa i

Programação: Modelo

S.a.:

​

​

​

​

​

​

​

​

MODELO MINIMIZA SOMA DOS ATRASOS

Min

Minimizando soma dos atrasos Ti

Min Soma dos Atrasos

Proc.(pi)

Instante(Ci)

Tarefa

3

6

4

SOMA = 6

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

SOMA = 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

c₂

6

c₃

10

c₁

13

Pesquisa Operacional II

Aula 41

Módulo 5.4 – P & P Min Soma Atraso: Gusek by A.A.