Otimização de Processos COQ 897 Prof. Evaristo C. Biscaia Jr. Prof. Príamo A. Melo Jr. Trabalho Final do Curso – 3º Período 2002

Otimização de Processos COQ 897

• Prof. Evaristo C. Biscaia Jr.

• Prof. Príamo A. Melo Jr.

Trabalho Final do Curso – 3º Período 2002

Utilização de Algoritmos Naturais no Planejamento Seqüencial

da Produção em Plantas Seriais Multiproduto Operando em Regime

de Batelada

Aluno: Alexandre Rodrigues Tôrres

Tópicos do Trabalho

• Introdução• Descrição do Problema de Planejamento da

Produção• Implementação e Testes dos Algoritmos de Busca da

Seqüência Ótima • Emprego dos Algoritmos SA e ACO na solução de

Problemas de Programação da Produção • Comparação com resultados da literatura • Conclusões

Introdução

• Novas Tecnologias – Automação e Informatização

• Produtos com alto valor agregado• Plantas Químicas — ‘Química Fina’• Problemas de PPCP• Aplicativos para ERP’s• Emprego de Algoritmos Naturais (SA e ACO)


• Introdução• Descrição do Problema de Planejamento da

Produção• Implementação e Testes dos Algoritmos de Busca da

Seqüência Ótima • Emprego dos Algoritmos SA e ACO na solução de

Problemas de Programação da Produção • Comparação com resultados da literatura • Conclusões

Descrição do Problema de Planejamento da Produção

• Programação da Produção– ordens de fabricação – jobs– recursos disponíveis – equipamentos

• Objetivo – menor make span– sem estoques intermediários– com estoques intermediários

• limitados

• ilimitados


• Formas de Avaliação dos PPP – GRAVES(1981)– geração de pedidos;– complexidade do processo produtivo;– critérios de programação.


• Geração de Pedidos– reposição de estoques de produto acabado ou a

chamada produção empurrada (make to stock ou closed shop)

– atendimento aos pedidos dos clientes, com a reposição de estoques em sentido contrário ao fluxo de produção ou produção puxada (make to order ou open shop)


• Complexidade do Processos– um estágio, um processador para cada ordem

de fabricação;– um estágio, processadores paralelos;– múltiplos estágios e mesma seqüência (flow

shop ou planta multiproduto);– múltiplos estágios e várias seqüências (job

shop ou planta multiprocesso).

• multipropósito — multiproduto ou multiprocesso


• Critérios de Programação– existência de estoques intermediários limitados

ou ilimitados– possibilidades de formar seqüências e suas

influência nos tempos de preparação dos recursos (setups dos equipamentos)

– existência de seqüências proibidas.


• Abordagem do PPP– regras de prioridade;– otimização combinatorial;– análise de restrições

• Abordagem neste trabalho– otimização combinatorial com o emprego de

algoritmos estocásticos de busca global


• Introdução• Descrição do problema de planejamento da

produção• Implementação e testes dos algoritmos de busca da

seqüência ótima • Emprego dos algoritmos SA e ACO na solução de

problemas de programação da produção • Comparação com resultados da literatura • Conclusões

Implementação e Testes dos Algoritmos de Busca da Seqüência

Ótima

• Algoritmos testados– Recozimento Simulado (SA – Simulated

Annealing)– Colônia de Formigas (ACO – Ant Colony

Optimization)

• Ambiente / Linguagem = MathCAD®


Ótima• Características dos Algoritmos

SA – Recozimento Simulado ACO – Colônia de Formigas

Entrada (Requisitados)

x – vetor inicial;f – função objetivo;T – ‘temperatura’ inicial; – fator de redução da ‘temperatura’;nx – número de ciclos em x;nT – número de ciclos para ‘temperatura’.

n – dimensão do problema;m – número de ‘formigas’;N – número de ciclos para busca; – expoente de peso na probabilidade relacionado à quantidade de ‘feromônio’; – expoente de peso na probabilidade relacionado à ‘distância’; – fator de evaporação do ‘feromônio’;T0 – quantidades iniciais de ‘feromônio’Q – numerador de normalização da distância total para acréscimo do ‘feromônio’;D – matriz das ‘distâncias’ entre cada dimensão da solução.

Saída (Resultados)

– valor da função objetivo no ponto ótimo;– vetor x correspondente ao ponto ótimo

– valor da função objetivo no ponto ótimo;– vetor x correspondente ao ponto ótimo


Ótima

• Problema Teste: Problema do Caixeiro Viajante (PCV)

PC

20

30

20

45

55

85

80

55

15

35

60

75

50

55

25

30


Ótima

•S

oluç

ão d

o P

CV

pro

post

o

35

75

TP1i 2

TP2i 2

8555

TP1i 1 TP2

i 110 20 30 40 50 60 70 80 90

10

20

30

40

50

60

70

80

90

Solução do PCV com 8 cidades


Ótima

• Exemplos de Soluções do SA e ACO

p0

1

6

7

3

4

8

2

5

S Annnealing p0 f 60 0.80 200 20( ) S

229.769

0

0

0

0

0

0

0

1

8

7

6

5

4

3

2

1

2

7

8

6

5

4

3

ACO 8 5 20 1 5 0.5 10 6 100 D

5

4

3

2

1

8

7

6

229.769

A solução do PCV corresponde a um ciclo fechado ótimo portanto a solução (5,4,3,2,1,8,7,6), obtida com o algoritmo ACO é idêntica a (1,8,7,6,5,4,3,2) obtida pelo algoritmo SA.






Emprego dos algoritmos SA e ACO na solução de PPP

• Estrutura de dados do PPP• Entrada idêntica ao PCV• Características do PPP:

– número de ordens de fabricação ou jobs (j);

– número de máquinas ou equipamentos (m);

– tempo de operação de cada job em cada equipamento (top)


• Critérios de Programação Testados– não existência de estoques intermediários

(WIS – without intermediate stocks);– existência de estoques intermediários com

limitações (LIS – limited intermediate stocks);– existência de estoques intermediários

ilimitados (UIS – unlimited intermediate stocks).

• Não foram testadas as influências dos tempos de setup e a existência de seqüências proibidas


• PPP TESTE básico– 8 ordens de produção– 4 equipamentos– nível de complexidade: flow shop– critérios de programação: WIS, LIS e UIS


• Matriz de tempos de operação do PPP TESTE

top

4

12

1

2

11

2

6

1

3

3

2

4

3

4

7

2

2

4

3

5

4

5

8

3

1

4

4

8

6

6

9

8


• Cenários verificados com o PPP TESTECenários Estoques Intermediários Tipo Função Objetivo

FS01 Sem WIS MS

FS02 Limitado (no equipamento)

LIS MS

FS03 Limitado (no equipamento)

LIS MS + EU

FS04 Limitado – único(fora do equipamento)

LIS MS

FS05 Limitado – único(fora do equipamento)

LIS MS + EU

FS07 Ilimitado UIS MS

MS = make span; EU = estoque utilizado


• Resultados com o SA e ACO

Cenários

MS EU Exemplo de Seqüência

FS01 59 0 (8,4,5,6,7,2,3,1)

FS02 53 27 (3,8,4,7,5,6,2,1)

FS03 57 11 (3,1,8,4,7,5,2,6)

FS04 52 24 (8,6,4,7,2,5,3,1)

FS05 55 11 (8,4,5,6,7,2,3,1)

FS07 52 31 (8,6,4,7,2,5,3,1)


• Gráfico de Gantt para o problema denominado Teste, sem estoques intermediários, com a melhor solução obtida representando um make span de 59 unidades de tempo (FS01).


• Gráfico de Gantt para o problema denominado Teste, com estoques intermediários limitados, com a melhor solução obtida representando um make span de 52 unidades de tempo e uma utilização total de estoque de 31 unidades de tempo(FS07).


• Análise dos Resultados do PPP TESTE


• Exemplo de evolução da solução, do problema Teste, em uma dada execução da rotina do método Simulated Annealing (SA) no MathCAD com os seguintes parâmetros:

HR AnnnealingG p0 FO 5 0.01 0.90 200 20( )Evolução da Solução - Problema Teste - SA (FS07)

52

HRis 1

is0 500 1000 1500 2000 2500 3000 3500 4000

40

50

60

70

80


• Exemplo de evolução da solução, do problema Teste, em uma dada execução da rotina do método Ant Colony Optimization (ACO) no MathCAD com os seguintes parâmetros:

SACO ACO 8 5 200 1 2 0.6 10 6 100 DopEvolução da Solução - ProblemaTeste - ACO (FS07)

52

SACO9 is

is0 20 40 60 80 100 120 140 160 180 200

50

55

60

65


• Testes com o SA:– ‘Temperatura’ inicial– Vizinhança– Número de iterações


• Testes com o SA: ‘Temperatura’ inicial– DAS et al. (1996) T_inicial p0( )

ri

FO p0( )

rnd 1( )

p0 viz p0 ( )

i 1 20for

FO_max max r( )

FO_min min r( )

FO FO_max FO_min

T0 FO

ln 0.10( )

T0


• Testes com o SA: Vizinhança– viz — idêntica a utilizada no PCV, uma posição na seqüência é sorteada randomicamente e trocada

com a posição seguinte;– viz1 — são sorteadas duas posições randomicamente e trocados os jobs um com o outro;– viz2 — somente uma posição é sorteada randomicamente, este job é deslocado para a última

posição da seqüência, enquanto os demais são deslocados uma posição em cascata.


• Testes com o SA: Número de iterações– nx– nt

s)(tentativa iterações de númerontnx

com 8 jobs o número de combinações é de 40.320 (possibilidades)


0

20

40

60

80

100

120

Make sapn mínimo

0

20

40

60

80

100

120

Make span mínimo

0

20

40

60

80

100

120

Make span mínimo

20 300

8 0.149

SA

Parâmetros:T= 3; = 0.9; nx= 300; nT= 20viz viz1 viz2

MS* = 52 (100%) MS* = 52 (25%) MS* = 52 (100%)


• Testes com o ACO:– Matriz ‘distâncias’– Número de iterações: número de ‘formigas’ x

número de ciclos


0

10

20

30

40

Make span mí nimo

0

10

20

30

40

Make span mí nimo

0

10

20

30

40

Make span mí nimo

5 300

8 0.037

10 300

8 0.074

15 300

8 0.112

ACO

Parâmetros: N = 300; = 1; = 2; = 0.6; T0 = 10-6; Q =1005 ‘formigas’ 10 ‘formigas’ 15 ‘formigas’

MS* = 52 (6%) MS* = 52 (9%) MS* = 52 (8%)


• Testes como o ACO: Matriz de ‘distâncias’– MS de dois jobs isolados [ 2 8 ] [ 8 2 ] (Seq. I)– diferença de MS em uma determinada seqüência

de j jobs de dois determinados jobs (Seq. II)


• Exemplo da influência da matriz ‘distância’Seqüência I Seqüência II

st1

1

2

3

4

5

6

7

8

st2

1

2

3

5

4

6

7

8

st3

8

7

6

4

5

3

2

1

st4

8

7

6

5

4

3

2

1

FO st1( ) 70 FO st2( ) 72 FO st3( ) 60 FO st4( ) 60






Comparação com resultados da literatura

• Resultados de AHON et al. (2000) – Problema Castier1– Problema Castier2


• Problema Castier 1– com 6 jobs distribuídos em 10 equipamentos

top

5

10

1

9

5

9

7

5

10

6

6

5

3

8

6

3

1

9

6

4

6

2

9

5

3

4

6

7

2

9

5

6

10

10

8

9

9

4

1

7

2

5

2

6

7

2

1

5

9

4

3

4

3

2

3

9

10

1

1

8


• Problema Castier2– com 12 jobs

distribuídos em 6 equipamentos

top

1

6

7

6

5

5

3

3

7

9

3

8

0

1

10

1

7

9

2

4

5

8

9

2

1

7

8

9

0

8

2

7

5

6

8

6

2

5

3

10

4

1

7

3

4

4

8

0

6

8

4

1

1

4

4

8

1

9

6

3

7

3

1

1

6

3

4

8

6

5

9

5


• Desempenho do SA em AHON et al. (2000)– Castier1 : MS mínimo = 88 unidades de tempo

em mais de 99% das execuções realizadas;– Castier2 : MS mínimo = 86 unidades de tempo

em mais de 70% das execuções realizadas.


• Resultados para Castier1– apresentou resultados ainda melhores que o

Problema Teste para os algoritmos SA e ACO. Este fato já era esperado pois é um problema de dimensão menor que o PPP TESTE, pois Castier1 tem 6! possibilidades enquanto o Problema Teste tem 8!.


• Resultados para Castier2– ... tem uma dimensão bem maior, constituindo-se

uma avaliação bastante adequada para este trabalho. O número de combinações possíveis é 11880 vezes maior que o PPP TESTE.


• Resultados ótimos obtidos com os algoritmos SA e ACO para o Problema Castier2

Cenários MS EU Exemplo de Seqüência

FS01 108 0 (1,2,4,11,10,3,5,7,8,6,9,12)

FS07 86 105 (8,1,11,3,7,10,9,2,5,4,6,12)


• Testes com o cálculo do MS – Castier2ig 1 6000 S Compara 6000 p0( )

Sig 2

Sig 1

86

Sig 1

85 90 95 100 105 110 115 120 125 13080

90

100

110

120

130

Gráfico dos resultados da busca aleatória para a solução ótima (mínimo) do Problema Castier2 Cenário FS07 com 20*300 = 6000 tentativas (Sig,1 = FO deste trabalho, Sig,2 =

FO de AHON et al. (2000)).


• Testes com o cálculo do MS – PPP Testeig 1 600 S Compara 600 p0( )

Sig 2

Sig 1

52

Sig 1

50 55 60 65 70 75 8050

60

70

80

Gráfico dos resultados da busca aleatória para a solução ótima (mínimo) do Problema Teste Cenário FS07 com 20*30 = 600 tentativas (Sig,1 = FO deste trabalho, Sig,2 = FO de

AHON et al. (2000))


• Resultados para Castier2SA

Parâmetros:T= 5; = 0.9; nx= 300; nT= 20viz viz1 viz2

MS* = 86 (3%) MS* = 86 (1%) MS* = 86 (3%)

0

10

20

30

40

50

60

Make span mínimo

0

10

20

30

40

50

60

Make span mínimo

0

10

20

30

40

50

60

Make span mínimo


• Resultados para Castier2SA

Parâmetros:T= 3; = 0.9; nT= 20- viz

nx = 300 nx = 500 nx = 1000

MS* = 86 (7%) MS* = 86 (7%) MS* = 86 (14%)

0

10

20

30

40

50

60

70

85 86 87 88 89 90 Mais

Make span mínimo

0

10

20

30

40

50

60

70

85 86 87 88 89 90 Mais

Make span mínimo

0

10

20

30

40

50

60

70

85 86 87 88 89 90 Mais

Make span mínimo


• Resultados para Castier2ACO

Parâmetros: N = 200; = 1; = 2; = 0.6; T0 = 10-6; Q =100

8 ‘formigas’ 16 ‘formigas’ 32 ‘formigas’

MS* = 90 (1%) MS* = 90 (1%) MS* = 89 (1%)

0

24

6

8

1012

14

16

Make span mínimo

0

5

10

15

20

25

30

Make span mínimo

0

5

10

15

20

25

30

Make span mínimo







Conclusões• o ambiente MathCAD é promissor na solução de PPP;

• em todos os testes realizados o algoritmo SA; mostrou-se, em condições de comparação, com desempenho superior ao ACO;– a simplicidade da estrutura de funcionamento do método SA é uma

vantagem inexorável sobre o ACO;

– a dependência do método ACO em relação à forma construção da matriz de ‘distâncias’ é muito elevada;

• as limitações impostas pelo ambiente MathCAD traduziram-se num tempo de execução elevado;

• A estrutura de definição da vizinhança é um fator preponderante para o sucesso na busca da solução para o método SA

Conclusões• a estrutura de construção da matriz de ‘distâncias’, decide o

desempenho do método ACO;

• a definição da ‘temperatura’ inicial com o algoritmo de DAS et al. (1990), é muito mais eficiente que qualquer outra forma de definir o parâmetro

Documents

Otimização de Processos COQ 897 Prof. Evaristo C. Biscaia Jr. Prof. Príamo A. Melo Jr. Trabalho Final do Curso – 3º Período 2002